Educational Codeforces Round 92 (Rated for Div. 2)

link

A. LCM Problem

构造

给定区间 \([l,r]\) 求 \(2\) 个在里面的数，使得它们的最小公倍数也在区间内，否则输出-1 -1 .

可以知道 \(l, l*2\) 是2个最小的可能组合，只要判断 \(l*2 > r\) 即可.

B. Array Walk

贪心

由于可以折返的步数比较少。我们可以枚举折返的步数。当折返的步数固定为 \(j\) 的时候。有2种情况，

  • \(j\) 步都是折返后又回来。这种情况最远走到了 \([1,k-2j]\)
  • \(j-1\) 步是折返后又回来，最后一步是折返后不回来。这种情况的区间是 \([1,k-2(j-1)-1]\)

可以证明：若折返，则必定是在当前区间的最大两个相邻元素间折返。

那么我们用前缀和的方式求出 \([1,i]\) 的和还有最大相邻元素的位置。那么分情况讨论这两种情况的最大值。最后取个更优的解即可

\(O(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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

typedef long long ll;
ll A[maxn], maxi[maxn], sum[maxn];
int n, m, k, z;

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> k >> z;
        sum[0] = A[0] = 0;
        int mxi = 1; 
        for (int i = 1;i <= n; ++i) {
            cin >> A[i];
            if (i <= k+1) sum[i] = sum[i-1] +  A[i];
            if (i >= 2) {
                if (A[i] + A[i-1] > A[mxi] + A[mxi-1]) mxi = i;
                maxi[i] = mxi;
            }
        }

        z = min(z, k);
        ll ans = sum[1 + min(n-1, k)];
        for (int j = 1;j <= z; ++j) { // 折返 j 次
            int leftk1 = k - (j-1)*2 - 1;
            int leftk2 = k - j*2;
            if (leftk1 >= 1) ans = max(ans, sum[1 + leftk1] + (j-1)*(A[maxi[1+leftk1]] + A[maxi[1+leftk1] - 1]) + A[leftk1]);
            if (leftk2 >= 1) ans = max(ans, sum[1 + leftk2] + j*(A[maxi[1+leftk2]] + A[maxi[1+leftk2] - 1]));
        }
        cout << ans << endl;
    }
    return 0;
}

C. Good String

暴力

  • \(n\) 奇数

    所有数字需相同

  • \(n\) 偶数

    数字必须形如 "abababab" 的形式

由于字符集比较小，直接暴力枚举每一种可能性 \((i,j) \in [9]^{2}\) 然后计算出它的数量。然后再上面两种情况中取最大值。然后答案是 \(|s| - max\) .

D. Segment Intersections

贪心 模拟

First we calculate the initial intersections. Then we calaculate how much we shoud extend to reach \(k\).

E. Calendar Ambiguity

同余 计数

数论题 $$

$$

Codeforces Round #660 (Div. 2)

link

A. Captain Flint and Crew Recruitment

构造

\(6, 10, 14, 15\) 是最小的 fast prime

找三个然后另一个正数是 \(n - (6+10+14)\) 如果这个数冲突了，那么把\(14\) 换成 \(15\) 即可

B. Captain Flint and a Long Voyage

贪心

首先要 \(r\) 最大，因为删掉 \(n\) 位的。首先我们保证位数最多数就可以最大。所有用 \(8(1000), 9(1001)\) 来构造即可. 同时要保证 \(x\) 最小。所以删去的部分用 \(8\) 来填充，其余部分用 \(9\) 来填充. 这里注意 \[\lceil \frac{n}{4}\rceil\] 用8来填充. 因为如果有一个数只删去了后面1-3位，那么\(8,9\)的作用是一样的，所以取最小的.

Codeforces Round #663 (Div 2)

A. Boboniu Likes to Color Balls

数学推导

\(4\) 种球能构成回文的充要条件是：奇数的球最多只有\(1\)个. 而每进行一次操作，球的数量的奇偶性就会翻转。所以能构成回文的条件变成了

  • \(4\)个球奇数数量不多于\(1\)个
  • 否则，若能翻转且则奇数球不少于 \(3\) 个

\(O(1)\)

B. Boboniu Plays Chess

构造

直接构造一组解即可. 比如一直向上走，然后从左往右，从右往左蛇字形走。直到把格子都填满.

\(O(n\cdot m)\)

C. Boboniu and Bit Operations

贪心，二进制枚举

我当时的解法有些复杂，应该有更好的。每次 \(\&\) 的时候都找结果最小的. 一轮之后可以确定出最左边那个数。然后第二轮把已经确定的数排除，每次找 \(\&\) 值最小的，这样可以确定第二个数。这样进行 \(9\) 轮即可确定最终答案。

\(O(n^{2})\)

我看他们都是用枚举来解的，虽然没我快，但是写起来好写，哈哈哈。

二进制枚举解法：https://blog.csdn.net/jziwjxjd/article/details/107971320

Educational Codeforces Round 93 (Rated for Div. 2)

A. Bad Triangle

构造

给定的是不减序列，只要第一个第二个和最后一个比就可以了，如果能构成三角形那么其余的都能构成。否则反例就输出 \(1,2,N\) 即可

B. Substring Removal Game

贪心

可以知道每个人都会拿最大连续的\(1\). 所以对每个连续的\(1\) 排序，然后取偶数项即可。

C. Good Subarrays

数学推导，前缀和，统计对数

这题没做出来，想歪了。要求的是 \(\sum_{i}^{j} a_{i} = j-i+1\) 的个数。把区间和用前缀和的形式表示 \(sum[j] - sum[i-1] = j-i+1\) .然后变形一下 \(sum[j]-j=sum[i-1]-(i-1)\) . 所以要求的是满足 \(sum[i]-i=sum[j]-j\) 相等的 \((i,j)\) 对数. 所以把他们每一个的 \(sum[i]-i\) 插入map 里. 然后遍历map来统计就好了。注意 \(sum[0]\) 也要统计减去，因为统计\([1,1]\) 是对应 \(sum[1]-sum[0]\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h> 
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;
ll T, n, sum[maxn], ans;
int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        sum[0] = ans = 0;
        map<ll, ll> cnt;
        cnt[0] = 1;
        for (int i = 1, x;i <= n; ++i) {
            char c; cin >> c;
            sum[i] = sum[i-1] + c - '0';
            cnt[sum[i] - i]++;
        }
        for (auto k : cnt) ans += k.second * (k.second - 1) / 2;
        cout << ans << endl;
    }
    return 0;
}

D. Colored Rectangles

贪心，类背包DP

可以发现，每次都从最大的和最大的开始匹配可以达到最优解。但每种颜色的棒子数量可能不一样。有可能可以使得棒子匹配数量最多来达到更优解。所以我们可以DP。但是我们要先按大小排序。因为根据贪心，棒子应该应该和大的棒子组合。所以转移方向只能从后方转移过来。 \[ f(i,j,k)=_{max}\begin{cases} f(i-1,j-1,k) + R_{i}\cdot G_j & \text{ if } i>0,j>0 \\ f(i, j-1,k-1) + G_j\cdot B_k & \text{ if } j>0,k>0 & 选\\ f(i-1, j,k-1) + R_i\cdot B_k & \text{ if } i>0, k>0\\ f(i-1,j,k) & \text{ if } i>0 \\ f(i,j-1,k)& \text{ if } j>0 &不选\\ f(i,j,k-1)& \text{ if } k>0 \end{cases} \]

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 5;
typedef long long ll;
int r, g, b;
ll f[maxn][maxn][maxn], R[maxn], G[maxn], B[maxn];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> g >> b;
    for (int i = 1;i <= r; ++i) cin >> R[i];
    for (int i = 1;i <= g; ++i) cin >> G[i];
    for (int i = 1;i <= b; ++i) cin >> B[i];

    sort(R+1, R+r+1, greater<ll>());
    sort(G+1, G+g+1, greater<ll>());
    sort(B+1, B+b+1, greater<ll>());

    for (int i = 0;i <= r; ++i) {
        for (int j = 0;j <= g; ++j) {
            for (int k = 0;k <= b; ++k) {
                if (i && j) f[i][j][k] = max(f[i][j][k], f[i-1][j-1][k] + R[i] * G[j]);
                if (j && k) f[i][j][k] = max(f[i][j][k], f[i][j-1][k-1] + G[j] * B[k]);
                if (i && k) f[i][j][k] = max(f[i][j][k], f[i-1][j][k-1] + R[i] * B[k]);
                if (i) f[i][j][k] = max(f[i][j][k], f[i-1][j][k]);
                if (j) f[i][j][k] = max(f[i][j][k], f[i][j-1][k]);
                if (k) f[i][j][k] = max(f[i][j][k], f[i][j][k-1]);
            }
        }
    }
    cout << f[r][g][b] << endl;
    return 0;
}

Codeforces Global Round 9

https://codeforces.com/contest/1375

A. Sign Flipping

构造

可以让奇数是整数，偶数是复数。这样既可构造一个解

B. Neighbor Grid

构造

可以把所有的格子都变成

2 3 2
3 4 3
3 4 3
2 3 2

的形式。如果不能变成就是不对的。

C. Element Extermination

性质推导

我当时的做法是模拟，从左到右一直消除，如果消除不了了就往后找一个比自己大的消除。如果找不到就不行。正解只需要 \(a_{1} < a_{n}\) 就可以了。

D. Replace by MEX

构造

把它变成 \(1,2,...,n\) 就可以了。用一个堆来维护 MEX ，如果是 \(0\) 的话，与当前仍以一个需要改变的元素交换既可。

Codeforces Global Round 10

官方题解

https://codeforces.com/blog/entry/81565

D. Omkar and Bed Wars

贪心，找规律

可以发现，每连续 \(3\) 个一样的就要修改一次. 分2种情况，第一种全部相同，答案是 \(n/3\) 向上取整。

第二种是有不同的：把所有相同的合并，然后每个\(cnt[i]/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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;
int n, m, T;

char at[maxn];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
        int flag = 1;
        for (int i = 1;i <= n; ++i) {
            cin >> at[i];
            if (at[i] != at[1]) flag = 0;
        }
        
        if (flag) {
            cout << (1 + (n-1)/3) << endl;
            continue;
        }
        
        vector<int> cnt;
        for (int i = 1;i <= n; ++i) {
            if (i != 1 && at[i] == at[i-1]) cnt[cnt.size()-1] ++;
            else cnt.push_back(1);
        }
        if (at[1] == at[n]) {
            cnt[0] += cnt[cnt.size()-1];
            cnt.pop_back();
        }
        ll ans = 0;
        for (int x : cnt) {
            ans += x / 3;
        }
        cout << ans << endl;
    }
    return 0;
}

Codeforces Round #665 (Div. 2)

官方题解

https://codeforces.com/blog/entry/81700

D. Maximum Distributed Tree

考虑元素的贡献，组合数学，统计个数

要使得 \[ \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} f(i,j) \] 最大。直接算肯定不行。考虑每条边对答案的贡献。 设 \(a\) 和 \(b\) 是边 \(e\) 的两个阶段， \(a\) 是 \(b\) 的父亲。如果 \(num[b]\) 是 \(b\) 的子树节点数目。那么子树的节点到其他节点一定会经过 \(e\) 这条边。所以它会被计算 \(num[b]\cdot (n-num[b])\) 次。我们把所有边都算出这个值，记为 \(val[i]\) 那么考虑贪心，把最大的值给次数多的边，小的值给次数少的边，即可。

Educational Codeforces Round 94 (Rated for Div. 2)

B. RPG Protagonist

枚举，贪心

枚举第一个人装多少个重量最小的装备。然后第二个人装剩下的知道装不下为止。然后取每次枚举的最大值

C. Binary String Reconstruction

从简单的点切入, 判断题

出现 \(1\) 有很多种情况，出现\(0\) 只有\(1\)种情况，就是左边和右边同时为 \(0\) . 所以先让 \(0\) 满足，其余的都设为 \(1\) 然后看 \(1\) 是不是冲突.

D. Zigzags

枚举，前缀和

我们可以用前缀和表示某个区间有多少个 \(i\) 出现。所以我们可以枚举中间的两个下标，确定 \(y,x\)，统计前面出现了多少个 \(x\) ，后面出现了多少个 \(y\).

Educational Codeforces Round 95 (Rated for Div. 2)

B. Negative Prefixes

前缀和, 贪心

发现：看某个 \(k\) 是不是成立，我们只需要 \(k+1\) 后面的前缀和都非负就好了，而 \(k\) 前面的顺序无关

而且发现：如果 \(k = n\) 那么整个数组的顺序就都无所谓了。如果答案想要优化到 \(n-1\) 那么可以把大的值都往前面放，使得整个前面 \(n-1\) 不要太小。所以就可以推出，如果把数组逆序放置，就可以使得 \(k\) 尽量靠前。

D. Trash Problem

平衡树

首先考虑： 如果把所有的都并成2堆，答案应该怎样计算？可能还有点复杂，那么先考虑如果一个区间\([x_{1},x_{n}]\)的垃圾要合并到区间中的某一个点 \(x\) . 那么代价是 \[ x - x_{1} + x_{n} - x \\ = x_{n} - x_{1} \] 再考虑之前的问题，所以所有的合并成两堆，从中间的 \(x_i\) 为分割点的话，可以写出 \[ x_i - x_1 + x_n - x_{i+1} \\ = x_n - x_1 - (x_{i+1} - x_i) \] 所以就是最后的点- 最开始的点，减去 某个间距。要让答案最小就是让间距最大。所以我们可以维护一个multiset来维护间距。每次取尾元素即可取到最大值。维护的时候还需要一个multiset来维护每个点的坐标（否则修改的时候不好操作，需要访问前驱后继）

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;

int n, m, q;
int X[maxn];
multiset<int> c;
multiset<int> gap;

int curAns() {
    if (c.size() < 3) return 0;
    return *c.rbegin() - *c.begin() - *gap.rbegin();
}

void add(int v) {
    if (c.empty()) c.insert(v);   
    else if (c.find(v) == c.end()) {
        if (v > *c.rbegin()) {
            gap.insert(v - *c.rbegin());
            c.insert(v);
            return;
        } else if (v < *c.begin()) {
            gap.insert(*c.begin() - v);
            c.insert(v);
            return;
        }
        auto x = *(--c.lower_bound(v));
        auto y = *c.upper_bound(v);
        gap.erase(gap.find(y - x));
        gap.insert(v - x); gap.insert(y - v);
        c.insert(v);
    } else c.insert(v);
}

void del(int v) {
    if (c.count(v) == 1) {
        if (v == *c.begin()) {
            c.erase(v);
            if (c.empty()) return;
            auto y = *c.upper_bound(v);
            gap.erase(gap.find(y - v));
            return;
        } else if (v == *c.rbegin()) {
            c.erase(v);
            if (c.empty()) return;
            auto x = *(--c.lower_bound(v));
            gap.erase(gap.find(v - x));
            return;
        }
        c.erase(v);
        auto x = *(--c.lower_bound(v));
        auto y = *c.upper_bound(v);
        gap.erase(gap.find(v - x));
        gap.erase(gap.find(y - v));
        gap.insert(y - x);
    } else c.erase(c.find(v));
}

int main() {
    freopen("d.txt","r",stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
  
    for (int i = 1;i <= n; ++i) {
        cin >> X[i];
        c.insert(X[i]);
    }
    sort(X + 1, X + n + 1);
    for (int i = 2;i <= n; ++i) {
        gap.insert(X[i] - X[i-1]);
    }

    cout << curAns() << endl;

    for (int i = 1, op, v;i <= q; ++i) {
        cin >> op >> v;
        if (op) {
            add(v);
        } else {
            del(v);
        }
        cout << curAns() << endl;
    }
    return 0;
}

Codeforces Round #671 (Div. 2)

A. Digit Game

判断题，性质推导

发现，总有一个人会删完所有自己的数，然后最后剩一个数。所以只要看每个人的序列里面如果是自己剩数，能不能让自己胜利就好了

B. Stairs

动态规划递推

找到递推公式就可以了

C. Killjoy

平均分配，性质推导

从简单的情况开始分离讨论，如果所有账户的rating都一样，那么0次

如果和的平均值和初始值相等，1次

如果有一个账号感染了，那么可以把其他账号都改成初始值，改变的数值全挤到感染的账户上保证和不变，就可以都感染上了，2次

D2. Sage's Birthday (hard version)

二分，排序，贪心

考虑，什么样的可以作为答案：自己比左右两边小。那么根据贪心，最好作为答案的数是最小的那些个数。假设我们选 \(k\) 个作为答案，那么需要\(k+1\)个比他们大的来包围他们. 因为如果\(k\) 可行，那么\(k+1\) 必然可行，所以我们可以用二分查找来枚举

Codeforces Round #670 (Div. 2)

A. Subset Mex

枚举

可以从0开始枚举，只要出现次数>=2 就两个都可以，=1是一个可以=0就结束了

B. Maximum Product

分类讨论

先分类讨论，然后贪心即可

树

发现：如果出现两个中心点\(x,y\)。 那么一个点\(x\)的子树大小 \(size(x)= \frac{n}{2}\) 否则就只要1个点。所以找到这样的店，然后把父亲的一个儿子拉到自己这里即可。

D. Three Sequences

差分

还没做出来

Codeforces Round #668 (Div. 2)

A. Permutation Forgery

构造

发现倒着输出就好了

B. Array Cancellation

模拟

发现，只要左边的正数给右边的负数，否则就得记录到答案上。所以维护一下从 \(1\) 到当前 \(i\) 的正数和，然后一路算下来就好了。

C. Balanced Bitstring

字符串

首先，如果一个串是平衡的，那么子串都平衡。所以一个子串和他相邻的要平衡，那么减少的字符要和增加的字符一样，于是发现 \(i \ mod \ k\) 的位置上的数都是相同的。

D. Tree Tag

分类讨论

有几钟情况，Alice 是肯定赢的

Codeforces Round #672 (Div. 2)

D. Rescue Nibel!

排列组合，逆元，组合数，维护

很好的一道题！我们要在计数的时候不记重复。考虑对于若 \(k\) 个线段相交后，它必然是一个线段。左端点必然是左端点最靠右的哪一个线段的左端点。考虑 \(sum[i]\) 是 \(i\) 这个点经过的总线段数。而这个线段(它的左端点与相交线段的左端点重合)的答案必然只与 \(sum[i]\) 其中的线段相交。假设对于一个点来说，\(cnt[i]\) 是左端点从 \(i\) 开始的线段。那么 \(i\) 对于答案的贡献就是 \[ {sum[i] \choose k} - {sum[i]-cnt[i] \choose k} \] 因为只统计与 \(i\) 开始的节点相关的答案，减去与当前节点不相干的答案(因为会在其他的\(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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5;
typedef long long ll;
const int MOD = 998244353;
ll n, m, ans, k;
ll f[maxn], rf[maxn], inv[maxn];
inline ll add(ll a, ll b) {
    return ((a + b) % MOD + MOD) % MOD;
}
inline ll mul(ll a, ll b) {
    return (a * b) % MOD;
}
ll c(int n, int k) {
    return (k < 0 || k > n) ? 0 : mul(f[n], mul(rf[n-k], rf[k]));
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    vector<pair<int, int>> A, B;
    map<int, int> cnt, sum;

    inv[1] = 1;
    for(int i = 2; i <= n; ++ i) {
        inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
    }
    f[0] = rf[0] = 1;
    for (int i = 1;i <= n; ++i) {
        f[i] = mul(f[i-1], i);
        rf[i] = mul(rf[i-1], inv[i]);
    }
    for (int i = 1;i <= n; ++i) {
        int l,r; cin >> l >> r;
        A.push_back({l, -1}); A.push_back({r, 1});
        cnt[l] ++;
    }   
    sort(A.begin(), A.end());
    int num = 0;
    for (auto x : A) {
        if (x.second == -1) {
            num ++;
            sum[x.first] = max(sum[x.first], num);
        }  else {
            num --;
        }
    }
    for (auto x : sum) {
        ans = add(ans, add( c(x.second, k) , -c(x.second - cnt[x.first], k)));
    }
    cout << ans << endl;
    return 0;
}