其实这篇文章也包含了“力扣第 311 场周赛”的程序简注，所以会有LeetCode标签，但是这场力扣周赛实在太顶针了，所以一篇精注都没有，就附在下面了，需要的可以直接通过左侧目录跳转。
竞赛情况和最终结果
Codeforces
Codeforces 的拿分难度较三年前似乎有亿点提高，总之摆平心态提升实力才是正道。
ACA – Two ElevatorsACB – Decode StringACC – Jumping on TilesTRD – Friends and the Restaurant--E – Guess the Cycle Size--F – Kirei and the Linear Function--G – Cut Substrings
LeetCode
本来听学长说学ACM的人是可以薄纱LeetCode的，我不是很信，因为上一次周赛出现了线段树（完全没有准备也没有复习分块，并且作为面向求职的平台应该也需要背板子）；不过这次LeetCode周赛真的就是在比谁代码打得快，谁能Bug Free。
AC最小偶倍数AC*最长的字母序连续子字符串的长度AC反转二叉树的奇数层AC字符串的前缀分数和
Codeforces 程序精注
A – Two Elevators
签到题，直接根据题意计算即可。
/////////////////////////////////////
// Codeforces Round #820 (Div. 3)
// Problem A
//
// Powered by Coder Web vsCode
// Typed on Ipad Air 5 Without Keyborad
/////////////////////////////////////
#include<bits/stdc++.h>
using namespace std;
namespace lovelive{
void main(){
int a,b,c,d,e;
scanf("%d%d%d",&a,&b,&c);
d = abs(a-1);
e = abs(c-b) + abs(c-1);
if(d>e){
printf("2\n");
}else if(d==e){
printf("3\n");
}else{
printf("1\n");
}
}
}
int main(){
int _t;
scanf("%d",&_t);
while(_t--){
lovelive::main();
}
return 0;
}B – Decode String
稍微有点思考量的签到题，由于题目中明确说了序号是从1开始的，也就是说如果涉及到以j(10)和t(20)结尾的情况，一定出现的是*100或者*200，而不是*10（指的是“*a”）或者*20（指的是“*b”）。遇到0了记得多看一位即可。
/////////////////////////////////////
// Codeforces Round #820 (Div. 3)
// Problem B
//
// Powered by Coder Web vsCode
// Typed on Ipad Air 5 Without Keyborad
/////////////////////////////////////
#include<bits/stdc++.h>
using namespace std;
namespace lovelive{
void main(){
string s,ans="";int n;
cin>>n;
cin>>s;
int l = 0, r = 0;
while(r<n){
if(s[r] == '0'){
if (s[r + 1] == '0') r += 1;
for(int i=l;i<r-2;i++){
ans = ans + char(s[i] - int('0') + int('a') - 1);
}
if (r - 2 >= l){
int sa = s[r-2] - int('0');
int sb = s[r-1] - int('0');
ans = ans + char(sa * 10 + sb + int('a') - 1);
}else{
ans = ans + char(s[r-1] - int('0') + int('a') - 1);
}
r += 1;
l = r;
}else{
r += 1;
}
}
while (l<n){
ans = ans + char(s[l] - int('0') + int('a') - 1);
l += 1;
}
cout<<ans<<endl;
}
}
int main(){
#ifdef DEBUG //奇怪的问题
freopen("output.txt","w",stdout);
#endif //需要手动设置断点
int _t;
scanf("%d",&_t);
while(_t--){
lovelive::main();
}
return 0;
}C – Jumping on Tiles
可以看到通过人数瞬间减半，不过这题的思考量也不算很大。
- 由于
两点之间线段最短求cost只与字母的字典序差有关，所以根据$|x-a|+|x-b| \geq |a-b|$的取等条件可知，只跳起点和终点字典序之间的字母，并且按照字典序递增或递减的顺序跳，即可控制$cost$不超过$|a-b|$； - 显然$cost$的值不可能小于$|a-b|$，即$|a-b|$就是要求的最小$cost$；
- 为了使跳跃的次数最大化，我们要尽可能把所有符合上列要求的节点全跳一遍；
- 由于$cost$的值仅与字母字典序之差有关，与字母的位置无关，所以对于所有字母相同的不同节点，爱怎么跳怎么跳；
- 在实现的时候储存字母对应出现过的所有索引，在遍历字母的时候直接把储存的索引以任意顺序输出。
/////////////////////////////////////
// Codeforces Round #820 (Div. 3)
// Problem C
//
// Powered by Coder Web vsCode
// Typed on Ipad Air 5 Without Keyborad
/////////////////////////////////////
#include<bits/stdc++.h>
using namespace std;
namespace lovelive{
void main(){
int head[30],nxt[300000],val[300000],cnt;
//这里小题大做用了邻接表
cnt = 0;
memset(head,0,sizeof(head));
memset(nxt,0,sizeof(nxt));
memset(val,0,sizeof(val));
string s;
cin>>s;
for(int i=1;i<s.size() - 1;i++){
int to = int(s[i]) - int('a') + 1;
nxt[++cnt] = head[to];
val[cnt] = i + 1;
head[to] = cnt;
}
//为了让输出的时候起点能输出在最前面
//所以故意利用邻接表特性单独处理第一位
int to = int(s[0]) - int('a') + 1;
nxt[++cnt] = head[to];
val[cnt] = 1;
head[to] = cnt;
int l = int(s[0]) - int('a') + 1;
int r = int(s[s.size()-1]) - int('a') + 1;
int step = (r - l) / max(abs(l - r),1);
//一个莫名其妙的试图省去if语句的求符号处理
if (!step) step = 1;
int m = 1;
//这里采用了先算数再输出答案的策略
//如果在向邻接表插入元素的过程中就计算好数量
//就不用多此一举
for(int i = l;i * step <= r * step;i += step){
for(int j=head[i];j;j=nxt[j]){
m ++;
}
}
cout<<abs(r - l)<<" "<<m<<endl;
for(int i = l;i * step <= r * step;i += step){
for(int j=head[i];j;j=nxt[j]){
to = val[j];
cout<<to<<" ";
}
}
cout<<s.size()<<endl;
}
}
int main(){
int _t;
scanf("%d",&_t);
while(_t--){
lovelive::main();
}
return 0;
}D – Friends and the Restaurant
因为在平板上用手打字用手框选什么的实在是太慢了，因此这题来不及调了。事后发现其实只是因为打得太晚了错误的用消费量减去预算进行计算了，翻转了一下就过了。
这题的逻辑实际上不是很难：
- 如果能够组队出去，那么每个队伍只塞两个人是最佳情况：当队伍里有两个人，且剩余预算足够再塞一个人时，这个人塞进来与否并不会影响这组能否组建成功，但可能会导致剩余的人出现落单而导致可以组建的队伍数量变少的情况；
- 以现有可用预算最多（不能为负）的人为依据，选择现有可用预算（可能为负）最少 且 加起来的总预算不为负 的人组队：若有盈余者$a_1,a_2$和亏欠者$b_1,b_2$，满足$|a_1|>|b_1|>|a_2|>|b_2|$，若当前预算最多的$a_1$选择与亏欠次多的$b_2$组队，那么$b_1,a_2$明显会无法组成合法的队伍；若剩余没有组队的人预算全部非负，上述配对方法依旧适用。
/////////////////////////////////////
// Codeforces Round #820 (Div. 3)
// Problem D
//
// Powered by Coder Web vsCode
// Typed on Ipad Air 5 Without Keyborad
/////////////////////////////////////
// 应该是贪心
// 首先求出每个人的欲望和预算的差值
// 剩余预算为正的组别可以互相蹭吃的
// 但剩余预算为负的就不可以互相组队
// -----------------------------
// 赛后总结
// 思路是对的，但是平板实在是不方便
// 然后就没有调出来
//
#include<bits/stdc++.h>
using namespace std;
namespace lovelive{
void main(){
int xi[100005],yi[100005],zi[100005],n;
bool used[100005];int l,r,ans = 0;
memset(used,0,sizeof(used));
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&xi[i]);
for(int i=0;i<n;i++){
scanf("%d",&yi[i]);
zi[i] = yi[i] - xi[i];//没错，正确代码和当时比赛刚结束时的代码就差了这一句
}
sort(zi,zi + n);
//按照剩余预算排序有助于实现上述算法
l = 0; r = n - 1 ;
while(l < r && zi[r] >= 0){
//printf("\t&d\t&d\n",l,r);
if(zi[l] >= 0){
r -=2 ;ans ++;//这里采取了特判，实际上不需要
}else{
while(l < r &&
(zi[r] + zi[l] < 0 || used[l]) ) l ++;
if (l < r){
ans ++ ; l ++;r -- ;
}
}
}
printf("\t%d\n",ans);
}
}
int main(){
int _t;
scanf("%d",&_t);
while(_t--){
lovelive::main();
}
return 0;
}E – Guess the Cycle Size
交互题，其实想通了就十分的简单，但在当时题面不清和晦涩描述的情况下也不是很好想通。
- 虽然题面给你留下的印象是一张图，实际上就是一个编号次序被打乱的环。
- 对于两个固定的编号$a,b$，实际上只会出现至多两个不同的答案。
- 虽然题目吓唬你说
? a b的结果问多少次都一样，但也提醒了你? b a的答案可能不同。
所以问题就变得非常简单：
- 只需要不停的问
? 1 i和? i 1，如果不幸发现两个答案是一样的，那么就把i换一个值接着问；这里建议采用初值为2逐级递增的方法问，以配合下面的策略； - 如果找到了不同的两个答案$a,b$，直接返回$a+b$即可；
- 如果图太小了没有机会问完，那么根据出现$-1$的最小的$i$返回$i-1$就是答案；
- 在25对数字的试探中，成功率应该能达到$>99.9%$，如果过于倒霉只能重新交……
感觉只有一千多人过了这题是有原因的，不只是因为来不及或者没想出来：我使用scanf("%lld",&a)读数据死活读不出来，然后换成cin秒过，大家有什么头猪吗？
#include<bits/stdc++.h>
using namespace std;
int main(){
long long a,b;
for(int i=2;i<30;i++){
printf("? 1 %d\n",i);
cin>>a;
if (a==-1){
printf("! %d\n",i-1);
fflush(stdout);
return 0;
}
printf("? %d 1\n",i);
cin>>b;
if (a != b){
printf("! %lld\n",a+b);
fflush(stdout);
return 0;
}
}
assert(false);
printf("! %lld\n",a+b);
fflush(stdout);
return 0;
}F – Kirei and the Linear Function
请开始压轴题的表演！（虽然Div3基本上认真想都能想出来，不像OI蓝紫题）
要点一：读懂题面
题目给出一个长数字$s$，数字的长度为$n$（要你自己算），可以从其中提取带有前导0的子区间组成数字$v\left(l,r\right)$，现在给你限定好了接下来所有询问中某些子区间的长度$w$，并在每次询问中给你不同的$l_i,r_i,k_i$，希望你能找出一对不同的子区间$ \left(L_1,L_1+w−1\right),\left(L_2,L_2+w−1\right)$，满足：
- $L_1 \neq L_2$（毕竟是不同的子区间）；
- $v\left(L_1,L_1+w−1\right) * v\left(l_i,r_i\right) + v\left(L_2,L_2+w−1\right)$对$9$求余的结果为$k$。
- 如果有多个结果，需要尽可能地使$L_1$更小，若有多个结果可以导致$L_1$取到最小值，那么就需要$L_2$尽可能小；
- 可能找不到这样的一对子区间，这时请输出
-1 -1。
要点二：处理 v(l,r)
虽然数字看起来十分地长以至于无法使用常规方式储存，不过也犯不上因此调用高精度，可以采用类似于前缀和的方法来处理。由于余数只有$9$，十分地小，所以如果想要边算边求余也不是不行。
但是Codeforces的官方题解给出了一个更为巧妙的方法：一个数除以$9$所得余数与将该数的所有位上的数字求和取余的结果是一样的，也就是说：
$$
(a_0 \times 10^0 + a_1 \times 10^1 + … + a_n \times 10^n)\space mod\space 9 = (a_0 + a_1 + … + a_n)\space mod\space 9
$$
证明也不算难，只要发现$10^n\space mod\space 9 = 1$就行了。
由于$w$在一组数据中是全局固定的，所以可以在查询之前预处理好$\left(L,L+w−1\right)$，这样在调用的时候就可以以$O\left(1\right)$的时间复杂度获得结果。并且为了快速找出所有的余数结果为$k_x$的所有数对，需要按照从小到大的顺序储存区间余数相同的左节点（为了在接下来的比较环节中节省力气）。
要点三：处理询问
首先当然是把$v\left(l_i,r_i\right)$算出来，由于对$9$求余产生的情况只有$9$种，大可以对$ v\left(L_1,L_1+w−1\right) $枚举$k_1$，然后算出来$ v\left(L_2,L_2+w−1\right)$的求余值$k_2$。
这时候就可以掏出刚才已经预处理好的那个“余数值为$k_i$的所有数对”的二维数组，然后若$k_1 \neq k_2$，直接选择每个$k_i$的最小$L_i$，否则就从同一个$k_i$数组中挑出最小和次小的$L_1,L_2$；当然如果数组里面可选择的子区间数量不够，就要果断放弃。
注意：在C++中选择pair储存$L_1,L_2$可以省去重定义比较符号的时间和精力。
写成代码
/////////////////////////////////////
// Codeforces Round #820 (Div. 3)
// Problem F
//
// Powered by Coder Web vsCode
// Typed on Ipad Air 5 Without Keyborad
// [Review Version Coded on LEGION]
/////////////////////////////////////
/////////////////////////////////////
// 赛后总结
// 光是理解题目和题解就看了将近一个小时？
// 理解了其实就能理解了（
// 首先，这个w是对于所有查询有效的，
// 所以可以预处理
// 预处理可以直接用前缀和，其实就是a1*10+a2
// 由于数字除以九的余数等于每位数字的和的余数
// （小技巧）其实可以直接对每位数字求和
//#define DEBUG // 交的时候记得关掉
#define add(a,b) (a + b >= 9 ? a + b - 9 : a + b)
#define sub(a,b) (a - b >= 0 ? a - b : a - b + 9)
#define mul(a,b) (a * b % 9)
#include<bits/stdc++.h>
using namespace std;
int pp[200005]; // 局部变量开不了这么大
namespace lovelive{
vector<int> dd[11];
string s;
int n,w,m,li,ri,ki,xi;
void init(){
for(int i=0;i<9;i++)
dd[i].clear();
pp[0] = 0;
//前缀和
for(int i=1;i<=n;i++)
pp[i] = pp[i-1] + (s[i-1] - '0');
//预处理
for(int l=1;l<=n-w+1;l++){
int r = l + w - 1;
int t = (pp[r] - pp[l-1]) % 9;
dd[t].push_back(l);
}
}
void main(){
cin>>s>>w>>m;
n = s.size();
init();
while(m--){
cin>>li>>ri>>ki;
xi = (pp[ri] - pp[li - 1]) % 9;
pair<int,int> ans=make_pair(100000000,100000000);
for(int a=0;a<9;a++){
int b=sub(ki,mul(a,xi));
//点不够就别选
if(dd[a].empty() || dd[b].empty()) continue;
if(a != b){
ans = min(ans,make_pair(dd[a][0],dd[b][0]));
}else if(dd[a].size()>=2){
ans = min(ans,make_pair(dd[a][0],dd[a][1]));
}
}
if(ans == make_pair(100000000,100000000)){
cout<<"-1 -1\n";
}else{
cout<<ans.first<<" "<<ans.second<<"\n";
}
}
}
}
int main(){
int _t;
scanf("%d",&_t);
while(_t--){
lovelive::main();
}
return 0;
}G – Cut Substrings
最后的一题！虽然光啃官方题解实在啃不动，但是丢进调试器然后一调，就能够理解了！（经典事后诸葛亮）
实现
对于当前的每一次合法切割，都有可能影响下一次切割时的方案数量。在每一个合法切割点$l[i]$，找到下一个能够被合法切割且不与当前切割点存在交集的切割点$l[j]$（切割点有宽度，切完一次下一次就不能切已经被切掉的部分），然后枚举所有与$l[j]$存在交集的切割点$l[k]$（当然包括$l[j]$自身，若$l[j]$与$l[k]$不存在交集，那么还可以再在$l[j]$上切割一次，导致方案不合法），若$dp[k] > dp[i] + 1$则更新切割次数$dp[k]$和方案数量$dpi[k]$；若$dp[k] = dp[i] + 1$说明又找到了若干种可以采用的方案，将$dpi[i]$加到$dpi[k]$中。
代码
/////////////////////////////////////
// Codeforces Round #820 (Div. 3)
// Problem G
//
// [Review Version Coded on LEGION]
/////////////////////////////////////
//#define DEBUG // 交的时候记得关掉
#define SaintSnow (int)(1e9+7)
#define add(a,b) (a = a + b >= SaintSnow ? a + b - SaintSnow : a + b)
#define sub(a,b) (a = a - b >= 0 ? a - b : a - b + SaintSnow)
#define mul(a,b) (a = a * b % SaintSnow)
#include<bits/stdc++.h>
using namespace std;
namespace lovelive{
string sf,ss;
int dp[1000]; //dp 储存最小切割数量
int dpi[1000]; //dpi 储存取到最小切割量时解的数量
int lenf,lens; //储存字符串长度
int pref[1000],cnt; //储存符合要求的切割位置的方案数量
void init(){
cnt=0;
lenf = sf.size();
lens = ss.size();
for(int i=0;i<=lenf-lens;i++){
bool flag=true;
for(int j=0;j<lens;j++){
if(ss[j] != sf[i + j]){
flag=false;break;
}
}if(flag) pref[++cnt] = i;
dp[cnt] = 0x3f3f;
dpi[cnt] = 0;
}
pref[0] = - 1000;
dpi[0] = 1;
dp[0] = 0;
dp[++cnt] = 0x3f3f;
dpi[cnt] = 0;
pref[cnt] = lens + lenf;
}
void solve(){
for(int i=0;i<cnt;++i){
// 寻找第一个不与当前处理切割点重合的切割点
int j=i+1;
while(j <= cnt && pref[j]<pref[i] + lens) ++j;
// 寻找与找到的切割点有重合的所有可能的切割情况
for(int k=j;k<=cnt && pref[k]<pref[j] + lens;++k){
if(dp[k] > dp[i] + 1){ // 如果可行切割次数更小
dp[k] = dp[i] + 1;
dpi[k] = dpi[i]; // 应该服从更小的切割次数
}else if(dp[k] == dp[i] + 1){
add(dpi[k],dpi[i]); // 可行次数相等应该兼收并蓄
}
}
}
printf("%d %d\n",dp[cnt]-1,dpi[cnt]);
}
void main(){
cin>>sf>>ss;
init();
solve();
}
}
int main(){
int _t;
scanf("%d",&_t);
while(_t--){
lovelive::main();
}
return 0;
}LeetCode 程序简注
基本上在利用python的特性偷懒
最小偶倍数
只有一行代码，可见题目有多水。
class Solution:
def smallestEvenMultiple(self, n: int) -> int:
return 2 * n if n % 2 else n最长的字母序连续子字符串的长度
一开始兴冲冲地用优化过的dp去计算，结果发现要求“子字符串字母序严格连续”，小题大做爆了个错误尝试，不然排名还可以上去一两百。
class Solution:
def longestContinuousSubstring(self, s: str) -> int:
def ctoi(c):
return ord(c) - ord('a')
ans = 1
l = 0
for i in range(1,len(s)):
if ord(s[i]) - ord(s[i-1]) == 1:
ans = max(ans,i - l + 1)
else:
l = i
return ans反转二叉树的奇数层
脑子有点乱导致代码也不是很美观，调了几次才满意。根据题意模拟即可。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
curs = [root]
nxts = []
step = 0
root.fa = None
while(len(curs)):
if step % 2 == 0:
for i in range((len(curs)+1)//2):
rev = len(curs)-1 - i
if curs[i].right :
tmp = curs[i].right
curs[i].right = curs[rev].left
curs[rev].left = tmp
# ------------
if i < rev:
tmp = curs[i].left
curs[i].left = curs[rev].right
curs[rev].right = tmp
if curs[i].right.right:
tmp = curs[i].right.right
curs[i].right.right = curs[rev].left.right
curs[rev].left.right = tmp
# ---------
tmp = curs[i].right.left
curs[i].right.left = curs[rev].left.left
curs[rev].left.left = tmp
# --------
if i < rev:
tmp = curs[i].left.right
curs[i].left.right = curs[rev].right.right
curs[rev].right.right = tmp
# ---------
tmp = curs[i].left.left
curs[i].left.left = curs[rev].right.left
curs[rev].right.left = tmp
print(i,rev)
for cur in curs:
if cur.left:
#cur.left.fa = cur
nxts.append(cur.left)
if cur.right:
#cur.right.fa = cur
nxts.append(cur.right)
#print(curs,nxts)
step += 1
curs = nxts.copy()
nxts = []
return root字符串的前缀分数和
直接用map偷懒了。
class Solution:
def sumPrefixScores(self, words: List[str]) -> List[int]:
mp = {}
for word in words:
for i in range(1,len(word) + 1):
if word[:i] in mp:
mp[word[:i]] += 1
else:
mp[word[:i]] = 1
ans = [0] * (len(words))
for i in range(len(words)):
for j in range(1,len(words[i]) + 1):
ans[i] += mp[words[i][:j]]
return ans
