CF2034A
题目链接
题意
找一个最小的$m$使得，$m \bmod a = m \bmod b$
解法
最小公倍数
1
2
3
4
5
6
7
|
int Main()
{
int a, b;
read(a, b);
printf("%d\n", std::lcm(a, b));
return 0;
}
|
CF2034B
题目链接
题意
把一个01串进行若干次修改，使得不存在连续的$m$个0。一次修改可以把长度为$k$的一段修改成$k$个1
解法
由贪心可知，如果出现连续的$m$个0，直接在最后一个0处修改即可。用双指针统计连续的$m$个0
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
|
int Main()
{
int n, m, k;
std::cin >> n >> m >> k;
std::string s;
std::cin >> s;
int cnt = 0;
int ans = 0;
for (int i = 0, j = 0; i + m - 1 < n;)
{
j = std::max(i, j);
while (j - i + 1 <= m)
cnt += s[j] == '1', j++;
if (cnt == 0)
{
i = j - 1;
for (int x = i; x <= i + k - 1 && x < n; ++x)
s[x] = '1';
i = i + k;
cnt = 0;
++ans;
}
else
{
cnt -= s[i] == '1';
i++;
}
}
std::cout << ans << "\n";
return 0;
}
|
CF2034C
题目链接
题意
有一个网格，有的点标记了上下左右四个方向，有的点没标记方向；现在问最多能使多少个点成环。
解法
没标记方向的点相当于有上下左右四条待选边；直接DFS找环即可
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
|
int Main()
{
int n, m;
std::cin >> n >> m;
auto index = [&](int x, int y) -> int
{
return m * (x - 1) + y;
};
std::vector<int> vis(n * m + 1);
std::vector<int> esc(n * m + 1);
std::vector<std::string> s(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> s[i];
auto dfs = [&](this auto &&self, int x, int y) -> bool
{
if (x == 0 || x > n || y == 0 || y > m)
return true;
int u = index(x, y);
if (vis[u])
return esc[u];
vis[u] = true;
if (s[x][y - 1] == 'R')
esc[u] = self(x, y + 1);
if (s[x][y - 1] == 'U')
esc[u] = self(x - 1, y);
if (s[x][y - 1] == 'L')
esc[u] = self(x, y - 1);
if (s[x][y - 1] == 'D')
esc[u] = self(x + 1, y);
if (s[x][y - 1] == '?')
{
bool ret = true;
ret &= self(x, y + 1);
ret &= self(x - 1, y);
ret &= self(x, y - 1);
ret &= self(x + 1, y);
esc[u] = ret;
}
return esc[u];
};
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
if (!vis[index(i, j)])
dfs(i, j);
}
int ans = n * m - std::accumulate(esc.begin() + 1, esc.end(), 0);
std::cout << ans << "\n";
return 0;
}
|
CF2034D
题目链接
题意
有一个值为$0,1,2$的长为$n$的数组，需要把它排序；
一次操作可以选择两个值相差不超过1的值，小的+1，大的-1。
用不超过$n$个操作使数组排好序
解法
排好序的数组不存在逆序对；因此按值域维护逆序对即可。
由于题目的限制，只需要维护$2,1$逆序对和$1,0$逆序对。
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
|
int Main()
{
int n;
read(n);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
std::array<std::set<int>, 3> sets{};
for (int i = 1; i <= n; ++i)
sets[a[i]].insert(i);
std::vector<std::pair<int, int>> res{};
while (true)
{
if (sets[0].size() && sets[1].size())
{
int last0 = *sets[0].rbegin(), first1 = *sets[1].begin();
if (last0 > first1)
{
sets[1].erase(first1);
sets[0].erase(last0);
sets[1].insert(last0);
sets[0].insert(first1);
res.push_back({last0, first1});
continue;
}
}
if (sets[1].size() && sets[2].size())
{
int last1 = *sets[1].rbegin(), first2 = *sets[2].begin();
if (last1 > first2)
{
sets[2].erase(first2);
sets[1].erase(last1);
sets[2].insert(last1);
sets[1].insert(first2);
res.push_back({last1, first2});
continue;
}
}
break;
}
printf("%d\n", res.size());
for (auto [i, j] : res)
printf("%d %d\n", i, j);
return 0;
}
|
CF2034E
题目链接
题意
构造$k$个排列，排成$k$行；每一列的和应该相等
解法
$k=1$的时候只有$n=1$有解
$k > n!$无解。
接下来考虑每一列的和是多少？
一行的总和固定为$n(n+1)/2$，$k$行总和为$kn(n+1)/2$
所以一列的和为$k(n+1)/2$
因此如果这个数不是整数，则无解。
如果$k$是偶数显然有解——选择$k/2$个不相同的排列和他们的倒置排列即可。
如果$k$是奇数？$n$也应该是奇数。$k=1$时无解（已特判）。
$k=3$有解。特殊构造一下即可。
如果$k=3$有解，那么$k=2x+3$也有解——直接接$x$个排列和它们的倒置排列即可。
但是最后接到最开始的3个排列的倒置排列时，就无解了，因为此时列的和不相等。所以$k$为奇数，最多到$n!-3$才有解。
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
|
int Main()
{
int n, k;
read(n, k);
if (n == 1 && k == 1)
return printf("YES\n1\n"), 0;
if (n == 1 && k != 1)
return printf("NO\n"), 0;
if (n != 1 && k == 1)
return printf("NO\n"), 0;
if (1ll * (n + 1) * k % 2 != 0)
return printf("NO\n"), 0;
std::vector<int> mn(n + 1), mx(n + 1);
std::iota(mn.begin(), mn.end(), 0);
std::iota(mx.begin(), mx.end(), 0);
std::reverse(mx.begin() + 1, mx.end());
if (k % 2 == 0)
{
std::vector<std::vector<int>> ans{};
ans.reserve(k);
for (int i = 1; i <= k; i += 2)
{
if (mn >= mx)
return printf("NO\n"), 0;
ans.push_back(mn), ans.push_back(mx);
std::next_permutation(mn.begin() + 1, mn.end());
std::prev_permutation(mx.begin() + 1, mx.end());
}
printf("YES\n");
for (int i = 0; i < k; ++i)
for (int j = 1; j <= n; ++j)
printf("%d%c", ans[i][j], " \n"[j == n]);
}
if (k % 2 == 1)
{
std::vector<int> p1(n + 1), p2(n + 1), p3(n + 1);
p1 = mn;
for (int i = 1; i <= (n - 1) / 2; ++i)
p2[(n + 1) / 2 + i] = i;
for (int i = (n + 1) / 2; i <= n; ++i)
p2[i - (n - 1) / 2] = i;
for (int i = 1; i <= (n + 1) / 2; ++i)
p3[i] = n - (i - 1) * 2;
for (int i = (n + 1) / 2 + 1; i <= n; ++i)
p3[i] = (n - 1) - (i - (n + 1) / 2 - 1) * 2;
std::vector<std::vector<int>> ans{p1, p2, p3};
ans.reserve(k);
while (ans.size() < k)
{
if (mn >= mx)
return printf("NO\n"), 0;
if (mn != p1 && mn != p2 && mn != p3 && mx != p1 && mx != p2 && mx != p3)
ans.push_back(mn), ans.push_back(mx);
std::next_permutation(mn.begin() + 1, mn.end());
std::prev_permutation(mx.begin() + 1, mx.end());
}
printf("YES\n");
for (int i = 0; i < k; ++i)
for (int j = 1; j <= n; ++j)
printf("%d%c", ans[i][j], " \n"[j == n]);
}
return 0;
}
|
CF2034F1
题目链接
题意
在第一象限上向右向上行走，$(0,0)$走到$(n,m)$。走一条横边的代价为2，竖边的代价为1。
坐标上有$k$个特殊点，如果经过了一个特殊点，则之前路径的代价翻倍。
问所有路径的总代价是多少。
解法
考虑一条路径经过的特殊点$p_1,p_2,…,p_x$。
$p_i$和$p_{i-1}$这条路径的权值是确定的，但是路径数量有很多，具体来说是$p_{i-1}$不经过其它特殊点走到$p_{i}$的路径数，有经典容斥做法，对于单个起点效率是$O(k^2)$。
因此设$dp[i]$为到特殊点$i$的路径权值总和，枚举之前经过的特殊点$j$，有转移$dp[i]+=2*f(j,i)(dp[j]+C_{x[j]+y[j]}^{y[j]}val(j->i))$
$f(j,i)$的计算对于单个$j$是$O(k^2)$的，因此总复杂为$O(k^3)$
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
|
int Main()
{
int n, m, k;
read(n, m, k);
std::vector<std::pair<int, int>> p(k + 2);
p[0] = {0, 0};
for (int i = 1; i <= k; ++i)
read(p[i].first, p[i].second);
for (int i = 1; i <= k; ++i)
p[i].first = n - p[i].first, p[i].second = m - p[i].second;
p[k + 1] = {n, m};
std::vector dp(k + 2, modint{0});
dp[0] = 0;
Combinatorics<modint> combinatorics(n + m + 1);
std::sort(p.begin(), p.end());
auto ways = [&](int i, int j)
{
auto [x1, y1] = p[i];
auto [x2, y2] = p[j];
int dx = x2 - x1, dy = y2 - y1;
if (dx >= 0 && dy >= 0)
return combinatorics(dx + dy, dx);
return modint{0};
};
auto value = [&](int i, int j)
{
auto [x1, y1] = p[i];
auto [x2, y2] = p[j];
int dx = x2 - x1, dy = y2 - y1;
if (dx >= 0 && dy >= 0)
return 2 * dx + dy;
return 0;
};
auto DP = [&](int x, int y, int s) -> std::vector<modint>
{
std::vector<modint> dp(k + 2, 0);
for (int i = s; i <= k + 1; ++i)
{
dp[i] = ways(s, i);
for (int j = s + 1; j < i; ++j)
dp[i] -= dp[j] * ways(j, i);
}
return dp;
};
for (int i = 0; i <= k; ++i)
{
auto [x, y] = p[i];
auto f = DP(x, y, i);
// for (int j = 0; j <= k + 1; ++j)
// printf("%d%c", f[j], " \n"[j == k + 1]);
for (int j = i + 1; j <= k + 1; ++j)
dp[j] += dp[i] * 2 * f[j] + 2 * f[j] * value(i, j) * ways(0, i);
}
modint all = ways(0, k + 1);
static modint inv2 = 998244354 >> 1;
modint ans = dp[k + 1] * inv2 / all;
printf("%d\n", ans);
return 0;
}
|
CF2034F2
题目链接
题意
在F1的基础上，$k=5000$
解法
F1的容斥解法对F2毫无帮助。
依然假设一条路径上的特殊点$p_1,p_2,…,p_x$。
这条路径的权值要怎么算？
$\sum_{i=1}^x (2(x[p_i]-x[p_{i-1}])+y[p_i]-y[p_{i-1}])\times 2^{x-i + 1}$
因为每个$p_i$被减一次被加一次，提取出来之后是
$\sum_{i=1}^x (2x[p_i]+y[p_i])*2^{x-i}$
对于每个$p_i$，$(2x[p_i]+y[p_i])$这个值是确定的；所以我们要求的就是$p_i$在经过它的每条路径里面，$2^{x-i}$这个系数的和。
接下来有一个很有趣的转化——$2^{x-i}=2^{x-i-1}+…+2^0+1$。
相当于一条路径上，$p_i$的系数，等价于$p_i$后面的点的系数之和+1。
那么对于点$j$，如果它能出现在点$i$的后面，点$j$目前的所有路径给$j$的系数都能给点$i$，并且$j$到$i$的所有路径，每一条都能对应一个$j$的系数和。
这就可以dp了。
$dp[i]$是点$i$的系数，那么有转移$dp[i]+=dp[j]*C_{x[j]-x[i]+y[j]-y[i]}^{x[j]-x[i]}$
最后把每个点的系数和权值贡献给答案。
复杂度$O(k^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
|
int Main()
{
int n, m, k;
read(n, m, k);
std::vector<std::pair<int, int>> p(k + 2);
p[0] = {0, 0};
for (int i = 1; i <= k; ++i)
read(p[i].first, p[i].second);
for (int i = 1; i <= k; ++i)
p[i].first = n - p[i].first, p[i].second = m - p[i].second;
p[k + 1] = {n, m};
std::vector dp(k + 2, modint{0});
// dp[k] = 1;
Combinatorics<modint> combinatorics(n + m + 1);
auto ways = [&](int i, int j)
{
auto [x1, y1] = p[i];
auto [x2, y2] = p[j];
int dx = x2 - x1, dy = y2 - y1;
if (dx >= 0 && dy >= 0)
return combinatorics(dx + dy, dx);
return modint{0};
};
std::sort(p.begin(), p.end());
modint ans = 0;
for (int i = k + 1; i >= 0; --i)
{
dp[i] = ways(i, k + 1);
for (int j = i + 1; j <= k; ++j)
dp[i] += dp[j] * ways(i, j);
ans += dp[i] * (2 * p[i].first + p[i].second) * ways(0, i);
}
modint all = ways(0, k + 1);
ans /= all;
printf("%d\n", ans);
return 0;
}
|
![Featured image of post [VP]Codeforces Round 989 A~F2](/p/vpcodeforces-round-989-a~f2/background_hu_61a0e603618c3f6f.png)