A
我不打了，但是考场上没想起来排列 stl 怎么写，所以在下面打 10 遍
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
next_permutation
你可以数一下，一共有 11 遍
B
\([1,1000]\)
典，对于这类数字和的题，直接考虑拆位处理，预处理一下就可以了
const int maxN = 1000 + 10;
int n;
string s[maxN];
int a[maxN][maxN];
int pre[maxN];
void solve(){
cin >> n;
fp(i, 1, n) cin >> s[i];
fp(i, 1, n) fp(j, 1, n) a[i][j] = s[i][j - 1] - '0';
int num = 1;
pre[0] = 1;
fp(i, 1, n) {
(num *= 10) %= mod;
pre[i] = (pre[i - 1] + num) % mod;
}
int ans = 0;
fp(i, 1, n) {
fp(j, 1, n) {
int x = (a[i][j] * pre[n - i]) % mod;
(x *= i) % mod;
(ans += x) %= mod;
x = (a[i][j] * pre[n - j]) % mod;
(x *= j) % mod;
(ans += x) %= mod;
}
}
cout << ans << endl;
}
C
\(n\in [1,20]\)
讲个笑话，老师发的代码过不去第一个样例……
还有个笑话，有个写了 D 的人 C 过不去
考场上想贪心想到头疼，正解是 DP ……
所以告诉我们，贪心没有正确性时，可以考虑 DP
一眼状压，但是我们不能直接枚举最终状态，考虑转移
我们目前已经将一些水杯中的水倒到了其他水杯中，然后考虑继续转移，可以将一杯水倒到另一个非空的杯子里进行更新
所以做完了
我是煞笔
const int maxN = 100, N = 1e7;
int n, m;
int f[N];
int c[maxN][maxN];
int popcount(int now) {
int sum = 0;
while (now) sum++, now -= (now & -now);
return sum;
}
void solve(){
n = rd(), m = rd();
fp(i, 1, n) fp(j, 1, n) c[i][j] = rd();
memset(f, 0x3f, sizeof(f));
if (m == n) {
cout << 0 << endl;
return ;
}
f[0] = 0;
int ans = inf;
fp(i, 1, (1 << n) - 1){ // black is k
fp(j, 1, n)
if (i & (1 << (j - 1))) // j to k
fp(k, 1, n)
if (!(i & (1 << (k - 1))))
f[i] = min(f[i], f[i ^ (1 << (j - 1))] + c[j][k]);
if (popcount(i) == n - m)
ans = min(ans, f[i]);
}
cout << ans << endl;
}
D
不太难