google code jam2016资格赛题解

A. Counting Sheep
小数据暴力呗。大数据也一样。。
B. Revenge of the Pancakes
小数据暴力呗。大数据没做。。
C. Coin Jam
小数据暴力呗。大数据没做。。
D. Fractiles
题意:一个序列由两种字符组成:L、G.给出k,c,s。表示序列初始长度k,变换了c次。每次变换:L的地方用最初始序列代替,G的地方用k个G代替。
现序列各个位置的值是看不到的,你可以选择查看其中的s个位置的值。问:能否通过小于等于s次查看,来推断出现序列是否包含G。
这题我是这样做的。小数据大数据一个做法。
如果查看一个位置发现是G,那么我们就知道序列是含有G的了,所以问题其实是在问:有没有一种查看的策略使得在查看的值都是L的情况下,可以断定序列必定没有G。
我们可以把整个变换的过程画出来,可以发现是一棵k叉树(注意一点这里我把原始序列的k个结点最为统一的“根结点”)。叶子节点是现序列。关键一点在于当得到了位置pos的值是L之后,我们就知道了pos位置的值是L之后,就知道了pos的父节点是L,它的父节点也是L。换言之,pos到树根的路径上的结点都是L。
那么为了尽可能通过一次查看得到最多信息,我们可以查看根节点的第二个子结点的第三个子结点的…………(一直到叶子结点)的值。这样就得到了min(c,k)个连续位置的值,接下来重复这个查看过程就行。
这个还是有个图比较好解释。。下次加个图。

2013 ACM/ICPC Asia Regional Chengdu Online–1010

hdoj4737 A Bit Fun
题意:给出n,m,然后给你n个正整数(n<=10^5),设f(i,j)=ai|ai+1|ai+2|……|aj,(i<=j),问有多少不同的f(i,j)<m.
总体思路:假如有一段连续的数[ai……aj aj+1],由于位或运算会使得结果越来越大,所以f(i,j)<f(i,j+1),那么可以很快得到二分的算法:一次枚举第i个数,二分[i,n]这一段数,找到最大的t,满足f(i,t)<m.
但是问题是n是10^5,每次暴力计算f(i,j)都是O(n)的(这样做就没有二分),这样复杂度是O(n^2)的,怎么降低复杂度呢(貌似这题数据比较水,比赛的时候很多大一队员是用暴力水过的,,==!)。
关键在于要常数时间计算ai|ai+1|ai+2|……|aj。可以这样做,a[i][k]表示前i个数对应第k位(把数分解成二进制)上“1”的个数之和,显然如果a[i-1][k]<a[j][k],那么说明[ai,aj]这段连续的数中至少存在一个数它的第k位是“1”,那么这段数位或起来,结果的二进制第k位一定是“1”,反之亦然。这样枚举结果的每一位分别是1还是0即可,一个数最多30位,自然是常数。

近期比赛待做的题

2013 ACM/ICPC Asia Regional Online —— Warmup
hdoj4714 Tree2cycle
hdoj4712 Hamming Distance
HDU Single Congtest 0905 (For Old ACMer)
zoj1301 The New Villa
HDU Single Congtest 0907 (For Old ACMer)
zoj1063 Space Station Shielding
zoj1066 Square Ice
zoj1197 Sorting Slides
HDU Team Congtest 0910 (For Old ACMer)
zoj1462 Team Them Up!
zoj1391 Horizontally Visible Segments