比赛链接：
https://codeforces.com/contest/1575
A. Another Sorting Problem
题目大意：
\(n\) 个长为 \(m\) 的字符串，对它们进行排序，比较奇数位时要实现递增，偶数位要递减。
思路：
直接 sort 就好了。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
struct node{
string s;
int p;
}nd[N];
bool cmp(node a, node b){
for (int i = 0; i < m; i++)
if (a.s[i] != b.s[i])
return (a.s[i] < b.s[i]) ^ (i & 1);
}
void solve(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
cin >> nd[i].s;
nd[i].p = i;
}
sort (nd + 1, nd + n + 1, cmp);
for (int i = 1; i <= n; i++)
cout << nd[i].p << " \n"[i == n];
}
int main(){
solve();
return 0;
}
D. Divisible by Twenty-Five
题目大意：
有一个由数字、'' 和 'X' 组成的字符串，每一个''都可以被 0 到 9 的数字替代，所有的'X'都只能被 0 到 9 的一个数字替代。求所有能组成的数字能被25整除的有几个，不能含有前导零。
思路：
能被25整除的话只用看结尾的两位就可以了，最后结尾要是00，25，50，75。
1. 可以直接去对结尾两位讨论。（我写出来的有点冗长 qwq）
2. 因为字符串长度最大只有 8 位，可以去 暴力 跑所有能组成的数，然后逐一判断。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
string s;
LL expo (LL a, LL b){
LL ret = 1;
while (b > 0){
if (b & 1) ret = ret * a;
a = a * a;
b >>= 1;
}
return ret;
}
int main(){
cin >> s;
int low = expo(10, (int)(s).size() - 1), high = expo(10, (int)(s).size()) - 1, ans = 0; //只从可能组成数的下界遍历到上界，然后去判断
if (low == 1) low--;
while (low % 25) low++;
for (; low <= high; low += 25){
string current = to_string(low);
char xval = '-';
bool can = 1;
for (int i = 0; i < (int)(s).size(); i++){
if (s[i] == '_') continue;
if (s[i] == 'X') {
if (xval != '-' && xval != current[i]){
can = 0;
break;
}
xval = current[i];
}
else if (s[i] != current[i]){
can = 0;
break;
}
}
ans += can;
}
cout << ans << "\n";
return 0;
}
当然，也可以用 dp 或者 dfs 去做。（后面补上）
J. Jeopardy of Dropped Balls
题目大意：
有一个 \(n * m\) 的网格，每个格子中有个数字，1、2或3，代表当球到达这个格子的时候，球会向哪边移动，1表示向右，2表示向下，3表示向左，不论格子中是什么数字，当球离开后，数字都变成2，现在在第一行放 \(k\) 个球，分别放在 \(c_1\)，\(c_2\)，...，\(c_k\) (1 <= \(c_i\) <= m) 的位置，判断球最后会从哪一列离开。
思路：
因为网格的大小只有1000 * 1000，所以可以直接暴力模拟跑一遍就好了。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int NA = 1e5 + 10;
int n, m, k, a[N][N], c[NA];
int f(int x, int y){
if (x > n) return y;
if (a[x][y] == 1){
a[x][y] = 2;
return f(x, y + 1);
}
else if (a[x][y] == 2)
return f(x + 1, y);
else if (a[x][y] == 3){
a[x][y] = 2;
return f(x, y - 1);
}
}
void solve(){
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= k; i++)
scanf("%d", &c[i]);
for (int i = 1; i <= k; i++)
cout << f(1, c[i]) << " \n"[i == k];
}
int main(){
solve();
return 0;
}
G. GCD Festival
题目大意：
给一个序列 \(a\)，求 \(\sum_{i = 1}^n \sum_{j = 1}^n gcd(a_i, a_j) * gcd(i, j)\)，结果对 1e9 + 7 取模。
思路：
加载中...
代码：