之所以写这个题是因为他提供了一种新的解决问题的思路。。两个暴力算法结合起来竟然就不暴力了。。
首先直接暴力枚举每个set里的余数然后解同余方程组可以得到一个Πki复杂度的算法，但是这个在k太大的时候会爆，然后k很大的时候就用了同余方程的另一种暴力解法，找到一个同余方程枚举他的所有解然后去判断其他的等式是否满足。。。这个在k比较大的时候比较快（但是感觉这俩算法组合还是有点看RP
代码基本上都是抄的书上就这。不过调了下LIMIT的范围发现从100到500000都可以过。。
[暴力][BFS][最短路][复杂度分析] codeforces 1064D Labyrinth
http://codeforces.com/contest/1064/problem/D
这个题最操蛋的是我把复杂度弄错了导致没有敢写暴力。。不过官方并没有出题解所以我也不知道我的做法是否可行，只能说通过了目前的所有数据。
做的思路就是求出来原点到每个点所用的最小的left和最小的right，求的方法就是暴力bfs，但是这里有个问题是有可能会有一个点可以通过多条路径到达，那么该如何确定最小值？如果直接裸搜不打标记会使得无限循环，如果打标记则会使得多种可能没有考虑，我这里用了一个玄学剪枝就是当当前点的下一个点的数据有被更新的时候才加到queue里，否则就不加，可以保证去掉了很多无用的扩展也可以保证搜索可以结束。另外一个优化是加了点是否已经在queue内的判断，可以避免多余的入队操作（这个貌似也可以用在一般的dij里啊）
[比赛][CF][预处理][问题本身的性质] codeforces 1060C Maximum Subrectangle
这场有点惨的过分了，怎么说呢。。。经过了这一段的训练感觉该提高一些了但是却还是这样子。。。继续努力吧
这个题卡了是最最难受的，因为从矩阵的角度考虑不管怎么样都搞不出来一个O(n3)的算法，无论如何都不可能，然 而 ，然 而！这题目根本就不用考虑矩阵。。。因为每一行每一列都是成比例的啊。。。光给个矩阵怎么可能n²算出来答案？很明显是跟题目数据自身的性质有关系的，然后自己就傻脸看了俩小时不知道怎么操作，呵呵，出发点就不对怎么可能算出来。。。
因为每一行都是成比例的，比例是bi，所以要求一个最大的不超过x的子矩阵，只需要枚举上下边然后给预处理出来的sb数组乘个上下边之差就可以了，小于x的操作可以用sb[x/(pa[j]-pa[i-1])]来操作。。。。。。所有的处理都极其暴力，但是因为所有的处理都是在a或者b的一维序列上进行的，所以暴力也是n²，如果脑子里只有那个矩阵的话怎么都不可能n²，因为他是个二维的。。
写错的地方的话是x可能会比pb[m]大，这时候只需要取到这个最大值就可以了。
继续阅读“[比赛][CF][预处理][问题本身的性质] codeforces 1060C Maximum Subrectangle”
[比赛][暴力][循环][复杂度分析] 2018 icpc 青岛网络赛 J Press the Button
还好没有鸽这场比赛，当时是做数模的最后几小时，我和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”
[思维][贪心] UVa1613 K-Graph Oddity
先说结论：构造的方法就是以任意一个点开始dfs，对于dfs到的点，把他的颜色设置为没有在与他所有的相邻的已经被染过色的节点的颜色的集合中出现过的最小值，比如和它相邻有4个点，其中3个分别为1，3，3，另一个未染色，那么就把当前的颜色设置为2。
这个做法，网上并没有找到一个说得过去的证明，我自己也无法严格证明贪心过程的正确性，也没有找到官方题解，就是很玄学。而且，同样的贪心过程，如果先对一个点先dfs再染色，也就是根据子孙节点的颜色修改当前的颜色，就会出现某个节点大于k的情况（虽然仍然是保证了不同点之间不同染色），但是如果先染色再dfs，也就是先处理好搜索过的节点，根据祖先节点修改当前的节点，就能保证通过所有数据。
继续阅读“[思维][贪心] UVa1613 K-Graph Oddity”
[比赛][暴力][搜索][题意] 2018 ICPC 徐州网络赛 C Cacti Lottery
比赛最后的时候三个人在看B和C，真的是紧张，根本看不懂题意，也不懂第二个样例怎么算出来的，今天看了看发现就完全是考的搜索，完 全 就 是 搜 索
能过了BC的话也算是有8个A了，没准可以进。。。可惜没如果，怪自己当时脑子进水，一脸懵逼。
两个dfs，第一个把对方知道的自己不知道的填充上，第二个把两个人都不知道的填充上，注意这里的题意，很坑，需要自己好好理解。可能是我写的太挫了，我这个码量有点大。。。
错误的话，排列写成了组合，wa了两发，意识到之后直接加了个阶乘。。懒癌。还有就是搜完一个填充点之后return之前要把那个点的状态复原。
[贪心][精度][排序] UVa1612 Guess
[CF][区间标记方法][暴力] codeforces 1028C Rectangles
比赛时候wa到哭，后来发现优化错了，把优化去掉玄学AC（这可是三个for啊这复杂度）
后来想一下，之所以能玄学过，就是因为题目保证了一定有解，如果无解的话那三个for还真有可能跑一遍，不说三个了两个跑一遍都够呛。。
我这里的玄学算法就是，对横纵坐标分别标记，当一个点在纵方向上被至少n-1个举行覆盖的时候才考虑这个横坐标，然后在这个横坐标上的所有纵坐标，也只有当被至少n-1个覆盖到的时候才考虑它，当然这只是必要条件而不是充分条件，然后对于一个要考虑的点遍历所有矩形（没错就是这么暴力）如果有超过1个没覆盖到这个点就退出直接不考虑。。。就这么超级暴力+剪枝，玄学过了cf的所有数据，emmm 继续阅读“[CF][区间标记方法][暴力] codeforces 1028C Rectangles”
[思维][预处理][贪心] codeforces 990E Post Lamps
连续做的又一道预处理+贪心的题目，一开始因为复杂度的原因一直没有下手，看了官方题解才意识到复杂度是nlogn，因为调和级数求和是logn。。。
贪心策略就是每次都选择能覆盖到的范围内的最右边的非block的点，如果这个点等于原来的出发点就直接return -1，因为说明不可行。这时候我们需要预处理出来每个点对应的它左边离他最近的那个非block的点（也有可能是他自己），当然这个预处理就很简单了。主要的思考难度在于没想到可以这么预处理，其次是复杂度的分析没有到位。
错误的点的话是对题意的理解：这里要求覆盖整条线段，而不仅仅是覆盖整点，但是放灯却只能在0到n-1的整点上放。。。第二个错误是如果0处禁止放的话那直接就是输出-1了，原来的算法在这里会失效，因为那个总是多考虑一步，而没有考虑出发点是不是合法的。
[CF][贪心][枚举][思维] CF1019A
http://codeforces.com/problemset/problem/1019/A
今天想起来这坑还没填。心情差.jpg
当时比赛想了一个小时dp，然后在最后10min意识到可以枚举最后所需要的人数然后贪心。。可是已经没时间来实现了，然后就果断地凉了。今天直接补了
一开始纠结，主要在于，这个决策既得考虑人数又得考虑钱，有点像背包，就很不好操作。但是实际上，n范围只有3000，所以完全可以枚举人数，在这个固定的条件下去考虑对于一特定的人数x需要多少钱，就很容易了：每次先把人数大于等于x的减到x-1，把减去的人加到党派1的支持者数量里，这个过程中挑最小的那些累计起来。在做完这些工作后就是看有没有达到人数x，如果达到了/超过了就说明行了，虽然超过的话就不是正好x但是我们只关心钱数的最小值，如果没有达到，那么还需要从剩下的所有人里从小到大累计够人数才可以。
我这里只排序1次，然后每次设置used数组表示一个人是不是在第一步里用过了。算是n^2复杂度吧。当然这个题数据貌似很水怎么都能过。。
实现的话还有一个问题就是按照我的写法遇到p为1的时候是不能设置used的，因为这个其实是针对于党派1之外的来说的。。。因为这个wa了一发。 继续阅读“[CF][贪心][枚举][思维] CF1019A”