[CF 306E]Levko and Game题解翻译 题解翻译 首先我们判断Levko是否能赢。 把所有可改变权值的道路权值都改成r[i],然后从以s1,s2为起点做两次Dijkstra算法。令d1[i]为s1到i的距离,d2[i]为s2到i的距离。考虑一条连接a和b,可以改变权值的道路。如果d1[a][……] 继续阅读
[CF 316F3]Suns and Rays解题报告 作者注 图片来自 http://www.cnblogs.com/wangck/p/4294282.html 题目大意 给出一张位图,是太阳和周围的光芒,像这样: 问有多少个太阳,并统计每个太阳周围的光线数量,排序后输出。 图的规模是1600*1600,光线的宽度[……] 继续阅读
[CF 329E]Evil题解翻译 题解翻译 这道题的解法实际上非常简单:http://codeforces.com/contest/329/submission/4122927 这道题要求我们证明一大堆东西(下面的证明超过80行)。 假设n>=4.显然nC,C->B,A->D,D->A。这里,点的配对是显然的,A和D配对,同样B和[……] 继续阅读
[CF 343E]Pumping Stations解题报告 题目翻译 http://cogs.pro/cogs/problem/problem.php?pid=1994 题解 首先,有一个东西叫Gomory-Hu(戈莫里-胡)树。就是说,对于一张题中这样的图可以建出来一棵树,使得图中s~t的最小割等于树中s~t路径上的最小边权。 那么问题来了:怎么建[……] 继续阅读
CTSC&APIO2015游记 5.3 这天报道…… 下午和@Asm.Def @Chenyao @CJJ 跑去北海公园旅游 本来准备去上机的……结果走到人大门口地图处发现道路阻且长(要从人大的东南部越过山和大海到西北部),不如高卧且加餐……加餐……然后果断转身上地铁,北海公园走你┏ (゜ω゜)=☞ 当天风儿非常的喧嚣,被吹了一[……] 继续阅读
HAOI2015 解题报告 先给出ydc的题解地址: http://ydc.blog.uoj.ac/blog/336 T1(树上染色): 题目地址: http://cojs.tk/cogs/problem/problem.php?pid=1962 首先有一个基础的想法是DP:令f[i][j]代表以i为根的子树中选了[……] 继续阅读
[CF 303D]Rotatable Number解题报告 题目翻译 http://cogs.pro/cogs/problem/problem.php?pid=1939 题解 出于可看性,就不用那么严格的数学语言讲了…… 首先明确一下“循环数”的定义:比如142857,它乘以1,2,3,4,5,6(必须是连续的这些数)能不重不漏地得到1[……] 继续阅读
[CF 251E]Tree and Table题解翻译 题解翻译 如果N=1,则答案为2. 如果树中存在一个度数大于3的节点在,则答案为0.原因是网格中的每个格子的邻居数不超过3. 如果树中没有度数为3的节点,则答案为2N^2-2N+4.这一公式可以在题目其他部分的解答中自然地推导出。同时,我们也可以写一个简单的DP来计算这种情况下的答案。无[……] 继续阅读