A
题目链接
串$s$和$t$如果具有一段公共前缀，那么可以用1s的时间复制这段前缀。找到这个最长的公共前缀即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int Main()
{
std::string s, t;
std::cin >> s >> t;
int n = s.length(), m = t.length();
int ans = n + m;
for (int i = 0; i < std::min(n, m); ++i)
{
if (s[i] != t[i])
break;
else
ans = std::min(ans, (i + 1) + 1 + (n - i - 1) + (m - i - 1));
}
std::cout << ans << std::endl;
return 0;
}
|
B
题目链接
手推一下不难得到，对于$(0\leq k<n)$，$c[n][k]=2^k$。直接输出答案即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
int Main()
{
int t;
read(t);
std::vector<int> n(t + 1), k(t + 1);
for (int i = 1; i <= t; ++i)
{
read(n[i]);
}
for (int i = 1; i <= t; ++i)
{
read(k[i]);
}
std::vector<modint> bi(100001);
bi[0] = 1;
for (int i = 1; i <= 100000; ++i)
bi[i] = bi[i - 1] * 2;
for (int i = 1; i <= t; ++i)
{
printf("%d\n", bi[k[i]]);
}
return 0;
}
|
C
题目链接
最优策略一定是从把价值为$x$的卡拿完之后再去拿$x+1$；重复这个过程直到下一种价值不存在或者已经拿到了$x+k-1$。
于是排序之后用双指针维护一下即可。
主要代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
int Main()
{
int n, k;
read(n, k);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
std::sort(a.begin() + 1, a.end());
int ans = 0;
for (int i = 1, j = 1; i <= n; ++i)
{
if (j < i)
j = i;
while (j < n && a[j + 1] - a[j] <= 1 && a[j + 1] < a[i] + k)
++j;
ans = std::max(j - i + 1, ans);
}
std::cout << ans << std::endl;
return 0;
}
|
D
题目链接
一共有$m$个技能点，每个技能点两种决策，提示我们用DP的方式解决问题。
设$dp[i][j]$表示前$i$个技能点，力量上加了$j$点能够通过的最多关卡。
显然在第$i$位有两种决策，加到力量上和加到智力上，子问题分别对应$dp[i-1][j-1]$和$dp[i-1][j]$。转移的时候检测一下子问题的状态能够在技能点$i-1$到技能点$i$中间通过多少关卡即可，即中间这些关卡在值域上的一段区间和，用前缀和处理一下就行了。
主要代码：
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
|
int Main()
{
int n, m;
read(n, m);
std::vector<int> r(n + 1);
for (int i = 1; i <= n; ++i)
read(r[i]), r[i] += m;
std::vector<int> s(1);
for (int i = 1; i <= n; ++i)
if (r[i] == m)
s.push_back(i);
s.push_back(n + 1);
std::vector dp(m + 2, std::vector<int>(m + 2, -1e9));
dp[0][0] = 0;
std::vector<int> b(m + m + 4), sum(m + m + 4);
for (int i = 1, p = 1; i <= m + 1; ++i)
{
for (int j = 0; j <= m + m + 2; ++j)
b[j] = 0;
while (p < s[i])
{
b[r[p]]++;
p++;
}
p++;
sum[0] = b[0];
for (int j = 1; j <= m + m + 2; ++j)
sum[j] = sum[j - 1] + b[j];
auto query = [&](int l, int r)
{
if (l == 0)
return sum[r];
return sum[r] - sum[l - 1];
};
for (int j = 0; j <= i; ++j)
{
if (i - 1 >= j)
dp[i][j] = std::max(dp[i][j], dp[i - 1][j] + query(-(i - 1 - j) + m, j + m));
if (j >= 1)
dp[i][j] = std::max(dp[i][j], dp[i - 1][j - 1] + query(j - i + m, j - 1 + m));
// printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
}
}
int ans = 0;
for (int i = 0; i <= m + 1; ++i)
ans = std::max(ans, dp[m + 1][i]);
std::cout << ans << std::endl;
return 0;
}
|
E
题目链接
这种计数问题首先考虑计数对象的特征——即什么样的牌能让玩家1永远胜过玩家2。
1牌很特殊，首先从1牌开始考虑。
假设玩家2抽到了$k$张1牌，那么玩家1至少要有$k$张1牌，且玩家2的每一张1牌，玩家1都有一张比它更大的。
如果把这$2k$个牌按大小排序，填上1或者2，发现它就是一个合法的括号序列。
玩家1还剩下$m-k-k$张1牌。
那么对于除了1牌的其它牌，玩家2不能被玩家1匹配的牌的数量之和应该恰好等于$m-k-k$。
玩家2不能被玩家1匹配的牌，即为括号序列中，左括号比右括号多的情况。
有经典dp——$f[i][j]$表示前$i$个括号，有左括号比右括号多$j$个。可以得到：
$$f[i][j]=f[i-1][j-1]+f[i-1][j+1]$$预处理这个dp。
接下来考虑除了1牌之外，左括号比右括号一共多$x$张的方案。即一个背包DP，把$f[m][i]$当做物品做背包，体积为$i$。
设$dp[i][j]$表示前$i$种非1牌，目前左括号比右括号多$j$个的方案，得到：
$$dp[i][j]=\sum_{x=0}^{j} dp[i-1][j-x]*f[m][x]$$枚举1牌的方案，玩家1比玩家2多$x$张牌，其实等价于把括号倒过来看，还是左括号比右括号多$x$张牌。
最终$ans=\sum_{x=0}^{m}f[m][x]*dp[n][x]$。
实际上这个题目$n,m$可以做到$10^5$级别。
首先是括号序列的dp。
前$m$个括号，有左括号比右括号多$i$个，等价于一个格路计数问题：
左括号看做$(1,0)$,右括号看做$(0,1)$，走的时候不能碰到$y=x+1$这根直线，走到$(\frac{m+i}{2},\frac{m-i}{2})$这个坐标。可以用组合数直接得到答案，记为$a[i]$。
第二个背包DP，用OGF的思想其实是$(\sum_{i=0}^m a[i]x^i)^n$。多项式快速幂取前$m+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
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
|
int Main()
{
int n, m;
read(n, m);
Combinatorics<modint> combinatorics(m + 1);
auto reflection = [&](int x, int y) -> std::pair<int, int>
{
return {y - 1, x + 1};
};
std::vector<modint> a(m + 1);
for (int i = m & 1; i <= m; i += 2)
{
int x = (m + i) / 2, y = (m - i) / 2;
a[i] = combinatorics(x + y, x);
std::tie(x, y) = reflection(x, y);
if (x >= 0)
a[i] -= combinatorics(x + y, x);
// printf("%d%c", a[i], " \n"[i == m]);
}
Poly f(a);
Poly g = f.pow(n - 1, m + 1);
modint ans = 0;
for (int k = 0; k + k <= m; ++k)
ans += g[m - k - k] * f[m - k - k];
printf("%d\n", ans);
return 0;
/*{
std::vector<modint> catalan(m + 1);
catalan[0] = 1;
for (int i = 1; i <= m; ++i)
catalan[i] = catalan[i - 1] * (i * 4 - 2) * combinatorics.inv[i + 1];
std::vector s(m + 1, std::vector<modint>(m + 1));
std::vector<modint> f(m + 1);
s[0][0] = 1;
for (int i = 1; i <= m; ++i)
{
for (int j = 0; j <= i; ++j)
{
if (j > 0)
s[i][j] = s[i - 1][j - 1];
if (j + 1 <= i - 1)
s[i][j] += s[i - 1][j + 1];
}
}
for (int i = 0; i <= m; ++i)
f[i] = s[m][i];
std::vector dp(n + 1, std::vector<modint>(m + 1));
dp[1][0] = 1;
for (int i = 2; i <= n; ++i)
{
for (int j = 0; j <= m; ++j)
{
for (int d = 0; d <= j; ++d)
dp[i][j] += dp[i - 1][j - d] * f[d];
}
}
modint ans = 0;
for (int k = 0; k + k <= m; ++k)
ans += s[m][m - k - k] * dp[n][m - k - k];
printf("%d\n", ans);
}*/
return 0;
}
|
F
题目链接
首先最终答案每个点代表的数只有0或者1。
证明：
假设有一个数是2，说明被加了至少两次。把其中1次换成减法，可以得到更小的。
于是最终一个点被操作了奇数次，则它的数是1；被操作偶数次，它的数是0.
这样就变成了一个奇偶性的判定。
假设有一个随便的方案。某一个询问中两个点$x,y$，其数字分别是1和1，那么不妨把这个询问的操作换成相反的，得到0,0。
而数字是(1,0)、(0,1)，再怎么换最终答案还是一样。
然而假设有两个询问，在某一个点上重叠，状态分别是1,0,1。两询问的操作分别取反，得到0,0,0。
这似乎跟图会有点关系。
考虑用一个询问代表一条边，建出图。边的颜色要么是0要么是1。
如果两个点$u,v$的数都是1，且$u,v$有一条路径相连，那么取反路径上每条边的颜色，只影响$u,v$两个点的值。
这是一个经典问题，每两个值为1的点配对，路径染色，可以消掉一对1。
最终一个连通块里只有最多1个1。
由于只需要$u,v$之间有路径，那么建出生成树即可。
边的0,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
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
|
struct DSU
{
public:
DSU() : n(0) {}
explicit DSU(int _n) : n(_n), parent_or_size(_n + 1, -1) {}
int merge(int a, int b)
{
int x = leader(a), y = leader(b);
if (x == y)
return x;
if (-parent_or_size[x] < -parent_or_size[y])
std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b)
{
return leader(a) == leader(b);
}
int leader(int a)
{
if (parent_or_size[a] < 0)
return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a)
{
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups()
{
std::vector<int> leader_buf(n + 1), group_size(n + 1);
for (int i = 1; i <= n; i++)
{
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(n);
for (int i = 1; i <= n; i++)
{
result[i].reserve(group_size[i]);
}
for (int i = 1; i <= n; i++)
{
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int> &v)
{ return v.empty(); }),
result.end());
return result;
}
private:
int n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
int Main()
{
int n, q;
read(n, q);
DSU dsu(n);
std::vector adj(n + 1, std::vector<std::array<int, 2>>{});
std::vector<int> d(n + 1);
std::vector<std::array<int, 2>> edge(q + 1);
std::vector sub(n + 1, std::vector<int>{});
for (int i = 1; i <= q; ++i)
{
int u, v;
read(u, v);
if (!dsu.same(u, v))
{
dsu.merge(u, v);
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
d[u] ^= 1;
edge[i] = {u, v};
}
for (int i = 1; i <= n; ++i)
{
if (d[i] == 1)
sub[dsu.leader(i)].push_back(i);
}
std::vector status(q + 1, 0);
std::vector tag(n + 1, 0);
auto dfs = [&](auto &&self, int u, int fa) -> void
{
if (fa != 0)
adj[u].erase(std::find_if(adj[u].begin(), adj[u].end(), [&](const std::array<int, 2> &cur)
{ return cur[0] == fa; }));
for (auto [v, i] : adj[u])
{
self(self, v, u);
status[i] = tag[v];
tag[u] ^= tag[v];
}
};
for (int i = 1; i <= n; ++i)
{
if (dsu.leader(i) != i)
continue;
auto &s = sub[i];
for (int j = 1; j < s.size(); j += 2)
{
int u = s[j - 1], v = s[j];
tag[u] ^= 1, tag[v] ^= 1;
// printf("%d %d\n", u, v);
}
dfs(dfs, i, 0);
}
for (int i = 1; i <= n; ++i)
d[i] = 0;
for (int i = 1; i <= q; ++i)
{
if (status[i])
std::swap(edge[i][0], edge[i][1]);
auto [u, v] = edge[i];
printf("%c%c\n", (status[i]) ? 'y' : 'x', (d[u]) ? '-' : '+');
d[u] ^= 1;
}
return 0;
}
|
