AtCoder Grand Contest 刷题记录

本文记录了0xfaner的AGC题解

写在前面

0xfaner在情人节的夜里打了一场Codeforces的Div.2。但是他D题也不会,E题赛后一分钟才写完,实在是菜得不行。

AtCoder Grand Contest(简称AGC)题目以思维难度高而出名。0xfaner奋发图强,从这一天夜里开始板刷AGC。

本文将会记录0xfaner的刷题过程和全部题解。

AGC001

A - BBQ Easy

题意

给定长度 $ 2n $ 的序列,从中两两配对成 $ n $ 对,每一对的价值为两者中的较小值。询问最大价值之和。

解法

一对的价值取决于较小值,那么较大值则应当尽可能地小。对于任意一个元素而言都应该取大于它的最小元素。

排序后两两一取即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
#define N 101
int a[N], n, ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= 2 * n; i++) scanf("%d", &a[i]);
sort(a + 1, a + 2 * n + 1);
for (int i = 1; i <= n; i++) ans += a[(i << 1) - 1];
printf("%d\n", ans);
return 0;
}

B - Mysterious Light

题意

给定一个正三角形的边长 $ n $ ,现有一条光线从某条边上距离顶点 $ x $ 的地方射出。该光线每次遇到三角形的边或该光线曾经经过的地方就会反射,直到回到射出点为止。询问你该光线经过的路径长度。

解法

画图总结发现,该光线会不断将三角形划分为平行四边形。对于已知长边 $ a $ 和短边 $ b $ 的平行四边形,该光线在其中经过的路径长度为 $ \lfloor \dfrac{a}{b} \rfloor \times 2b $ 。特别地,如果 $ a|b $ 那么路径长度需要减去一个 $ b $ ,并且此时光线将回到射出点。

使用递归法求解即可,理论时间复杂度 $ \mathcal{O}(\log n) $ 。总结规律也可以得到 $ \mathcal{O}(1) $ 的公式 $ ans=3(n-gcd(n,x)) $ 。

代码

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll ans(ll n, ll x) { return x ? (ans(x, n % x) + n / x * x * 2) : -n; }
ll x, n;
int main() {
scanf("%lld%lld", &n, &x);
if (n < x + x) x = n - x;
printf("%lld\n", n + ans(n - x, x));
return 0;
}

C - Shorten Diameter

题意

给定一颗 $ n $ 个节点的树,可以在保证树的连通性的情况下删去一部分节点。

询问最少删去多少节点,使得树的直径为 $ k $ 。

解法

  • $ k $ 为偶数时,枚举每一个点为最后的树的直径的中点,和这个点的距离大于 $ \frac{k}{2} $ 的点全部删去。
  • $ k $ 为奇数时,枚举每一条边为最后的树的直径的中边,分别从两端点出发遍历,距离大于 $ \lfloor \frac{k}{2}\rfloor $ 的全部删去。

时间复杂度 $ \mathcal{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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 2010
#define M 4010
int hd[N], nx[M], e[M];
int n, k, ans = -1;
int dfs(int x, int fa, int dep) {
int num = dep > k / 2;
for (int i = hd[x]; i; i = nx[i])
if (e[i] != fa) num += dfs(e[i], x, dep + 1);
return num;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1, Num = 0, x, y; i < n; i++) {
scanf("%d%d", &x, &y);
nx[++Num] = hd[x], hd[x] = Num, e[Num] = y;
nx[++Num] = hd[y], hd[y] = Num, e[Num] = x;
}
if (k & 1) {
for (int i = 1; i <= n; i++)
for (int j = hd[i]; j; j = nx[j]) {
int x = dfs(i, e[j], 0) + dfs(e[j], i, 0);
if (ans == -1 || ans > x) ans = x;
}
} else
for (int i = 1; i <= n; i++) {
int x = dfs(i, 0, 0);
if (ans == -1 || ans > x) ans = x;
}
printf("%d\n", ans);
return 0;
}

D - Arrays and Palindrome

题意

给定一个长度为 $ M $ 元素和为 $ N $ 的序列 $ A = \{ a_1,a_2,\dots,a_m \} $ 。

称一个字符串 $ S $ 为 $ A $ 的特殊回文串当且仅当该字符串长度为 $ M $ 且满足其前 $ a_1 $ 项、接下来 $ a_2 $ 项、接下来 $ a_3 $ 项……都是回文串。

现在要求你构造一个序列 $ B $ ,使得有且仅有一个字符串满足其既是重排后的 $ A $ 的特殊回文串也是 $ B $ 的特殊回文串。

解法

结论 $ 1 $ :若 $ A $ 中奇数个数超过两个则无解。

要求一个子串是回文串,相当于要求一些位置的字符相同。如果对对应位置相互连边,那么要求所有字符相同则相当于要求这些点在同一个联通块内。那么至少要连 $ n-1 $ 条边,共计 $ 2n-2 $ 个端点。

每个偶数长度的回文串每个点都会成为一条边的端点,但是奇数长度中间那个字符不会连边,就会少一个端点。

由于是两次划分,总端点数不会超过 $ 2n $ 。所以若奇数长度的个数超过两个,显然边数不够。

结论 $ 2 $ :若第 $ 1 $ 到 $ n $ 个字符组成回文串且第 $ 1 $ 到 $ n-1 $ 个或第 $ 2 $ 到 $ n $ 个字符组成回文串,则这 $ n $ 个字符相同。

结论 $ 3 $ :若 $ n $ 为奇数且第 $ 1 $ 到 $ n-1 $ 个字符与第 $ 2 $ 到 $ n $ 个字符组成回文串,则这 $ n $ 个字符相同。

由这 $ 3 $ 个结论,我们得到解法:

在 $ A $ 中把奇数放在首尾, $ B $ 相对 $ A $ 有 $ b_1=a_1+1 $ , $ b_m=a_m−1 $ ,对于其它 $ i \in [2,n-1] $ 。

特别的,对于 $ m=1 $ 的情况构造为 $ 1,a_1−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
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int a[N], n, m, num;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
num += a[i] & 1;
}
if (num > 2) {
printf("Impossible\n");
return 0;
}
for (int i = 2; i < m; i++)
if (a[i] & 1) swap(a[(a[1] & 1) ? m : 1], a[i]);
for (int i = 1; i < m; i++) printf("%d ", a[i]);
printf("%d\n", a[m]);
if (m == 1) a[++m] = a[1], a[1] = 0;
a[1]++;
printf("%d\n", (--a[m]) ? m : --m);
for (int i = 1; i < m; i++) printf("%d ", a[i]);
printf("%d\n", a[m]);
return 0;
}

E - BBQ Hard

题意

给定 $ n $ 个包,第 $ i $ 个包里有一个编号为 $ i $ 的棍子、 $ a_i $ 个肉和 $ b_i $ 个菜。你可以任选两个不同的背包,把这两个背包里所有的肉和菜都用两根棍子串起来形成一个烤串,问能串出多少种烤串。

称这两种烤串不同当且仅当至少有一根棍子的编号不同或肉和菜的数目不同或排列方式不同。

解法

易知任意一对 $ i,j $ 对答案的贡献为 $ \mathcal{C}_{a_i+b_i+a_j+b_J}^{a_i+a_j} $ ,则 $\displaystyle ans = \sum_{1 \leq i< j \leq n} \mathcal{C}_{a_i+b_i+a_j+b_j}^{a_i+a_j} $ 。

该公式计算时间复杂度 $ \mathcal{O}(n^2) $ ,不能满足条件,考虑对其优化。

对 $ \mathcal{C}_{a_i+b_i+a_j+b_J}^{a_i+a_j} $ 进行抽象,可以理解为从坐标 $ (-a_i,-b_i) $ 出发,每次只能沿 $ x $ 轴或 $ y $ 轴正方向移动一单位长度,最终到达 $ (a_j,b_j) $ 的方案数。

那么定义 $ f(i,j) $ 表示从 $ (i,j) $ 左下方任意 $ (-a_s,-b_s) $ 出发,每次只能沿 $ x $ 轴或 $ y $ 轴正方向移动一单位长度,最终到达 $ (i,j) $ 的方案数.

所以 $ \displaystyle ans = \dfrac{\sum_{i=1}^n f(a_i,a_j) - \sum_{i=1}^n \mathcal{C}_{2(a_i+a_j)}^{2a_i}}{2} $ ,其中 $ f(a_i,a_j) $ 可以DP求解。

代码

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
#include <bits/stdc++.h>
using namespace std;
#define Pii pair<int, int>
#define ll long long
#define mod 1000000007
#define N 10001
#define S 2000
ll Qpow(ll x, ll n) {
ll s = 1;
while (n) {
if (n & 1) s = s * x % mod;
x = x * x % mod;
n >>= 1;
}
return s;
}
ll inv(ll x) { return Qpow(x, mod - 2); }
ll fac[N], ifac[N];
ll C(int x, int y) { return fac[x] * ifac[x - y] % mod * ifac[y] % mod; }
void Prepare() {
fac[0] = 1;
for (ll i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod;
ifac[N - 1] = inv(fac[N - 1]);
for (ll i = N - 1; i; i--) ifac[i - 1] = ifac[i] * i % mod;
}
Pii P[S * S];
int d[S << 1 | 1][S << 1 | 1], n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &P[i].first, &P[i].second);
Prepare();
for (int i = 1; i <= n; i++) d[S - P[i].first][S - P[i].second]++;
for (int dis = 1; dis <= S << 2; dis++)
for (int i = max(0, dis - (S << 1)); i <= min(S << 1, dis); i++) {
int j = dis - i;
if (i) d[i][j] = (d[i][j] + d[i - 1][j]) % mod;
if (j) d[i][j] = (d[i][j] + d[i][j - 1]) % mod;
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
int x = P[i].first, y = P[i].second;
ans = (ans + d[x + S][y + S]) % mod;
ans = (ans - C(2 * x + 2 * y, 2 * x) + mod) % mod;
}
printf("%lld\n", ans * inv(2) % mod);
return 0;
}

F - Wide Swap

题意

给定长度为 $ n $ 的序列 $ p $ ,对任意两个满足 $ |i-j|\geq k $ 并且 $ |p_i-p_j| = 1 $ 的 $ p_i $ 和 $ p_j $ ,可以进行交换。

求任意次操作之后可得的最小字典序的序列。

解法

令 $ i $ 的位置为 $ q_i $ ,从这个角度考虑问题和给定的操作,就是每次交换相邻的两个数,并且它们要满足差不小于 $ k $ ,使得最终 $ 1 $ 的位置尽量靠前, $ 2 $ 的位置尽量靠前,依此类推。

可以发现差小于 $ k $ 的数的相对位置不会发生变化,并且满足这个条件的排列都是合法排列。

可以证明最小字典序的 $ q $ 一定对应最小字典序的 $ p $ 。求出最小字典序后在 $ i $ 前面的数一定都是比 $ i $ 小或者比 $ i $ 大且差小于 $ k $ 且在原来 $ q $ 中就在 $ i $ 前面的数。这样就保证了 $ i $ 在不比它小的数中尽可能靠前,就得到了最小字典序的 $ p $ 。

那么如果 $ |i−j|<k $ 并且 $ p_i<p_j $ 那么从 $ i $ 向 $ j $ 连边,求这张图的最小字典序拓扑排列即可。

其中边数最多可达 $ 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
#include <bits/stdc++.h>
using namespace std;
#define N 2000010
int p[N], a[N], b[N];
struct node {
int l, r, mid, minn;
} s[N << 2];
void build(int di, int l, int r) {
s[di].l = l, s[di].r = r, s[di].mid = l + r >> 1, s[di].minn = 1e9;
if (l == r) return;
build(di << 1, l, s[di].mid), build(di << 1 | 1, s[di].mid + 1, r);
}
void ins(int di, int x, int v) {
if (s[di].l == s[di].r) {
s[di].minn = v;
return;
}
ins(x <= s[di].mid ? di << 1 : di << 1 | 1, x, v);
s[di].minn = min(s[di << 1].minn, s[di << 1 | 1].minn);
}
int query(int di, int l, int r) {
if (l <= s[di].l && s[di].r <= r) return s[di].minn;
if (r <= s[di].mid) return query(di << 1, l, r);
if (l > s[di].mid) return query(di << 1 | 1, l, r);
return min(query(di << 1, l, r), query(di << 1 | 1, l, r));
}
int hd[N], nx[N << 1], e[N << 1], Num;
void adde(int x, int y) { nx[++Num] = hd[x], hd[x] = Num, e[Num] = y; }
priority_queue<int> q;
int n, k, In[N];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
a[x] = i;
}
for (int i = 1; i <= n / 2; i++) swap(a[i], a[n - i + 1]);
build(1, 1, n);
for (int i = n; i >= 1; i--) {
int x = query(1, max(1, a[i] - k + 1), a[i]);
if (x > 0 && x <= n) adde(a[i], a[x]);
x = query(1, a[i], min(n, a[i] + k - 1));
if (x > 0 && x <= n) adde(a[i], a[x]);
ins(1, a[i], i);
}
for (int i = 1; i <= n; i++)
for (int j = hd[i]; j; j = nx[j]) In[e[j]]++;
for (int i = 1; i <= n; i++)
if (!In[i]) q.push(i);
int num = 0;
while (!q.empty()) {
int u = q.top();
q.pop();
b[++num] = u;
for (int i = hd[u]; i; i = nx[i])
if (!(--In[e[i]])) q.push(e[i]);
}
for (int i = 1; i <= n / 2; i++) swap(b[i], b[n - i + 1]);
for (int i = 1; i <= n; i++) p[b[i]] = i;
for (int i = 1; i <= n; i++) printf("%d\n", p[i]);
}

AGC002

A - Range Product

题意

给定两整数 $ a $ 与 $ b $ ,询问区间 $ [a,b] $ 的乘积为正数负数还是 $ 0 $ 。

解法

  1. $ a \leq 0 \leq b $ 时为 $ 0 $
  2. $ a>0 $ 时为正数
  3. $ b<0 $ 时若 $ b-a $ 为偶数数则为负数,否则为正数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
scanf("%d%d", &a, &b);
if (a > 0)
puts("Positive");
else if (b >= 0)
puts("Zero");
else if ((b - a) & 1)
puts("Positive");
else
puts("Negative");
return 0;
}

B - Box and Ball

题意

初始有 $ n $ 个盒子, $ 1 $ 号盒子中有一个红球,其余盒子中均有一个白球。

按顺序给定 $ m $ 次操作,每次从 $ x $ 号盒子中随机取一个球放到 $ y $ 号盒子中。

询问你最后有多少盒子中可能存在红球。

解法

模拟这个过程即可,令 $ a_i $ 表示 $ i $ 号盒子中球的数量, $ v_i $ 表示当前 $ i $ 号盒子中是否有可能存在红球。

每次 $ a_i $ 减到 $ 0 $ 时只需让 $ v_i $ 变为false即可。时间复杂度 $ \mathcal{O}(n) $

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
#define N 100001
int a[N], v[N], n, m;
int main() {
v[1] = true;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) a[i] = 1;
for (int i = 1, x, y; i <= m; i++) {
scanf("%d%d", &x, &y);
if (v[x]) v[y] = true;
if (a[x] == 1) v[x] = false;
a[x]--, a[y]++;
}
int num = 0;
for (int i = 1; i <= n; i++)
if (v[i]) num++;
printf("%d\n", num);
return 0;
}

C - Knot Puzzle

题意

给定 $ n $ 根绳子,第 $ i $ 根绳子长度为 $ a_i $ 。现在这 $ n $ 根绳子按顺序首尾连接了起来(打结),你可以每次选择长度不小于 $ l $ 的一段,并把它的某一个结断开。

询问你把这些结全部断开的方案。

解法

可以发现只要存在相邻两段的长度和不小于 $ l $ 即可。

找到该结点,分别从左到右解开左边的结点,从右到左解开右边的节点,最后再解开该节点即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
#define N 100001
int a[N], n, m;
int main() {
scanf("%d%d", &n, &m);
int add = 0;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i < n; i++)
if (a[i] + a[i + 1] >= m) add = i;
if (add) {
puts("Possible");
for (int i = 1; i < add; i++) printf("%d\n", i);
for (int i = n - 1; i > add; i--) printf("%d\n", i);
printf("%d\n", add);
} else
puts("Impossible");
return 0;
}

D - Stamp Rally

题意

给定一个无向图, $ q $ 次询问。每次询问给出两个点 $ x $ 与 $ y $ ,求以 $ x,y $ 为起点的两条长度和不少于 $ z $ 的路径中的边的编号的最大值的最小值。

解法

一个比较容易想到的做法是对每一个询问单独处理,并查集维护联通块,直接二分答案。

$ \mathcal{O}(n) $ 建好并查集后可以 $ \mathcal{O}(1) $ 求出 $ x $ 和 $ y $ 所在联通块的大小之和( $ x $ 和 $ y $ 联通需要特判)。

但是该做法时间复杂度 $ \mathcal{O}(qn\log m) $ ,考虑对其优化。

注意到询问间并查集有重复构造,其实可以复用。所以采用整体二分的思想,时间复杂度 $ \mathcal{O}(n\log n) $ 。

太棒了,学到许多

代码

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
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int f[N], ans[N], num[N];
int n, m, q;
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
void Union(int a, int b) {
int fa = find(a), fb = find(b);
if (fa == fb) return;
if (num[fa] > num[fa]) swap(a, b);
f[fa] = fb, num[fb] += num[fa];
}
int size(int a, int b) {
int fa = find(a), fb = find(b);
if (fa == fb) return num[fa];
return num[fa] + num[fb];
}
struct edge {
int a, b;
} edg[N];
struct data {
int x, y, z, id;
};
struct Divide {
int l, r, ansl, ansr;
};
vector<data> que[2];
vector<Divide> Div[2];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, x, y; i <= m; ++i) {
scanf("%d%d", &x, &y);
edg[i] = (edge){x, y};
}
scanf("%d", &q);
for (int i = 1, x, y, z; i <= q; ++i) {
scanf("%d%d%d", &x, &y, &z);
que[0].push_back((data){x, y, z, i});
}
Div[0].push_back((Divide){0, q - 1, 0, m});
int p = 0;
while (Div[p].size()) {
int cur = 1;
Div[p ^ 1].clear(), que[p ^ 1].clear();
for (int i = 1; i <= n; ++i) f[i] = i, num[i] = 1;
for (int i = 0; i < (int)Div[p].size(); ++i) {
int num = 0;
if (Div[p][i].ansl == Div[p][i].ansr) {
for (int j = Div[p][i].l; j <= Div[p][i].r; ++j)
ans[que[p][j].id] = Div[p][i].ansl;
continue;
}
int mid = (Div[p][i].ansl + Div[p][i].ansr) >> 1;
for (; cur <= mid; ++cur) Union(edg[cur].a, edg[cur].b);
for (int j = Div[p][i].l; j <= Div[p][i].r; ++j)
if (size(que[p][j].x, que[p][j].y) >= que[p][j].z)
que[p ^ 1].push_back(que[p][j]), num++;
if (num)
Div[p ^ 1].push_back((Divide){(int)que[p ^ 1].size() - num,
(int)que[p ^ 1].size() - 1,
Div[p][i].ansl, mid});
num = 0;
for (int j = Div[p][i].l; j <= Div[p][i].r; ++j)
if (size(que[p][j].x, que[p][j].y) < que[p][j].z)
que[p ^ 1].push_back(que[p][j]), num++;
if (num)
Div[p ^ 1].push_back((Divide){(int)que[p ^ 1].size() - num,
(int)que[p ^ 1].size() - 1,
mid + 1, Div[p][i].ansr});
}
p ^= 1;
}
for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
return 0;
}

E - Candy Piles

题意

给定 $ n $ 堆糖果,第 $ i $ 堆有 $ a_i $ 个糖果。两人博弈,每次可以取尽最大的一堆糖果,或者从所有堆中取走一个糖果。取走最后一颗糖果的输,问均采取最优策略时的胜方。

解法

把这 $ n $ 个糖果从大到小排好序以后建立直方图后对应成格点。发现两种操作分别是删去最左边一列和删去最下面一行。

转化为坐标,可以理解为初始坐标 $ (1,1) $ ,每次可以向上或向右移动一格,最先无法移动的人赢。

可以发现处在同一条斜率为 $ 1 $ 的直线上的点对应的胜败状态是相同的,所以任意一点的胜败状态可以直接由边界状态推得。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
#define N 100001
int a[N], n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
sort(a + 1, a + n + 1, greater<int>());
int add = 1, adds = 1;
while (add < n && a[add + 1] >= add + 1) add++;
while (a[adds + 1] >= add) adds++;
int ans = ((a[add] - add) & 1) || ((adds - add) & 1);
puts(ans ? "First" : "Second");
return 0;
}

F - Leftmost Ball

题意

给定 $ n $ 种颜色的球,每种颜色有 $ k $ 个。将这 $ n \times k $ 个球排成一排, 并将每一种颜色最左边的球涂成第 $ n + 1 $ 种颜色。问最终的颜色序列有多少种。

解法

因为每种颜色第一次出现的位置会被涂成另一种颜色。那么标记这 $ n $ 个位置为特殊位置,假定这 $ n $ 个特殊位置的球的初始颜色从左到右颜色是 $ 1 $ 到 $ n $ ,最后答案再乘 $ n! $ 即可。

令 $ dp[i][j] $ 表示已经涂完前 $ i $ 种颜色,并已经涂了 $ j $ 个特殊颜色的方案总数。

易知此时普通颜色位置涂了 $ (k−1)\times i $ 个,再加上被涂成特殊颜色的格子,所以共确定了 $ (k−1)\times i+j $ 个格子。并且显然有 $ i \leq j $ ,于是考虑 DP 转移。

考虑 $ dp[i][j] $ 对于其他的贡献:

  1. 下一个格子选择涂特殊颜色: $ dp[i][j+1] $ += $ dp[i][j] $
  2. 下一个格子涂最终序列中颜色 $ i+1 $ : $ dp[i+1][j] $ += $ \mathcal{C}_{k(n−i)−(j−i)−1}^{k−2} dp[i][j] $

需要特判 $ k=-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
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 2001
int n, k;
ll fac[N * N], inv[N * N], dp[N][N] = {1};
ll Qpow(ll x, ll n) {
ll s = 1;
while (n) {
if (n & 1) s = s * x % mod;
x = x * x % mod;
n >>= 1;
}
return s;
}
ll C(int n, int m) {
if (m < 0 || m > n) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
scanf("%d%d", &n, &k);
if (k == 1) {
puts("1");
return 0;
}
for (int i = fac[0] = 1; i <= n * k; i++) fac[i] = fac[i - 1] * i % mod;
inv[n * k] = Qpow(fac[n * k], mod - 2);
for (int i = n * k; i; i--) inv[i - 1] = inv[i] * i % mod;
for (int i = 0; i <= n; i++)
for (int j = i; j <= n; j++) {
dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
ll s = C(k * (n - i) - (j - i) - 1, k - 2) + dp[i + 1][j];
dp[i + 1][j] = dp[i][j] * s % mod;
}
printf("%lld", dp[n][n] * fac[n] % mod);
return 0;
}

AGC003

A - Wanna go back home

题意

给定二维平面 $ n $ 次移动方向(上下左右),每次移动长度自定,询问 $ n $ 次移动后能否回到起始点。

解法

左右与上下要么都有,要么都没有即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
#define N 1001
char c[N];
int X0, Y0, X1, Y1;
int main() {
scanf("%s", c);
int n = strlen(c);
for (int i = 0; i < n; i++)
(c[i] == 'N' ? X0 : c[i] == 'W' ? Y0 : c[i] == 'S' ? X1 : Y1) = 1;
puts(((X0 ^ X1) || (Y0 ^ Y1)) ? "No" : "Yes");
return 0;
}

B - Simplified mahjong

题意

给定 $ n $ 种卡牌,第 $ i $ 种卡牌权值为 $ i $ ,有 $ a_i $ 张。每次可以不放回取出差值不超过 $ 1 $ 的一对卡牌。

询问最多可以取出多少对卡牌。

解法

贪心即可,从小到大每次比自己小 $ 1 $ 的那种卡牌如果有剩就直接取,否则自己和自己配对即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
int a[N], n;
ll ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] && a[i - 1]) a[i]--, ans++;
ans += (a[i] >> 1), a[i] &= 1;
}
printf("%lld\n", ans);
return 0;
}

C - BBuBBBlesort!

题意

给定一个序列,每次可以交换距离为 $ 1 $ 或 $ 2 $ 的一对元素,询问你最少交换多少次距离为 $ 1 $ 的元素,可以使这 $ n $ 个元素从小到大排列。

输入为 $ [1,n] $ 且保证无重复元素。

解法

因为输入保证无重复元素,所以每个元素的最终位置都已确定。现在给定了每个元素的初始位置,那么就知道了每个元素的位移,而若位移是偶数,则只需要每次交换距离为 $ 2 $ 即可,若位移为奇数,则需要 $ 1 $ 次交换距离为 $ 1 $ 的元素。

假定 $ n $ 个元素中位移为奇数的元素有 $ k $ 个,易证 $ k $ 为偶数。答案就是 $ \dfrac{k}{2} $ 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int a[N], b[N], n, k;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++)
if ((lower_bound(b + 1, b + n + 1, a[i]) - b - i) & 1) k++;
printf("%d\n", k >> 1);
return 0;
}

D - Anticube

题意

给定长度为 $ n $ ( $1\leq n \leq 10^5 $ )的序列 $ S $ ( $ 1 \leq s_i \leq 10^{10} $ ),要求从中选出尽可能多的数,使得任意一对选中的数之积不为立方数。

解法

首先假定有 $ s_is_j=x^3 $ ,对其分析。

根据唯一分解定理,对于每一个 $ s_i $ ,有 $ \displaystyle s_i = \prod_{i=1}^{m} p_i^{k_i} $ , 若 $ s_i $ 能与 $ s_j $ 配对,则 $ \displaystyle a_i = \prod_{i=1}^{m} p_i^{k_i \bmod 3} $ 同样可以和 $ s_j $ 配对。这样一来多个 $ s_i $ 就可以对应到同一个 $ a_i $ 。

这样就可以将这 $ n $ 个 $ s_i $ 分为 $ k $ 类 $ a_i $ 。预处理出 $ 10^{\frac{10}{3}} $ 以内的质数(约有 $ 300 $ 个)可以优化时间复杂度,这样分类的总时间复杂度即可降为 $ \mathcal{O}(300n) $ 。

对于每一类质数,和它对应成完全平方数的只有一类。如此两两配对,每一对贪心取最大的一类即可。最坏时间复杂度 $ \mathcal{O}(n \log n) $

这样总时间复杂度即为 $ \mathcal{O}(n \log n + 300n) $ (但是实现有点繁琐

代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 300010
#define S 100000
int prime[N], snum = 325, pnum;
bool p[N];
void EulerSieve(int n) {
for (int i = 2; i <= n; i++) {
if (!p[i]) prime[++pnum] = i;
for (int j = 1; j <= pnum; j++) {
if (i * prime[j] > n) break;
p[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
ll s[N], a[N];
int n, len[N], k[N], num[N];
int id[N], ans;
bool cmp(int x, int y) { return a[x] < a[y]; }
int main() {
EulerSieve(S);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &s[i]);
k[i] = len[i] = 0, a[i] = 1;
for (int j = 1; j <= snum; j++) {
if (s[i] % prime[j]) continue;
int m = 0;
while (s[i] % prime[j] == 0) s[i] /= prime[j], m++;
if (m %= 3) k[i] |= ((m & 1) << len[i]), len[i]++, a[i] *= prime[j];
}
if (s[i] > 1) {
if (s[i] < S)
k[i] |= (1 << len[i]), len[i]++, a[i] *= s[i];
else {
ll ss = sqrt(s[i]);
if (ss * ss != s[i])
ans++, i--, n--;
else
len[i]++, a[i] *= ss;
}
}
}
for (int i = 1; i <= n; i++) id[i] = i;
sort(id + 1, id + n + 1, cmp);
for (int l = 1, r = 1; l <= n; l = r + 1, r = l) {
while (r < n && a[id[r]] == a[id[r + 1]]) r++;
if (a[id[l]] == 1) {
ans++;
continue;
}
int maxn = (1 << len[id[l]]) - 1;
for (int i = l; i <= r; i++) num[k[id[i]]]++;
for (int i = l; i <= r; i++) {
int x = k[id[i]], y = (maxn ^ k[id[i]]);
if (num[x] >= num[y]) ans += num[x], num[x] = num[y] = 0;
}
}
printf("%d\n", ans);
return 0;
}

E - Sequential operations on Sequence

题意

给定一个长度为 $ n $ 的序列 $ S $ ,元素按顺序为 $ 1,2\dots n $ 。

接着给定 $ q $ 次操作,每次操作给定一个正整数 $ q[i] $ 。首先先把序列 $ S $ 无穷重复,然后把前 $ q[i] $ 项截取出来成为新的序列 $ S $ 。

求这 $ q $ 次操作后, $ 1 $ 到 $ n $ 在序列 $ S $ 中分别出现的次数。

解法

首先可以发现若有第 $ i $ 次操作与第 $ j $ 次操作满足 $ i<j $ 且 $ q[i] \geq q[j] $ ,那么第 $ j $ 次操作将会无效化第 $ i $ 次操作。

那么可以将所有的无效操作剔除,得到一系列 $ q[i] $ 不断增大的操作。

这样我们就发现每一次操作后的序列相对于操作前的序列而言,就是将这段序列重复若干次,然后在加上这个序列的一段前缀。这个前缀的长度是 $ q_i \bmod q_{i-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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
int q, n, num;
ll len[N], val[N], ans[N], x;
void search(ll x, ll v) {
if (x == 0) return;
int add = upper_bound(len + 1, len + num + 1, x) - len - 1;
if (add) {
val[add] += (x / len[add]) * v;
search(x % len[add], v);
} else
ans[1] += v, ans[x + 1] -= v;
}
int main() {
scanf("%d%d", &n, &q);
len[++num] = n;
while (q--) {
scanf("%lld", &x);
while (num && len[num] >= x) num--;
len[++num] = x;
}
val[num] = 1;
for (ll i = num - 1; i; i--) {
val[i] += len[i + 1] / len[i] * val[i + 1];
search(len[i + 1] % len[i], val[i + 1]);
}
ans[1] += val[1], ans[len[1] + 1] -= val[1];
for (ll i = 1; i <= n; i++) printf("%lld\n", ans[i] += ans[i - 1]);
return 0;
}