CF2039A
题目链接
题意
找一个最小的$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;
}
|
CF2039B
题目链接
题意
把一个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;
}
|
CF2039C
题目链接
题意
有一个网格，有的点标记了上下左右四个方向，有的点没标记方向；现在问最多能使多少个点成环。
解法
没标记方向的点相当于有上下左右四条待选边；直接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;
}
|
CF2039D
题目链接
题意
有一个值为$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;
}
|
CF2039E
题目链接
题意
构造$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;
}
|
CF2039F1
题目链接
题意
设一个数组$a$的$f(k)$为所有长度为$k$的滑动窗口的最大值的GCD；
如果数组$a$是好的，那么对于所有$k$，$f(k)$都是互不相同的。
现在给定$a$中数值的上限$m$，求问所有长度的数组$a$，好数组的数量。
解法
需要有几个重要的观察。
1.$f(k)$单调递增；这样$k$不超过$O(log_2m)$。因为每次递增都是前一个的倍数。
2.一个合法的数组，长度为$n$。$f(n)$必然是数组最大值；而$f(n-1)$则是两个窗口最大值的GCD，于是必然有一个窗口取到了最大值，另一个窗口的最大值必然不能和全局最大值相等（否则违反了$f(k)$互不相同的原则）。那么全局最大值的合法位置，只有数组两侧；从$f(n-1)$向$f(n-2)$推理，能推理出次大值的位置也是数组两侧；如果我从小到大向数组里扔值，相当于每一次扔都有两个位置填最大值（第一次除外）；于是确定了数组从小到大的取值之后，合法的序列数是$2^{n-1}$个。
现在问题被简化成，选择一个单调递增的数组，其后缀GCD互不相同；反过来变成单调递减，前缀GCD互不相同。
于是有$dp[i][x][d]+=dp[i-1][c][k*d](k\geq 2,gcd(x, kd)=d,c>x)$
从大到小枚举这个$x$可以把第二维滚动掉，有$dp[i][d]+=dp[i-1]k*d$
直接做是$O(m^2log_2^2m)$。
有GCD的判断条件，考虑莫反——$gcd(x/d,k)=1$
$dp[i][d]=\sum_{dj|x,j|k}\mu(j)dp[i-1][kd](k\geq 2)=\sum_{dj|x}mu(j)\sum_{k=1}^{m/dj}dp[i-1][dj*k]-dp[i-1][d]$
实时维护$sum[l][i]=\sum_{j=1}^{m/i}dp[l][i*j]$，可以做到$O(1)$转移。
这样复杂度是$O(mlog_2^3m)$在4s的时限内应该是能过的。
如果将$dp[i][d]$给答案的贡献系数$2^{i-1}$也纳入DP，可以滚动掉一维长度。
$dp[d]+=2*(\sum_{dj|x}mu(j)\sum_{k=1}^{m/dj}dp[djk]-dp[d])$
这样复杂度是$O(mlog_2^2m)$就很轻松。
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
|
int Main()
{
int m;
read(m);
// std::array<std::vector<modint>, 2> dp{};
std::vector<modint> dp(m + 1);
std::vector<modint> sum(m + 1);
for (int x = m; x >= 1; --x)
{
for (int j : fac[x])
{
modint delta = 0;
for (int d : fac[x / j])
delta += mu[d] * sum[d * j];
for (int d : fac[j])
sum[d] += 2 * (delta - dp[j]);
dp[j] += 2 * (delta - dp[j]);
}
dp[x] += 1;
for (int j : fac[x])
sum[j] += 1;
}
modint ans = std::accumulate(dp.begin(), dp.end(), modint{0});
printf("%d\n", ans);
return 0;
}
|
![Featured image of post [VP]CodeTON Round 9 A~F1](/p/vpcodeton-round-9-a~f1/background_hu_61a0e603618c3f6f.png)