620
T1简单。
T3需要注意到n,q并不同阶。那么说明不预处理亏大了。
另外的，两种转化：
将 |a-b| 转化成枚举分界点或者说 \(\sum_{}pre_i\times suf_{i+1}\) 会不重不漏算出。
事实上你也可以直接把111,11111 异或一下看popc。\(5-3=popcount(11111\mathrm{xor}111)\).
真的要记住预处理。
621
先写博客在写代码是好习惯（不是）
如何评价？本来以为肯定爆蛋了，但是实际上要是把T1乞丐分写了也没太爆蛋/ch
还是想切题。。。这个T1好厉害，想不到呀。。。。。
6.22 写题解。。。
首先第一题。。。。暴力很简单。
实际上你可以观察到实际上我们每次枚举所有边会有很多不合法的。
所以可以想到对于部分分，设定阈值超过阈值的选最小的就好。这样容易得到 \(sn+n\log^2 n\) 的算法。
这是不够的，但是据说可以用法数据结构，分块等优化这个。
题解很巧妙呀（可能是很常见）。就是如果任意一边都没有到达这条边的一半，那么不可能选这条边。
但是我们每次枚举到一般这样的优化效果太有限了。
于是考虑实际上如果任意一条边到达了一半，那么把这条边减去delta后，一定除二。
所以我们可以动态维护每条边距离 \(w_i\) 的大小，如果和上一次更改比delta达到了一半，那么我们就 check 合不合法，合法就删掉，不合法就重新更新w，和delta。 \[ \begin{aligned} \frac{exp}{2}\le w_{now}-w_0\\ \frac{exp}{2}+w_0\le w_{now}\\ \end{aligned} \]
提一嘴，这个 \(lim\) 大于一半想说的是增加量大于一半。
如果当前做到了一条边的话，说明他的两边的增长量都小于 \(lim/2\)。
这样就很有道理了！。
第二题，构造题，题意很模糊
我们可以想到 \(\mathrm{1212}\) 这样的匹配可以让四个全部覆盖。
那么空位也可以很 naiive 的用一个匹配给盖住，这样就一定进不去了。
被盖住的里面的我们让他们互相匹配。
剩下的用 \(\mathrm{1212}\) 就好。
这个当然是充分的，但是不必要。也就是说我们不能把这样构造不出来的就 -1。
于是很自然能想到，我们不能构造出来的只有一种情况也就是剩下的 \(\bmod4 = 2\) 的
我们观察，可以发现 \(\mathrm{123132}\) 这样的可以让我们原先不合法的，给出合法构造。
于是把这个和上述构造方法拼起来就行了。
具体的我们找到一对相邻的“极长的空位”，然后把他们外面，里面两两匹配，然后把左面开始的pre匹配到右面开始的pre。
结束了。
给出一个（两个结论）都不会证，会口胡其中一个。
首先是有限小数，结论是每次选二进制小数的lowbit。
为什么？选一次 \(S\) 肯定是不优于 选两次 \(A|B=S\) 的。李子豪说对就对。
那为啥是Low Bit ，因为如果不选 low 那么选比low高的不管寄不寄都选不了这位了，那就浪费了。
容易得到dp。 \[ \begin{aligned} \mathrm{dp}[i][0]=\mathrm{dp[i-1][1]}+hdqijwoijvoihjvaoivsa\\ \mathrm{dp}[i][1]=\mathrm{dp[i-1][1]}+hdqijwoijvoihjvaoivsa \end{aligned} \] 不管具体是啥了，反正是\(i-1\) 的线性组合，可以写成矩阵。
无穷小数，因为有理一定有循环节。
那么实际上只需要求出循环节矩阵的无线次幂的收敛结果，就能转移了。
那就解方程 \(CB=C\) \(C\) 不满秩，解方程。
应该能做。
ls告诉我可以把线性变换看成函数复合。。。。。。
然后就写成 \(kx+b\) 一次函数一直复合，显然复合后还是一次函数。
那么变成了有理数无穷级数，也可以做。
ljs告诉我实际上决策是不需要管每次递增的。
随机决策有如下结论，如果小于一半all in 。否则赌 \(1-x\) 。
不知道为啥对。你妈的
这样你会发现 \(a/b\) 块钱，我们只会选 \(x/b\) 的赌，可以整数 \(\mathrm{dp}\) 真牛逼。
<<<<<<< Updated upstream
补。
7.1号
T1 写的 50实际上这个东西的决策会被分为子问题。所以可SG。
T2 实数题，很离谱。。就挺普通的 \(f_{s,i,sum}\) 这样 dp 可以做到 \(O(2^nm^2n)\)，但是这样是过不去的。。。
实际上这dp的\(sum\) 想想都没啥大用，所以直接去掉一维，含义变成从前面没选的选出选出减去。
剩下的就是EGF的卷积。
T3不是很会。
7.4
T1 直接求出后缀数组二分哈希。。。。
这样的话复杂度是2log的，需要单哈希不取模卡一卡。
但是可能需要注意啥二分上界 ，无解判断。
特别的。哈希不能将a的值设成0，负责aaaa和a完全一样了！！
不是很懂T2润润润
T3 \[ f_i=1/2 f_{i-1} + 1/4f_{i-2}+1/8f_{i-3}\\ 1+\frac{1}{2}+\frac{1}{4}+\cdots+\frac{}{} \] ======= -----------------------------
咕咕咕了几天的？
7-1
T1 我没发现奇偶互不影响/kk,然后对于一个颜色实际上就是分成子问题，这样可以SG加法了。
要是真想做出来就，这种没有明确策略的博弈一定要想一想能不能SG和。。。。
T2 感觉是厉害题，考场时候写了个 \(O(2^nm^2n)\) 的WA+TLE了。/。。。。。。
实际上还好，，，，，首先能想到这个人运气很差，一个都打不死的概率，这个大概就是有上界背包，实际上EGF二项卷积就好。
这个是极其容易计算的。。。。
这样就不难想到把杀死的和活下来的分开考虑。这样我们记录死了的状态，沿着\(m\) 一个一个填入。
多 \(m\) 的做法是设状态 \(dp_{sta,sum}\) 表示我们能打 \(sum\) 次，（能打死人），并且 sta 这些人全死了。
转移平凡 \(2^nm^2n\) ，然后我们只需要 \(dp_{sta,0}\) 和EGF 乘起来就行。
这样你会发现实际上你这个 \(sum\) 描述的不是很清楚，并且最后只需要一项的值，那不妨考虑删去 \(sum\) 维，你发现实际上我们没必要钦定他呀。
T3 咕咕咕
7.4的T1 是个简单字符串题，这个拼接实际上就可以直接二分哈希了。
这样2log需要卡常， >>>>>>> Stashed changes