Educational Codeforces Round 89
/ / 阅读耗时 21 分钟 Educational Codeforces Round 89。
A. Shovels and Swords
这游戏明显是Minecraft吧。
设两个物品有$a,b$个，则当$2a\geq b$时，答案就是$b$，同理$2b\geq a$时，答案是$a$，这很显然。
当不满足上面情况时，答案是$\lfloor \frac {a+b}{3}\rfloor$。这个可以用如下方式证明：
先证明$a=b$且$a+b=x$时答案是$\lfloor \frac {x}{3}\rfloor$，可用数学归纳法。在$x=1,2,3$时显然都是成立的，在$x=k>3$时，我们可以先将两波物品分别拿出三个，这样可以使答案加二，于是答案就是$2+\lfloor\frac{x-6}{3}\rfloor=\lfloor\frac {x}{3}\rfloor$。得证。
当$a\not =b$时，不妨设$a>b$，我们先让$b$减去$a-b$，$a$减去$2(a-b)$使答案加$a-b$，这样$a$变为$a-2(a-b)=2b-a>0$同时$b$变为$b-(a-b)=2b-a>0$，两个物品相等，再根据上面的证明，答案就是$a-b+\lfloor\frac{2b-a}{3}\rfloor=\lfloor\frac{a+b}{3}\rfloor $。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
int main()
{
int t;
scanf("%d", &t);
while (t--) {
int a, b;
scanf("%d%d", &a, &b);
if (2 * min(a, b) <= max(a, b)) {
printf("%d\n", min(a, b));
} else {
printf("%d\n", (a + b) / 3);
}
}
return 0;
}
B. Shuffle
一个区间相关的$DFS$。一开始只有区间$[x,x]$，当来了一个区间与其相交时，我们就把区间更新为两者的并，最后答案就是区间的长度。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
int l[10005], r[10005];
int main()
{
int t;
scanf("%d", &t);
while (t--) {
int n, x, m;
scanf("%d%d%d", &n, &x, &m);
for (int i = 1; i <= m; i++) scanf("%d%d", l + i, r + i);
int ll = x, rr = x;
for (int i = 1; i <= m; i++) {
if (r[i] < ll || l[i] > rr) continue;
ll = min(l[i], ll);
rr = max(r[i], rr);
}
printf("%d\n", rr - ll + 1);
}
return 0;
}
C. Palindromic Paths
可以发现对于两个点$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
37
38
39
40
using namespace std;
int op[50][50], n, m;
vector<int> vec[100];
map<int, int> mmp;
inline int solve(int x)
{
mmp.clear();
for (int i = 0; i < vec[x].size(); i++) {
++mmp[vec[x][i]];
}
int maxn = 0;
for (auto s : mmp) {
if (s.second > maxn) maxn = s.second;
}
return vec[x].size() - maxn;
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n - 1 + m - 1; i++) vec[i].clear();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) scanf("%d", &op[i][j]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) vec[min(i - 1 + j - 1, n - i + m - j)].push_back(op[i][j]);
}
int ans = 0;
for (int i = 0; i <= n - 1 + m - 1; i++) {
if (vec[i].empty()) continue;
if (((n + m - 2) % 2 == 0) && (i == (n + m - 2) / 2)) continue;
ans += solve(i);
}
printf("%d\n", ans);
}
return 0;
}
D. Two Divisors
可以证明只有数$x$有至少两个互异的质因子时才可能有解。显然质数是无解的。
假设数$x$的所有互异的质因子是$p_1\cdots p_k$，那么答案可以构造成$d_1=p_1$，$d_2$是$p_2$到$p_k$的乘积。这样显然满足$gcd(d_1+d_2,x)=1$。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
using namespace std;
int pr[10005], tot, bin[10005];
vector<int> aans, bans;
int main()
{
for (int i = 2; i <= 10000; i++) {
if (!bin[i]) pr[++tot] = i;
for (int j = 1; j <= tot; j++) {
if (pr[j] * i > 10000) break;
bin[pr[j] * i] = 1;
if (i % pr[j] == 0) break;
}
}
// for (int i = 1; i <= 10; i++) cout << pr[i] << endl;
// cout << tot << endl;
int n;
scanf("%d", &n);
vector<int> pp;
for (int i = 1, x; i <= n; i++) {
pp.clear();
scanf("%d", &x);
for (int z = 1; z <= tot; z++) {
if (x == 1) break;
if (x % pr[z] == 0) {
pp.push_back(pr[z]);
while (x % pr[z] == 0) x /= pr[z];
}
}
// cout << endl;
if (x != 1) pp.push_back(x);
if (pp.size() == 1) {
aans.push_back(-1), bans.push_back(-1);
} else {
int s = 1;
for (int j = 1; j < pp.size(); j++) s *= pp[j];
aans.push_back(pp[0]);
bans.push_back(s);
}
}
for (int i = 0; i < aans.size(); i++) printf("%d ", aans[i]);
printf("\n");
for (int i = 0; i < bans.size(); i++) printf("%d ", bans[i]);
printf("\n");
return 0;
}
E. Two Arrays
一种很容易想到的方法是$DP$，我们可以定义$dp(x,y)$表示对于$a$数组的$[x,n]$，去满足$b$数组的$[y,m]$的方案数。
但是这样$dp$是$O(nm)$的，不可取。注意到$b$数组严格增，可以将$dp$的第二维优化掉。
可以发现对于$dp(i,j)$，当$i$确定了之后，$j$一定是确定的。因为只要$dp(i,j)$有解，$a$数组的$[x,n]$中最小值必然等于$b_j$，这样可以根据$a$数组在$[x,n]$的最小值来直接得出第二维。
$dp$转移的时候需要使用二分配合前缀和的方法来加速递推，最终时间复杂度$O(n(logn+logm))$。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
using namespace std;
int n, m, a[N], b[N], dp[N], st[N][20], lg[N], bin[20];
inline int query(int l, int r)
{
int t = lg[r - l + 1];
return min(st[l][t], st[r - bin[t] + 1][t]);
}
inline int findB(int l, int r, int who)
{
if (l > r) return -1;
if (l == r) return b[l] == who ? l : -1;
int mid = (l + r) >> 1;
if (b[mid] > who) return findB(l, mid - 1, who);
if (b[mid] < who) return findB(mid + 1, r, who);
return mid;
}
inline int findL(int at, int who, int l, int r) //(,]
{
if (r == l + 1) return r;
int mid = (l + r) >> 1;
if (query(at, mid) == who) return findL(at, who, l, mid);
return findL(at, who, mid, r);
}
inline int findR(int who, int l, int r) //(,]
{
if (r == l + 1) return r;
int mid = (l + r) >> 1;
if (query(mid, n) < who) return findR(who, mid, r);
return findR(who, l, mid);
}
inline int findLL(int who, int l, int r) //[,)
{
if (r == l + 1) return l;
int mid = (l + r) >> 1;
if (query(mid, n) > who) return findLL(who, l, mid);
return findLL(who, mid, r);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", a + i), st[i][0] = a[i];
for (int i = 1; i <= m; i++) scanf("%d", b + i);
lg[0] = -1, bin[0] = 1;
for (int i = 1; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i < 20; i++) bin[i] = bin[i - 1] << 1;
for (int i = 1; i < 20; i++) {
for (int j = 1; j <= n; j++) {
if (j + bin[i] - 1 <= n) st[j][i] = min(st[j][i - 1], st[j + bin[i - 1]][i - 1]);
}
}
if (query(1, n) != b[1]) {
printf("0");
return 0;
}
for (int x = n; x >= 1; x--) {
int at = findB(1, m, query(x, n));
if (at == -1) {
dp[x] = dp[x + 1];
continue;
}
if (at == m) {
dp[x] = (1 + dp[x + 1]) % MOD;
continue;
}
int atL = findL(x, b[at], x - 1, n);
int atL2 = findR(b[at + 1], x - 1, n);
if (query(atL2, n) != b[at + 1]) {
dp[x] = dp[x + 1];
continue;
}
atL = max(atL, atL2 - 1);
int atR = findLL(b[at + 1], atL2, n + 1) - 1;
if (atR < atL) {
dp[x] = dp[x + 1];
continue;
}
++atL, ++atR;
dp[x] = ((dp[atL] - dp[atR + 1]) % MOD + dp[x + 1]) % MOD;
}
printf("%d", (((dp[1] - dp[2])) % MOD + MOD) % MOD);
return 0;
}
F. Jog Around The Graph
这是一道好题，强烈建议一做。
由于边可以重复走，那么对于一条路径，它后来的决策必然是反复走一条边。也就是说，无论这条路径有多长，它的策略必然是这样：
- 先走$k$步来到某条边$e$的一个端点，这$k$步尽可能长。
- 后来的若干步反复走$e$。
我们先求出$1$到点$u$走$k$步的最长到达的路径$dis(u,k)$，这是一个很常规的$dp$，复杂度在$O(n^2)$。然后我们就可以找出一条对于边$e$，$i$路径长的答案：
其中$u$和$v$是$e$的两个端点，$w_e$是$e$的边权。$k$属于$[0,n-1]$，这里不用考虑$k\geq n$的情况，因为走过$n-1$条边必然可以从$1$到任意点。
枚举$k$，找出使得$f(e,i)$最大的$k$（将$i$看做常量），然后规定：
则：
这是一个一次函数，需要考虑每一个$e$在哪一段区间上取最大值。对于给定的若干条直线，求它们在给定区间上的最大值之和，这是一个经典问题，可以在$O(n^2)$复杂度内解决。计算时为了防止端点处重复计算，规定每一条直线忽略其左端点。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
using namespace std;
struct Edge
{
int next, to, v;
} edge[N << 1];
int head[N], cnt = 1, n, m, q;
long long dp[2][N], b[N], k[N];
inline void add(int x, int y, int v)
{
edge[cnt].v = v, edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
inline void jiao(long long& l, long long& r, long long L, long long R)
{
if (L == -1 || R < l || L > r) {
l = r = -1;
return;
}
l = max(l, L), r = min(r, R);
}
vector<pair<pair<int, int>, int>> vec;
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1, v, x, y; i <= m; i++) {
scanf("%d%d%d", &x, &y, &v);
add(x, y, v), add(y, x, v);
k[i] = v, b[i] = -inf;
}
int kk = 0;
long long ans = 0;
for (int j = 0; j < n; j++) {
kk = !kk;
if (j == 0) {
dp[kk][1] = 0;
for (int i = 2; i <= n; i++) dp[kk][i] = -inf;
} else {
for (int i = 1; i <= n; i++) {
dp[kk][i] = -inf;
for (int e = head[i]; e; e = edge[e].next) dp[kk][i] = max(dp[kk][i], edge[e].v + dp[!kk][edge[e].to]);
}
}
for (int i = 1, toa, tob; i < cnt; i += 2) {
toa = edge[i].to, tob = edge[i + 1].to;
b[(i + 1) >> 1] = max(b[(i + 1) >> 1], max(dp[kk][toa], dp[kk][tob]) - j * edge[i].v);
}
long long tmp = -inf;
for (int i = 1; i <= n; i++) tmp = max(tmp, dp[kk][i]);
ans = (ans + tmp) % MOD;
}
for (int i = 1; i <= m; i++) {
long long l = n, r = q;
for (int j = 1; l <= r && j <= m; j++)
if (i != j) {
long long sasd = k[i] - k[j];
long long db = b[j] - b[i];
if (sasd > 0)
l = max(l, db / sasd + 1);
if (sasd < 0)
r = min(r, db / sasd);
if (sasd == 0) {
//若db==0说明两直线相等，只计算一个，即下标最小的那一个
if (!(db < 0 || (db == 0 && j > i)))
r = -1;
}
}
if (l <= r) ans = (ans + (l + r) * (r - l + 1) / 2 % MOD * k[i] % MOD + (b[i] % MOD + MOD) % MOD * (r - l + 1) % MOD) % MOD;
}
printf("%lld", (ans + MOD) % MOD);
return 0;
}
G. Construct the String
方法仍然是$dp$。定义$dp(i,j)$表示第一个串前$i$位匹配上第二个串的前$j$位需要删除的最少字符数。转移情况如下：
当$S_1[i]$不是$”.”$且$S_1[i]=S_2[j]$时：
当$S_1[i]$不是$”.”$且$S_1[i] \not=S_2[j]$时：
当$S_1[i]=”.”$时情况比较复杂，我们首先可以直接删去它，然后转移到$dp(i-1,j)+1$，但是如果不删除，那么转移的方向不容易确定。
考虑不删去这个$”.”$，那么同时需要不删去前面的一个多余字符，但是如果$”.”$前面还是一个$”.”$，则需要删去两个。综合考虑，我们需要找到一个$a_i$，使得经过字符串一的$[a_i,i]$的操作后得到一个空串，并且$i-a_i$最小。$a_i$可以使用栈在$O(n^2)$内解决，然后$dp(i,j)$就可以转移到$dp(a_i-1,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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
char s[N], t[N];
int dp[N][N], a[N], ls, lt, sta;
int main()
{
scanf("%s%s", s + 1, t + 1);
ls = strlen(s + 1), lt = strlen(t + 1);
for (int i = 1; i <= ls; i++) a[i] = -1;
for (int i = 1; i <= ls; i++) {
sta = 0;
for (int j = i; j <= ls; j++) {
if (s[j] >= 'a' && s[j] <= 'z')
++sta;
else if (sta == 0)
break;
else if (sta == 1) {
a[j] = i - 1;
break;
} else
--sta;
}
}
// for (int i = 1; i <= ls; i++) cout << a[i] << " ";
// cout << endl;
for (int i = 1; i <= lt; i++) dp[0][i] = 0x3f3f3f3f;
for (int i = 1; i <= ls; i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
dp[i][0] = dp[i - 1][0] + 1;
} else {
if (a[i] == -1)
dp[i][0] = dp[i - 1][0] + 1;
else
dp[i][0] = min(dp[a[i]][0], dp[i - 1][0] + 1);
}
for (int j = 1; j <= lt; j++) {
if (s[i] == '.') {
if (a[i] == -1) {
dp[i][j] = dp[i - 1][j] + 1;
} else {
dp[i][j] = min(dp[a[i]][j], dp[i - 1][j] + 1);
}
} else if (s[i] == t[j]) {
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j] + 1);
} else {
dp[i][j] = dp[i - 1][j] + 1;
}
// cout << dp[i][j] << " ";
}
// cout << endl;
}
printf("%d", dp[ls][lt]);
return 0;
}