超码在线编程大赛初赛 第3场

赛后做的，第二题不会 d p dp dp，太菜了。。

1.最大公倍数

思路：枚举最后四个数的所有情况，若只有三个数，则这三个数 l c m lcm lcm就是答案。

2.房屋染色

思路： d p dp dp

令： d p [ i ] [ j ] [ 0 ] dp[i][j][0] dp[i][j][0] 为前 i i i个房屋中第 i i i个房屋颜色为 j j j没有步行街的最小花费。

d p [ i ] [ j ] [ 1 ] dp[i][j][1] dp[i][j][1]为第 i i i个房屋是步行街的最小花费。

然后进行 d p dp dp转移即可。

可以先做下这题，是题2的低配版。
传送门

3.字符串游戏

思路：把相同的字符看作一堆石子，然后就是反 N i m Nim Nim的裸题。

1.异或和不为0时，若存在石子数大于 1 1 1的堆则必胜，因为先手可以改变石子让后手面对异或和不为0情况。

2.异或和为0时，若每堆石子数都为1，则必胜。因为此时堆数为偶数。

4.完美字符串

思路：暴力统计连续 0 0 0计算贡献即可。