0%

CF Round 1316

F比较难写,先咕咕咕。

$\text{A}$

肯定尽量堆给第一个,和 $m$ 取个 $\min$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int t, n, m, a[N];


int main() {
scanf ("%d", &t);
while (t--) {
scanf ("%d%d", &n, &m);
int sum = 0;
for (int i = 1; i <= n; ++i) scanf ("%d", &a[i]), sum += a[i];
cout << min(sum, m) << endl;
}
}

$\text{B}$

枚举 $k$ ,模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int t, n;
int main() {
cin >> t;
while (t--) {
cin >> n;
string s; cin >> s; s = "%" + s;
string ans = "";
int p = 0;
for (int k = 1; k <= n; ++k) {
string t = "";
int total_twist = (n - k + 1);
for (int j = k; j <= n; ++j) t.push_back(s[j]);
if (total_twist % 2 == 0) {
for (int j = 1; j < k; ++j) t.push_back(s[j]);
} else for (int j = k-1; j >= 1; --j) t.push_back(s[j]);
if (ans == "") ans = t, p = k;
else if (ans > t) ans = t, p = k;
}
cout << ans << '\n' << p << '\n';
}
}

$\text{C}$

考虑先抛开 $\gcd$ 的鬼畜限制,来看看咋构造。

其实如果考虑卷积的意义就很显然:找出第一个 $a_i\mod p \neq 0$ 的 $i$ 和 $b_j \mod p \neq 0$ 的 $j$ ,$i + j$ 就是答案。因为你手动展开一下就会发现除了$a_i \times b_j$ 非零之外其他的都是 $0$。

这个gcd嘛…只是告诉你一定有解…如果没有 $\mod p \neq 0$ 的那肯定 $\gcd$ 至少是 $p$。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

const int N = (int)1e6 + 5;
int n, m, p, a[N], b[N];
int main() {
cin >> n >> m >> p;
for (int i = 0; i < n; ++i) scanf ("%d", &a[i]);
for (int i = 0; i < m; ++i) scanf ("%d", &b[i]);
int px = 0, py = 0;
for (int i = 0; i < n; ++i) if (a[i] % p != 0) px = i;
for (int i = 0; i < m; ++i) if (b[i] % p != 0) py = i;
cout << px + py << endl;
}

$\text{D}$

这题考试的时候想的很艰难…甚至还因为细节 wa 了两发怀疑人生

对于每个点,如果这个点终点不是 $(-1, -1)$,就把终点直接设成 X

之后从每一个 X 的角度考虑,若这个点周围有人的终点恰好是它,就直接把那个点的方向改成向这个 X 即可。

这样为什么能是一组解呢?因为,对于这组解,我们通过改很少的格子来让他满足了目的,因此其他格子也只会因此受到一点点影响。所以本质上是感性理解

同理,我们如果改了那个点的方向,就可以继续往外 $dfs$ ,直到找不到可以遍历的格子即可。

所以我们已经把不是 $(-1, -1)$ 的点搞完了。那是的怎么办呢?

显然,这些走到环里的点构成了若干个联通块。对每个联通块分别考虑,考虑随便找两个相邻的格子,然后让他们互相指,然后让联通块里的其他格子指向他们两个即可。不难发现,这么构造是最省步数的。

如何让其他格子指向他呢?可以沿用从 X dfs 的思路,也从这两个相邻的格子 dfs,记录反方向操作即可。

记得最后要用 dp 检验不是 $(-1, -1)$ 的格子是否走到了原定位置,以及 $(-1,-1)$ 的格子是否为 X,来判定矛盾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
const char dr[4] = {'U', 'D', 'L', 'R'};
char is[N][N];
int x[N][N], y[N][N], n;
void dfs(int nx, int ny, int ox, int oy) {
for (int i = 0; i < 4; ++i) {
int fx = nx + dx[i], fy = ny + dy[i];
if (fx < 1 || fx > n || fy < 1 || fy > n) continue;

if (x[fx][fy] == -1) continue;
if (is[fx][fy] != ' ') continue;
if (x[fx][fy] == ox && y[fx][fy] == oy) {
is[fx][fy] = dr[i];
dfs(fx, fy, ox, oy);
}
}
}
void dfs1(int nx, int ny) {
for (int i = 0; i < 4; ++i) {
int fx = nx + dx[i], fy = ny + dy[i];
if (fx < 1 || fx > n || fy < 1 || fy > n) continue;
if (is[fx][fy] == ' ' && x[fx][fy] == -1) {
is[fx][fy] = dr[i];
dfs1(fx, fy);
}
}
}
pair <int, int> dp[N][N];
double cl;

pair <int, int> DP(int xx, int yy) {
if (dp[xx][yy] != make_pair(0, 0)) return dp[xx][yy];
if ((double)(clock() - cl) / CLOCKS_PER_SEC > 1.5) {
puts("INVALID");
exit(0);
}
if (is[xx][yy] == 'X') return dp[xx][yy] = {xx, yy};
else if (is[xx][yy] == 'L') return dp[xx][yy] = DP(xx, yy - 1);
else if (is[xx][yy] == 'R') return dp[xx][yy] = DP(xx, yy + 1);
else if (is[xx][yy] == 'U') return dp[xx][yy] = DP(xx - 1, yy);
else if (is[xx][yy] == 'D') return dp[xx][yy] = DP(xx + 1, yy);
}
int main() {
cl = clock();
scanf ("%d", &n);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
is[i][j] = ' ';
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf ("%d%d", &x[i][j], &y[i][j]);
if (x[i][j] != -1 && y[i][j] != -1) is[x[i][j]][y[i][j]] = 'X';
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
if (is[i][j] == 'X') dfs(i, j, i, j);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (is[i][j] == 'X' && x[i][j] == -1) return puts("INVALID"), 0;
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (x[i][j] == -1 && y[i][j] == -1 && is[i][j] == ' ') {
bool f = 0;
for (int d = 0; d < 4; ++d) {
int ii = i + dx[d], jj = j + dy[d];
if (ii < 1 || ii > n || jj < 1 || jj > n) continue;
if (x[ii][jj] == -1) {
is[ii][jj] = dr[d];
is[i][j] = dr[d ^ 1];
dfs1(ii, jj); dfs1(i, j);
f = 1;
break;
}
}
if (!f) {
puts("INVALID");
return 0;
}
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
if (x[i][j] != -1) {
if (DP(i, j) != make_pair(x[i][j], y[i][j])) {
puts("INVALID");
return 0;
}
}
}
puts("VALID");
for (int i = 1; i <= n; ++i)
for (int j =1; j <= n; ++j) {
putchar(is[i][j]);
if (j == n) puts("");
}
}

$\text{E}$

比上一个题好写的多。

发现这个 $p$ 很小可以状压。但是我考试的时候一直不知道如何记录选的 $a_i$,考试后才恍然大悟。

原来,如果你选哪些 $s$ 确定了,那剩下的选 $a_i$ 一定是贪心地选。所以我们可以先按 $a_i$ 排序,这样的话我们选的就是一个前缀。

那又已知前缀中有多少个被选了 $s$,那对应的也知道了多少个被选了 $a$,所以就令 $f_{i, j}$ 为前 $i$ 个,当前队伍选择情况为 $j$ 的最优方案,枚举这个数选/不选转移即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
const int N = 100005, S = (1 << 7) + 5;
int n, p, k;
int aa[N], ss[N][8], a[N], s[N][8], id[N];
bool cmp(int x, int y) {
return aa[x] > aa[y];
}
long long dp[N][S];
int main() {
scanf ("%d%d%d", &n, &p, &k);
for (int i = 1; i <= n; ++i)
scanf ("%d", &aa[i]), id[i] = i;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < p; ++j) scanf ("%d", &ss[i][j]);

sort (id + 1, id + n + 1, cmp);
for (int i = 1; i <= n; ++i) a[i] = aa[id[i]];
for (int i = 1; i <= n; ++i) {
memcpy(s[i], ss[id[i]], sizeof(ss[id[i]]));
}
memset(dp, 0xcf, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
memset(dp[i], 0xcf, sizeof(dp[i]));
for (int j = 0; j < (1 << p); ++j) {
int left = i - __builtin_popcount(j);
dp[i][j] = max(dp[i][j], dp[(i - 1)][j] + (left <= k) * a[i]);
for (int k = 0; k < p; ++k) if (j >> k & 1) {
dp[i][j] = max(dp[i][j], dp[(i - 1)][j ^ (1 << k)] + s[i][k]);
}
}
}
cout << dp[n][(1 << p) - 1] << endl;
return 0;
}