题意如果一个序列中[l,r]里面的数，可以通过调整每个数的二进制位使得其异或和为0，那么这个[l,r]对就是good的，然后求有多少个这种[l,r]对，序列长度3e5。
一开始想dp，又是分位又是奇偶的，始终没搞出来。看了官方题解才发现判定一个[l,r]段是否为goog的充分必要条件只有两个，首先设bi为ai的二进制表示中的1的个数，则充要条件为：
① Σbi(l<=i<=r) 为偶数
② max(bi)<=Σbi(i!=index(max(bi)) 继续阅读“[暴力][分块][思维] CF 1030E Vasya and Good Sequences”
题意：给定n,m,k,要求在横坐标小于n纵坐标小于m的整点中找到一个三角形使得三角形面积为 n*m/k。一开始一直纠结于存在性。首先可以证明如果2*n*m%k!=0那么一定是NO。当满足这一条件的时候，可以把n*m/k上下拆分，把k拆成gcd(n,k)*(k/gcd(n,k))，然后上下约分就可得到一组ab，这时候如果后者和m不能完全约分说明分母里会剩下一个2（因为分子上*2是可以完全约分的），这时候ab就是答案的两条边因为不需要除2了。如果能完全约分则还需要在分子的a或者b上乘一个2，哪个小乘哪个就好了。为什么乘2不会超过原来的n或者m？因为我们这时候一定是n*m%k==0，而且题中k>=2，所以n和m至少有一个可以除一个2。
感觉做的时候问题主要在于无法验证正确性，但是后来发现k>=2这个条件是极其重要的。。。。没有这个条件就可能无解了 继续阅读“[几何][数学][思维] CF 1030D Vasya and Triangle”
还好没有鸽这场比赛，当时是做数模的最后几小时，我和lyq没办法只能让iSika单挑，期间顶着40小时没休息的脑袋帮他过了一个水题和一个计数递推形的dp，然后看看J过的人挺多，准备去看却发现脑子实在太疼根本读不完题，然后iSika说他大概能过那个B，然后我就不管了去瞎编数模论文。。。
没想到的是晚上肝完数模去打印论文的时候，掏出手机发现代哥给我发消息问去沈阳赛区不去。。当时其实本来已经累得要死了但是看到这个瞬间高潮了，简直哭了，真的好不容易得到的icpc现场赛机会。。。
然后我在队里小群兴高采烈地发消息结果半天没人回我，嗯友尽系列（都在睡觉吗朋友们？？
然后后来一直在忙微软俱乐部的面试，到现在在高铁上才有空去看这几场区域赛攒的题，先把这个J补了，当时以为复杂度不可取，实际上就是一lcm循环，而lcm里a或c的倍数的数量最多1e6，所以不会超时。需要分成三段处理，第一段是[0,lcm)，第二段是[lcm,k*lcm)，第三段是[k*lcm,t]，其中第二段的计算只需要算(k-1)*[lcm,2*lcm)就可以了，也就是说三段复杂度都是1e6。当然有几段还得根据t与lcm的相对大小来具体判断。之所以第一段和中间循环段分别考虑，就是因为一开始的条件是灯都是灭的，但是在第一个lcm循环结束之后灯光却有可能是亮的，所以需要特别考虑这种情况。最后把三段的答案加起来就得到了最后的答案。
继续阅读“[比赛][暴力][循环][复杂度分析] 2018 icpc 青岛网络赛 J Press the Button”
收获：
1 我以前一直疑惑set能不能边遍历边erase，现在看来是可以的，erase(it++)就可以
2 二维转一维的思想，经常使用。
比赛的时候一看计算几何直接跳过了，其实不是不可以做。。。
这个里面，各个草莓的半径其实对计算影响不大，由于圆的对称性，只要求出能覆盖s个草莓的圆心的最小圆就可以了，输出答案时加上草莓的半径r即可。
然后求定长圆的最大点覆盖就是有点模板了，有两种算法，n^3和n^2logn的，但是既然是抄板子那肯定是抄最快的了。。。
继续阅读“[比赛][二分][计算集合][定长圆最大点覆盖] 2018 ICPC 沈阳网络赛 E The cake is a lie”
比赛时候其实想的就是正解，但是没时间实现了。
这里并不是把猫狗分离开来，而是把voter分离开，换句话说原来的边变成了点，支持猫的在一边，支持狗的在另一边，如果有冲突的话连一条边，这样的话就是求最大独立集了。
本来看这个输入感觉头疼，后来想了想，忽然意识到：1 重复的人可以不用管，照例读入建立点，因为把他变成点之后对图没有任何影响。2 可以不用管字符后的数字，直接把他们当成一个整体就好了，整个字符串比较。 3 建立图的时候可以不用分左右两边，只要i和j有冲突就line[i][j]=line[j][i]=1；这样会使得建图的过程更简单，然后相当于把二分图对称了一下，最后输出的时候最大匹配数除以2就可以了.
先说结论：构造的方法就是以任意一个点开始dfs，对于dfs到的点，把他的颜色设置为没有在与他所有的相邻的已经被染过色的节点的颜色的集合中出现过的最小值，比如和它相邻有4个点，其中3个分别为1，3，3，另一个未染色，那么就把当前的颜色设置为2。
这个做法，网上并没有找到一个说得过去的证明，我自己也无法严格证明贪心过程的正确性，也没有找到官方题解，就是很玄学。而且，同样的贪心过程，如果先对一个点先dfs再染色，也就是根据子孙节点的颜色修改当前的颜色，就会出现某个节点大于k的情况（虽然仍然是保证了不同点之间不同染色），但是如果先染色再dfs，也就是先处理好搜索过的节点，根据祖先节点修改当前的节点，就能保证通过所有数据。
继续阅读“[思维][贪心] UVa1613 K-Graph Oddity”
题目最重要的是理解题意。。然后第二重要的是把原来的分散的点变成连续的：因为如果一开始的时候list上两个人就不相邻这时候最好就直接宣布了这个8g，因为这时候他们不会有任何一个人离开，这些操作之后也不用考虑了，这一步操作肯定的是最优的。
然后剩下的就是一块一块的被8g连起来的段，他们两两有一个8g，然后这时候可以用类似于矩阵链乘的算法，枚举第一次宣布的8g点，然后分成左右两块计算。max表示枚举断点取最大值，min表示顾客的想法：他们要让答案尽量小。
比赛时候一直想推通式，然而并没有成功，和队友两个人用两种思路推出来两个公式。。。然后最后得知答案的通式是分奇偶性的，每个公式正好对一半，呵呵。。。。。
就题目本意来讲应该是dp。先把圆环展开为链，然后考虑一个满足题意的局面，这时候最后一位客人的面具与第一位客人的面具的关系决定了这条链是否能形成符合要求的环。如果一开始用两个状态分别表示最后一位与第一位冲突以及最后一位与第一位不冲突的两种情况，则会发现无法继续往后转移，因为从n位摆到n+1位的方法数是会受到前一位与第一位是否相同的影响的，因此需要再加一个状态信息，三个状态信息分别表示，最后一位与第一位相同，最后一位与第一位冲突，既不相等也不冲突，三种情况下的方案数，写出状态转移方程即可。
比赛最后的时候三个人在看B和C，真的是紧张，根本看不懂题意，也不懂第二个样例怎么算出来的，今天看了看发现就完全是考的搜索，完 全 就 是 搜 索
能过了BC的话也算是有8个A了，没准可以进。。。可惜没如果，怪自己当时脑子进水，一脸懵逼。
两个dfs，第一个把对方知道的自己不知道的填充上，第二个把两个人都不知道的填充上，注意这里的题意，很坑，需要自己好好理解。可能是我写的太挫了，我这个码量有点大。。。
错误的话，排列写成了组合，wa了两发，意识到之后直接加了个阶乘。。懒癌。还有就是搜完一个填充点之后return之前要把那个点的状态复原。
