感觉清华集训的题目都好神啊...从策爷那儿搞到题解之后总算可以写几道了囧..

[12.25]这游戏好难啊...什么题都不会做

[12.26]人类何苦为难人类...还是坑掉吧

现在做了几题

6

【D1T1】玛里苟斯 如果把[tex]x_i[/tex]异或上[tex]x_j[/tex]，答案不会变化，所以可以先消元，最后得到至多[tex]\frac{64}{k}[/tex]个数，对于[tex]k \leq 2[/tex]可以求每一项对答案的贡献否则暴力就好了。爆long long实在是恶心吐了。

【D1T2】主旋律 计算不是强连通的子图有多少个，然后就是各种状压+容斥...好神的题...大致就是考虑计算缩点后的DAG的个数。

【D1T3】奇数国 良心送分题，计算区间出现过的数字集合以及区间乘积，用线段树就好了。

【D2T3】矩阵变换 一道有趣的贪心题，行尽量取靠前的数，如果出现冲突则把数归到他出现位置靠后的行中，另一个行从上次枚举的终点重新进行。

【D4T2】玄学 感觉这题不难？现场只有一个人A可能是因为现场的debuff？假设操作序列在最开始给定，那么很自然的想法就是对操作建线段树，然后每一个节点维护的是只考虑这些操作的有序值不同的区间段，如果有[tex]x[/tex]个操作，那么至多有[tex]\log x[/tex]段，建树的时候只要把两个儿子归并起来就好了，这样建树的复杂度是[tex]O(n \log n)[/tex]，然后询问只需要在每一个节点上面二分就好了，复杂度是[tex]O(n \log^2 n)[/tex]。有动态插入的话只需要开一个很大的线段树然后把一个节点建出来当且仅当它以及插满了。

【D3T1】sum 补了一下金斌的论文回头做了这道题。只要求出[tex]\lfloor i \sqrt r \rfloor[/tex]为奇数的个数就好了，这个可以转化为求[tex]\sum_{i=1}^n \lfloor i \sqrt r \rfloor- \sum_{i=1}^n 2 \lfloor \frac{i \sqrt r}{2} \rfloor[/tex]。然后用类欧几里得算法做就好了，注意卡精度要手写高精度（表示成[tex]\frac{a+b \sqrt r}{c}[/tex]）。