【做题记录】Codeforces Round 943 (Div. 3)/CF1968A-F

conti123 / 2024-10-17 / 原文

【做题记录】Codeforces Round 943 (Div. 3)/CF1968A-F

A

暴力枚举即可。

B

双指针枚举即可,能匹配就匹配。

C

考虑构造出 \(a[1]=1,a[i]=a[i-1]+x[i]\) 的数列,发现满足要求。

D

有个明显的结论,两人最终一定是在某个点上的。

于是从起点开始扫一遍,求出到每一个点的距离和路上的分数,最终时取个 \(\max\) 即可。

E

发现答案的的上界是 \(2n-1\),考虑构造出这个上界。

发现 \(n=1\) 时成立,\(n=2,3\) 时不成立,\(n=4\) 时成立,考虑 \(n>4\) 的情况。

考虑每个点的贡献。

第一个为 \(1\),第二个为 \(1\)

那么存在一种构造将 \((1,1),(1,2)\) 覆盖,然后填上对角线从 \((3,3)\) 开始,但是发现这样只是 \(2n-2\),还少了 \(1\)

那么考虑构造 \(4\) 个点,使得它们符合题意,这里给的是:

\((1,1),(1,2),(1,4),(5,2)\),剩下的就是从 \((5,5)\) 开始填好对角线即可。

F

发现可行的话一定可以表示为 \(x=x\) 或者 \(x=x=x\)

\(f[i]=\oplus_{j=1}^ia[i]\)

对于前者,即是 \(\oplus_{i=l}^xa[i]=\oplus_{i=x+1}^ra[i]\),即 \(f[l-1]\oplus f[x]=f[x]\oplus f[r]\),即 \(f[l-1]=f[r]\)

对于后者,即是 \(f[l-1]\oplus f[x]=f[x]\oplus f[y]=f[y]\oplus f[r]\),那么就有 \(f[l-1]=f[y],f[x]=f[r]\)

考虑找出 \(l\) 后面最后的 \(f[y]\) 和 最先的 \(f[x]\),看一下位置是否符合即可。

G

\(\dots\) 没学 SA 的我直接趋势。

Code

官方题解