前言：

A - 雾之湖的冰精

思路：

  • 无

以下是代码部分

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if(a + b >= 10)
        cout << "No\n";
    else
        cout << "Yes\n";

    return 0;
}

B - 博丽神社的巫女

思路：

  • 题目意思容易理解错。
  • 数值到达即可

以下是代码部分

#include <bits/stdc++.h>
using namespace std;

int a[101010];

int main()
{
    int n, x, ans = 0;
    cin >> n >> x;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = n; i >= 1; i --)
    {
        if(x >= a[i])
        {
            x -= a[i];
            cout << i << ' ' << x;
            return 0;
        }
    }
    cout << 0 << ' ' << x;

    return 0;
}

C - 红魔馆的馆主

思路：

  • 枚举
  • 假设一个数n%495的时候，算出来的是与下界差多少的值
  • 然后我每次n10或者n100或者n*1000的时候%495都算出来此时与成为495时与下界的差值， 记为x。
  • x + y == 495 ,同时判断y的范围就行了。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main()
{
    ll n, temp;
    cin >> n;
    //计算出距离下界的距离
    n %= 495;
    if(n == 0) return cout << -1, 0;
    temp = n * 10 % 495;
    if((495 - temp) % 495 < 10) return cout << right << setw(1) << setfill('0') << (495 - temp)% 495, 0;
    temp = n * 100 % 495;
    if((495 - temp) % 495 < 100) return cout << right << setw(2) << setfill('0') << (495 - temp)% 495, 0;
    temp = n * 1000 % 495;
    cout << right << setw(3) << setfill('0') << (495 - temp) % 495;
    return 0;
}

D - 迷途之家的大贤者

思路:

  • 小红和小紫每个人至多操作1次, 且不能全删掉，那么留下来的必然只能是开头或者结尾的字符
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    string s;
    cin >> n >> s;
    cout << max(s.front(),s.back());

    return 0;
}

E - 魔法之森的蘑菇

思路：

  • BFS分层图
    • 分成四张不同方向的图进行BFS，方向分别为：
    • 延X轴正方向
    • 延X轴负方向
    • 延Y轴正方向
    • 延Y轴负方向

以下是代码部分,代码参考来源——比那名居的桃子

#include <bits/stdc++.h>
using namespace std;

//总共四种不同的面积最大为1010 * 10101的图
int dis[1010][1010][4];
//存储地图
string mp[1010];
//分别代表， 向下， 向上， 向左， 向右的方向
int op[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};

bool check(int x, int y, int n, int m)
{
    if(x >= 0 && x < n && y >= 0 && y < m && mp[x][y] != '#')
        return true;
    return false;
}

void solve()
{
    int n, m, u, v;
    cin >> n >> m;
    //输入地图
    for(int i = 0; i < n; i ++)
        cin >> mp[i];
    //给每张图的每个位置到起点的距离赋值为无穷
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            for(int k = 0; k < 4; k ++)
                dis[i][j][k] = 1e9;
    queue<vector<int>> q;
    //找到起点，存入队列中， 并让每张图初始化距离为0
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
        {
            if(mp[i][j] == 'S')
                for(int k = 0; k < 4; k ++)
                {
                    q.push({i, j, k});
                    dis[i][j][k] = 0;
                }
            //储存终点的坐标
            if(mp[i][j] == 'T')
                u = i, v = j;
        }
    //bfs
    while(!q.empty())
    {
        vector<int> temp = q.front();
        q.pop();
        int x = temp[0], y = temp[1];
        if(mp[x][y] == '.' || mp[x][y] == 'T' || mp[x][y] == 'S')
        {
            //向所对应的图的方向前进
            int xx = x + op[temp[2]][0], yy = y + op[temp[2]][1];
            if(check(xx, yy, n, m))
                //如果此位置未被遍历过
                if(dis[xx][yy][temp[2]] > dis[x][y][temp[2]] + 1)
                {
                    //存入队列中
                    q.push({xx, yy, temp[2]});
                    //把距离存入到对应的位置中
                    dis[xx][yy][temp[2]] = dis[x][y][temp[2]] + 1;
                }
        }
        //如果碰到了毒蘑菇
        else if(mp[x][y] == '*')
        {
            for(int i = 0; i < 4; i ++)
            {
                //毒蘑菇不会使人掉头
                //通过奇偶的转换，把相反方向的情况排除掉
                if((i^temp[2]) == 1) continue;
                int xx = x + op[i][0], yy = y + op[i][1];
                if(check(xx, yy, n, m))
                    if(dis[xx][yy][i] > dis[x][y][temp[2]] + 1)
                    {
                        q.push({xx, yy, i});
                        dis[xx][yy][i] = dis[x][y][temp[2]] + 1;
                    }
            }
        }
    }
    
    int mi = 1e9;
    //只有一张图可以遍历到终点
    //找到四张图中最后到终点的距离的最小值
    for(int i = 0; i < 4; i ++) mi = min(mi, dis[u][v][i]);
    if(mi > 8e8) cout << "-1\n";
    else cout << mi << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t --)
        solve();

    return 0;
}

F - 三途川的摆渡人

思路：

  • 动态规划，类似于背包dp
  • dp[此时的数值][取或者不取] = {使得按位与运算的值为此时的值所取的最少人数}
  • 所以可得状态转移方程：
    • dp[][1]代表取这次的数， dp[][0]代表不取这次的数的状态
    • dp[船上取的数&这次的数值][1] = min(dp[所留下的这个数值的人&数值j][1], dp[这次的数][0])
    • 每轮的状态转移完，记得更新
#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n, temp, dp[200][2];
    cin >> n;
    vector<int> tong(200, 0);
    //桶来判断是否有这个数
    for(int i = 0; i < n; i ++)
        cin >> temp, tong[temp] = 1;
    //dp[]初始化为穷大
    for(auto & i : dp) i[0] = i[1] = 1e9;
    //============== dp ================
    for(int i = 0; i < 200; i ++)
    {
        //如果存在这个数
        if(tong[i])
        {
            dp[i][1] = 1;
            for(int j = 0; j < 200; j ++)
                dp[i&j][1] = min(dp[i&j][1], dp[j][0] + 1);
        }
        //判断完之后，没取的状态更新，作为下次判断所用
        for(auto & j : dp) j[0] = j[1];
    }
    //如果没有一个被抛下，则为-1， 否则输出
    cout <<  (dp[0][0] > n ? -1 : n - dp[0][0]) << '\n';
    //同样正确的输出
    //cout <<  (dp[0][1] > n ? -1 : n - dp[0][1]) << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while(t --)
        solve();

    return 0;
}