test20191024

T1spongebob

送的，十多分钟就A了，节奏算是把握的还不错吧，给后面留足了时间。

T2

算是一个对于我这种弱鸡来说比较有难度的题吧，对于每个修改，可以使用结论，也可以学习hxy神仙的分类讨论，我分类讨论的确是一大弱项。并且在一道题上卡久了，浪费了很多时间，下次考试一定注意：先看10分钟，有思路就再看几分钟，否则，先写暴力

T3

非常难得一道题，首先建图可以建出来，但是因为时间不够了，没有细想。见完图以后，不停地规约边就行了，反正属于不可做题。并且暴力又双叒叕嗝屁了！！！

practice20191023

T1

模拟，居然没有任何特判的SB垃圾STL程序水A了

T2

非常有意思的一道题。首先如果考虑二维的情况，那么有 \(|x_1-x_2|+|y_1-y_2|\) 那么绝对值拆开有4中情况 $x_1-x_2+y_1-y_2\\-x_1-x_2+y_1-y_2\\x_1-x_2-y_1+y_2\\-x_1-x_2-y_1+y_2$ 然后又如下结论： $x_1-x_2\le |x_1-x_2|\ge x_2-x_1$ 于是乎用$O(2^5)$枚举每个数前的符号，算出来的最大值一定是合法的，且最优的。

T3

mlgp，之前不是做过类似的题吗？lsr说了一句我才想起来，就是别墅那个题，枚举上下界，然后压成一行，然后单调栈O(n)地跑出每个点最左最右地小于它的值得下标。

T4

瞎几把爆搜+剪枝。 这次考试依然挂在开题顺序上，并且在一道题上死磕了很久，明明T4比前几道都水，却没有去开，连输出-1都没有打，下次长教训了，无论如何也要给它交程序上去，不可以不交。还是那句话，看到题10分钟没有思路马上写暴力，然后往下走，暴力写完再来正解。

test20191024

T1

虽然是个大水题，但是一开始明明写对了，少了个判断，调了半天，还写了SPJ，浪费了不少时间。说明下次写题要冷静分析清楚在动手，不要边打边思考，逻辑清楚一点，思路清晰一点。

T2

线性DP？想不到吧？考试的时候凭感觉猜了几个结论，但是都完全没有用上，一开始就想了个错误的$n^2$DP，然后之后就一直在死磕，也没有想办法去优化之类的Orz，说明不要一开始就被自己的思路搞死了，当一条思路行不通，先看看是不是写挂了，然后马上去换思路，如果没有思路，分段写暴力然后开下一题。

T3

其实这种数据结构乱搞题还是挺有意思的，只可惜当时时间不多，没有去仔细思考，千万要改正！！！！！！像这种数据结构优化模拟，需要代码能力，也对思维能力有一定要求，下次要敢于乱搞，瞎几把做正确的优化，哪怕觉得效果不好也行，说不定势能分析一波就复杂度正确了Orz。

Summary

纵观几次考试，依然存在暴力写挂的情况，并且最关键的是开题顺序及时间安排，不要一定去想正解，想不出来想个靠谱点的乱搞写上去再分段暴力然后开下一题，一定避免一道题卡很久的情况。对于T1，保证正确尽快A掉，这样心态就比较稳了。

test 1029

今天爆零了Orz，跪了跪了。

T1

其实这题真的坑，看出拓展欧几里得不难，但是要写对代码就比较困难了。$ax+by=c->a(x+kb/gcd)+b(x-ka/gcd)=c$然后$\Delta x = b/gcd \Delta y/gcd$，然后不妨设x的系数大于y的系数，那么我们就要使x的绝对值最小，于是把x调整为最小正整数解，计算一次，然后把c取反，再做一次。

T2

神仙题，考虑临项交换，分类讨论：如果$a_i<b_j并且b_i>a_j$那么显然i放在j前面更优，对于相反情况，则j在i前面，对于其他情况，不构成比较关系，于是随便排。但是这个东西不满足strick weak ordering,要想办法把它变得符合，于是使用a+b这种玄学的东西来搞就行了。考试的时候遇到这种贪心虽然不会证明，但是我的乱搞法第一个就是这种东西，由于DP定义错了，所以直接样例都没有过，这也是考试的问题。

T3

魔改dijkstra，把每个点作为起点，同时跑dijkstra，然后对于一个点记一个由哪个点更新过来，然后枚举边，看一下它的两个端点是不是由不同的源点更新过来，如果是，尝试更新答案。

Summary

今天考试暴露除了最显然的问题，就是如果某道题卡死了，就会导致整个考试的心态爆炸，今天不管是肝T2还是T3都会有较好的结果，结果因为T1没跳出来，就嗝屁了，千万注意改正。

test2019

T1

没开long long 见祖宗

T2

不可做 四边形不等式优化DP，我能写出40分暴力都很不错了

T3

不可做，分治高消

test20191101

今天挂分110

T1

水题，不开long long 见祖宗，挂分40

T2

类似于莫队的区间移动算法可做，爆了CE，挂分70

T3

可做题，但是由于最后几分钟去扫雷去了，发现了关键性质却没有写.Orz跪了。

20191102

mlgp wc

T1

又双被细节卡了，忘了特判逆元不存在的情况，直接爆10分。日。下次做题千万不要忘了逆元不存在的情况。

T2

本来可以想想发下它是一个偏序的，但是由于10.30才写完T1，已经没有时间去想正解了，最后瞎几把爆搜搜出来40分。 对于这些偏序，如果从小到大排序会存在一定的后效性，如果从大到小排序就不存在这些问题，然后树状数组维护最长段就行了。注意以后做题，特别是那种正着做和到着做都可以或者第一反应正着做的题，都看看能不能倒着做，防止出题人卡Orz。

T3

一个计数类DP的比较套路的题。记$dp[i][d]$表示i个点，深度不超过j的的方案数，那么有转移：$dp[i][d] = \sum dp[i-j][d]*dp[j][d-1]* {i-2 \choose j-1}$ 后面那一坨的意思是从(i-1)个标号里面选取(j-1)个给这个子树，因为根的标号已确定，而我们默认当前考虑的子树的根的标号是次小的，所以是$i-2\choose j-1$

summary

这两天的考试真的考的西撇，D1因为低级错误挂了110分，下次千万注意，如果不卡常还是最好全局long long，T2最后手残，挂了70分爆CE，D2因为T1没考虑好细节，10.30才过样例，主要是一开始较长时间没做出来，心态就非常慌，其实9点写出T1是非常正常的事情，千万做到想好再写，不要怕分类讨论，不要慌，T1挂了就挂了，不要在意它！

20191105

T1

读错题了，做成了毒瘤分类讨论+模拟就当练习分类讨论吧！

T2

挂了屑。还是最小生成树的套路，建树，然后维护LCA及路径最大边，然后分类讨论。讨论可以加到原树上的边，不能加到原上的边分别记为cnt1和cnt2.如果最小生成树就是X，那么答案是：$(2^{cnt1+n-1}-2)\times 2^{m-cnt1-(n-1)}$前面一坨的意思是候选边颜色任选，但是不能全是一个颜色，后面的意思是非候选边任意选择是否加进去。 对于小于X的情况答案就是$2\times 2\times({cnt1}-1)\times 2^{cnt2}$前面一坨的意思是每条候选边任选颜色，但是必须有一条初始边颜色确定，剩下的边随便选

T3

不可做，wyh的神仙代码被hxy 卡了

test20191106

T1

不可做，懵逼钨丝反演

T2

神仙模型转换，不可做。Xor出奇迹，见fsy代码。

T3

不可做

test20191108

T1

2019全国一卷数学22题原题，OI做法就不赘述了，下面是严格的数学证法： \(p_i = ap_{i-1}+bp_i+cp_{i+1}\\\) 因为\(a+b+c=1\) 所以 原式等于\((1-b)p_i=a*p_{i-1}+c*p_{i+1}\) \((a+b)p_i=a*p_{i-1}+c*p_{i+1}\) 移项 \(a(p_i-p_{i-1})=c(p_{i+1}-p_{i})\) 所以 \(\frac{p_{i+1}-p_{i }} {p_{i}-p_{i-1 }} =\frac{a}{c}\) 设$b_i=p_{i+1}-p_i$ 那么 \(\frac{b_i}{b_{i-1 }} =\frac{a}{c}\) 所以 \(b_n = (\frac{a}{c})^{n}b_0\) \(b_0 = p_1-p_0\) 所以 \(p_{n+1}-p_n = (\frac{a}{c})^{n}(p_1-p_0)\)

\[p_{n+1}-p_n=(\frac{a}{c})^np_1\]

所以 \(p_n = \sum_{i=1}^{n-1}(\frac{a}{c})^{i}p_1+p_1\) 由等比数列求和公式 \(p_n=p_1\times \frac{\frac{a}{c}(1-(\frac{a}{c})^{n-1})}{1-\frac{a}{c }} +p_1\) 令$n=2n$

然后有 \(p_n=p_1\times \frac{\frac{a}{c}-(\frac{a}{c})^n+1-\frac{a}{c }} {1-\frac{a}{c }}\) 因为$p_n=1$

所以有 \(p_1=\frac{1-\frac{a}{c }} {1-(\frac{a}{c})^n}\) 然后现在要求$p_k$

所以 \(p_k = \sum_{i=1}^{k-1}(\frac{a}{c})^{i}p_1+p_1\) 这也是一个等比数列求和 \(\therefore p_k = \frac{\frac{a}{c}(1-(\frac{a}{c})^{k-1})}{1-\frac{a}{c }} \times p_1+p_1\)

\(p_k=p_1\times \frac{1-\frac{a}{c }} {1-(\frac{a}{c})^k}\) 终于推出严格的数学证明了，中途合并消去的时候消漏了一个$p_1$，把我整惨了呜呜呜~~~

T2

模拟题，多用STL。没想到我的40复杂度错误做法居然A了ORz

T3

不可做

test20191112

没想到啊，今天真的爆零了Orz。

T1

如果我开它的话，我绝对可以A掉它。。。

T2

的确正解那个化式子的方式的确不好想，但是我写60分的暴力应该还是没有问题的，可是我为什么不写？

T3

这道屑题，我在考试的时候一个小地方卡起了，就一直死磕这道题，然后十点过的时候心态就完全奔溃了，整个考试都不想写了。其实这套题如果认真做的话，得分应该是：$100+60+60$的，就算T3大挂了，也有不错的分数，结果因为开错题爆零。 shit 最后一次考试居然以爆零收场