本场摘要

这一场无功无过,rank 为 411,rating 加了 55,来到了 1889。比赛时通过了 ABCD 四个题目。

感觉这一场题目难度在中等偏上,思路上虽然非常清晰直接,但是实现难度比一般场次大。E、F 题的 idea 较为新颖,作为拓展思路的场次还是很不错的。出题老哥是个华南师范大学附属中学的初三学生这么小就是红名了,反观我这个老古董却越来越菜了。。。,不得不说出题水平相当可以。

这一场的 D 题很早就有了 idea,但是写的时候非常坎坷,先是 DP 写错调半天,然后再是递归写挂。。。可见退役久了水平下降得十分明显——放在本科的时候应该能 1h 内写完前四个题的。。。不过这也是应该的,毕竟很久没有系统训练过了,以后想上分还是得多多补题。天天空想着上个红名,不脚踏实地是不可能的。

这两天几乎听完了肖斯塔科维奇的弦乐四重奏,然后又在B站上看了很多他的故事,发现天才如他其实也是位卷王,在圣彼得堡音乐学院读书的时候几乎门门功课都卷到了 5 分。既然我只是一个普通人,要做成事情需要更加努力才是,继续加油吧。

传送门:

题目

C.

题目大意:

给出一个大小为 nnn * n 的方阵,方阵的每个位置上都是 0。题目定义了两种操作:

  • 操作一,把一行中的所有数字变成一个大小为 n 的排列,排列的顺序可以自定义。
  • 操作二,把一列中的所有数字变成一个大小为 n 的排列,排列的顺序可以自定义。

要求最多进行 2n2 * n 此操作,要求使得最后的结果方阵中,每个位置上的数字之和最大。

题解:

构造题虽然变化万千,但是还是有一定套路的。一般来说,拿到问题后先构造找出理论最大值,一般来说这种情况是有对应解的,然后我们再去构造这个解。

观察可知,一个相同的数字,不能同时出现在一个矩形的四个顶点的位置上。既不存在这样的四个点 (i,j),(i,j+m),(i+n,j),(i+n,j+m)(i, j), (i, j + m), (i + n, j), (i + n, j + m) 上的值相等。所以一个数字在方阵中最多出现 2n12 * n - 1 次,即反“L 型”地排列在方阵的右下角。大的数字肯定要出现尽量多次,所以越大的数字要约放在右下。形如(以 n=4n = 4 为例):

1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4

在想出构造的期望样式后,我们就能有的放矢了。先放最后一行,排列为 1,2,...,n1, 2, ..., n,然后是倒数第二行和倒数第二列,排列依然是 1,2,...,n1, 2, ..., n。这样一直做下去,直到放完第一行和第一列,总共操作 2n12n - 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
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <vector>
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 2e5 + 5;
int n, sum[maxn];
void print(int c, int index) {
std::cout << c << ' ' << index << ' ';
for (int i = 1; i <= n; ++i) {
std::cout << i << ' ';
}
std::cout << '\n';
}
int main() {
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);

int T = 1;
std::cin >> T;
sum[0] = 0;
for (int i = 1; i <= 500; ++i) {
sum[i] = i * (2 * i - 1) + sum[i - 1];
}
while (T--) {
std::cin >> n;
std::cout << sum[n] << ' ' << 2 * n - 1 << '\n';
print(1, n);
for (int i = n - 1; i >= 1; i--) {
print(1, i);
print(2, i);
}
}

return 0;
}

D.

题目大意:

题目给定一个大小为 n 的整数序列,其中 n18n \leq 18。每次操作可以选择一个 [l,r][l, r] 的区间,然后将这个区间中的整数变成 Mex(l,r)Mex(l, r)Mex(l,r)Mex(l, r) 定义为「区间中最小的未出现的非负整数」。可以进行不限次这样的操作,要求使得最后的整数序列和最大,并输出构造出该序列过程中选取的一系列区间

题解:

考虑一个长度为 m 的初始全为 0 的区间,经过观察可知,题目中定义的构造后最大的可能结果就是区间的数字全部变为 m(可以从从 m=1m = 1m=2m = 2 等大概递推出任意长区间的构造方式)。

这样一来,问题就分成了两个部分,第一部分是将原序列划分成若干个区间,对于一个长度为 m 的区间,其内部可以全部变成数字 m,也可以保持原状,要使得结果最大;第二部分是给定一个长度为 m 的区间,将区间中的所有数字变成 m。

前者是一个非常经典的区间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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <vector>
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll, int> pli;
typedef std::pair<ll, ll> pll;
typedef double db;
typedef long double ldb;
const int maxn = 2e5 + 5;
int n, a[maxn];
std::vector<pii> operations;
void update(int l, int r) {
std::vector<int> vec;
for (int i = l; i <= r; ++i) {
vec.push_back(a[i]);
}
std::sort(all(vec));
int mex = 0;
for (int i = 0; i < r - l + 1; ++i) {
if (mex == vec[i]) ++mex;
else break;
}
for (int i = l; i <= r; ++i) {
a[i] = mex;
}
}
void pushOperation(int l, int r) {
operations.push_back({l, r});
update(l, r);
}
void clear(int l, int r) {
pushOperation(l, r);
if (a[l]) pushOperation(l, r);
}
void fromZero2Sequence(int l, int r){
if (l == r) {
return;
}
fromZero2Sequence(l, r - 1);
pushOperation(l, r);
clear(l, r - 1);
fromZero2Sequence(l, r - 1);
}
void addOperations(int l, int r, int isFirstDivIn) {
if (l == r && isFirstDivIn) {
if (!a[l]) pushOperation(l, l);
else return;
} else {
clear(l, r);
fromZero2Sequence(l, r);
pushOperation(l, r);
}
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);

int T = 1;
// std::cin >> T;
while (T--) {
operations.clear();
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
}
pii dp[20][20];
dp[0][0] = {0, 0};
for (int i = 1; i <= n; ++i) {
int val = 0;
int pos = 0;
for (int j = 1; j <= i; ++j) {
dp[i][j] = dp[i - 1][j - 1];
int newVal = 0;
if (j > 1) {
newVal = dp[i - 1][j - 1].first + j * j;
} else {
newVal = dp[i - 1][0].first + std::max(1, a[i]);
}
if (val < newVal) {
val = newVal;
pos = i - 1 - (j - 1);
}
}
dp[i][0] = {val, pos};
}
int pos = n;
while(pos) {
int next = dp[pos][0].second;
addOperations(next + 1, pos, 1);
pos = next;
}
std::cout << dp[n][0].first << ' ' << operations.size() << '\n';
for (auto it : operations) {
std::cout << it.first << ' ' << it.second << '\n';
}
// std::cout << "=======\n";
// for (int i = 1; i <= n; ++i) {
// std::cout << a[i] << ' ';
// }
// std::cout << '\n';
}

return 0;
}

E.

题目大意:

给定长度为 n 的一个序列 a。从前往后,从 i=1i = 1 开始,让 ai+1=max{ai+1ai,0}a_{i + 1} = \max\left\{a_{i + 1} - a_i, 0\right\}。i 的取值依次递增,当 i=ni = n 时,使 a1=max{a1an,0}a_1 = \max\left\{a_1 - a_n, 0\right\},然后再让 i=1i = 1。如此循环往复,无限次地操作下去。直到这样的操作不能让序列中的元素产生变化。求最后“尘埃落定”后的序列中所有不为零的元素的下标。

题解:

显然,操作的次数最多能达到 Int32 次。例如仅有三个元素的序列:0,1,1e90, 1, 1e9。问题到这里似乎就走进了死胡同,因为如果序列短一点还好说,可以构造式子求解,但是面对大小为 n 的序列,除了暴力模拟就别无他法了——于是尝试分析这个序列的性质,我们可以发现,如果一个数字前面的连续非零数字越多,它被减的值的数量级就会越大。

例如,假设序列为 0,a1,a2,a3,...0, a_1, a_2, a_3, ...。经过 m 轮操作后,假设 a2,a3a_2, a_3 仍非 0,不妨设 a2moda1=0a_2 \bmod a_1 = 0,那么新的序列为0,a1,a2a1n,a3(a22a1(n+1))n/2,...0, a_1, a_2 - a_1 * n, a_3 - (a_2 * 2 - a_1 * (n + 1)) * n / 2, ...。观察到 a3a_3 减少值比 a2a_2 大了至少 O(n)O(n) 倍。

所以经过至多 1e9131e9^{\frac{1}{3}} 轮后,则原序列的连续非零子串长度最大为 3。

发现这个性质之后,这个题就完全没有思维难度了,只需要暴力计算后,把原序列划分成若干个子序列,然后分别求解即可。但是这道题实现过程较为繁琐,且在 E2 进行了卡常,即使是 std 的耗时也来到了 1000ms 左右,而笔者实现的代码会在 E2 的第 22 个点 TLE。。。这里还是放 std 吧。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=2e5+5;
int n,a[MAXN];bool b[MAXN];
bool check(){
a[n+1]=a[1],a[n+2]=a[2],a[n+3]=a[3];
for(int i=1;i<=n;i++)
if(a[i]&&a[i+1]&&a[i+2]&&a[i+3]) return true;
return false;
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(n==2){
while(a[1]&&a[2]){
a[2]=max(0,a[2]-a[1]);
a[1]=max(0,a[1]-a[2]);
}
b[1]=(a[1]>0);b[2]=(a[2]>0);
}else if(n==3){
while(a[1]&&a[2]&&a[3]){
a[2]=max(0,a[2]-a[1]);
a[3]=max(0,a[3]-a[2]);
a[1]=max(0,a[1]-a[3]);
}
b[1]=(!a[3]&&a[1]);
b[2]=(!a[1]&&a[2]);
b[3]=(!a[2]&&a[3]);
}else{
while(check()){
for(int i=1;i<=n;i++) a[i%n+1]=max(0,a[i%n+1]-a[i]);
}
for(int i=1;i<=n;i++) b[i]=false;
auto attack=[&](ll x,ll y){
ll k=x/y;
return (2*x-(k+1)*y)*k/2;
};
for(int p=1;p<=n;p++)
if(a[p]&&a[p%n+1]) a[p%n+1]=max(0,a[p%n+1]-a[p]);
else break;
for(int i=1;i<=n;i++) if(!a[i]&&a[i%n+1]){
b[i%n+1]=true;
b[(i+2)%n+1]=(a[(i+2)%n+1]>attack(a[(i+1)%n+1],a[i%n+1]));
}
}
int cnt=0;
for(int i=0;i<=n;i++) if(b[i]) cnt++;
cout<<cnt<<endl;
for(int i=1;i<=n;i++) if(b[i]) cout<<i<<' ';
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
int _;cin>>_;
while(_--) solve();
}

F.

题目大意:

操场上 n 个学生站成一排(其中 n1e6n \leq 1e6),每个学生有一个抛球的力度区间 [li,ri][l_i, r_i],对于两个学生 i 和 j 而言,如果满足 ij<[li+lj,ri+rj]|i - j| < [l_i + l_j, r_i + r_j],则 i 和 j 可以互相抛球。体育老师在一次活动开始时,可以给某个同学一个球,然后这个同学再传给其他同学,每个同学只要能接到球,就可以传给其他人或者扔掉这个球,且每个人在单次活动中可以接球多次。体育老师在下课后还有一个约会,很赶时间,所以期望能通过尽量少次的活动,让每个同学都能至少接到一次球。问这样的活动至少需要多少次。

题解:

说来惭愧,拿到这道题后我几乎是直奔题解,根本没指望能自己想出来。但看完题解后发现其实也不是“不可做”,甚至说是一个很经典的前缀建边。如果是初见这类题目的话,参考价值非常大。即使是知道题解,我在实现的过程成依然花费了不小的功夫。

言归正传,琢磨这道题目的条件,看到“一个同学可以接球多次”,“ij<[li+lj,ri+rj]|i - j| < [l_i + l_j, r_i + r_j]”的字眼,容易联想到利用图的联通性,然后加点连边。显然,这是开了“上帝视角”的马后炮。。。乐

对于那个看起来非常怪异的不等式条件,有一个很合乎直觉的理解方法,即:我们可以把 [i+li,i+ri][i + l_i, i + r_i] 看作是 i 同学的“右手”,把 [iri,ili][i - r_i, i - l_i] 看作是 i 同学的“左手”。不妨设 i<ji < j,如果满足 [i+li,i+ri][jrj,jlj][i + l_i, i + r_i] \cap [j - r_j, j - l_j] \neq \varnothing,则说明能 i 同学和 j 同学能相互通过右手拉左手的方式够到彼此。

每个学生都可以看成是白点,然后再构造 n 个黑点来表示每个坐标,如果一个学生 i 的手能伸到点 x,则在白点 i 和黑点 x 之间连一条边。即:如果满足 x[iri,ili]x[i+li,i+ri]x \in [i - r_i, i - l_i] \lor x \in [i + l_i, i + r_i],则连接 i 和 x。

但是我们仍然会面临两个问题:

  • 可能会存在两个学生同时用左手拉左手,或者右手拉右手,这样是不符合不等式约束要求的。
  • 上述的解法显然要加 O(n2)O(n^2) 条边,在 n 如此巨大的情况下,明显无法通过题目。

对于问题一,我们可以注意到这样一条性质,如果有若干个学生能够到同一个点,且满足这些学生中既有使用左手的,也有使用右手的,那么这些学生一定能在一次传球活动中同时接到球——比如,可以选定某个使用右手的学生作为支点,在使用左手的学生之间来回传球,这样就能遍历完这个点相连的所有使用左手的学生(右手亦然)。假如一个点 x 上连接的只有都使用左手(右手)的学生,那我们就舍弃掉这个点,则问题解决。

对于问题二,假如一个学生的左(右)手能够到区间 [i,j][i, j],其实不必对区间内每个点都连边,可以仅连到 i 点,然后再依次连接 (i,i+1),(i+1,i+2),...,(j1,j)(i, i + 1), (i + 1, i + 2), ..., (j - 1, j)。这样下来总的连边数是 n+n1n + n - 1,即可通过题目。

笔者写的代码一直收到 WA,且对比 std 后发现写的十分臃肿,改了改去也远不如标程,索性干脆不改了,这里建议直接看 std。once again, 我好菜啊

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
const int MAXN=2e6+5;
int n,tot,le[MAXN],ri[MAXN];
int fa[MAXN<<1],s[MAXN],t[MAXN],pre[MAXN],suf[MAXN];
inline int find(int x){
while(x^fa[x]) x=fa[x]=fa[fa[x]];
return x;
}
void solve(){
cin>>n;
for(int i=1;i<=2*n+1;i++) fa[i]=i;
for(int i=0;i<=n+1;i++) s[i]=t[i]=pre[i]=suf[i]=0;
for(int i=1;i<=n;i++){
cin>>le[i]>>ri[i];
s[max(1,i-ri[i])]++;s[max(0,i-le[i])+1]--;
t[min(n+1,i+le[i])]++;t[min(n,i+ri[i])+1]--;
}
tot=n;
for(int i=1;i<=n;i++){
s[i]+=s[i-1],t[i]+=t[i-1];
if(s[i]&&t[i]) suf[i]=pre[i]=++tot;
}
suf[n+1]=0;
for(int i=1;i<=n;i++) pre[i]=(pre[i]?pre[i]:pre[i-1]);
for(int i=n;i>=1;i--) suf[i]=(suf[i]?suf[i]:suf[i+1]);
for(int i=1;i<=n;i++){
int l=max(1,i-ri[i]),r=max(0,i-le[i]);
if(l<=r){
l=suf[l],r=pre[r];
if(l&&r&&l<=r) for(int i=find(l);i<r;i=find(i)) fa[i]=i+1;
}
l=min(n+1,i+le[i]),r=min(n,i+ri[i]);
if(l<=r){
l=suf[l],r=pre[r];
if(l&&r&&l<=r) for(int i=find(l);i<r;i=find(i)) fa[i]=i+1;
}
}
for(int i=1;i<=n;i++){
int l=max(1,i-ri[i]),r=max(0,i-le[i]);
if(l<=r){
l=suf[l],r=pre[r];
if(l&&r&&l<=r) fa[find(i)]=find(l);
}
l=min(n+1,i+le[i]),r=min(n,i+ri[i]);
if(l<=r){
l=suf[l],r=pre[r];
if(l&&r&&l<=r) fa[find(i)]=find(l);
}
}
int ans=0;
for(int i=1;i<=tot;i++) if(fa[i]==i) ans++;
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false);
// freopen("Otomachi_Una.in","r",stdin);
// freopen("Otomachi_Una.out","w",stdout);
int _;cin>>_;
while(_--) solve();
return 0;
}