f(Program,Poet)=Programet

前几天看到GoogleCamp有人在校内分享了GoogleCamp Code Jam的比赛报名呼叫，突然发现其实还有着这么一个东西。之前一直没有参加过，因为高中没有那么多自由的周末给我选择做什么，而且当时估计也正处于NOIP的巨大阴影之中。昨天C++上机课的时候就决定报名了。

昨天早上7点开始比赛，虽说是持续24小时的资格赛，但是不可能和它耗那么久，我就8点起床了。结果一起床发现一整版都是已经做完题目的人……当时那个瀑布汗。反正我已经决定了将整个早上都拿来做这个，就慢慢来好了。没想到……第一题就花了我15min才完全看懂，英文水平还有待欠缺啊……幸好A题很水，算法速度出现，结果我提交small，居然出错。仔细检查了我的输出，发现我所有的输出都写着”Case #1″（满脸黑线），改掉之后就AC掉小数据了，然后直接提交大数据，就继续往下走。粗略地看了看B题，发现还是没看懂，但是看到大数据的规模后，Cpp选手表示鸭梨很大，决定略过之。当时大概9点多一点，想着时间还有很多，就耐下性子看C题。C题倒是很好理解，使用模拟就能过小数据，思考大数据的算法我还思考了一下，而我想的顺序和最后Google官方给出的顺序差不多（顺便跪求那个O(N)的算法，我没想到，官方也没有给出明确的解）。然后意识到太复杂的coding是我的弱项，就选了第二个优化方法，填填补补地和模拟算法对拍上了小数据，就提交了。当时好像快11点了，我就决定先到此为止，下午再战B题。

中午和zxy远在美国的同学Simon大约交流了一下进度，发现他已经搞定了B题——因为高精度题目对python选手来说不痛不痒，所以只有Cpp选手在墙角内牛满面。下午4点多的时候回来看了看B题（也看了很久），算法易得，代码难写。最后草草地A掉小数据就完事了，看懂题目后大概花了15min。最近各种杂事，我就把GCJ放下了，其实要进入Round 1 的门槛还是很低的，只需要完整地过掉一题就好了。刚才看了看成绩，我提交了的都AC了，满足，等两个星期之后再战Round 1 。这次进入Round 1的人有8523只，而Round 2会有3000个名额。我看上的是Round 2 的top500可以得到一件拉风的T恤……恩，RP++保佑我能进入Round 2. 下面是我的题解和A、C两题的代码，B题要贴也要加高精度库，这里就不贴了。

A题的大概意思就是：有N个串联在一起的可开关插座板以及一个一直有电的总电源，1号插座板连接着总电源。一开始每一个插座板都处于关闭状态，我每打一个响指，那么所有处于有供能状态的插座板开关都会反转状态，即从开到关或者从关到开。一号插线板一直都处于有供能状态，因为总电源一直有电。而当1号处于ON的状态时，2号才处于有供能状态，当1号和2号都处于ON的状态时，3号才处于供能状态，依此类推。在第N个插线板上面有一个灯泡，问题就是如果我打了K个响指，那么灯泡会不会亮？

显然这个要用二进制来考虑，1表示一个插座板的开关处于ON的状态，而0就表示OFF。那么一开始就是N个0（为了方便讨论不妨设N=5）.第一次响指就变成了00001，第二次响指后就是00010，第三次就是00011，第四次就是00100……看出来了么？进行几次模拟运算之后就会发现打K次响指那么这个二进制串的值就等于K，不过要注意当K>2^N时，整个串会循环出现。那么我们其实就是判断那个K是不是会导致11111的出现。11111就是2^N-1，再考虑到循环出现，则灯泡会亮就等价于 2^N|(K+1)。交一个2^N的表，代码短短就可以解决了，贴在下面。

B题说了那么一大串，都把我弄晕了，其实意思很简单：给出N个正整数，希望找到一个最小的非负整数y，使得有最大的公约数T。首先就是要确定这个T是多少，然后求出y就是很简单的事情了。先看n=2的情况，对于两个正整数，如果且，那么必有T|b-a。再令T最大，那么显然就有T=b-a。得出这个结论后，就可以拓展到n个数字了。这时候的T，就是n个数字一共个两两之差的最大公约数。又可以证明，如果a_1是最小的数，那么这n-1个数的最大公约数等同于之前个数的最大公约数。所以可以用O(N)的时间算出T。最后算y的时候要注意判断y是否等于0的情况。我怕麻烦就没有写高精度，也就没有提交B-large，普通精度的代码就不贴了，一个gcd函数加几句判断就好。

C题是很好理解的，也是这三道题目里最好玩的一题。有一个能容纳k个人的过山车，一天运行r次。同时有很多人来玩这个过山车，但他们是抱成很多团出现的，意即每一堆人要么一起上车，要么不上车，每一堆人玩玩过山车后会还想玩，会按照上车之前的顺序排到队伍的末尾。每一次过山车等到没有人上车（全都上了或者坐不下了）就运行一轮。现在给出过山车的运行次数r，容量k以及n个团的顺序及大小，如果每一个人做一次能得一块钱，请你计算这个过山车这一天内能赚多少钱。给个例子，比如r=4，k=6,n=4,其中每一个团的大小分别是1，4，2，1。第一次运行是第一二个团上车，这时上了5个人，结束时队伍就变成了2,1,1,4，因为前两个团下车后排到了队伍的末尾，第二次运行上了3个团，一共4人，结束后队伍就变成了4,2,1,1。接着队伍还会变成1,1,4,2以及2,1,1,4。此时过山车运行结束，一共赚了21块。

这题初看很像直接模拟的题目，而且直接模拟每一次上人确实是可以解决小数据的，可以写一个用来检查优化算法是否可行。由于在large的时候N<=1000，R=10^9，直接模拟会死人，那么必然不行。首先考虑到，因为R>>N，又由于每一个团都有可能出现在排头，所以其实最多有N只不同的队伍，如果我们建立一个表next[i]表示第i个团做排头时下一个排头是谁，那么就可以加快模拟速度了。但是这个算法在8分钟内难以算完，我们必须接着优化。接着的优化只往前想了一小步，但是效果很明显，因为R>>N，那么必然会出现一个排头的循环，长度不超过N，每一个循环都是一样的，意即我们只要算出每一个循环内赚的钱，再看看当天会有几个完整循环，一乘即可，最后修补一下开始和结束，就可以得到最终结果了。如上面举出的例子，循环长度为3。我就用这个算法过了C的大数据。

Google赛后给出的题解说，还存在一个O(N)的算法，留给大家作为练习，也可以在Group上进行讨论……估计会有什么我不常用的数据结构出现，果断坐等此法。

恩，过两周再加油争取挺进Round 2然后靠RP拿T恤……感觉蛮困难的，不过试试也好~

附：A题代码：

#include
using namespace std;
 
int t,tt,n,k,i,j,flag,power[31]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824};
 
int main()
{
    FILE *in,*out;
    in=freopen("A-large.in","r",stdin);
    out=freopen("A-large.txt","w",stdout);
    cin>>t;
    for (tt=1;tt<=t;tt++)
    {
        cin>>n>>k;
        flag=0;
        k++;
        if (k%power[n]==0)
            flag=1;
        if (flag)
            cout&lt;&lt;"Case #"&lt;<tt>&lt;&lt;": ON"&lt;&lt;&lt;"Case #"&lt;<tt>&lt;&lt;": OFF"&lt;</tt></tt>

C题代码：

<tt><tt>#include
using namespace std;
 
long long r,n,k,g[1000],head,sum,once,t,tt,i,j,a,b,round[1000],mark[1000]={0},backtrack[1000],length,circle,roundsum,markflag;
 
int main()
{
    FILE *in,*out;
    in=freopen("C-large.in","r",stdin);
    out=freopen("C-small.txt","w",stdout);
    cin&gt;&gt;t;
    for (tt=1;tt&lt;=t;tt++)
    {
        cin&gt;&gt;r&gt;&gt;k&gt;&gt;n;//k is the capacity
        sum=0;
        for (i=0;i&gt;g[i];
            sum+=g[i];
        }
        if (sum&lt;=k)
            sum=sum*r;//the simplest case
        else
        {
            sum=0;
 
            for (i=1;i&lt;1000;i++)
            {
                mark[i]=0;
                backtrack[i]=0;
            }
            mark[0]=1;
            backtrack[0]=1;
            markflag=0;
            i=0;
            circle=1;
            roundsum=0;
            while (markflag==0)
            {
                once=0;
                while (once+g[i]&lt;=k)
                {
                    once+=g[i];
                    i=(i+1)%n;
                }
                round[circle]=once;
                circle++;
                if (mark[i])
                    markflag=1;
                else
                {
                    mark[i]=1;
                    backtrack[i]=circle;
                }
            }
            for (j=backtrack[i];j&lt;&lt;"Case #"&lt;<tt>&lt;&lt;": "&lt;&lt;</tt></tt></tt>

本文由 严酷的魔王 创作，转载或引用前请联系我们。

相关文章：

1. 问问matlab:WHY?
2. 让我们比比长短
3. NOIP实用算法 7.分治
4. 从(0,1]×(0,1]到(0,1]的双射
5. 每周软件推荐-TeX

2010年5月9日 星期天