287 Amusing Qc Machine
很有意思的一道题。
f[i] = i次猜测可以确定的范围。
首先我们猜一个,如果得到了right就over了是吧。
否则我们还不知道应该往哪边猜,先蒙一个方向猜,这样可以确定的范围是f[i - 1]
然后c次以后得到了正确的方向,如果是另一个方向那么能确定的范围是f[i - c]
so, f[i] = f[i - 1] + f[i - c] + 1...
288 Best Tournament Schedule
经典的构造题
289 Challenging Tic-Tac-Toe
经典的博弈树搜索 + memorize
290 Defend the Milky Way
三维凸包
291 Evolution
用queue来模拟,最多只有1000*1000个繁殖事件。
292 Field for the Cemetery
q*c的格子最多可以放多少个1*c的长条(sgu292)
基本YY是只有2种可能,一种是使劲摆横然后摆竖,另一种是弦图那样摆
for e.g. 7 * 6放1*4
aaaahi
bbbbhi
cccchi
de hi
degggg
dehhhh
deiiii
伪代码:
if (q < n || c < n) 直接算;
t1 = q % n, t2 = c % n;
s1 = n - t1, s2 = n - t2;
ans = max((q * c - t1 * t2) / n, (q * c - s1 * s2) / n);
293 Game with Q an C
应该是很麻烦的构造,还没想好。
294 He's Circles
Polya原理
295 Identifier Duplicated!
分别计算latin-russian和空格放置的方案数,乘起来。后者是不定方程的解数。