2018.8安师大附中游记

## Day ~~4294967295~~ 在车上对着书敲了一道线段树优化dp，然后洛谷没有、bzoj题目丢失...只好找了个标程对拍了一下。 晚上：不知道干嘛了。 ## Day 0 本来想干掉Splay的..结果好不容易把书看懂了又懒得写。颓炉石。 下午又见到了dew&达不溜勾whywhywhy两位奆佬。 晚上颓IG VS RNG & 奶粉的神仙连胜露娜冰法。 ## Day 1 死磕T2然后暴力没打满..然后惊奇的发现把暴力打满就可以rank3了（然而还是被@rushcheyo julao吊打）也不能这么说..毕竟还有正解写挂的，很多人暴力也没打满. ### T1 给n个点然后q个询问，每个询问给你一个点让你求它到n个点的切比雪夫距离之和。 切比雪夫距离转曼哈顿距离..[例题](https://www.luogu.org/problemnew/show/P3964)，第一次见，打了个52分暴力。  如图，转45°后的曼哈顿距离就是切比雪夫距离的 $\sqrt2$ 倍，而转45°是 $\begin{bmatrix}\frac{\sqrt2}{2}&\frac{\sqrt2}{2}\\-\frac{\sqrt2}{2}&\frac{\sqrt2}{2}\end{bmatrix}$ 所以直接转45°再缩小为$\frac{\sqrt2}{2}$倍，方便算，又直接转化成了曼哈顿距离。 即：$(x,y),(a,b)$的切比雪夫距离为$\left(\frac{x+y}{2},\frac{x-y}{2}\right),\left(\frac{a+b}{2},\frac{a-b}{2}\right)$的曼哈顿距离 反过来是一样的，$(x,y),(a,b)$的曼哈顿距离为$(x+y,x-y),(a+b,a-b)$的切比雪夫距离 ### T2 两种操作：区间修改为max和区间求小于x的最小k个数（其实就是判断小于x的有没有k个+输出区间最小的k个数） 毒瘤出题人给了个Segment tree Beats!.pdf，这分明就是骗我~~去补Angel Beats!~~用里面的毒瘤方法增加代码量，然后莫名其妙想了个线段树内嵌二分查找的做法，结果跑的比暴力还慢..估测了一下复杂度好像是$O(mlog^{logn}n)$的..最后竟然混到了7分。~~7KB代码被0.7KB暴力吊打~~ 然后这题其实完全用不到~~A~~STB，区间修改为max很好写，记录一下最小值位置，然后把[l,r]分成[l,pos)和(pos,r]塞进堆里，取出堆顶继续操作..好神仙的操作。 ### T3 正解二分图劈配.对劈配有阴影的我选择先跳过 ## Day 2 dewtql！！！177分被吊打Orz.我的172分15分因没时间调试炸掉，12分被特殊数据hack掉...起码比昨天好一些。 ### T1 木棍加工输出方案版.nlognLDS的时候每个数被放到哪就是答案了。 ### T2 计算方差+证明一个结论+[求覆盖特殊点矩形个数](https://www.luogu.org/problemnew/show/P2611)弱化版 $σ^2=\overline{x^2}-\overline{x}^2$或者说$E(x^2)-E^2(x)$，算是个简便运算的工具吧。 求覆盖特殊点矩形个数比较神仙..1e5的笛卡尔树就先不管了，~~出题人表示他写不出来~~，$O(n^2)$的也很神仙，点排个序然后枚举，枚举某个点只计算不含比它前的矩形，枚举过程中夹紧左右边界。 ### T3 出题人说这是一道Trie树+树状数组综合，完全在NOIP考查范围内，是一道好题..好像也没毛病。题解就不复述了，也很神仙。 总之Day1毒瘤Day2神仙 ## Day 3 Rank2，叒被@rushcheyo 虐了。 ### T1 $f(x)=$小于等于 $x$ 、与 $x$ 的 $gcd$ 为 $1$ 的非负整数之和的两倍除以这些数的个数。 求$\sum\limits_{i=1}^nf(i)$ 打表得到 $f(x)=x$... 因为 $gcd(a,b)=gcd(a-b,b)\quad(a>=b)$ ### T2 题面懒得说了，求个最小生成树，然后求个树的隔三遍历。 题解是说按深度奇偶前/后序遍历，和我的方法其实完全一样。 然而我考场上并没有想出这个构造方法... 考虑一颗子树，两种构造分别为以根为起点和以根为终点。对于当前子树的每一棵子树，用另一种方法构造。这样最大距离就是 $3$ 了。 ### T3 [lxctr竟然搬原题！](https://www.luogu.org/problemnew/show/P3477) 考场上打了25分..实际上至少35分是可做的，真的打满的话能到50分。 ## Day 4 最神仙的一次膜你赛..估分60实际175.T2提交前一分钟才发现getchar没判\n，然后手忙脚乱地把'.'打成了'*'，然后老师一直在催，就没交T2的80分。后来在吃饭的时候想到了100分做法。T1玄学乱搞做法30→75。[T3](https://www.luogu.org/problemnew/show/CF869E)$O(nmq/\sum\text{操作中矩形面积和})$暴力艹标算1s+70M。 ~~圣诞~~七夕前的乱搞膜你赛。 ### T1 给你 $f(1,[1,2n-1])$，$f(i,j)=mid(f(i-1,j-1),f(i-1,j),f(i-1,j+1))$，求$f(n,n)$ 二分答案，根据大小关系把数变成01，然后找规律。 这种套路以前倒是见过[一次](https://www.luogu.org/problemnew/show/P2824).. ### T2 先找规律，然后会转化成一个求最大（size）子矩阵。吃饭的时候想出来了$O(n^2)$求法，后来才知道这种做法已经烂大街了..上台口胡还被（轻）怼了. ### T3 二维树状数组+随机化，[原题](https://www.luogu.org/problemnew/show/CF869E)就不仔细说了. ## Day 6 ### T1 dp+组合数，其实挺简单的，没想到.. ### T2 并不是什么套路题..就不说了。 ### [T3](https://www.luogu.org/problemnew/show/P3502) 一个是当成大进制数 $O(n^2)$ 预处理 $O(1)$ 求子串hash，并以此来求最长前后重合部分 另一个是倍增floyd，可以视作重定义乘法运算的矩阵乘法 ## Day 7 ### T1 求个lca然后算一下就好了，然后我其它部分写对了，调了一个小时才发现自己有且仅有lca写错了...虽然说我确实在且仅在半年前写过两次lca ### [T2](https://blog.csdn.net/g19zwk/article/details/78322093) 有个dp做法..然而我乱搞贪心都不知道自己在做什么就过样例了QAQ这篇博客解释了为什么贪心是正确的. ### T3 ## Day 8 ### [T1](https://www.luogu.org/problemnew/show/P2860) 前一天说要考双连通分量，然后搜了下，随便找篇博客例题就是这道..然而我认为不会考原题就没做..然后就考了.. ### T2 按最大质因数分类+背包+状压，能想到其实不难.我写的40分算法打的表打表的时候就发现了每个表后端都是一样的，竟然没有试着乱搞一下数据分治，结果数据发下来一看，4种数据范围对应4个不同的答案.....最大那个就是大样例.. ### T3 树上什么什么的+2-SAT.20分暴力滚粗 ## Day 9 ### T1 div2A难度 ### T2 一开始样例出锅了，写完T3之后还没改过来，然后就写了T3dp.改过来之后看了下就是矩形覆盖，然后想都没想直接打了离散化+扫描线+线段树.然而前两个东西我都没打过，愉快地没调出来然后爆零。后来发现数据范围只有2000..其实不用线段树的..然而我觉得我多半是离散化写炸了。 后来跟rushcheyo说，他说可以动态开点.....我太菜了.. ### T3 贪心+堆（priority_queue），数据范围炸了，讲题的时候被直播改数组大小AC了.上次直播重测还是寒假在清北直播被卡掉20分... ## Day 10 ### T1 贪心送分题，rushcheyo神犇敲了个什么什么劈配..当时没听清 ### T2 数论题，打表发现长度为12的循环节，然后对拍一下，发现19*6错了？？？然后在excel里面仔细看了眼，发现并没有真正的循环节，而是每12/840/720720/144403552893600……各有循环，最大那个还没法对拍..幸好最后A了。 ### T3 毒瘤图论题，无限分类讨论，~~做p~~ ## 总结 见到了@rushcheyo 神犇 㕛见到了@wjyyy @威慑（dew） 两位奆佬 学到的套路大约都在上文了... 办了人生中第一场公开赛 …… …… $\vdots$ $\cdots$