20210502总结

T1：手玩了几组样例发现对于长度为偶数的询问，答案全是0;对于奇数的询问答案是奇数位的数字的异或和，直接2颗线段树完事了。

T2：求一个 不同字母个数等于k的且不同字符出现次数都相同 的字串个数。拿到题自闭了从8：40到9：40除了个 O(\(n^2\)) 暴力几乎啥都没写，全在想，一开始思路错了，打算从出现次数入手，每种字符出现的位置都没任何联系，发现很难整，没法确定左右端点。然后打算单独想 subtask3 ，想枚举右端点，找左端点的个数。想了想感觉好难，9：40时突然想到对于一段合法的区间，他们的前缀和增加的量相同即 \(sum_a-sum_b=c\) ，码了一个 O(\(n\)) 的做法。然后想对于多维的该怎么做， $sum_a\pm sum_b\pm sum_c\pm\dots \pm sum_z $ 试了一些 \(\pm\) 号感觉都没啥联系啊，想了想发现做完差分以后，后 \(cnt-1\) 个东西相同（其实 \(sum_a-sum_b=c\) 就是最后一个差分相同）。然后写了一个hash拉链法就没了。最后忘取模了 \(100\rightarrow 70\) 。

T3：写完T2就10点17了，看了看题，感觉像一个区间dp，另外需要枚举一些左右端点的颜色。算了算复杂度 O(\(n^3\times3^6\)) ，笑死，根本过不去。打算试一下转移不枚举中间断点，从2边的一个转移，但是样例都过不去。想了想最低档暴力，不知道要换多少步，感觉趋近于 O(\(n!\)) 自闭了，直到现在都不知道题解为啥说小于 O(\(3^n\))。然后发现只用2种颜色的subtask3很好写，只要将1种颜色间隔放好，另一种也归位了。写完了以后发现没这一档的样例，手造了一个跑了跑发现没问题，但是没卡掉我，我计数器没清零。\(15\rightarrow0\)。

T4：(差点没看到)，看着 \(N\le6\) 感觉像个状压，一开始写了个线性筛分解质因数。看了看表11点了，先码了一个最裸的 O(\(c^p\times p\)) 的dfs，没想出来怎么优化判断是否有数字和你不互质，就没了。

这个T3感觉挺不好想的，看到 \(n\le400\) 思维只停留在了区间dp，dp还是练的不够。

T4的2次状压优化太神了，学到了学到了，（感觉其他地方用不上）。

T2又犯错误了，淦。