C 小红充电

  • 思路：这题的坑点就是，我们可以先把手机玩没电再用超级充电充，可能会花更少的时间。
  • 由题知：a >=b >= c, 所以a是没用的，纯迷惑你。
  • 实现代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define endl '\n'
const int N = 1e5 + 10;

signed main()
{
    int x, y, t, a, b ,c ;
    cin >> x >> y >> t >> a >> b >> c;
    double res;
    if(x <= t)
    {
        res = (100 - x) / (c * 1.0);
        printf("%lf", res);
    }
    else
    {
        double res1 = 0, res2 = 0;
        res1 = (100 - x) / (b * 1.0);
        res2 = (x - t) / (y * 1.0) + (100 - t) / (c * 1.0);
        res = min(res1, res2);
        printf("%lf", res);
    }
    
    return 0;
}

D 小红的gcd

  • 思路：因为a的值比较大，不能直接取模，我们考虑用竖式计算的方法
  • 实现代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define endl '\n'
const int N = 1e5 + 10;
int get_mod(string s, int x)
{
    int res = 0;
    for(int i = 0; i < s.size(); i ++)
    {
        res = (res * 10 + s[i] - '0') % x;
    }
    return res;
}
signed main()
{
    string a;
    int b;
    cin >> a >> b;
    int res = get_mod(a, b);
    if(res == b) cout << b << endl;
    else
    {
        cout << __gcd(b, res) << endl;
    }
    return 0;
}

E 小红走矩阵

  • 思路：
    1. 求解最大值的最小值，我们考虑用二分。
    2. 二分最小值是多少，l = 1， r = 1e9;
    3. check(mid): 用bfs进行遍历，当这个点的值大于mid的时候我们不走这里，因为但走了会使路径上的最大值超过mid
    4. 注意：不能用dp，因为可能会有回路,我们不可能一次找到最小值，当我们用已知的去更新新的点的时候，其实所谓的一直的点不一定是确定的，因为新更新的点可能会更新它。而且遍历的顺序是是确定的，而我们实质走的路，不一定按照这个顺序来。
  • 实现代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define endl '\n'
const int N = 510;
int g[N][N], st[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n;
int check(int mid)
{
    memset(st, 0, sizeof st);
    queue<pair<int, int>> q;
    q.push({1,1});
    st[1][1] = 1;
    if(g[1][1] > mid) return 0;
    while(q.size() != 0)
    {
        auto t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        for(int i = 0; i < 4; i ++)
        {
            int nex = x + dx[i];
            int ney = y + dy[i];
            if(nex < 1 || nex > n || ney < 1 || ney > n) continue;
            if(st[nex][ney]) continue;
            if(g[nex][ney] <= mid)
            {
                q.push({nex, ney});
                st[nex][ney] = 1;
            }
        }
    }
    if(st[n][n] == 1) return 1;
    return 0;
}
signed main()
{

    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <=n; j ++) cin >> g[i][j];
    }
    int l = 1, r = 1e9;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}
  • 错误代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define endl '\n'
const int N = 510;
int g[N][N], st[N][N];
int f[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
signed main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <=n; j ++) cin >> g[i][j];
    }
    memset(f, 0x3f, sizeof f);
    f[1][1] = g[1][1];
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            if(i == n && j == n) continue;
            for(int k = 0; k < 4; k ++)
            {
                int nex = i + dx[k];
                int ney = j + dy[k];
                if(nex < 1 || nex > n) continue;
                if(ney < 1 || ney > n) continue;
                int t = max(f[i][j], g[nex][ney]);
                f[nex][ney] = min(f[nex][ney], t);    
            }
        }
    }
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= n; j ++)
        {
            cout <<i << " " << j << " " <<f[i][j] << endl;
        }
    }
    cout << f[n][n] << endl;
    return 0;
}