当前位置: 代码迷 >> 编程 >> Codeforces Round #167 (Div. 二 && Div.1)
  详细解决方案

Codeforces Round #167 (Div. 二 && Div.1)

热度:2856   发布时间:2013-02-26 00:00:00.0
Codeforces Round #167 (Div. 2 && Div.1)

Div2  A : 水题

Div2  B: 把每一个数都变成1,所需要的步数就是这个数的f值(奇数减一,偶数除以2)

Div1  A: 记录当前最高的高度即可

DIV1 B: SB题 , 会有很多个点的x坐标相同,但有可能有一些重点,所以要乘上cnt! / (2^c),由于总的cnt加起来不超过100000,所以,每次暴力算也可以。我开始还在想有没有什么取模的技巧。。。。。

DIV1 C:好像是原题,给你一幅图,每个点的度数不超过三,要你把点分成两组,使得每组中不存在某个点有 >=2个邻接点与其在同一组。

解法:先假设所有的点都在同一组,然后不断的找两组中不合法的点,将其放到另外一组(随便搜过去就好了)

证明:假设两个点颜色一样的边的总条数为M,每次找到一个不合法的点u,有三种情况:

1:u有三个邻接点且颜色与u相同,那么将u变为相反的颜色会使得M-3

2:u有两个邻接点颜色与u相同,另外一个不同,那么将u变为相反的颜色会使得M-1

3:u只有两个邻接点,将u变为相反的颜色会使得M-2

综上所述,将某个不合法的点变为相反的颜色总会使得M的数量减少,所以算法的运行次数是O(M)级别的

代码


ps: 上面两题都是考验计算复杂度的能力,看着很暴力的算法其实不然。

DIV1 D:

DIv1 E:

  相关解决方案