CF2030A
题目链接
题意
给出一个数组$a$，调整它的顺序，使得它每个前缀中的最大值减最小值的和最大
解法
不难发现只要把前两个元素调整成整个数组的最大值和最小值就可以
1
2
3
4
5
6
7
8
9
10
11
|
int Main()
{
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
int mx = *std::max_element(a.begin() + 1, a.end()), mn = *std::min_element(a.begin() + 1, a.end());
std::cout << (mx - mn) * (n - 1) << std::endl;
return 0;
}
|
CF2030B
题目链接
题意
构造一个01串，使得只含0的非空子序列和包含至少1个1的非空子序列的差值绝对值最小
解法
题目所求的两个数的差，实际上加起来就是非空子序列总数$2^n-1$。那么显然最小值就是1，即只含0的非空子序列是$2^{n-1}-1$，所以0的个数有$n-1$个。
1
2
3
4
5
6
7
8
9
10
|
int Main()
{
int n;
std::cin >> n;
for (int i = 1; i < n; ++i)
putchar('0');
putchar('1');
putchar('\n');
return 0;
}
|
CF2030C
题目链接
题意
有$n$个布尔值常量，$A$和$B$轮流在常量中间放置操作符$and$和$or$。$and$的优先级更大。
$A$希望最终结果是true，$B$希望最终结果是false。请问最终谁获胜。
解法
$A$的决策是尽量放$or$，$B$的决策是尽量在0和1之间放$and$。
假设$s[0]$是1，因为$A$是先手，那么$A$在$s[0]$和$s[1]$中间放一个$or$，这样无论$B$怎么放，运算到最后一步这第一个$or$的左边总是1。
对于$s[n-1]$是1的情况是一样的。
进一步，如果字符串中有两个1，先手在中间放一个$or$的话，后手想获胜必须用$and$消灭这两个1。然而后手在第一次操作只能最多消灭一个1，这样先手在另一边继续放一个$or$，形成$or\ 1\ or\ 1$的局面；于是有一个1被保护住，那么最终答案一定是1。
综上，先手必胜当且仅当出现两个连续的1，或者开头结尾是1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int Main()
{
int n;
std::string s;
std::cin >> n;
std::cin >> s;
for (int i = 1; i < n; i++)
if (s[i - 1] == '1' && s[i] == '1')
return printf("YES\n"), 0;
if (s[0] == '1' || s[n - 1] == '1')
return printf("YES\n"), 0;
printf("NO\n");
return 0;
}
|
CF2030D
题目链接
题意
给出一个排列$p$和一个由$LR$组成的字符串$s$。
如果$s[i]=L$，你可以交换$p[i]$和$p[i-1]$;
如果$s[i]=R$，你可以交换$p[i]$和$p[i+1]$;
现在给出$q$个操作，每次修改一个$s[i]$，问操作后整个排列是否能够通过上述交换方法来排序。
解法
考虑面对一个字符串$s$的时候如何能够排好序。给排列排序的时候往往思考怎么交换。因为$p[i]$最终的位置是确定的。一次交换相当于断掉置换环上一条边。
假设我们要交换两个位置$i<j$上的数，那么需要二者通过字符串指引的方向，能在中间相遇即可。即应该是$RRRRRLLLLL$这样的字符串。
如果字符串出现了$LR$，相当于方向在中间断掉了，两个数就不能交换。
因此需要判定$i$和$p[i]$是不是能交换，即$[min(i, p[i]), max(i, p[i])]$区间里是不是有$LR$这样的字符。
具体地可以将影响交换的$LR$记录下来存在一个$set$里，每次修改的时候实际上改了两个位置，简单判断一下即可。
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
|
char s[200005];
int Main()
{
int n, q;
scanf("%d%d", &n, &q);
std::vector<int> p(n + 1);
for (int i = 1; i <= n; ++i)
scanf("%d", &p[i]);
scanf("%s", s + 1);
std::vector<int> vis(n + 1);
for (int i = 1; i <= n; ++i)
{
int l = std::min(i, p[i]), r = std::max(i, p[i]);
vis[l]++, vis[r]--;
}
for (int i = 1; i <= n; ++i)
vis[i] += vis[i - 1];
std::set<int> invalid{};
for (int i = 1; i < n; ++i)
if (s[i] == 'L' && s[i + 1] == 'R' && vis[i] > 0)
invalid.insert(i);
while (q--)
{
int x;
scanf("%d", &x);
s[x] = (s[x] == 'L') ? 'R' : 'L';
if (vis[x])
{
if (s[x + 1] == 'R' && s[x] == 'L')
invalid.insert(x);
else
invalid.erase(x);
}
if (vis[x - 1])
{
if (s[x] == 'R' && s[x - 1] == 'L')
invalid.insert(x - 1);
else
invalid.erase(x - 1);
}
if (invalid.empty())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
|
CF2030E
题目链接
题意
假设数组$b$的分数是把$b$切分成若干个非空多重集，求这些多重集$MEX$和的最大值。
现在给出一个长度为$n$的数组$a$，求它的所有非空子序列的分数和。
解法
首先想面对一个数组$b$怎么计算分数。
先把0都拿出来，假设有$k_0$个0，分成$k_0$个集合，那么现在至少得到了$k_0$分。
接下来把1都拿出来，假设有$k_1$个1，分到原$k_0$个集合中去。如果$k_1<k_0$，那么我们多了$k_1$分；否则多了$k_0$分。即多了$min(k_0,k_1)$分。
这样一看，可以按数字分层计算分数，每多一层，分数会多一个层内的数的前缀最小值。
我的做法比较麻烦，当时做的时候有点上头了。
设$score[i][j]$为前$i$层，且前$i$层，层内数最小值是$j$的分数和。
看起来是$O(n^2)$的状态，但是实际上第$i$层不会放超过$cnt[i]$个数，$cnt[i]$为$a$数组中值为$i$的数的个数。因此状态是$O(n)$的。
由于是按层算分数，那么第$i$层的分数为$j$*合法的方案数。设这个方案数为$dp[i][j]$。
先考虑算$dp[i][j]$。
有两种转移，第一种是最小值出现在第$i$层，那么就是$dp[i][j]=(\sum_{x=j+1} dp[i-1][x])\times C_{cnt[i]}^j$;第二种是最小值出现在前$i-1$层，那么$dp[i][j]+=(\sum_{x=j+1}C_{cnt[i]}^x)\times dp[i-1][j]$。后缀和简单优化一下就行了。
接下来算$score[i][j]$，它是第$i$层的方案数乘前$i-1$层分数和第$i$层分数以及前i层总方案数。是一个差不多的转移。
然后$i$枚举到整个数组的$mex$之后，后面的数可以出现在任意一个子序列里，还要再乘一个2的幂次。
实际上每一层的分数都乘上后面2的剩下的数的幂次就把这一层对后面所有方案的贡献都累加了。只需要做一个$dp[i][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
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
|
int Main()
{
int n;
read(n);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
std::sort(a.begin() + 1, a.end());
int mex = 0;
for (int i = 1; i <= n; ++i)
if (mex == a[i])
mex++;
std::vector<int> cnt(n + 1);
for (int i = 1; i <= n; ++i)
cnt[a[i]]++;
modint ans = 0;
Combinatorics<modint> combinatorics(n + 1);
std::vector sum(n + 1, std::vector<modint>{});
for (int i = 0; i <= mex; ++i)
{
sum[i].assign(cnt[i] + 1, 0);
sum[i][0] = 1;
for (int j = 1; j <= cnt[i]; ++j)
sum[i][j] = sum[i][j - 1] + combinatorics(cnt[i], j);
}
std::vector dp(mex + 1, std::vector<modint>{});
std::vector sumdp(mex + 1, std::vector<modint>{});
std::vector<modint> score(n + 1);
auto get_sum = [&](int i, int l, int r) -> modint
{
r = std::min(cnt[i], r);
l = std::min(cnt[i], l);
return sumdp[i][r] - sumdp[i][l];
};
int rem = n;
for (int i = 0; i <= mex; ++i)
{
dp[i].assign(cnt[i] + 1, 0);
sumdp[i].assign(cnt[i] + 1, 0);
if (i == 0)
{
for (int j = 0; j <= cnt[i]; ++j)
dp[i][j] = combinatorics(cnt[i], j);
}
else
{
dp[i][0] = dp[i - 1][0] * sum[i][cnt[i]];
for (int j = 1; j <= std::min(cnt[i - 1], cnt[i]); ++j)
dp[i][j] = dp[i - 1][j] * (sum[i][cnt[i]] - sum[i][j - 1]);
for (int j = 0; j <= cnt[i]; ++j)
dp[i][j] += get_sum(i - 1, j, cnt[i - 1]) * combinatorics(cnt[i], j);
}
modint tmp = 0;
if (i)
{
for (int j = cnt[i - 1]; j > cnt[i]; --j)
{
tmp += score[j];
score[j] = 0;
}
}
for (int j = cnt[i]; j >= 1; --j)
{
tmp += score[j];
score[j] = (tmp - score[j]) * combinatorics(cnt[i], j) + score[j] * (sum[i][cnt[i]] - sum[i][j - 1]) + dp[i][j] * j;
}
score[0] = tmp + score[0] * sum[i][cnt[i]];
sumdp[i][0] = dp[i][0];
for (int j = 1; j <= cnt[i]; ++j)
sumdp[i][j] = sumdp[i][j - 1] + dp[i][j];
rem -= cnt[i];
}
ans = score[0];
ans *= modint(2).pow(rem);
printf("%d\n", ans);
return 0;
}
|
CF2030F
题目链接
题意
玩过祖玛的就知道这其实就是祖玛。
相邻同色就能消灭，然后合并前后两段，依次做直到完全消除；
现在问你某个区间是不是可完全消除的。
解法
这题其实跟我做过的另一道题有点像。
首先发现消除是有严格的先后顺序的。那么可行与否可以通过有向图的角度去思考
假设$i$前面和它同色的是$j$，那么$[j+1,i-1]$都要先于$i，j$消除，可以连一条有向边。这个图成环的时候就不可行。
什么时候成环？$i$和$j$连到$[j+1,i-1]$，而$j+1\leq p \leq i-1$又连到了$j$上。假设$p$前面同色是$q$，说明$[i, j]$和$[p,q]$相交了。
称相邻同色之间构成的区间为同色区间，那么问题转变为给定查询区间，是否存在同色区间之间相交。
由于没有修改操作，可以考虑按查询区间的某一个端点预处理一个结果。
具体来说，可消除的区间具有单调性，假设以$r$为端点的极大可消除的区间左端点是$l$，那么$j>l$，$[j, r]$可消除；$j<l$, $[j, r]$不可消除；并且$l$对于$r$是单调递增的。
那么可以考虑预处理出以每个$r$为右端点的最右可行左端点。从前往后枚举$r$，有点类似于扫描线一样在线段树上加入一个以$r$为右端点的区间左端点$pre[r]$；同时可行左端点向右滑动，当$[l, r]$中的左端点都大于$pre[r]$的时候停。
需要注意的是相同颜色的区间可以交在同一个点上，因此这里判定区间相交指的是区间交集大于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
|
int Main()
{
int n, q;
read(n, q);
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
read(a[i]);
std::vector<int> pre(n + 1), last(n + 1);
std::vector<int> suf(n + 1);
for (int i = 1; i <= n; ++i)
{
pre[i] = last[a[i]];
last[a[i]] = i;
}
for (int i = 1; i <= n; ++i)
if (pre[i] == 0)
pre[i] = i;
std::vector<int> right_most(n + 1);
struct Max
{
int operator()(int a, int b) const
{
return std::max(a, b);
}
};
SegmentTree<int, Max> segment_tree(n + 1);
segment_tree.modify(pre[1], 1);
right_most[1] = 1;
for (int i = 2; i <= n; ++i)
{
right_most[i] = right_most[i - 1];
for (int &l = right_most[i]; l < pre[i]; l++)
{
auto res = segment_tree.query(l, pre[i] - 1);
if (res <= pre[i])
break;
}
// printf("%d\n", right_most[i]);
if (pre[i] != 0)
segment_tree.modify(pre[i], i);
}
std::vector<int> ans(q + 1);
for (int i = 1; i <= q; ++i)
{
int l, r;
read(l, r);
if (l >= right_most[r])
ans[i] = true;
else
ans[i] = false;
}
for (int i = 1; i <= q; ++i)
printf("%s\n", ans[i] ? "YES" : "NO");
return 0;
}
|
CF2030G1
题目链接
题意
给出若干个区间，你可以选择以1的代价向右或者向左拉长一个区间，拉长的长度为1。
这些区间的分数为最小的使得所有区间都包含同一个点的代价。
现在给出$n$个区间，问所有子序列的分数和。
解法
又是这种，和E差不多的思路。先考虑给定若干区间怎么算分数。
这里我的做法不太一样。
考虑一个长度为1的小线段能为答案提供多少贡献。
这个小线段假设左边有$l$个区间不包含它，右边有$r$个区间不包含它。因为终究是要包含到这个小线段，那么根据贪心思想，肯定是$min(l, r)$个区间向这个小线段的方向扩展。
那么一个长度为1的小线段提供的贡献就是$min(l,r)$。把数轴上所有小线段枚举一遍就行了。
接下来考虑原问题。
发现一个小线段的代价跟左边右边不包含它的区间数量有关。考虑枚举左右不包含它的数量$l, r$。设左右不包含它的区间总数分别为$L, R$。
那么代价就是$min(l,r)\times C_L^l\times C_R^r\times 2^{n-L-R}$。
现在枚举小线段的位置$i$，左右的$l,r$，复杂度是$O(n^3)$。
考虑把$min(l,r)$拆开，变成两个式子：
$2^{n-L-R}(\sum_{l=0}^L l\times C_L^l \sum_{r=l+1}^R C_R^r) $
$2^{n-L-R}(\sum_{l=0}^L C_L^l \sum_{r=0}^l r\times C_R^r) $
预处理组合数前缀和就行了。
G2从这种做法很难优化；看来还是得用中位数的思路直接找最优的那个被包含的点，但是难点在于处理端点重合的部分。
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
|
int Main()
{
int n;
read(n);
Combinatorics<modint> combinatorics(n + 1);
std::vector<std::pair<int, int>> interval(n + 1);
for (int i = 1; i <= n; ++i)
{
auto &[l, r] = interval[i];
read(l, r);
}
std::vector<int> cntl(n + 1), cntr(n + 2);
for (int i = 1; i <= n; ++i)
{
auto [l, r] = interval[i];
cntl[r]++, cntr[l]++;
}
for (int i = 1; i <= n; ++i)
cntl[i] += cntl[i - 1];
for (int i = n; i >= 1; --i)
cntr[i] += cntr[i + 1];
std::vector<int> incl(n + 1);
for (int i = 1; i <= n; ++i)
{
auto [l, r] = interval[i];
incl[l]++;
incl[r]--;
}
for (int i = 1; i <= n; ++i)
incl[i] += incl[i - 1];
std::vector<modint> bi(n + 1, 1);
for (int i = 1; i <= n; ++i)
bi[i] = bi[i - 1] * 2;
std::vector sum1(n + 1, std::vector<modint>(n + 1)), sum2(n + 1, std::vector<modint>(n + 1));
for (int i = 0; i <= n; ++i)
{
sum1[i][0] = 1, sum2[i][0] = 0;
for (int j = 1; j <= i; ++j)
{
sum1[i][j] = sum1[i][j - 1] + combinatorics(i, j);
sum2[i][j] = sum2[i][j - 1] + combinatorics(i, j) * j;
}
for (int j = i + 1; j <= n; ++j)
sum1[i][j] = sum1[i][j - 1], sum2[i][j] = sum2[i][j - 1];
}
modint ans = 0;
for (int i = 1; i <= n - 1; ++i)
{
modint sum = 0;
for (int l = 0; l <= cntl[i]; ++l)
{
sum += l * combinatorics(cntl[i], l) * (bi[cntr[i + 1]] - sum1[cntr[i + 1]][l]);
sum += combinatorics(cntl[i], l) * sum2[cntr[i + 1]][l];
// for (int r = 0; r <= l; ++r)
// sum += combinatorics(cntl[i], l) * combinatorics(cntr[i + 1], r) * r;
}
sum *= bi[incl[i]];
ans += sum;
}
printf("%d\n", ans);
return 0;
}
|
![Featured image of post [VP]Codeforces Round 979 A~G1](/p/vpcodeforces-round-979-a~g1/background_hu_61a0e603618c3f6f.png)