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: