Day3 总结

Part.1 赛时历程

依旧扫视所有题目，确定大概难度，发现 $T3$ 十分眼熟。

顺序开题。

$T1$ 思考了一会，选择打表找规律，发现可以从差值入手，又重新打了一个表，发现直接打表会超出代码长度限制。 然后观察答案，注意到答案都为差值的倍数，然后就直接使用调和级数写完了。（一直寻找 O(n) 做法没找到） （时间 $8:45:10$）

$T2$ 直接想，没得到结果，观察到提示中有 “出现数字种类数 ≤ 100” 和 "每个数字出现次数 ≤ 2"。然后就隐约知道需要分治。考虑从容斥的角度考虑，事实上我推出了题解中的式子 $f(i) = C_{x_i + y_i - 2}^{x_i - 1} - \sum_{j = 1}^{i - 1}[x_j \leq x_i \cup y_j \leq y_i](f(j) \times C_{x_i + y_i - x_j - y_j}^{x_i - x_j})$，但是觉得时间复杂度太大，放弃了。

随后推测根据种类数根号分治，发现时间复杂度不对，放弃了($10:20$ 左右)。

在写完 $T3$ 后（$11:01:25$）再回过头来补充 $T2$ 代码，最终选择写了一个 $bfs$ 形式的 $dp$ 草草收场 ($11:25:03$)。

在 $T2$ 受挫后，我被迫开始写 $T3$，然后开始推 $dp$，虽然之前不知道在哪里见到过($hhj$ 杯)，但是我已经几乎忘完了。但是还是看到 $r \geq n$ 就直接判断，只用考虑 $r \leq n$ 就行了。

推了一个 $dp_{i,j}$ 指第 $i$ 个数时，前面总共加了 $j$ 的方案数。

$i$ 用滚动数组优化掉，得到了原始的 $O(nr ^ 2)$ 的 $dp$ ($r \leq n$)。

发现了每次更新只会选最小值或次小值，优化到 $O(nr)$，后面试图套数据结构或者推出矩阵形式，但是都没时间尝试了。（赛后推了一下，感觉不太行）

$T4$ 第一眼感觉是一个树套树来维护二维平面，但是不太对，先交了一个暴力 $11:49:23$，后面感觉维护特别困难，有回去看一看 $T3$ 看能不能在改进一下。

Part.2 赛后总结

估分 $100 + 16 + 75 + 25 = 216$

实分 $100 + 8 + 75 + 25 = 208$

大差不差，还是在 $T2$ 上花费了大量时间，距离答案实际就只剩下一个分讨，有点可惜。$T3$ 的 $dp$ 应该没法继续优化了，基本上走到了死路。

Part.3 改进

可能是对时间的把控还有对 $dp$ 的设计。

一些思路可能有所猜测但是总是差一点。

前言 “🐘🛏️✈️JDS”

总结

棒棒🍭题

有点🍭🍭🍭，想了一会吧，打标没找到啥规律，发现gcd与异或都与差值有关，枚举一下。

🍭🍭题

🍭🍭🍭，赛时写完T1有点晕，想T2时一看到数据范围与部分分就知道是根号分治，结果只写了种类少的，另一个想出容斥DP，但状态有点错，没写。

🍭🍭🍭题

一眼感觉是原题，但忘了是什么时候的题？想到了和第一次见到时一样的思路，但好像错了。发现r>n时的简单做法，但误以为可能改多个，已🍭完！！！

🍭🍭🍭🍭题

打了暴力走了，赛后才发现把为0的点删掉正好是第一个特殊性质，太🍭了，赛时以为没啥优化。😭

得分：100+56+0+25

评价：没挂

餹粉：蔗🍭

总结：

估分：30+32+20+25，实际：30+16+20+0。T1不会，打表没找到规律，后来一直在想拆位。T2以为就是容斥，但我的想法太不好容斥了。写了相同元素数<=2的，居然挂了（还花了最多的时间）。。。T3，dp一会儿想着部分分写法，一会儿又想正解的限制，思路混乱，最后只写了最低档暴力（比hjj杯还写得烂）。T4数组开小了，Re了。

加强推式子和代码能力。。

30+16+0+70

T1:

不知道$gcd$和$异或$的取值范围

只知道 $a,b,$ $a<b,$ $gcd(a,b)<=a,a$ ^ $b$ $\le b$

还推出

$1.$ 如果满足条件 $a$ 的二进制位数与 $b$ 的二进制位数 要一样

$2.$ 一定有一个偶数

$3.$ $b<=1.5a$

$4.$ 可以发现对于每个$a=$ $2^n$ 及其后的一些紧挨着的数字 都有 $a , 1.5a$满足题意

且每个 $2^n$ 后跟着的数字个数有规律

$2$ 只有$2$ $1$个

$4$ 只有$4$ $1$个

$8$ 有$8和10$ $2$个

$16$ 有 $3$个

$32$ 有 $5$个

后面的有$8,13,21,34,55...$个

是一个斐波那契数列

但是不怎么能用上这个性质

两个多小时过去了

只能$30pts$ 跑了

$T2$ 读完题 感觉不怎么好写 ，打算先读完题

$T3$ 读完就有点畏惧了,先跑了

$T4$ 这个看着就有意思，暴力有好写，就写了

先写了最最最暴力的 $mpq$ 的 这个连最小的测试点都过不了，我想的先写出来再改，这个好改

但是怎么写都是错的

于是就直接写 $(mn+ \sum h(生命值))log^{怪兽数量}_{2}$

调了一会调对了

本来回去想写其他题的暴力的

但是一下子就想到了如何优化

就改成了 $(m log ^ n _2 + \sum h(生命值))log^{怪兽数量}_{2}$

直接获得$70pts$

还有$10mins$

花了$5mins$写了$B$的$16pts$ 的暴力

还有$5mins$ 没时间了

前期不是很正常

幸好还有个$D$题，才有3位数的分数

我觉得明天还是先花小于$1h$将所有题全部读一遍且写完一眼就能看出的暴力

总结

估分：100+56+75+20 = 251

结局：100+56+75+35 = 266

今天的评测机还是跑得一如既往的快捏

*快速评测机重度依赖

T1

刚开始看到这道题的时候感觉就很奇怪，觉得这个数据范围就是$O(n)$的

然后想了想，想出来一个枚举因数的做法。写了大概20min，结果并没有通过样例

给我气死了，索性直接想正解，打表找规律，找到了 ^_^

以下是我的规律发现：

• 每个$(2n,2n+1)$的数对都是可行的
• 然后这些数对的有些整数倍数是可行的
• 就对每个$(2n,2n+1)$枚举倍数，判断可行性

最后是一个调和级数的复杂度 $O(n \log n)$

T2

最开始往容斥方面想了一下其实，但是想着想着发现时间复杂度不太优，就没往那方面想了

(但是其实subtask3用容斥非常快啊，为什么我没有使用容斥ne，绝对不是因为我把这个特殊条件看成 "出现数字种类数$≤2$" 了)

然后就只有老老实实朴素dp得了56pts（悲）

T3

一眼顶针，黑胡椒杯原题（强化版）

效仿当年写了一份代码，加了一个$r>n$的特判 75pts

不错不错

T4

照着题面20min敲了一份模拟，惊异地发现剩余时间还有两个小时。

于是我毅然决然的进行了一个敲打线段树的行动，妄想以此通过AB特殊点。

结果到了比赛结束还是没有调出来。

终

黄一轩还给我提前结束比赛了，坏孩子打屁股。

感觉比赛策略没有什么大的问题

差不多差不多差不多差不多差不多就写到这了

比代码源模拟赛难捏。

有点不在状态，这俩天的睡眠时长远小于在西大附中时候的睡眠时长，有点困。

打算慢慢写的，然后 A 第一眼这不是一个找规律题，然后打表找无果，然后浅度思考 +inf seconds 后只想出了个 $O(n \log^2 n)$ 的捏。然后看 B，我恨 ALL of 格路计数，写了个暴力跑了，不知道为啥后面几个大样例会 RE，应该是栈空间爆了？不知道可能是吧，搜了一下怎么调整栈空间，没学会，没管了。然后撇了一眼 C， 贪心/dp/ds 优化 dp，反正啥都想到了，没啥欲望写，先跳，然后 D，我靠这么长的题面吓哭了，然后细读一下，大数据结构，想了一会觉得没啥性价比然后写了个暴力跑了。

后三道想 + 写挺慢的，基本上就是边写边想 A 了，然后没啥时间了吧。然后总结了一下后三题，dp、ds 优化 dp、Ad-hoc，我靠我咋啥都知道啥都不会，啥都来不及写啊，反正最后开始写 C 没多少时间了，暴力 dp 没调出来，然后糊了个完全没有丝毫正确性的随机化交上去了。

赛时差不多就这样吧，调调生物钟好好休息。

打个表格玩玩。

• $[1]$：我觉得线段树优化 dp 我还是能想出来的叭。

• $[2]$：能算 Ad-hoc 吗，反正我应该想不到做法，就算 40 分叭。

不要死磕第一题。

差不多叭感觉上面这句话已经体现出来这场模拟赛的意义惹。

投诉：

• 显示屏色差严重。
• $O(n \log n)$ 你给 $n_{max}=10^7$？这不 $O(n)$ 数据范围。
• 怎么还有原。

30+16+0+70

T1:

不知道$gcd$和$异或$的取值范围

只知道 $a,b,$ $a<b,$ $gcd(a,b)<=a,a$ ^ $b$ $\le b$

还推出

$1.$ 如果满足条件 $a$ 的二进制位数与 $b$ 的二进制位数 要一样

$2.$ 一定有一个偶数

$3.$ $b<=1.5a$

$4.$ 可以发现对于每个$a=$ $2^n$ 及其后的一些紧挨着的数字 都有 $a , 1.5a$满足题意

且每个 $2^n$ 后跟着的数字个数有规律

$2$ 只有$2$ $1$个

$4$ 只有$4$ $1$个

$8$ 有$8和10$ $2$个

$16$ 有 $3$个

$32$ 有 $5$个

后面的有$8,13,21,34,55...$个

是一个斐波那契数列

但是不怎么能用上这个性质

两个多小时过去了

只能$30pts$ 跑了

$T2$ 读完题 感觉不怎么好写 ，打算先读完题

$T3$ 读完就有点畏惧了,先跑了

$T4$ 这个看着就有意思，暴力有好写，就写了

先写了最最最暴力的 $mpq$ 的 这个连最小的测试点都过不了，我想的先写出来再改，这个好改

但是怎么写都是错的

于是就直接写 $(mn+ \sum h(生命值))log^{怪兽数量}_{2}$

调了一会调对了

本来回去想写其他题的暴力的

但是一下子就想到了如何优化

就改成了 $(m log ^ n _2 + \sum h(生命值))log^{怪兽数量}_{2}$

直接获得$70pts$

还有$10mins$

花了$5mins$写了$B$的$16pts$ 的暴力

还有$5mins$ 没时间了

前期不是很正常

幸好还有个$D$题，才有3位数的分数

我觉得明天还是先花小于$1h$将所有题全部读一遍且写完一眼就能看出的暴力

今日总结

感觉还行，预估分数60+16+50+25，实际分数90+16+45+55。

写第一道题时，先打了个暴力，然后看了看数据点发现n的范围比较大，思考了30分钟左右，发现O(nlogn)的复杂度可以，于是开始想做法，经过推导发现答案和因子有关，而通过推导发现GCD=a-b,但是后面时间改为200ms，但是我不知道那能不能过，于是跳了。

第二题，经过我的思考，想不出如何在除了暴力以外的任何方法，在我写完其他题后我把剩下的时间都拿来完成这道题的思考。

第三题，一道HHJ杯的原题改版，先把50分写了，又想了30-60分钟的样子，想不出来，就写第四题了，但是这道题犯了个问题，在初始化时我忘记了计算答案的最大值，DP数组的初值设小了。

最后一道题，读完题后先写了个O(nq)的暴力让后去看了一下数据点，发现特殊数据A，B不好写，但是特殊数据C在我的暴力下很好修改，于是我就去写了特殊点C，写完后就去思考第二题的方法了。

总的来说这次除了第三题初始化写错了，其他的都十分的不错。

总分：40+16+70+0估分：60+72+75+25，T1认为很难也没有发现性质，打了个根号的表以为可以过60分但是只有40分，T2很快会了72，想到了容斥但是似乎神秘的分析出来是指数级的。看特殊性质很像根号分治，但是没想清个数小的如何做，就写了72pts暴力，但是由于没有曲摸没去干净，发现《=2的wa了，但也不是负数，以为是写错了，发现56分过了对应的大样例，只交了56分，结果是样例太水了，挂成了16分，只有差不多1个小时了，发现了一个和正解很像的贪心，和正解dp转移判断条件是一样的，但发现似乎是错了，当时比较慌张就去看部分分了，看特殊性值发现mod>k可以直接贪心，就写了一个75分，但是挂成70分了，T4了，写了一个暴力但是Re了。🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭🍭

一般吧。实际分数比预期分数高 $10$ 分（预期：$100$，$16$，$20$，$25$；实际：$100$，$16$，$20$，$35$）。

先看的 $\text{A}$ 题，简短的题面直接想到找规律（性质）。思考了 $25$ 分钟决定先把暴力写出来（$\text{30tps}$），再思考大概 $25$ 分钟没有想出来。

然后去看了 $\text{B}$ 题。题意简单一眼有暴力模拟思路，$10$ 分钟写完暴力（当时还不知道是暴力），以为没有问题去跑大数据发现没有输出，排查后发现写的是爆搜 $\text{dfs}$ $O\left(2^n\right)$ 的复杂度级别严重超时。没想到怎么优化，突然觉得 $\text{A}$ 的枚举有优化思路便继续去看 $\text{A}$。发现 $\text{gcd}$ 与异或一些关系后过了样例，交了。

我去看 $\text{C}$ 题。题意而很简单，大概 $15$ 分钟写完暴力了样例，交。

10:00 点左右，我看 $\text{D}$ 题。$\text{D}$ 题题意很长，我一眼认为是大模拟，没有涉及什么算法。花了一些时间理清题意开始模拟，写完花了 $40$ 分钟，没过样例。找了 $10$ 分钟发现写法错误导致逻辑错误（两处错误，要求在线和 auto 出问题）。 错误的代码：

int l,r;
cin>>l>>r;
l=min((l+sco)%p,(r+sco)%p);
r=max((l+sco)%p,(r+sco)%p);//前面修改过的l导致r计算错误
for(auto[x,y,hp,w]:ms){
    if(hp<=0)continue;
    if(l<=x&&x<=r){
        hp--;
        if(hp<=0)sco+=w;
    }
}

修改后的：

int _,__;
cin>>_>>__;
int l=min((_+sco)%p,(__+sco)%p),r=max((_+sco)%p,(__+sco)%p);
for(auto&[x,y,hp,w]:ms){
    if(hp<=0)continue;
    if(l<=x&&x<=r){
        hp--;
        if(hp<=0)sco+=w;
    }
}

然后过了样例，算出来分数应该是 $\text{25tps}$，实际运气好了多了 $10$ 分。

后面的时间再返回看 $\text{B}$，$\text{C}$ 思考其正解但没想出来。

以后应该先理清“在线”逻辑（赋值对后续操作有没有影响之类），再写代码。

（30-56-100-0） Problem A: 45 minutes Problem B: 70 minuetes Problem C: 100 minutes problem D: 40 minutes B题知道正解但是认为复杂度太高了没有写 A题没有想到a^b=c -> a^c = b D提没有想到先用一维线段树，再用两个线段树拆半生命值 LOL