PRE-PCOI Mini Comp 1

开始用了15分钟把四道题都看了。

先看的第一题，感觉不难，应该可以拿满、已经有了一定的思路，想先做出来，但还是决定看后面的题。

第二第三题大致把题目看了一下，看懂题目之后，发现第二题的n和q都是1e5的级别，直觉认为解法是nlogn的，打算后面再做。

第三题是数学题，由于以前常遭数学题折磨，因此也打算放到后面才做。

早就想到难度可能不是递增的，但没想到差距会那么大，第四题瞄一眼就想到了做法，直接考虑胜者树，虽说是交互题，但也有了一定的经验，不至于手忙脚乱。

今天的题没怎么看subtask，直接就开始做了。

16:43的时候就把第四题很轻松地做出来了，然后就开始想第一题。

第一题想到很直接的做法就是二进制分解，考虑直接把1,2,4等全部表示出来，然后求和

很明显超步数了，看一下subtask，前面几个都是二的幂次，直接疯狂自增即可

然后就是28，分解二进制之后发现一步多余的都不能有，也就是说不可以进行一些意义不大的操作，为了处理这个花了很久。

中间代码写得又很丑，调了很久。

接下来便是16383，发现相较于偶数来说，奇数不太好处理，于是就考虑奇数偶数分开处理。

后面想到一种方法，比如从28为结尾，一步步往前可以是14,7,6,3,2,1，也就是一个乘二或者加一的操作

于是考虑重构代码，又花了一段时间

写完后发现对于\(2^n-1\)的情况会严重超出步数，但此时已经过了一个半小时，18:21了，于是便直接交上去打算后面再做了。

看第二题，已经准备使用线段树和莫队等算法了，于是认怂先跳过（宁做数学题不做数据结构）

第三题，设每个的答案分别为\(k_1,k_2,k_3\)等。操作和为\(sum\)，于是就有\(a_1-k_1x+(sum-k_1)y\)，再写一个\(a_2-k_2x+(sum-k_2)y\)

k是非负数，我们令这两个相等（题目要求），然后我们会有\(a_1-k_1x+(sum-k_1)y=a_2-k_2x+(sum-k_2)y\)

有\(a_1-k_1x+sum\cdot y-k_1\cdot y=a_2-k_2x+sum\cdot y-k_2\cdot y\)

有\(a_1-k_1x-k_1\cdot y=a_2-k_2x-k_2\cdot y\)

有\(a_1-k_1(x+y)=a_2-k_2(x+y)\)

越做到后面越觉得不可思议，No的情况直接比较一下所有a模（x+y）的余数即可

Yes的情况就是让最小的a的k为0，剩下的k都可以算出来

然后就过了....

18:38Acceptded T3

那就去面对第二题吧

已经准备了去拿subtask了

思考一下，我首先要从其他地方走到区间内，那么这里面一定要修桥，而且不用拆

那就数一下要建多少桥，也就是a数组从起始位置到区间开始的位置有多少个零，前缀和可以解决

然后我们开始在区间内修桥，由于我们移动不消耗时间，因此可以先把所有桥都建上

那会不会有时候不用建呢，如果从区间的某一端开始到一个地方，这里面全都是对上的，那我们就可以不去

（那我们为什么不直接缩小询问区间呢）

于是如果我们在区间以左起始位置，缩右边的，以右起始则缩左边，在区间内就两边都缩

我们这里可以预处理解决，然后区间内桥全修上，然后没用的拆了

然后自己猛然发现做完了，样例也都过了

比赛也快结束了，那就直接交上去吧

结果就Accepted了

19:07 finished T2

最终自认为简单的T1还是没做出来（

Expext:100+50 +75 +100

reality:76+100+100+100

Total Expected Score: 325
Total Reality: 376
Rating: 3

总结：

一定要先把题全看了再做，如果一道题一段时间没思路那就先换一题，否则如果今天我第二题没有那么幸运的话就很麻烦

无论如何暴力分一定要打上

Time：

[00:00-00:15]看题

[00:15-00:33]T4

[00:33-02:11]T1

[02:11-02:28]T3

[02:28-02:57]T2

[02:57-03:00]T1