马上就要FJOI二试和CTSC了。然而FJOI二试迷之延时至下旬。CTSC就是下个月的事情。比较紧张。
51nod算法马拉松23
这场比赛做得很不及时。
4月1日听到同学讨论才想起有51nod比赛，然后点进去看已经有9个AK了……赚钱基本是没戏了。那就试着做一下呗。点进去第一题，觉得是结论题，然后自信有解就把 $x=\frac{\pi}{6}$ 代入，直接找出循环节，然后写了几个 if 不检查直接交就A掉了……挺送分。那么再看第二题，好像推个式子就行了然而 $m\le 10^7$？输入有点爆炸唉我先码个输入优化，码码码，OK了，然后推了个 $\frac{1}{m}\sum_ia_i$ 的式子交上去结果只过了第一个点……囧……
这么短代码要错肯定是结论错咯。看下题发现题意理解错，每次生成都要加进答案，再推了一波让人难以置信的是答案居然和输入的 $a_i$ 无关。。。？？？然后读入两个 $n,m$ 输出 $\frac{n(n-1)}{2m}$ 就过了？就过了？输入优化都没删。。。怎么都是纯数学题啊2333【讲道理这种题出在数学考试都是可以的
然后看第三题，一开始理解错以为要枚举小的对大的分段，好像还得分块，还不能处理图的情况，觉得做不了。immortalCO问我答案是不是就是次大值，我当时想到某道CF题觉得不太可能吧看了下那道CF题，发现一个条件 $a_i > a_j$。。。靠，读错题了。那看来真的是严格次大值无误。然而想了很久还是搞不清楚怎么对每个点 $v$ 求能到 $v$ 的点权中比 $v$ 的值小的最大值，好难啊先扔了。
这时候dick32165401他们好像在刚D题，就去看D。
一开始觉得状态要记原点到6个点的最短路，这样状态数至少 $O(m^6)$ 了……思考了一会儿明白了相邻两格最短路差不超过1，那就是 $100^2\times 3^5$ 级别的状态数了挺能接受，转移的时候就枚举下一列的状态，总共 $100^2\times 3^5\times 2^6$ 好像能过，就写了一会儿写完了。交上去WA掉。发现 $n,m$ 又打反，尼玛我怎么老是犯这种毛病啊QAQ第二次就过了。
这时候好像有10人AK了。惨。
E题一开始想分治之类的东西结果毫无进展，一定是我想复杂了。然后看着式子联想到一道自己出过（其实是我出完以后在BZOJ看到一模一样的题）的区间逆序数，好像只能分块搞，不过这题离线所以写个莫队+BIT好像能卡过去……然后写了一会儿写出来，接着你们懂的本SB又是过了样例WA飞了，为啥？immortalCO：你输出的时候 unsigned long long 开了没？我：没……
感觉正式比赛出这种情况就真的毁前途。看F。一开始想了想暴力怎么写，然后写完交上去想验证暴力正确性结果除了第一个点全是大数据，我去。。。不过样例和第一个点过了应该就没错了。接着开始用莫比乌斯反演推式子，推了一会儿推出一个 $\sum_{i=1}^n\sum_{j=1}^n[(i,j)=1]$ 状物，我想这应该就是 $2\varphi(n)-1$ 吧，验证了下好像是对的。接着式子就变成了分段求区间次大因数和以及区间 $\varphi$ 和，后一个好像有原题上个杜教筛容斥就行，$O(n^\frac{2}{3})$，问题是前一个怎么求不是很会= =
然后想暴力该怎么写，就是埃氏筛法，好像和筛法函数长得很像？接着就开始推筛法函数的DP，推了几步发现中间某一步要求 $\sum_{i=1}^ni^K$，$n$ 又很大，好像只能强上插值了……于是目前的想法是“插值+容斥+DP”三合一，感觉会很难写很难调。
然而好像拉格朗日插值没逆元，还是写 $O(K^2)$ 的牛顿插值吧，然而并不会牛顿插值的式子，上网搜了一堆资料结果半懂不懂的，决定自己推，然后推对了……RP不错，接着开始写，写完一测发现萎了。。。怎么回事？调调调。。。卧槽我的方法用到了除以阶乘然而阶乘不一定有逆元，日。。。
最后还是只好质因数分解保平安了2333写完以后开始写容斥求 $\varphi(x)$ 前缀和，由于一开始忘记预处理 $\varphi(1)=1$ 导致怎么都是错，也费了好多时间。终于开始写筛法函数了，一开始还把定义搞错把质数也筛掉了，后来觉得不妙才改了，然而还是出一堆问题。接着两三个小时发现一堆bug，一个个改完以后终于过样例了，然后第一个点WA了，又调了一下发现丢了一个 pow。
结局是艰难地过掉了F。。。感觉这种难度的题我还得折腾这么久我这迟早要完啊。。。
然后C还是不会做。。。4月2日起来继续想，想了很久一直往强连通分量去想，结果不知道怎么提取第一个比自己小的权值，还是做不出来。最后想出枚举权值区间floodfill再把这个权值的点去掉，求出每个点能到达它的不等于自己的最大权值，又想想觉得不对= =于是改成floodfill搞出每个点能到达它的最大和次大权值，这样就靠谱了。于是12点多把C题过了。论最后想出来的是C题是一种怎样的体验2333
最后rank14 GG，可能我早点开始打也不太能进前10。
看完题解之后
C题原来缩强连通分量以后直接递推一发就做完了，不知道我当时在想什么
E题分块做好像就能不带log了，当然莫队把BIT换成分块维护好像也能优化掉log（不过好像更难写就懒得优化了）
F题居然可以多设几个函数来搞，不用插值了……不过不知道常数会不会大
集训队互测 Round 1
开场看T1，感觉得推什么复杂的式子，不知道有没结论，于是先写个随机模拟打个表再说，然后发现 $k=1$ 时答案全是 $0$。看下子任务居然有 $k\le 1$ 的部分分，难道是我写错了？再看 $k=2$ 的，发现是 $\frac{m(n-1)}{n^2}$，这个应该有分……好我写一写，交。
交上去居然是 Invisible，这不科学啊一定是OJ的问题……于是OJ修了一会儿看到结果，才5分= =然而怎么右边显示了标准输出？趁着工作人员修OJ的时候调代码，然后发现期望忘记除以方案总数了。。。接着又看了看表看出 $k=3$ 是 $\frac{m(n-1)(n-2)}{n^3}$ 感觉挺稳，觉得答案应该就是 $\frac{m(n-1)(n-2)\cdots(n-k+1)}{n^k}$，接着发现 $k\ge 4$ 就挂了……
算了先交 $k=3$。看到得了45分就放心了。然后试着推通用的式子，然而每次计算是 $O(m)$ 的，而且怎么都化简不了。先放一边。
接着去看T2，这题不出意外一定是JOHNKRAM的题，联想到WC时的仙人掌计数……已经不打算想正解了，那就写 $O(n^2)$ 吧。
推了一下好像得预处理 $i$ 个点的强连通图个数？然后就开始想，想到后面以为只要求这个了，又想到清华集训2014的主旋律，然而我并没有A。。。然后又是线上比赛，不如找一份std对着写？点开以后意识到问题并不是这么简单……
继续推，发现主旋律做法还是有用的，然而接着处于掉坑状态，想了非常久还是没想出怎么做。后来干脆考虑每种图会被枚举到多少次，接着就好像会 $O(n^2)$ 了，只要DP出每种点数的和合法图个数，然后枚举源点集合大小加起来就是答案了。
写到210min的时候终于写完，居然对了。70分到手，有点开心。
最后看T3，好像是个比较麻烦的题，感觉我不可能做出来了，就写了个15分暴力交上去。交完以后发现 $K\le 5000$ 可以离散化啊= =就写了离散化交上去，发现前面WA掉了。。。原来是数组开小了2333
改完以后想多捞点分，就想 $q=0$ 可不可做，似乎只要找出每一列最后一次被染色的时刻然后按这个顺序做一遍，不需要什么复杂的数据结构就搞定了，不过不太确定能否写对。不过还是试着写写吧……
最后10min终于调过样例，交上去。后来看到自己这题得了50分，挺满意的了。
然后还想rush一下T1的另外15分，结果没时间了。
最后45+70+50=165，出榜以后发现我这一堆暴力加起来居然有rank 2……有点爽。再看下其他人，好多大爷都是刚某道题没时间做别的题，然后送了我这个机会……所以我实力还是不行的。
看完题解之后
xumingkuan的T1好神奇啊。题解里讲了“有可能出现的情况是找出 $k=3$ 的答案公式，与 $k=2$ 时的答案公式形式相似，试图推出一个普适的规律，然而发现 $k=4$ 时这个规律就挂了”，这不就是我的情况吗2333
也许学过stirling相关知识这题就能多做一些分？我的姿势水平还需要提高。。。
JOHNKRAM的T2我可能需要多花一些时间理解。
zsyzssoft的T3可能细节偏多？然而场上2人AC，可能我还是没跟上大家的水平啊。
集训队互测 Round 2
还是开场看T1，以为直接状压就行了，结果 $O(3^nn^2)$ 写完一交才4分，好气啊，暴力分真少。优化一发，好像只要考虑包含某个点的集合就行了，再交，20分。分数这么低一定是我想偏了。
然后发现这题 $p=17$ 居然是给出的，一定是有什么很妙的算法，想到了Codechef的BIKE。那就只要一开始把所有式子DFT一下，乘的时候只要 $O(p)$，最后IDFT回来就行了。不过不太确定能否AC。
当然由于时间效率是 $3^{16}\times 17=7.3\times 10^8$，$3\texttt{s}$ 还是跑出来了……$O(3^np)$ 能过看来这题肯定大家都会。接着看T2。
然后就说明了我有多弱……一开始没注意到对 $M$ 取模，然后觉得好像可以网络流，正在想怎么建图的时候发现了要对 $M$ 取模，于是瞬间不会了。原本想二分贪心，结果发现二分也是错的。脑补了好几种贪心，结果全是错的，然后一点思路都没有了。
接着放弃T2去想T3了。一开始觉得条件有点复杂，不过如果枚举了 $m$ 就可以压位高斯消元了，$O(\frac{n^4}{w})$，这大概有30分。不过要跑 $n$ 次高斯消元，可能我有些性质没用上？
于是仔细分析了一下性质，发现 $m$ 每增加 $1$，就少一个约束，多一个变量，好像处理起来不方便。如果 $m$ 减少 $1$，就多一个约束，少一个变量，直接把最后一列删掉，然后用前面的行消这一行，这样复杂度就优化到 $O(\frac{n^3}{w})$ 了？不知道能不能60分的说。。。
接着开始写，写了挺久的，写完过了两个样例交上去，一直Waiting，就继续想第二题，还是没想出来。
测出来了，0分。点进去一看，全都是WA和TLE。
样例怎么这么弱啊，怎么过了两个样例都能爆0。。。难道是系统差？自定义测试一发，过了。
那肯定是我写挂了。写了个 $O(2^nn^2)$ 暴力拍，拍了一会儿拍出一个问题，改完以后过了对拍。交。继续想第二题，还是没想出来。
测出来了，0分。点进去一看，全都是WA和TLE。
这就尴尬了……无论如何都拍不出错怎么交上去就是0分？难道是我题目理解错了？
把 $O(2^nn^2)$ 暴力特判 if(n>20)return 0; 交上去。
测出来了，0分。点进去一看，全都是WA，而且都是0s。不可能跑这么快啊？难道是……数据……犹豫了一会儿把暴力的 gets(a) 换成 scanf("%s",a)，交上去，10分了。估计是毛爷爷用Windows造的数据导致文件末有多余字符 gets 会挂，惨啊= =
再把原来的代码交上去，40分，中间TLE了。好像被卡常数了，开始优化。接着发现我数组开的 $50000\times 782$ 于是 memcpy 炸复杂度了……改完交了两发（有一发优化错了）一共经过7次提交终于过60分了，真是艰难。
最后1个多小时继续刚T2，然而除了 $K=1$ 的特判和答案小于 $M$ 的网络流以外都不会，我好菜啊……最后还是写了这两档一共25分，然而不明原因得了40分，而且9~11测试点还是WA的。好玄学，不过也没时间做什么了。
结果是GG了，100+40+60=200，rank 7。一看怎么大家都会T2，惨啊……果然T1大家都会，T3也有很多60。
于是就成了T2最低分选手。。。我做的题还是太少啊。。。
看完题解之后
cy的T1正解是 $O(2^nn^2p)$ 的，好像比较麻烦。。。（反正我没去想就是了）不过似乎 $3^{17-1}$ 和 $2^{17}\times 17^2$ 运行效率差不多的样子？
yjqqqaq表示他的T2是NOI第一题难度，想想我NOI2016 D2T1的分数……
T2正解是贪心+结论，最后一步用数据结构优化。然而我不仅没看出只要判断连续 $K$ 个数的结论，还没看出有解时答案为最大值的结论，更没有看出答案不超过 $2M$……可以说我是完全不会。另外好像直接输出最大值好像就有很多分？？？
matthew99的T3竟然真的是WC讲的Berlekamp-Massey算法……yyt16384 AC了好劲啊。
有空的时候我也学一学这个算法。
Codechef APRIL17
难得参加了一场Codechef。感觉这场比往常的都水啊，最后都是比谁Challenge分数高。
除了最后一题以外几乎是倒着往前做的。
Chef and Digits（DGTCNT）
一眼看觉得是个数位DP？仔细看下，原来是带了 $10$ 个约束的计数，约束这么少感觉容斥一波就行了= =先把 $[L,R]$ 转成 $[1,R+1)$ 和 $[1,L)$ 的差，求 $[1,N)$ 有多少个 $x$ 满足时，枚举 $x$ 和 $N$ 的LCP和第一个不同的数，然后容斥，枚举数字集合 $S$，要求 $\forall i\in S$，$i$ 在 $x$ 中恰好出现 $a_i$ 次，组合数算算就好，再乘上 $(-1)^{|S|}$ 就行了？于是一下子码完，肉眼调了几个SB错误，就过了第一个样例。
然后第二个样例一直过不去。自己出了几组小数据都没问题。
对着代码想了好一会儿终于发现哪里错了，我的做法假设 $x$ 和 $N$ 位数相同，于是把前导零算进去了！改……先强制最高位不能是 $0$……然后把之前的代码强制复制一遍，枚举一下 $x$ 的长度再搞搞……
然后过了两个样例，用暴力和正解拍了几组大数据就交了，一发AC。爽。
Bear and Random Grid（RNDGRID）
点进来就看到数据随机生成，题意大概是给一个有障碍的矩阵和一个操作序列，求从每个格子出发按这个操作序列走第一次碰到障碍或出界的时刻，粗略感觉随机走的话走几步就碰到障碍了，于是直接模拟2333然后发现不对劲，如果矩阵是空的就挂了- -
再想想这个做法期望复杂度是 $O(\frac{N^2}{P})$，$P$ 小的时候会跪。
不过 $P=0$ 的话没有障碍，就可以预处理每个点第一次出界的时刻。那么 $P$ 很小做法应该也类似。又想了想就明白只要对每个障碍和每个 $i$ 找出从哪个点出发走操作序列长度为 $i$ 的前缀能到它就能更新答案了，这么搞复杂度是 $O(N^2PL)$。
那就把 $P$ 以 $\frac{1}{\sqrt L}$ 分界一下就能做到期望 $O(N^2\sqrt L)$……然而我本机上调参用的是二分，于是二分出 $P=1.2\%$ 两个做法都是 $3.8\texttt{s}$ 左右，好像可以过就交了……
事实证明Codechef的运行效率比本机快得多，交上去一个点还不到 $1\texttt{s}$ 就AC了。
Stable market（SMARKET）
首先想到了游程编码一发，然后问一个区间的时候把两个端点所在的段取出来，判一判是否大于等于 $k$，查一下区间里有多少个不小于 $k$ 的段就行了吧。
整个思路无比显然。。查区间不小于 $k$ 的数先想到了可持久化线段树，然后发现这题可以离线，就用个BiT搞= =挺好写的。
然而我居然TLE了一发。。。？？什么鬼，原来是数组忘清空了= =b想到去年NOI有些大佬D1T1本来高我5分因为这个错误炸成比我少85分感觉我还是RP选手= =
Chef and Divisor Tree（CHEFDIV）
一看 $B-A < 10^5$ 就知道可以枚举整数 $n\in[A,B]$ 然后求 $n$ 的答案 $f(n)$，一开始打了个表没看出熟悉的东西，就质因数分解一下 $n=\prod_{i=0}^{k-1}p_i^{c_i}$，$f(n)$ 就是每次把一个正的 $c_i$ 减掉 $1$，过程中 $\prod_{i=0}^{k-1}(1+c_i)$ 的和。联想到自己以前给NOIP组出的一道题就猜了个结论每次找个最大的 $c_i$ 减，再用之前打的表验证了一下感觉没问题。
然后懒得优化直接写了个 $O((B-A)\log^2B)$（可能有更好的上界？反正跑的挺快），结果过完样例交上去后面的点挂了。然后发现我犯了两个错误，一个是存质因数的数组用了 int，于是用 $\sqrt n$ 以内的质数分解完以后如果大于 $1$ 再把剩下的数加进数组就溢出了……另一个就不说了
for(int i=2;i<1000;i++)if(!a[i]){ // 于是1000~1000000的质数都没被考虑进去
for(int j=i*i;j<=1000000;j+=i)a[j]=1;
for(long long j=(L+i-1)/i<i?i*i:(L+i-1)/i*i;j<=R;j+=i)f[j-L][c[j-L]++]=i;
}
改完两个bug过了……
Bear and Clique Distances（CLIQUED）
把团上的点和一个附加结点都连上边以后就是裸的最短路咯，写写写，写完了，测样例，过了，交，AC。
Bear and Row 01（ROWSOLD）
一开始看错题以为是最小化的SB题，再想想原来是最大化，不过好像也很简单，猜个结论每次把最左边能右移的右移，好像没错，试试，写完，测样例，过了，交，AC。
Dish Of Life（DISHLIFE）
水水的模拟，先统计每个数出现次数，有 $0$ 次就是 sad，没有的话枚举删哪一个看看有没哪个次数会变 $0$。偷懒直接上了 vector。
Similar Dishes（SIMDISH）
水水的模拟，然而偷懒直接上了 string、sort、lower_bound、upper_bound。
Heavy-Light Decomposition（HLD）
终于来做最后一题了，不过比想象中要简单。
一开始瞎猜了几个贪心，每次取个深度最大的连重链，然后凭借多年写树链剖分的经验这样只要弄一条链然后从下往上依次在每个点挂长度为 $1,2,3,\cdots$ 的链就能叉掉。又猜是不是按子树大小贪心，发现在某个结点上瞎挂一堆叶结点就能卡掉。看来直接贪心会炸。
那就树形DP。一开始的想法是记 $f(i,j)$ 为 $i$ 上方的重链长度为 $j$，$i$ 子树内的最大cost。转移的时候枚举重链连向哪个子结点，好像能转移。一看数据范围 $N\le 100,000$……
于是又在想更靠谱的状态设计，如果 $j$ 改成定义为 $i$ 下方的重链长度呢？如果能够不遍历深度最大的子结点的DP数组复杂度就对了。链的长度怎么搞呢？那就令距离链的顶端 $1,2,3,5,9,\cdots,2^i+1$ 的重边和所有轻边长度为1，其它为0。接着开始想递推方程。
如果所有子结点 $c_1,c_2,\cdots,c_k$ 中，重链连的是 $c_m$，那么
$$f(i,j)=\max\{g(c_1),g(c_2),\cdots,f'(c_m,j-1)+[d=1\lor\exists k\in\mathrm{N},d=2^k+1],\cdots,g(c_k)\}$$
其中 $g(i)=\max\{f(i,j)\}$。至于 $f'$ 呢，是个好像有后效性的玩意。。。不太好做？
看了下AC人数感觉这题肯定不难，一定是我没想到点子上。
脑补了一下，发现 $c_m$ 肯定是 $g$ 值最大的子结点，那么只要记 $g(c_1),\cdots,g(c_k)$ 中的最大值 $g(c_m)$ 和次大值 $v$ 就OK了，一边DFS一边方案就确定了，$j$ 这一维都不需要了。接着就只剩快速计算 $i$ 到 $m$ 子树的点 $v$ 的最大cost了，因为只有当 $v$ 往上第一次到 $i$ 所在重链到达的点到 $i$ 的cost是 $1,2,3,5,9,\cdots$ 的时候才会加1，所以只要每个点 $i$ 维护这个点往下的轻边子树到它的最大深度 $d_i$，然后把 $O(\log n)$ 个点 $d_i$ 加1，就解决了。
看起来确实挺简单，就开始码了。因为懒得写不定长数组所以用了 vector，不过空间复杂度是 $O(n)$ 的，不虚。过样例就一遍AC了挺开心。
(CH) Serejs and Billiards（SEABIL）
体现我近似算法水平低的时候到了。
看完题，先想分数为正的有什么好的搞法，一开始想把球一个个打进洞，这样步数上界是 $2M$ 的。在想能不能先把球打到对角线上，然后一次全打进洞，就想到每列打一次把这一列的球全打到主对角线上，再把所有球一次打进洞，步数上界 $N+1$，不错的样子。写完得了60分。
再搞搞分数有负数的吧，感受了下如果不考虑球的分数正负的话实际得分期望是负的，不爽，得把负的都搞掉。然而把负的打到一个边角可能会把影响正的，经过思考，打算这么构造：负的球打到相邻偶数列，正的球打到相邻奇数列，接着把正的打到对角线上，再一次打进洞。这样步数上界期望大概 $\frac{M+N}{2}$ 吧，好像没什么优化余地了，就写了。
写完一交得了98.5分，以为这分数应该不错，结果一看榜怎么全是99+分的。。。GG。。。
最后1h还是没能搞出更高的分。。。最后rank 24滚粗，再见。。。
集训队互测 Round 3（围观）
因为这场由immortalCO、fateice和我出题，所以我不是参赛者而是观察者……
我出的是T3，一道槽点一大堆的提交答案题。
其实也没什么想说的吧。当然这场被很多人当成辣鸡比赛= =
不少人整场疯狂交T2（10个点，时限8s的题），有一段时间评测队列卡了五六个Waiting，卡评测严重。主要原因是这题 $n\le 20,000$，数据组数 $t\le 5$，$\sum n\le 70,000$，于是大家都想用 $O(n^2)$ 卡常数过掉……
由于我的T3下发的checker直接告诉了分数，于是大家不怎么提交，一般都是最后再交。不过悲催的是yyt16384最后没交上去，惨。。。
最后就是我的题估分大爆炸。当时给fateice验题的时候，fateice一小时做了6个点，当时还觉得现场好几个小时大家应该很容易上60的，结果。。。没人上60。。。【一定是fateice太强啦！
不知道会不会给人一种“FJ卡常队”的印象……去年AKF的集训队互测也有人被卡常数，今年呢，T1没人写正解就不说了，T2卡常数，T3也有人被卡了常数……T3 57分（最高分）xumingkuan有的点被卡了些结点个数的常数，于是少了点分，惨……
选个时间把这场放到UOJ上让大家玩一玩？
集训队互测 Round 4
开场看了下三题，觉得T1好像很可做，先跑一遍Manacher在每次指针右移的时候记下区间，就可以转化成每次询问右下角有多少个点。。。开始写的时候突然发现这个做法是错的。。。
然后开始fix，脑补了各种回文串的性质无果；转成后缀数组的每个后缀维护一个集合，区间插入一个数，发现集合难合并；考虑维护所有不同回文串的最左出现位置，不断删第一个字母，看起来很靠谱结果复杂度是错的……总之一共想了2个多小时还是一无所获。哎。
算了去想后面的题，第二题一开始想到 $[a,b]$ 的一个左子结点 $[a,c]$ 被覆盖的条件是 $l\le a\le c\le r < b$，写了个暴力交上去只有10分，原来我 $type=0$ 的也异或上一次答案了。。。算了我想想稍微不暴力点的做法。
发现这是个三维偏序，不资磁！不过 $a\le b < c$ 是个好性质，我们转化一下，答案是满足 $1\le a\le c\le r$ 的个数减去满足 $1\le a\le b\le r$ 的个数，再转化一下就是区间长度（$r-l+1$）减去 $l\le a\le b\le r$ 的非叶结点 $[a,b]$ 个数，就变成了二维偏序了。写了一下发现结论没错，好像能做。
然而又要在线又要带修改……强上两个log吧。线段树套线段树？不资磁，空间是 $O(n\log^2 n)$ 的。那就线段树套……平衡树？虽然时间还是 $O(n\log^2n)$ 但空间只有 $O(n\log n)$ 了，效果也许不错？
于是就陷入了深坑。
15点多开始线段树套平衡树，到16点半的时候调出来了，交上去，60分。一看，被卡了8个点的内存。
惨。
我就在想，$64\texttt{MB}$ 可以开 $1.6\times 10^7$ 个 int，$200000\times 20$ 个结点，每个节点大概长这样：
struct snode{
int val,siz;
snode*fa,*ch[2];
};
如果每个节点是 $8$ 个 int 大小，那就起码 $128\texttt{MB}$，有点崩。然而明明只要查后缀区间为什么要写线段树？写个树状数组就行了啊期望还能省一半内存= =
于是又花了20多分钟改成了树状数组套平衡树，交上去，还是60分。。。
想了好久还是不知道怎么优化。至今不明白为什么连 $64\texttt{MB}$ 都卡不进去。
一看比赛只剩1h了，得赶紧写掉剩下两题暴力。
于是先写了T3的 $O(n\min\{n,m\})$ 暴力，一开始写错了一次，调了一会儿过了35。
又写了T1的 $O(n^2\log n+qn\log n)$ 暴力，20分。
最后又想多rush T3的分又想优化T2的内存，结果都没成功。
于是20+60+35=115滚粗。。。T2一堆100，只有我一个60。。。然而T2分这么低居然还有rank 4。。。
immortalCO T2标算AC，太强啦！
fateice T2神奇算法AC，太强啦！
看完题解之后
philipsweng的T1正解是回文树+分块，然而我不会回文树，哎我怎么这么菜啊
srwudi的T2确实带给选手们无与伦比的卡内存做题体验啊……不过说到底还是我自己的问题，我还！是！不！会！分！析！问！题！性！质！推了个二维偏序就不管了，最后GG……
线段树结点和普通区间相比有明显的规律啊，覆盖区间的结点一定是一段递增一段递减，然而我怎么就把问题给一般化了，问题一般化就丢性质了。。。immortalCO教导得是啊。
yyt16384的T3看起来不可做，当然也可能是我太弱了。
集训队互测 Round 5
血崩。
由于晚上熬夜出题，状态不好，看到题啥思路都没有。于是想想T1，好像是后缀自动机，然而我不会，于是写了后缀Trie的35分。又想想T2，好像可以FWT，结果细节考虑不清楚，怎么都是错的，最后调来调去弄了30分，不知道为什么2、3过了4没过。然后又去看T3，觉得是三合一的恶心题，没啥写的欲望。然后花了很久才写掉了第一个subtask。回头准备试着写SAM，然而考场上确实不应该写不熟悉的算法，还是放弃了。T2感觉造数据很麻烦，就盯着代码看，没看出问题。。。GG。。。T3的第二个subtask好像可以均摊搞搞，写着写着开始怀疑人生，觉得复杂度爆炸，于是不写了。。。最后还是把subtask3的裸暴力写了，然而前面的点莫名其妙地WA了，又没法Rejudge，就只剩25分了。
结果#9滚大粗。。。35+30+25=90。。。膜immortalCO 170分#1。
最后一次互测考成这样我对自己已经没什么信心了。大概我就只有rank 9的水平吧。况且最近也没时间刷题了，只能CTSC坐等GG同时围观immortalCO怒拿rank 1进国家队了。
看完题解之后
SkyDec的T1是继sone3之后的又一道神字符串题，不想做。然而把我的后缀Trie换成后缀自动机就有60分了啊……我一定要想办法学会后缀自动机。
qiaoranliqu的T2感觉自己状态好的话完全是可以想出来的，因为我前段时间学过FWT了。。。然而自己傻逼到盯着50分一直码写挂了还懒得调感觉我心态实在太糟糕。。。（也可能是晚上睡太少了）
sunyaofeng的T3后两个subtask正解好复杂啊，可是immortalCO说敢写暴力就能AC，orz……我纠结了好久的错误复杂度光荣滚粗……
FJOI2017 二试
一场挂得心碎的省选。
http://wronganswer.blog.uoj.ac/blog/2565
NOIP和省选一试优势全部浪没。失去了所有对好成绩的梦想。
51nod算法马拉松24
见另外的博客。
又好久没打Codeforces了，CTSC前如果有不在半夜的CF还是挺想打一打的。尽管打了有可能掉rating，但不掉rating怎么涨rating？
鄂公网安备 42010202000505 号