牛客周赛 Round 51
锐评
A四道题排600名+，小孩哥都放假发力了吗？
这场典型的数学场啊，全是数学，还是对数字敏感的有优势，比完细看都不难。
A.小红的同余
题目描述
给出一个奇数 m，请找出一个整数 x（0 ≤ x < m），使得 2x ≡ 1(mod m)，也就是 2x除以 m 的余数是 1。你需要输出这个整数 x。
可以证明，这样的整数 x 存在且唯一。
输入描述:
第一行一个整数 m，表示给出的奇数。 3 ≤ m ≤ 109
输出描述:
输出一个整数 x（0 ≤ x < m），满足 2x ≡ 1(mod m)。
输入
3输出
2说明
2 × 2 ≡ 1 (mod 3)
思路
已知 2x ≡ 1(mod m)，即 2x ≡ qm + 1，m 是奇数，所以令 q = 1，求出 x 即可。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int m;
void solve() {
cin >> m;
cout << (m + 1) / 2 << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}B.小红的三倍数
题目描述
现在有 n 个整数，需要寻找一种拼接方式，将所有整数首尾相连，是否存在一种方式让拼接后的整数是3的倍数。
输入描述:
第一行给出一个n，代表有多少个数字。 第二行输入n个整数 ai。 1≤n≤100 ，1 ≤ ai ≤ 10100
输出描述:
如果有一种拼接方式让这个数是3的倍数，那么就输出“YES”，否则输出 “NO”。
输入
3
12 3 7输出
NO说明
不存在一种拼接方式让这个数是3的倍数。
输入
3
12 3 6输出
YES说明
1263 是 3 的倍数。
思路
一个数如果要是 3 的倍数，那么各个位数之和也是 3 的倍数，因此与拼接方式无关，将个个位数之和相加看是否为 3 的倍数即可。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n;
string a[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; ++ i) cin >> a[i];
int x = 0;
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j < a[i].size(); ++ j) {
x += a[i][j] - '0';
}
}
if (x % 3 == 0) cout << "YES\n";
else cout << "NO\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}C.小红充电
题目描述
小红手机充满电是100%，现在手机有x%的电，不充电玩手机每分钟会损失y%的电，充着电玩手机每分钟会充a%的电，充着电不玩手机每分钟会充b%的电，电量不高于t%开始触发超级充电(充到t%之后仍然保持超级充电)，超级充电时不能玩手机，每分钟会充c%的电。小红现在有急事要出门，问最短多长时间会充满电？
输入描述:
第一行输入6个整数x, y, t, a, b, c。 1 ≤ x, y, t ≤ 100， 1 ≤ a ≤ b ≤ c ≤ 100
输出描述:
输出小红充满电的最短时间，如果你的答案与标准答案的绝对误差不超过10−6，则视为正确。
输入
10 2 20 3 4 5输出
18.000000000说明
已经触发了超级充电，所以不玩手机，每分钟充5%的电，所以18分钟充满电。
思路
模拟题，注意精度就可以了，先看是不是要直接超级快充，如果不是，那就判断先玩到 t 电量再超级快充块还是直接普通快充快即可。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
double x, y, t, a, b, c;
void solve() {
cin >> x >> y >> t >> a >> b >> c;
double ans = 0;
if (x >= t) {//普通充电
ans = (100.0 - x) / b;
double sum = (x - t) / y + (100.0 - t) / c;//先玩到t再超级充电
ans = min(ans, sum);
}else {//超级充电
ans = (100.0 - x) / c;
}
printf("%.9lf", ans);
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}D.小红的gcd
题目描述
给两个正整数a,b，输出他们的最大公约数 gcd(a,b)。
输入描述:
第一行一个正整数 a。 第二行一个正整数 b。 len表示a的十进制位数，1 ≤ len ≤ 106。 1 ≤ b ≤ 109。
输出描述:
输出一个整数，表示gcd(a,b)。
输入
12345678
12输出
6思路
人畜无害的题面，一个长度 106 才爆露出来真面目，先用的 python，果不其然被卡了，高精度又太麻烦，根据gcd的性质：a = qb + r，gcd(a，b) = gcd(b， r)（其实就是辗转相除了），突然想到了之前再 csdn 写的一篇秦九韶算法，可以对大数取模，这样就能得到 r，就可以完成了。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
#define int long long
const int MOD = 1e9 + 7;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n;
int qmod(string s,int p)
{
int ans = 0;
for(auto &i : s)
{
ans = (ans * 10 + i - '0') % p;
}
return ans;
}
void solve() {
string a;
int b;
cin >> a >> b;
int r = 0;
r = qmod(a, b);
cout << gcd(r, b) << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}E.小红走矩阵
题目描述
给定 n × n 的矩阵，矩阵中的每个元素都是正整数，小红能当前位于左上角 (1,1)，每次可以从 (x,y) 走到 (x+1,y)、(x,y+1)、(x−1,y)、(x,y−1)，但不能走出矩阵。小红希望找到一条到右下角 (n,n) 的路径，定义路径权值为路径上经过的每个点的最大值，求所有路径中的最小路径权值。
输入描述:
第一行一个整数 n，表示矩阵的大小。 接下来 n 行，每行 n 个整数，表示矩阵中的元素 ai,j， 1≤n≤500，1 ≤ ai,j ≤ 109
输出描述:
输出一个整数，表示所有路径中的最小路径权值。
输入
3
3 2 1
6 5 4
9 8 7输出
7说明
先一直往右走，再一直往下走，路径上的最大值为7。
思路
是一道典型题，有很多方法解决，我认为二分+bfs是较为容易理解的。二分所有点，bfs判断到右下角的路上是否一定出现大于mid的值的点，出现说明这个数值偏小，向右找，不出现就向左，找最小的数值。
赛时跑一个dfs一分不给的超时qwq，输出 1，1 和 n，n 的最大值能得将近一半的分。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 509;
#define int long long
#define PII pair<int, int>
const int MOD = 998244353;
int qmi(int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int x) {return qmi(x, MOD - 2, MOD);}
int gcd(int a, int b) {return b > 0 ? gcd(b, a % b) : a;}
int lcm(int a, int b) {return a / gcd(a, b) * b;}
int n, a[N][N];
int ans = 1e9;
bool vis[N][N];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
bool inmp(int x, int y) {return x < 1 || x > n || y < 1 || y > n;}
bool bfs(int ans) {
bool st[N][N];
memset(st, 0, sizeof st);
queue<PII> q;
st[1][1] = 1; q.push({1,1});
if (a[1][1] > ans) return 0;
while (q.size()) {
auto t = q.front();
q.pop();
for( int i = 0; i < 4; ++ i) {
int nx = t.first + dx[i];
int ny = t.second + dy[i];
if (inmp(nx, ny)) continue;
if (st[nx][ny]) continue;
if (a[nx][ny] > ans) continue;
q.push({nx,ny});
st[nx][ny] = 1;
if (nx == n && ny == n) return 1;
}
}
return 0;
}
void solve() {
cin >> n;
vector<int> v;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
cin >> a[i][j];
v.push_back(a[i][j]);
}
}
sort(v.begin(), v.end());
int l = 0, r = v.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (bfs(v[mid])) r = mid;
else l = mid + 1;
}
cout << v[r] << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}