比赛的时候一看计算几何直接跳过了，其实不是不可以做。。。
这个里面，各个草莓的半径其实对计算影响不大，由于圆的对称性，只要求出能覆盖s个草莓的圆心的最小圆就可以了，输出答案时加上草莓的半径r即可。
然后求定长圆的最大点覆盖就是有点模板了，有两种算法，n^3和n^2logn的，但是既然是抄板子那肯定是抄最快的了。。。
继续阅读“[比赛][二分][计算集合][定长圆最大点覆盖] 2018 ICPC 沈阳网络赛 E The cake is a lie”
[二分图][建图] UVa 12168 Cat vs Dog
比赛时候其实想的就是正解，但是没时间实现了。
这里并不是把猫狗分离开来，而是把voter分离开，换句话说原来的边变成了点，支持猫的在一边，支持狗的在另一边，如果有冲突的话连一条边，这样的话就是求最大独立集了。
本来看这个输入感觉头疼，后来想了想，忽然意识到：1 重复的人可以不用管，照例读入建立点，因为把他变成点之后对图没有任何影响。2 可以不用管字符后的数字，直接把他们当成一个整体就好了，整个字符串比较。 3 建立图的时候可以不用分左右两边，只要i和j有冲突就line[i][j]=line[j][i]=1；这样会使得建图的过程更简单，然后相当于把二分图对称了一下，最后输出的时候最大匹配数除以2就可以了.
[思维][贪心] UVa1613 K-Graph Oddity
先说结论：构造的方法就是以任意一个点开始dfs，对于dfs到的点，把他的颜色设置为没有在与他所有的相邻的已经被染过色的节点的颜色的集合中出现过的最小值，比如和它相邻有4个点，其中3个分别为1，3，3，另一个未染色，那么就把当前的颜色设置为2。
这个做法，网上并没有找到一个说得过去的证明，我自己也无法严格证明贪心过程的正确性，也没有找到官方题解，就是很玄学。而且，同样的贪心过程，如果先对一个点先dfs再染色，也就是根据子孙节点的颜色修改当前的颜色，就会出现某个节点大于k的情况（虽然仍然是保证了不同点之间不同染色），但是如果先染色再dfs，也就是先处理好搜索过的节点，根据祖先节点修改当前的节点，就能保证通过所有数据。
继续阅读“[思维][贪心] UVa1613 K-Graph Oddity”
[DP][思维] ZOJ3161 Damn Couples
题目最重要的是理解题意。。然后第二重要的是把原来的分散的点变成连续的：因为如果一开始的时候list上两个人就不相邻这时候最好就直接宣布了这个8g，因为这时候他们不会有任何一个人离开，这些操作之后也不用考虑了，这一步操作肯定的是最优的。
然后剩下的就是一块一块的被8g连起来的段，他们两两有一个8g，然后这时候可以用类似于矩阵链乘的算法，枚举第一次宣布的8g点，然后分成左右两块计算。max表示枚举断点取最大值，min表示顾客的想法：他们要让答案尽量小。
[比赛][递推][计数DP] 2018 ICPC 徐州网络赛 A Hard to prepare
比赛时候一直想推通式，然而并没有成功，和队友两个人用两种思路推出来两个公式。。。然后最后得知答案的通式是分奇偶性的，每个公式正好对一半，呵呵。。。。。
就题目本意来讲应该是dp。先把圆环展开为链，然后考虑一个满足题意的局面，这时候最后一位客人的面具与第一位客人的面具的关系决定了这条链是否能形成符合要求的环。如果一开始用两个状态分别表示最后一位与第一位冲突以及最后一位与第一位不冲突的两种情况，则会发现无法继续往后转移，因为从n位摆到n+1位的方法数是会受到前一位与第一位是否相同的影响的，因此需要再加一个状态信息，三个状态信息分别表示，最后一位与第一位相同，最后一位与第一位冲突，既不相等也不冲突，三种情况下的方案数，写出状态转移方程即可。
[比赛][暴力][搜索][题意] 2018 ICPC 徐州网络赛 C Cacti Lottery
比赛最后的时候三个人在看B和C，真的是紧张，根本看不懂题意，也不懂第二个样例怎么算出来的，今天看了看发现就完全是考的搜索，完 全 就 是 搜 索
能过了BC的话也算是有8个A了，没准可以进。。。可惜没如果，怪自己当时脑子进水，一脸懵逼。
两个dfs，第一个把对方知道的自己不知道的填充上，第二个把两个人都不知道的填充上，注意这里的题意，很坑，需要自己好好理解。可能是我写的太挫了，我这个码量有点大。。。
错误的话，排列写成了组合，wa了两发，意识到之后直接加了个阶乘。。懒癌。还有就是搜完一个填充点之后return之前要把那个点的状态复原。
[比赛][博弈论][SG表] 2018 ICPC徐州网络赛 B BE, GE or NE
赛后过题，心塞。
这题搞明白以后就是一个暴力打SG表的过程，-1表示bad，0表示normal，1表示good，从最后一轮开始，分奇偶轮，如果是奇数轮也就是先手轮，那就尽可能往1，也就是往大了转移，如果是偶数轮，也就是后手轮，那就往小了转移。真的是服了，这么简单当时就是没想到，唉。
因为n只有1000，每次的状态也最多只有200，（妈的限制上下界不就是为了可以暴力打表或者暴搜吗。。这么明显的特征没看出来我也是呵呵）想到这儿的时候直接明白了，为什么比赛时候那么多人过还那么高的通过率，呵呵呵呵呵，当时脑子真是短路。心情复杂。思考。 继续阅读“[比赛][博弈论][SG表] 2018 ICPC徐州网络赛 B BE, GE or NE”
[线段树][扫描线][面积交] HDU 1255
这次写了这个题目之后我发现之前对面积并的那个cal计数的意义还是理解还是有一点偏差：这个东西表示的是当前节点对应的线段整体覆盖的情况。为0时没有被全覆盖（注意不等于没有被覆盖），为1时被全覆盖了1次（意为min(l,r)==1，不代表不大于1)，为k时表示min(l,r)==k。而且对应的只是一个节点对应的整个线段，跟只表示当前整段线段的状况，儿子是什么样不知道。。。
这个题也貌似有很多种方法，我参考了一位前辈的博客之后用了Len1表示全覆盖次数≥1的长度，Len2表示全覆盖次数≥2的长度，当然全部都是针对当前节点。Len1的维护方法和面积并的方法完全一样。然后Len2维护的时候就是，如果cnt[o]大于等于2，那么说明当前节点被全覆盖了两次，直接Len2=Len1，如果为1，说明当前节点被全覆盖了一次，那么只需要加上子节点中被全覆盖了一次的Len1就可以了（这样相当于在双亲节点里覆盖了两次），如果是叶子节点，没有孩子，那就直接是0，如果cnt为0，那就只有孩子里面的被全覆盖了两次之和才能更新当前点了。
这里还有一个需要注意的是，如果cnt为0，那么要么说明，当前节点从来没有被计算过，要么说明只计算过子节点，所以不会出现错误。
继续阅读“[线段树][扫描线][面积交] HDU 1255”
[贪心][精度][排序] UVa1612 Guess
[贪心][优先队列] UVa 1623 Enter the Dragon
从后往前，如果遇到下雨的天气就存进优先队列里，如果遇到不下雨的天气，优先解决离当前位置最近的湖，用vis记录一个湖是否有危险，如果遇到一个下雨天这个湖已经有危险了那么就输出NO，否则标记为有危险，如果是不下雨的天有则把有危险的（队列中的）前一个最大的湖去掉。到最后如果队列非空则也输出NO，说明有的湖的危险没有解决。