CodeForces 265 DIV2 题解

September 8, 2014 | 16:52

A. inc ARG

找到第一个0的位置, 将位置序号+1输出; 若找不到0, 则输出N即可.

 

B. Restore Cube

每一段连续的1的个数+1, 所有连续段加起来-1即可.

 

C. No to Palindromes!

这题的关键点是如何判断一个串是否含有回文子串. 首先需要用dfs穷举, 从已知序列开始按照字典序生成下一个序列. 每穷举出来一个序列, 就check是否符合题意. check的方法是从被修改位开始到最后一位都检查是否与前两位相等. 比如说当前位是b[pos], 则需要保证 b[pos] != b[pos-1] 且 b[pos] != b[pos-2].

dfs函数需要有两个参数, 一个是pos, 一个是ok. pos用来表示当前位是哪一位, ok用来表示递归到当前层之前的那些祖父层是否曾经修改过某一位. 如果修改过那么ok == true.

 

D. Restore Cube

这题我看上去没什么思路, 但是畅神看了秒出正确思路. 对生成 (3!)^8 个可能的组合进行check, 如果符合条件则输出. 思路和上一题一样. 这题和上一题都隐藏得比较好, 有一种穷举会TLE的错觉. 实际上复杂度并不高.

check的方法也非常朴素, 有很多种方法, 其中一种方法是, 对于每一个点都应该有三个点和他距离为cube的边长. 而且这个点和那三个点组成的三条边应该两两垂直. 还有另一种判断的方法是, 对于每一个点, 其余七个点到他的距离的平方应该是 三个L^2, 三个2*(L^2), 一个3*(L*2).

这样一来就可以做了.

 

( 转载请注明: Jecvay Notes )

说几句