先说结论：构造的方法就是以任意一个点开始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之前要把那个点的状态复原。
赛后过题，心塞。
这题搞明白以后就是一个暴力打SG表的过程，-1表示bad，0表示normal，1表示good，从最后一轮开始，分奇偶轮，如果是奇数轮也就是先手轮，那就尽可能往1，也就是往大了转移，如果是偶数轮，也就是后手轮，那就往小了转移。真的是服了，这么简单当时就是没想到，唉。
因为n只有1000，每次的状态也最多只有200，（妈的限制上下界不就是为了可以暴力打表或者暴搜吗。。这么明显的特征没看出来我也是呵呵）想到这儿的时候直接明白了，为什么比赛时候那么多人过还那么高的通过率，呵呵呵呵呵，当时脑子真是短路。心情复杂。思考。 继续阅读“[比赛][博弈论][SG表] 2018 ICPC徐州网络赛 B BE, GE or NE”
这次写了这个题目之后我发现之前对面积并的那个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”
从后往前，如果遇到下雨的天气就存进优先队列里，如果遇到不下雨的天气，优先解决离当前位置最近的湖，用vis记录一个湖是否有危险，如果遇到一个下雨天这个湖已经有危险了那么就输出NO，否则标记为有危险，如果是不下雨的天有则把有危险的（队列中的）前一个最大的湖去掉。到最后如果队列非空则也输出NO，说明有的湖的危险没有解决。
有趣的一道dp，让我想起了msc面试的时候问的扔杯子的问题。
首先，如果确定了对于长度为n的代码要写x个printf，那么这x个一定是尽量均匀分布（数学显然）才能使得最坏情况最好！因此，可以写出递推式：f(n)=min(f(ceil(1.0*n/i))+r+i*p);记忆化搜索暴力转移即可。
这个复杂度分析很数学：[n/i]的只有O(sqrt(n))种可能，每种可能的情况递归下去的话[n/ab]=[[n/a]/b],仍然是在那sqrt(n)种可能里面。所以总共有sqrt(n)个点会往下递归，每个递归点又最多有sqrt(n)次，相乘的话相当于O(n)； 继续阅读“[DP][复杂度分析] Gym – 101485D Debugging”
这个题当时tle到哭，心态爆炸，也几乎直接导致了没去看很简单的G，心情复杂。
这个判重刚好卡unordered_set，怎么都过不了，只能自己手写Hash判重。另外一个优化的点就是一定要边Manachar边计算，我一开始写的跑一遍Manacher之后枚举中点然后计算左右端点（那不就退化成n^2了嗯我当时就这么傻）。一边Manacher一边做，好处就是关于某个点对称的重复的回文串只会被算一次！这也是Manacher自身的算法决定的。。这个题其实出题人就是想让这么做的，不然要想计算所有出现的回文串的（不判重）MOD，应该是只能n^2吧。。（或许SAM可以？我没想过）。
需要巩固的地方：字符串Hash，字符串子串预处理（取模等），Manacher的原理的深刻理解。
继续阅读“[字符串][Manacher][Hash] 2018ICPC 南京网络赛 I Skr”
