题意如果一个序列中[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”
先说结论：构造的方法就是以任意一个点开始dfs，对于dfs到的点，把他的颜色设置为没有在与他所有的相邻的已经被染过色的节点的颜色的集合中出现过的最小值，比如和它相邻有4个点，其中3个分别为1，3，3，另一个未染色，那么就把当前的颜色设置为2。
这个做法，网上并没有找到一个说得过去的证明，我自己也无法严格证明贪心过程的正确性，也没有找到官方题解，就是很玄学。而且，同样的贪心过程，如果先对一个点先dfs再染色，也就是根据子孙节点的颜色修改当前的颜色，就会出现某个节点大于k的情况（虽然仍然是保证了不同点之间不同染色），但是如果先染色再dfs，也就是先处理好搜索过的节点，根据祖先节点修改当前的节点，就能保证通过所有数据。
继续阅读“[思维][贪心] UVa1613 K-Graph Oddity”
题目最重要的是理解题意。。然后第二重要的是把原来的分散的点变成连续的：因为如果一开始的时候list上两个人就不相邻这时候最好就直接宣布了这个8g，因为这时候他们不会有任何一个人离开，这些操作之后也不用考虑了，这一步操作肯定的是最优的。
然后剩下的就是一块一块的被8g连起来的段，他们两两有一个8g，然后这时候可以用类似于矩阵链乘的算法，枚举第一次宣布的8g点，然后分成左右两块计算。max表示枚举断点取最大值，min表示顾客的想法：他们要让答案尽量小。
从后往前，如果遇到下雨的天气就存进优先队列里，如果遇到不下雨的天气，优先解决离当前位置最近的湖，用vis记录一个湖是否有危险，如果遇到一个下雨天这个湖已经有危险了那么就输出NO，否则标记为有危险，如果是不下雨的天有则把有危险的（队列中的）前一个最大的湖去掉。到最后如果队列非空则也输出NO，说明有的湖的危险没有解决。
自己看看了半天都找不到规律，倒是感觉和逆序数应该有关系，但是直接按照偶序列有解奇序列无解来算wa，因为按照我原来的理解是，偶序列4个反转一定还是偶序列，奇序列4个反转也一定是奇序列。搜了题解之后发现漏掉了一个条件，那就是这个是个环，所以他从任意一个地方开始都可以，这就相当于在原来的4个翻转的变换的基础上多了一种变换：把后面的一段整个的移动到前面的一段。这个操作是如果按照一次简单变换来衡量的话，相当于做了i*j次变换，其中i是分界点前一段的个数，j是后一段的。当n为偶数的时候可以找到一个分界点分为两个奇数段，则相乘之后仍然是奇数，等于说这时候是可以从奇序列变成偶序列的；而当n为奇数的时候，i和j必定一奇一偶，这时候相乘必定为偶数，无法变换序列的奇偶性。所以，只有当序列为奇序列且n为奇数的时候才无解，其他情况均有解，因为均可以变换为偶序列。
连续做的又一道预处理+贪心的题目，一开始因为复杂度的原因一直没有下手，看了官方题解才意识到复杂度是nlogn，因为调和级数求和是logn。。。
贪心策略就是每次都选择能覆盖到的范围内的最右边的非block的点，如果这个点等于原来的出发点就直接return -1，因为说明不可行。这时候我们需要预处理出来每个点对应的它左边离他最近的那个非block的点（也有可能是他自己），当然这个预处理就很简单了。主要的思考难度在于没想到可以这么预处理，其次是复杂度的分析没有到位。
错误的点的话是对题意的理解：这里要求覆盖整条线段，而不仅仅是覆盖整点，但是放灯却只能在0到n-1的整点上放。。。第二个错误是如果0处禁止放的话那直接就是输出-1了，原来的算法在这里会失效，因为那个总是多考虑一步，而没有考虑出发点是不是合法的。
首先确定，什么时候是NO，因为把ai全部异或起来一定是整个矩阵全异或，bi同理所以这俩数字应该相等，xor为0，如果不为0一定是不存在的。所以，如果存在，那么a全部xor和b全部xor一定是相等的，记为tmp
否则的话，把b1到bm-1全放到第一行的左边m-1个空位，剩下的右边那个补上一个t使得这一行xor为a1，此时最右边一列的xor为tmp^a1^t=tmp^(b1^bi..^bm-1)==bm，所以这样构造的矩阵一定满足要求！！！
继续阅读“[XOR][思维][构造] codeforces 1016D Vasya And The Matrix”
还是找星星，但是数据量升高了，不能用n^3复杂度的算法了
这里可以用六个预处理的矩阵来表示信息，前四个分别为上下左右到当前位置的连续的星个数，这样就不用每次到一个坐标都从新求了。后两个分别为两个标记矩阵，这里的思想很像之前有个AC自动机替换禁忌词的题目，因为那个题目禁忌词可能互相冲突，互相交错，互相包含，而这个里面的不同的星星也会出现这种情况，所以采用了类似的方法：在左端点标记+1，右端点标记-1，然后再把矩阵从左往右过一遍，h[i][j]=h[i][j]+h[i][j-1]，这样的话，就可以确定出来一个点有没有被星星覆盖到：如果他的h或v大于0就被覆盖了，否则就没有。所有的矩阵预处理都是n^2的复杂度，总共6*n^2大概。
继续阅读“[思维][预处理][区间信息技巧] codeforces 1015E2 Stars Drawing (Hard Edition)”
https://cn.vjudge.net/problem/HDU-1299
学到了设k求整数解个数的方法？emmm似乎非常常用的样子
wa在ans写在if外面了，这样会多乘。。。
