​​​48days强训——day5

第一题：游游的you

链接：游游的you__牛客网

题目描述 游游现在有a个'y'，b个'o'，c个'u'，他想用这些字母拼成一个字符串。 三个相邻的字母是"you"可以获得2分，两个相邻的字母是"oo"，可以获得1分。 问最多可以获得多少分？ 输入描述: 第一行一个整数qqq，代表询问次数。 接下来qqq行，每行三个正整数a,b,ca,b,ca,b,c，用空格隔开。 1≤q≤1051\leq q \leq 10^51≤q≤105 1≤a,b,c≤1091\leq a,b,c \leq 10^91≤a,b,c≤109 输出描述: 输出qqq行，代表每次询问的答案。 示例1 输入 3 1 1 1 2 3 2 1 5 2 输出 2 4 5 说明 第一次询问，可以拼出"you"，获得2分。 第二次询问，可以拼出"oyouyou"，获得4分。 第三次询问，可以拼出"uooooyou"，获得5分。

题解：优先去拼凑you，而后在拼凑oo即可。

代码：

#include <iostream>
using namespace std;

void solve()
{
    int t,y,o,u;
    cin >> t ;

    while(t--)
    {   
        cin >> y >> o >> u;
        int it = min(y,min(o,u));
        int ret = it * 2;
        o -= it;
        if(o  >= 2)
            ret += o - 1;
        cout << ret << endl;
    }
}
int main() 
{
    solve();
    return 0;
}

第二题：腐烂的苹果

链接：腐烂的苹果_牛客题霸_牛客网

描述 给定一个 n×m n×m 的网格，其中每个单元格中可能有三种值中的一个 0 , 1 , 2。 其中 0 表示这个格子为空、1 表示这个格子有一个完好的苹果，2 表示这个格子有一个腐烂的苹果。 腐烂的苹果每分钟会向上下左右四个方向的苹果传播一次病菌，并导致相邻的苹果腐烂。请问经过多少分钟，网格中不存在完好的苹果。如果有苹果永远不会腐烂则返回 -1 数据范围： 1≤n,m≤1000 1≤n,m≤1000 ，网格中的值满足 0≤val≤2 0≤val≤2 示例1 输入： [[2,1,1],[1,0,1],[1,1,1]] 返回值： 4 示例2 输入： [[2,1,0],[1,0,1],[0,0,0]] 返回值： -1

题解：本质是一道多源的bfs，先将腐烂的苹果加入队列，而后按规则一一遍历即可。

代码：

#include <unistd.h>
#include <vector>
class Solution {
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
  public:
    int rotApple(vector<vector<int> >& grid) 
    {
        int n = grid[0].size(), m = grid.size();
        queue<pair<int, int>> q;
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) 
            {
                if (grid[i][j] == 2) 
                {
                    q.push({i, j});
                    vis[i][j] = true;
                }
            }
        int ret = 0;
        while (q.size()) 
        {

            int k = q.size();
            ret++;
            while (k--) 
            {
                
                auto [a, b] = q.front();
                q.pop();

                for (int i = 0; i < 4; i++) 
                {
                    int x = a + dx[i], y = b + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) 
                    {
                        vis[x][y] = true;
                        q.push({x, y});
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
                if (!vis[i][j]  && grid[i][j] == 1)return -1;
        return ret-1;
    }
};

第三题： 约瑟夫环

链接：孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网

描述 每年六一儿童节，牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中，有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0... m-1报数....这样下去....直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？

数据范围：1≤n≤50001≤n≤5000，1≤m≤100001≤m≤10000 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) 示例1 输入： 5,3 复制返回值： 3 复制 示例2 输入： 2,3 复制返回值： 1 复制说明： 有2个小朋友编号为0，1，第一次报数报到3的是0号小朋友，0号小朋友出圈，1号小朋友得到礼物 示例3 输入： 10,17 复制返回值： 2

题解： 一：模拟法，直接模拟得出结果。二：数学推理法。

代码：

class Solution
{
public:

    int LastRemaining_Solution(int n, int m)
    {
      int f = 0;
      for(int i = 2; i <= n; i++) f = (f+m) % i;
      return f;
    }
};