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 小红走矩阵
- 思路:
- 求解最大值的最小值,我们考虑用二分。
- 二分最小值是多少,l = 1, r = 1e9;
- check(mid): 用bfs进行遍历,当这个点的值大于mid的时候我们不走这里,因为但走了会使路径上的最大值超过mid
- 注意:不能用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;
}