本场摘要
这一场无功无过,rank 为 411,rating 加了 55,来到了 1889。比赛时通过了 ABCD 四个题目。
感觉这一场题目难度在中等偏上,思路上虽然非常清晰直接,但是实现难度比一般场次大。E、F 题的 idea 较为新颖,作为拓展思路的场次还是很不错的。出题老哥是个华南师范大学附属中学的初三学生这么小就是红名了,反观我这个老古董却越来越菜了。。。 ,不得不说出题水平相当可以。
这一场的 D 题很早就有了 idea,但是写的时候非常坎坷,先是 DP 写错调半天,然后再是递归写挂。。。可见退役久了水平下降得十分明显——放在本科的时候应该能 1h 内写完前四个题的。。。不过这也是应该的,毕竟很久没有系统训练过了,以后想上分还是得多多补题。天天空想着上个红名,不脚踏实地是不可能的。
这两天几乎听完了肖斯塔科维奇的弦乐四重奏,然后又在B站上看了很多他的故事,发现天才如他其实也是位卷王,在圣彼得堡音乐学院读书的时候几乎门门功课都卷到了 5 分。既然我只是一个普通人,要做成事情需要更加努力才是,继续加油吧。
传送门:
题目
C.
题目大意:
给出一个大小为 n ∗ n n * n n ∗ n 的方阵,方阵的每个位置上都是 0。题目定义了两种操作:
操作一,把一行中的所有数字变成一个大小为 n 的排列,排列的顺序可以自定义。
操作二,把一列中的所有数字变成一个大小为 n 的排列,排列的顺序可以自定义。
要求最多进行 2 ∗ n 2 * n 2 ∗ 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) ( i , j ) , ( i , j + m ) , ( i + n , j ) , ( i + n , j + m ) 上的值相等。所以一个数字在方阵中最多出现 2 ∗ n − 1 2 * n - 1 2 ∗ n − 1 次,即反“L 型”地排列在方阵的右下角。大的数字肯定要出现尽量多次,所以越大的数字要约放在右下。形如(以 n = 4 n = 4 n = 4 为例):
1 2 3 4
2 2 3 4
3 3 3 4
4 4 4 4
在想出构造的期望样式后,我们就能有的放矢了。先放最后一行,排列为 1 , 2 , . . . , n 1, 2, ..., n 1 , 2 , . . . , n ,然后是倒数第二行和倒数第二列,排列依然是 1 , 2 , . . . , n 1, 2, ..., n 1 , 2 , . . . , n 。这样一直做下去,直到放完第一行和第一列,总共操作 2 n − 1 2n - 1 2 n − 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 ); 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 的整数序列,其中 n ≤ 18 n \leq 18 n ≤ 1 8 。每次操作可以选择一个 [ l , r ] [l, r] [ l , r ] 的区间,然后将这个区间中的整数变成 M e x ( l , r ) Mex(l, r) M e x ( l , r ) ,M e x ( l , r ) Mex(l, r) M e x ( l , r ) 定义为「区间中最小的未出现的非负整数」。可以进行不限次这样的操作,要求使得最后的整数序列和最大,并输出构造出该序列过程中选取的一系列区间
题解:
考虑一个长度为 m 的初始全为 0 的区间,经过观察可知,题目中定义的构造后最大的可能结果就是区间的数字全部变为 m(可以从从 m = 1 m = 1 m = 1 ,m = 2 m = 2 m = 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 () { std ::ios::sync_with_stdio(false ); std ::cin .tie(NULL ); int T = 1 ; 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' ; } } return 0 ; }
E.
题目大意:
给定长度为 n 的一个序列 a。从前往后,从 i = 1 i = 1 i = 1 开始,让 a i + 1 = max { a i + 1 − a i , 0 } a_{i + 1} = \max\left\{a_{i + 1} - a_i, 0\right\} a i + 1 = max { a i + 1 − a i , 0 } 。i 的取值依次递增,当 i = n i = n i = n 时,使 a 1 = max { a 1 − a n , 0 } a_1 = \max\left\{a_1 - a_n, 0\right\} a 1 = max { a 1 − a n , 0 } ,然后再让 i = 1 i = 1 i = 1 。如此循环往复,无限次地操作下去。直到这样的操作不能让序列中的元素产生变化。求最后“尘埃落定”后的序列中所有不为零的元素的下标。
题解:
显然,操作的次数最多能达到 Int32 次。例如仅有三个元素的序列:0 , 1 , 1 e 9 0, 1, 1e9 0 , 1 , 1 e 9 。问题到这里似乎就走进了死胡同,因为如果序列短一点还好说,可以构造式子求解,但是面对大小为 n 的序列,除了暴力模拟就别无他法了——于是尝试分析这个序列的性质,我们可以发现,如果一个数字前面的连续非零数字越多,它被减的值的数量级就会越大。
例如,假设序列为 0 , a 1 , a 2 , a 3 , . . . 0, a_1, a_2, a_3, ... 0 , a 1 , a 2 , a 3 , . . . 。经过 m 轮操作后,假设 a 2 , a 3 a_2, a_3 a 2 , a 3 仍非 0,不妨设 a 2 m o d a 1 = 0 a_2 \bmod a_1 = 0 a 2 m o d a 1 = 0 ,那么新的序列为0 , a 1 , a 2 − a 1 ∗ n , a 3 − ( a 2 ∗ 2 − a 1 ∗ ( n + 1 ) ) ∗ n / 2 , . . . 0, a_1, a_2 - a_1 * n, a_3 - (a_2 * 2 - a_1 * (n + 1)) * n / 2, ... 0 , a 1 , a 2 − a 1 ∗ n , a 3 − ( a 2 ∗ 2 − a 1 ∗ ( n + 1 ) ) ∗ n / 2 , . . . 。观察到 a 3 a_3 a 3 减少值比 a 2 a_2 a 2 大了至少 O ( n ) O(n) O ( n ) 倍。
所以经过至多 1 e 9 1 3 1e9^{\frac{1}{3}} 1 e 9 3 1 轮后,则原序列的连续非零子串长度最大为 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 个学生站成一排(其中 n ≤ 1 e 6 n \leq 1e6 n ≤ 1 e 6 ),每个学生有一个抛球的力度区间 [ l i , r i ] [l_i, r_i] [ l i , r i ] ,对于两个学生 i 和 j 而言,如果满足 ∣ i − j ∣ < [ l i + l j , r i + r j ] |i - j| < [l_i + l_j, r_i + r_j] ∣ i − j ∣ < [ l i + l j , r i + r j ] ,则 i 和 j 可以互相抛球。体育老师在一次活动开始时,可以给某个同学一个球,然后这个同学再传给其他同学,每个同学只要能接到球,就可以传给其他人或者扔掉这个球,且每个人在单次活动中可以接球多次。体育老师在下课后还有一个约会,很赶时间,所以期望能通过尽量少次的活动,让每个同学都能至少接到一次球。问这样的活动至少需要多少次。
题解:
说来惭愧,拿到这道题后我几乎是直奔题解,根本没指望能自己想出来。但看完题解后发现其实也不是“不可做”,甚至说是一个很经典的前缀建边。如果是初见这类题目的话,参考价值非常大。即使是知道题解,我在实现的过程成依然花费了不小的功夫。
言归正传,琢磨这道题目的条件,看到“一个同学可以接球多次”,“∣ i − j ∣ < [ l i + l j , r i + r j ] |i - j| < [l_i + l_j, r_i + r_j] ∣ i − j ∣ < [ l i + l j , r i + r j ] ”的字眼,容易联想到利用图的联通性,然后加点连边。显然,这是开了“上帝视角”的马后炮。。。乐
对于那个看起来非常怪异的不等式条件,有一个很合乎直觉的理解方法,即:我们可以把 [ i + l i , i + r i ] [i + l_i, i + r_i] [ i + l i , i + r i ] 看作是 i 同学的“右手”,把 [ i − r i , i − l i ] [i - r_i, i - l_i] [ i − r i , i − l i ] 看作是 i 同学的“左手”。不妨设 i < j i < j i < j ,如果满足 [ i + l i , i + r i ] ∩ [ j − r j , j − l j ] ≠ ∅ [i + l_i, i + r_i] \cap [j - r_j, j - l_j] \neq \varnothing [ i + l i , i + r i ] ∩ [ j − r j , j − l j ] = ∅ ,则说明能 i 同学和 j 同学能相互通过右手拉左手的方式够到彼此。
每个学生都可以看成是白点,然后再构造 n 个黑点来表示每个坐标,如果一个学生 i 的手能伸到点 x,则在白点 i 和黑点 x 之间连一条边。即:如果满足 x ∈ [ i − r i , i − l i ] ∨ x ∈ [ i + l i , i + r i ] x \in [i - r_i, i - l_i] \lor x \in [i + l_i, i + r_i] x ∈ [ i − r i , i − l i ] ∨ x ∈ [ i + l i , i + r i ] ,则连接 i 和 x。
但是我们仍然会面临两个问题:
可能会存在两个学生同时用左手拉左手,或者右手拉右手,这样是不符合不等式约束要求的。
上述的解法显然要加 O ( n 2 ) O(n^2) O ( n 2 ) 条边,在 n 如此巨大的情况下,明显无法通过题目。
对于问题一,我们可以注意到这样一条性质,如果有若干个学生能够到同一个点,且满足这些学生中既有使用左手的,也有使用右手的,那么这些学生一定能在一次传球活动中同时接到球——比如,可以选定某个使用右手的学生作为支点,在使用左手的学生之间来回传球,这样就能遍历完这个点相连的所有使用左手的学生(右手亦然)。假如一个点 x 上连接的只有都使用左手(右手)的学生,那我们就舍弃掉这个点,则问题解决。
对于问题二,假如一个学生的左(右)手能够到区间 [ i , j ] [i, j] [ i , j ] ,其实不必对区间内每个点都连边,可以仅连到 i 点,然后再依次连接 ( i , i + 1 ) , ( i + 1 , i + 2 ) , . . . , ( j − 1 , j ) (i, i + 1), (i + 1, i + 2), ..., (j - 1, j) ( i , i + 1 ) , ( i + 1 , i + 2 ) , . . . , ( j − 1 , j ) 。这样下来总的连边数是 n + n − 1 n + n - 1 n + 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 ); int _;cin >>_; while (_--) solve(); return 0 ; }