[CF 329E]Evil题解翻译

题解翻译

这道题的解法实际上非常简单:http://codeforces.com/contest/329/submission/4122927

这道题要求我们证明一大堆东西(下面的证明超过80行)。

假设n>=4.显然nC,C->B,A->D,D->A。这里,点的配对是显然的,A和D配对,同样B和C配对。

首先,如果A+D为空或B+C为空,我们就一定能得到上述上界。我们可以简单地交替选择剩下两个配对区域中的点。因此我们假设A+D非空,B+C也非空。

首先,我们讨论B和C之间的关系(A和D同样符合这一关系)。(译者注:原文为‘A和B’,疑为作者笔误)

定理1:

|B-C|[......]

继续阅读

[CF 343E]Pumping Stations解题报告

题目翻译


题解

首先,有一个东西叫Gomory-Hu(戈莫里-胡)树。就是说,对于一张题中这样的图可以建出来一棵树,使得图中s~t的最小割等于树中s~t路径上的最小边权。

那么问题来了:怎么建树呢?

有两篇资料:
Wiki百科:

yangff的博客:

如果你看完之后还[……]

继续阅读

CTSC&APIO2015游记

5.3

这天报道……

下午和@Asm.Def @Chenyao @CJJ 跑去北海公园旅游
本来准备去上机的……结果走到人大门口地图处发现道路阻且长(要从人大的东南部越过山和大海到西北部),不如高卧且加餐……加餐……然后果断转身上地铁,北海公园走你┏ (゜ω゜)=☞
当天风儿非常的喧嚣,被吹了一脸……
看到了传说中的白塔……“四周环绕着绿树红墙”……以及奇怪的北京小学生作文展,还有约一个排的武警拿着透明的防爆盾默默走过……买了联票,然而在白塔处选择了一条逗比的路线结果没看到主建筑群,在团城处发现它关门了……所以等于联票并没有什么用……Orz
北海公园某偏僻角落处有若干长椅,基本每个上都坐着[……]

继续阅读

HAOI2015 解题报告

先给出ydc的题解地址:

http://ydc.blog.uoj.ac/blog/336


T1(树上染色):

题目地址:

首先有一个基础的想法是DP:令f[i][j]代表以i为根的子树中选了j个黑色点的最小代价(代价指该子树中所有边对答案的贡献之和)。在转移时,只需要枚举在当前儿子中放几个黑色点,计算这条父子边对答案的贡献。

代码:

#include
#include
#include
#include
#include
using namespace std;
typedef[......]

继续阅读

[CF 303D]Rotatable Number解题报告

 题目翻译


题解

出于可看性,就不用那么严格的数学语言讲了……

首先明确一下“循环数”的定义:比如142857,它乘以1,2,3,4,5,6(必须是连续的这些数)能不重不漏地得到142857的所有循环排列。

假设我们拿到了一个(十进制下的)循环数,不妨取142857.令x=0.142857142857……显然它是一个有理数,设为最简分数q/p((p,q)=1)。
因为x是一个无限纯循环小数,所以(10,p)=1.

我们考察这两组数:

第一组:x=0.1428571[……]

继续阅读

[CF 251E]Tree and Table题解翻译

题解翻译


如果N=1,则答案为2.

如果树中存在一个度数大于3的节点在,则答案为0.原因是网格中的每个格子的邻居数不超过3.

如果树中没有度数为3的节点,则答案为2N^2-2N+4.这一公式可以在题目其他部分的解答中自然地推导出。同时,我们也可以写一个简单的DP来计算这种情况下的答案。无论如何,我们现在证明这一公式。

首先,我们解决一个略有不同的问题,它在原问题的一个主要情况中也能用到。我们希望找出将一棵所有节点度数小于3的树放在网格中的方案数量,使得一个度数为1的点被放在左上角的格子中(令它为1号节点)。我们发现,如果网格的大小是2*K,则放置方案数等于K。这一公式可以用数学[……]

继续阅读

[CF 273D]Dima and Figure解题报告

题目翻译


题解

就是DP……
F[k][mask][i][j]代表:当前图形的最下端是第k行,左右边界的开放/收缩情况是mask,第k行涂黑了i~j列。
具体讲,mask=0代表左右边界均收缩,mask=1代表左开放右收缩,mask=2代表左收缩右开放,mask=3代表左右均开放。
“收缩”左边界的意思是:在第k行之前的每一行,涂黑部分最左都没有越过i,右边界就是最右没有越过j。
“开放”左边界的意思是:在第k行之前的某一行,涂黑部分最左越过了i,右边界就是某一行越过了j。
显然,收缩边界[……]

继续阅读