2024 东北四省 K / CC 网络赛模拟 C. Tasks

Link

[[…/contests/2024-09-07-2024 CCPC 网络赛热身赛|2024-09-07-2024 CCPC 网络赛热身赛]]

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 n;
cin >> n;

using node = struct { int l, r, b, id; };
vector<node> a(n);
for (int i = 0; i < n; ++i) {
	cin >> a[i].l >> a[i].b;
	a[i].id = i;
}
sort(a.begin(), a.end(), [&](node a, node b) {
	return a.l == b.l ? a.b < b.b : a.l < b.l;
});

vector<int> num(n), lst(n, -1);
for (int i = 0; i < n; ++i) {
	num[a[i].b] = i;
	if (a[i].b) lst[i] = num[a[i].b - 1];
}

bool ok = 1;
vector<vector<int>> vec(n + 1);
for (int i = n - 1; i >= 0; --i) {
	if (!vec[a[i].b].empty() && a[vec[a[i].b].back()].l == a[i].l) ok = 0;
	vec[a[i].b].push_back(i);
}

int noww = 1e6;
for (auto& j : vec[0]) {
	a[j].r = noww--;
	if (a[j].l > a[j].r) ok = 0;
}

for (int i = 1; i <= n; ++i) {
	int noww = 1e6;
	for (auto& j : vec[i]) {
		if (lst[j] == -1) ok = 0;
		noww = min(noww, a[lst[j]].r);
		a[j].r = noww--;
		if (a[j].r == a[lst[j]].r && a[j].l == a[lst[j]].l) {
			a[j].r = noww--;
		}
		if (a[j].l > a[j].r) ok = 0;
	}
}

sort(a.begin(), a.end(), [&](node a, node b) {
	return a.id < b.id;
});

if (!ok) printf("-1\n");
else for (int i = 0; i < n; ++i) {
	printf("%d\n", a[i].r);
}

2024 牛客多校 8J - Haitang and Triangle

[[…/contests/2024牛客多校/2024-08-08：2024牛客暑期多校训练营8|2024-08-08：2024牛客暑期多校训练营8]]

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
#include <cstdio>
using ll = long long;
constexpr int N = 5e5 + 8;
inline ll read() {
    ll S = 0, C = 0; char Y = getchar();
    while (Y > 57 || Y < 48) C |= Y == 45, Y = getchar();
    while (Y <= 57 && Y >= 48) S = (S << 3) + (S << 1) + Y - 48, Y = getchar();
    return C ? -S : S;
}

int a[N];

void eachT() {
    int n = read(), m = read();
    int t = n - m;

    if (t == 2) {
        printf("-1\n");
        return;
    }

    if (t == 3) {
        a[1] = 3;
        a[2] = 2;
        a[3] = 1;
    }
    else if (t % 3) {
        int now = t;
        for (int i = 1; i <= t; i += 3) a[i] = now--;
        for (int i = 2; i <= t; i += 3) a[i] = now--;
        for (int i = 3; i <= t; i += 3) a[i] = now--;
    }
    else {
        int now = t;
        for (int i = 1; i <= t; i += 3) a[i] = now--;
        a[t] = now--;
        for (int i = 2; i <= t - 2; i += 3) a[i] = now--;
        for (int i = 3; i <= t - 2; i += 3) a[i] = now--;
        a[t - 1] = now--;
    }

    for (int i = n; i > t; --i) {
        printf("%d ", i);
    }
    for (int i = 1; i <= t; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main() {
    for (int T = read(); T--; eachT());
    return 0;
}

2024 牛客多校 3D - Dominoes!

[[…/contests/2024牛客多校/2024-07-23：2024牛客暑期多校训练营3#D - Dominoes!|2024-07-23：2024牛客暑期多校训练营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
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

void out(const vector<pii>& vec) {
    for (const auto& [f, s] : vec) {
        cout << f << ' ' << s << '\n';
    }
}

int main() {
    int n;
    cin >> n;
    vector<pii> a(n);

    // 统计same
    map<int, int> same;
    for (auto& [f, s] : a) {
        cin >> f >> s;
        if (f == s) same[f] += 1;
        else if (f < s) swap(f, s);  // 保证first大
    }

    // same数量最多的当wall
    int wall = 0, wallnum = 0;
    for (auto& [k, num] : same) {
        if (num > wallnum) {
            wall = k;
            wallnum = num;
        }
    }

    /// 赛时推了个公式 但没必要
    // if (wallnum > n - wallnum - son[wall] + 1) {
    //     cout << "No" << '\n';
    //     return 0;
    // }

    // 统计
    vector<vector<pii> > gap(wallnum);   // 墙中间
    vector<pii> diffdiff, diffwall;
    for (auto& it : a) {
        auto& [f, s] = it;
        if (f == s) continue;
        else if (f == wall) swap(f, s), diffwall.push_back(it);  // 保证后面是墙
        else if (s == wall) diffwall.push_back(it);
        else diffdiff.push_back(it);  // 不一样的
    }
    sort(diffdiff.begin(), diffdiff.end());

    // 先填 0,1,...,wallnum-1
    int cnt = 1;
    same.erase(wall);  // wall不填
    while (!same.empty()) {
        auto& [k, num] = *same.begin();
        while (num--) {  // 一直填直到填完
            gap[(cnt++) % wallnum].push_back({ k, k });
        }
        same.erase(k);
    }
    while (cnt < wallnum) {   // 不够
        if (diffdiff.empty()) {   // 还不够
            cout << "No" << '\n';
            return 0;
        }
        gap[cnt++].push_back(diffdiff.back());
        diffdiff.pop_back();
    }

    // 输出
    cout << "Yes" << '\n';
    for (auto& vec : gap) {
        out(vec);
        cout << wall << ' ' << wall << '\n';
    }
    out(diffwall);
    out(diffdiff);

    return 0;
}

2024 杭电多校 2001 - 鸡爪

[[…/contests/2024杭电多校/2024-07-22：2024“钉耙编程”中国大学生算法设计超级联赛（2）|2024-07-22：2024“钉耙编程”中国大学生算法设计超级联赛（2）]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int c1 = 1, c2 = 2;
        int maxx = (n / 3) + 4;
        int flag = n % 3;
        while (n--) {
            if (c1 + c2 > maxx && flag --<= 0) {
                c1++;
                c2 = c1 + 1;
            }
            cout << c1 << " " << c2 << endl;
            c2++;
        }
    }
    return 0;
}

2024 牛客多校 2A - Floor Tiles

[[…/contests/2024牛客多校/2024-07-18：2024牛客暑期多校训练营2#A. Floor Tiles|2024-07-18：2024牛客暑期多校训练营2]]

Description

有AB两种类型的瓷砖如下：

![[…/data/img/Pasted image 20240718172445.png]]
拼凑起来会得到弧：
![[…/data/img/Pasted image 20240718172711.png]]
T组测试用例中每行给出N，M，分别代表需要铺瓷砖的地板大小，并给出需要的弧数K。
接下来给出x,y,tx,y,t ,代表坐标(x,y)(x,y) 的瓷砖一定是tt 。
对每个测试样例，如果满足题意的情形存在则输出"YES"并给出一种存在的情况，否则输出”NO“。

Input

1
2
3
4
5
2
2 4 6
1 1 A
2 4 15
1 1 A

Output

1
2
3
4
Yes
ABAB
ABAA
No

Code

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
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
using ll = long long;
const int N = 1000;
char a[N][N];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k, x, y; char op;
        cin >> n >> m >> k;
        cin >> x >> y >> op;
        int ans = m + n;
        int flag = ((x & 1) ^ (y & 1));

        // 初始为ABAB
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (((i & 1) ^ (j & 1)) == flag) {
                    a[i][j] = op;
                }
                else {
                    a[i][j] = 'A' + 'B' - op;
                }
            }
        }

        // 从最大值开始
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (ans == k) {
                    a[i][j] = op;
                }
                else if (a[i - 1][j - 1] == 'A' && a[i - 1][j] == 'B' && a[i][j - 1] == 'B' && a[i][j] == 'A') {
                    ans++;
                }
            }
        }


        if (ans == k) {
            cout << "Yes" << endl;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    cout << a[i][j];
                }
                cout << endl;
            }
        }
        else cout << "No" << endl;
    }
    
    return 0;
}

800

Q.\Large\mathcal{Q}. 给定nn 和kk，找出长度最小的字符串ss，使得所有长度为nn 的用前kk 个小写英文字母组成的字符串都是ss 的子串。(CF1925A. We Got Everything Covered!)

A.\Large\mathcal{A}.s=abc…xabc…x…abc…xs=abc\dots xabc\dots x\dots abc\dots x

Q.\Large\mathcal{Q}. 规定一个数列的求和方法，从前向后遍历，若这一项大于前一项，按常规方式求和，否则将和清零。在 1 到 n 的全排列中找出和的最大值。(VJwin4D, CF1728B. Best Permutation)

A.\Large\mathcal{A}.{If n=2k:2k−2, 2k−3, …, 3, 2, 1, 2k−1, 2kIf n=2k+1:1, 2k−1, 2k−2, 2k−3, …, 3, 2, 2k, 2k+1\begin{cases}\text{If }n=2k: & 2k-2,~ 2k-3,~ \dots,~ 3,~ 2,~ 1,~ 2k-1,~ 2k \\ \text{If }n=2k+1: & 1,~ 2k-1,~ 2k-2,~ 2k-3,~ \dots,~ 3,~ 2,~ 2k,~ 2k+1\end{cases}

900

Q.\Large\mathcal{Q}. 给定正整数数列{an}\lbrace a_n \rbrace，构造{bn}\lbrace b_n \rbrace，满足ai≠bi(1⩽i⩽n)a_i \ne b_i(1\leqslant i\leqslant n)，∑i=1nai=∑i=1nbi\sum\limits_{i=1}^{n} a_i = \sum\limits_{i=1}^{n} b_i。(VJwin14J, CF1856B. Good Arrays)

A.\Large\mathcal{A}. 如果某个元素是 1，那至少给它增加 1，我们只需要看非 1 的元素减少的量够不够给它增加 1，也就是它们的总和是否大于 n，再特判 n=1 的情形即可。

1
2
3
4
5
6
ll n = read(), sum = 0;
for (int i = 0; i < n; ++i) {
    int x = read();
    if (x > 1) sum += x;
}
printf("%s\n", n > 1 && sum >= n ? "Yes" : "No");

另一种（或许更容易理解的）思路是：分别计算当前总和以及所需的最小和 wt。

1
2
3
4
5
6
7
8
ll n = read(), sum = 0, wt = 0;
for (int i = 0; i < n; ++i) {
    int x = read();
    sum += x;
    if (x > 1) wt += 1;
    else wt += 2;
}
printf("%s\n", n > 1 && sum >= wt ? "Yes" : "No");

事实上上述两种方法等价。

1200

Q.\Large\mathcal{Q}. 每次询问给长度为nn 的数组，你要将其划分为若干段，使得对每段的mex⁡\operatorname{mex} 值相等。(1200, CF1935B. Informatics in MAC)

A.\Large\mathcal{A}. SupposeMEX⁡(x,y)=MEX⁡(y+1,z)\operatorname{MEX}(x, y) = \operatorname{MEX}(y + 1, z), what can be said aboutMEX⁡(x,z)\operatorname{MEX}(x, z)?

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int T;
	cin >> T;

	while (T--) {
		int n;
		cin >> n;

		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}

		vector<int> pre(n), suf(n);
		vector<int> mp(n);
		int x = 0;
		for (int i = 0; i < n; i++) {
			mp[a[i]]++;
			while (mp[x]) {
				x++;
			}
			pre[i] = x;
		}
		x = 0;
		mp.assign(n, 0);
		for (int i = n - 1; i > 0; i--) {
			mp[a[i]]++;
			while (mp[x]) {
				x++;
			}
			suf[i] = x;
		}

		int ans = 0;
		for (int i = 1; i < n; ++i) {
			if (pre[i - 1] == suf[i]) {
				ans = i;
			}
		}

		if (!ans) {
			cout << "-1\n";
		}
		else {
			cout << "2\n1 " << ans << "\n" << ans + 1 << " " << n << "\n"; 
		}
	}

	return 0;
}

1800

Q.\Large\mathcal{Q}. 构造一个序列，任何集合{x∣1⩽x⩽n∧x≠k}\lbrace x \mid 1\leqslant x\leqslant n \land x\ne k \rbrace 中的数ii 都可以是某个子序列的元素之和。(CF1966D. Missing Subsequence Sum)

A.\Large\mathcal{A}.

引理 如果我们已经能表示1∼s1\sim s，且拥有数t>st>s，则能表示t∼t+st\sim t+s。

问题 1 求一个数组，任何满足1∼n1 \sim n 的数ii 都可以是某个子序列的元素之和。

  • 问题 1 的解答 取{1, 2, 4, …, 2w}\lbrace 1,~2,~4,~\dots,~2^{w} \rbrace，其中2w⩾n2^w\geqslant n，具体地应取⌈log⁡2(n)⌉−1\lceil\log_2(n)\rceil-1。为叙述方便，以下记w=⌈log⁡2(n)⌉−1w=\lceil\log_2(n)\rceil - 1。

问题 2 求一个数组，所有子序列的和恰好是1∼n1 \sim n。

  • 问题 2 的解答 注意到取{1, 2, 4, …, 2w−1}\lbrace 1,~2,~4,~\dots,~2^{w-1} \rbrace 可表示1∼2w−11 \sim 2^{w}-1，为了恰好表示到nn，希望表示?∼n? \sim n，根据引理，只需拥有数n−(2w−1)n-(2^{w}-1) 即可，因此我们取{1, 2, 4, …, 2w−1, n−(2w−1)}\lbrace 1,~2,~4,~\dots,~2^{w-1},~n-(2^{w}-1) \rbrace。

问题 3 现在已经恰好能表示1∼k−11\sim k-1，求一个数组，任何满足k+1∼nk+1 \sim n 的数ii 都可以是某个子序列的元素之和。

  • 问题 3 的解答 根据引理，已经拥有k+1k+1，因此可表示k+1∼(k+1+k−1=2k)k+1\sim (k+1+k-1=2k)，若是再拥有2k+12k+1，因此可表示2k+1∼3k2k+1\sim 3k，再拥有3k+13k+1，因此可表示3k+1∼4k3k+1\sim 4k。当然，此过程不能无限进行，毕竟有步数限制。但幸运的是，当拥有k+1,2k+1,3k+1k+1,2k+1,3k+1 时，我们已经可以表示k+1∼6k+1k+1\sim 6k+1 了，此时再添加6k+26k+2，便可表示k+1∼12k+3k+1\sim 12k+3，如此倍增，就能表示题设要求的所有数。

原问题的解答 根据问题 2，先取{1, 2, 4, …, 2v−1, k−(2v−1)}\lbrace 1,~2,~4,~\dots,~2^{v-1},~k-(2^{v}-1) \rbrace，根据问题 3，再取{k+1, 2k+1, 3k+1, 2(3k+1), 22(3k+1), … }\lbrace k+1,~2k+1,~3k+1,~2(3k+1),~2^2(3k+1),~\dots\rbrace，即是问题的答案。

1
2
3
4
5
6
7
8
9
10
int n = read(), k = read();
int bit = 0; while ((1ll << bit) <= k) ++bit; --bit;
vector<int> ans;
for (int i = 0; i < bit; ++i) ans.push_back(1ll << i);
if (k - (1ll << bit)) ans.push_back(k - (1ll << bit));
if (k + 1 <= n) ans.push_back(k + 1);
if (2 * k + 1 <= n) ans.push_back(2 * k + 1);
if (3 * k + 1 <= n) ans.push_back(3 * k + 1);
for (int x = 6 * k + 2; x <= n; x <<= 1) ans.push_back(x);
print(ans);

Q.\Large\mathcal{Q}. 给定nn，输出一个数列，其中包含nn 个递增子列。(CF1922E. Increasing Subsequences)

A.\Large\mathcal{A}. 注意到{0,1,…,x−1}\{0,1,\dots,x-1\} 中有2x2^x 个递增子列，我们对nn 作二进制拆分，即n=2a0+2a1+⋯+2akn=2^{a_0}+2^{a_1}+\dots+2^{a_k}，首先输出0∼ak−10\sim a_k-1，对于其它二进制位，可以错位构造aia^i 个数，但为了节约输出的个数，我们借助第一位输出的数，直接输出aia_i 即可。最终的输出结果是0,1,…,ak−1,ak−1,ak−2,…,a00,1,\dots,a_k-1,a_{k-1},a_{k-2},\dots,a_0。

1
2
3
4
5
6
7
8
ll n = read();
vector<int> ans;
ll tmp = n, bit = -1; while (tmp) ++bit, tmp >>= 1; // 找到最高位
for (int i = 0; i < bit; ++i) ans.emplace_back(i); // 0 ~ a_k-1
while (bit--) if (n & (1ll << bit)) ans.emplace_back(bit); // a_{k-1} ~ a_0
printf("%lld\n", ans.size());
for (auto i : ans) printf("%d ", ans[i]);
printf("\n");

1900

Q.\Large\mathcal{Q}. 给定n,kn,k，构造nn 个四元组，满足所有四元组的所有元素互不相同，且每个四元组的最大公约数皆为kk。求所有元素最大值最小的一组构造。

A.\Large\mathcal{A}. 首先把所有四元组除以kk ，那么所有四元组的最大公约数为11。注意到，任意一个四元组都只能存在一个偶数，至少三个奇数，于是元素最大值的下界为6(n−1)+5=6n−16(n-1)+5=6n-1。另一方面，每个四元组取6i+1,6i+2,6i+3,6i+5(0⩽i<n)6i+1,6i+2,6i+3,6i+5(0\leqslant i<n)。

2300

Q.\Large\mathcal{Q}. 每次操作可选择一个二元组(xi,yi)(x_i,y_i)，使得axia_{x_i} 和ayia_{y_i} 的值变为f(axi,ayi)f(a_{x_i},a_{y_i})。f(x,y)f(x,y) 的值未知，但对于相同的x,yx,y，f(x,y)f(x,y) 的值相同。给出一种操作方案使任意函数ff 经过若干次操作后数列中最多只有22 个不同的数。(VJwin7F, CF1408F. Two Different)

A.\Large\mathcal{A}. 显然，若数列的长度是n=2kn=2^k，可分成2k−12^{k-1} 组，两两操作，再错位着操作，最终会全部相同。比如对于n=8n=8，可以这样操作：| 1 2 3 4 5 6 7 8 || 1 3 2 4 5 7 6 8 || 1 5 2 6 3 7 4 8 |。那麽如果不是22 的幂呢？比如n=9n=9，划分为9=8+1=4+59=8+1=4+5？实操后发现不行，实际上，不一定做加法拆分，可以先对前88 个操作，然后借用第2∼82\sim8 个元素和后面第99 个元素一併操作，也就是 | 1 2 3 4 5 6 7 8 || 1 3 2 4 5 7 6 8 || 1 5 2 6 3 7 4 8 |||| 2 3 4 5 6 7 8 9 || 2 4 3 5 6 8 7 9 || 2 6 3 7 4 8 5 9 |。现在只要把这些数字输出来就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int cnt = -1, t = n;
while (t) { cnt++; t >>= 1; }
t = 1 << cnt;  // 2的最高幂

for (int i = cnt; i >= 1; --i) { // 第i行（倒着数）2
    for (int j = 1; j <= (1 << i) / 2; j++) { // 组 第i行有(1 << i)/2组，组差为t*2/(1 << i)，每个组的起始值为t*2/(1 << i)*(组数-1)
        for (int k = 1; k <= t / (1 << i); k++) { // 每组的对数
            printf("%d %d\n", k + t * 2 / (1 << i) * (j - 1), k + t * 2 / (1 << i) * (j - 1) + t / (1 << i)); // 两个数间隔t / (1 << cnt)
        }
    }
}
for (int i = cnt; i >= 1; --i) {
    for (int j = 1; j <= (1 << i) / 2; j++) {
        for (int k = 1; k <= t / (1 << i); k++) {
            printf("%d %d\n", n - t + k + t * 2 / (1 << i) * (j - 1), n - t + k + t * 2 / (1 << i) * (j - 1) + t / (1 << i));
        }
    }
}

输出练习题

BUC1E 杨辉三角

  • 题意 输出杨辉三角，注意每行第一个数字前没有空格，其它数字的位宽为杨辉三角中最大数的宽度加上一。

  • 代码 主函数预处理：

    1
    2
    3
    4
    5
    for (int i = 0; i < maxN; ++i) {
        num[i][0] = num[i][i] = 1;
        for (int j = 1; j < i; ++j)
            num[i][j] = num[i - 1][j] + num[i - 1][j - 1];
    }

    每次询问：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int maxx = num[n - 1][n / 2];
    int cnt = 0;
    while (maxx) maxx /= 10, ++cnt;
    for (int i = 0; i < n; ++i) {
        std::cout << std::setw(0) << num[i][0];
        for (int j = 1; j < i + 1; ++j)
            std::cout << std::setw(cnt+1) << num[i][j];
        std::cout << "\n";
    }
    std::cout << "\n";