over 2 years ago

又到一年GCJ。

无奈人还是这么傻逼。


  • A Counting Sheep

这题比较简单,很容易发现当且仅当n = 0的时候无解。
否则只要从小到大枚举i,到符合要求的时候停止,就可以了。


  • B Revenge of the Pancakes


这题只要贪心就好了,考虑连续的 - 的数量,答案显然就是 - 的段数乘以2。
要注意一种特殊情况: 第一个元素是- 这种情况要把答案减一。


  • C Coin Jam


这题还是挺有意思的
注意到这题解空间是非常大的,然而只要求输出500个解就行了,所以考虑一种构造解的方法。
如果一个多项式f(x)存在一个非平凡的因式g(x), 那么不管x为多少,g(x) | f(x),因此f(x)就不是质数。
简单起见,我们可以令g(x) = x + 1, 这样我们要求一个h(x), 使得f(x) = h(x) * g(x) 满足每一项的系数都是0/1且最高项和最低项的系数都是1。
这个h(x)就随便搞了..


  • D Fractiles


这题需要一定的观察能力.不过能看出来这个生成方式是怎么回事的话,就挺好做了。
如果原序列中有G的话,那么只需要区分出形如GLL, LGL, LLG 这样的序列中只有一个G的序列就行了(显然).
每次询问一个位置可以覆盖若干个这样的序列,我们要求的就是用最少的位置覆盖所有的序列。
显然每一个位置最多只能区分出C个不同的序列(考虑每次变换最多只能区分出一个序列(L, G))
只要算一下是否不超过S, 然后按照上述方法构造出一个解就好了。

← 一些基础dp题 HNOI2016 爆零记 →
 
comments powered by Disqus