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)个连续位置的值,接下来重复这个查看过程就行。
这个还是有个图比较好解释。。下次加个图。

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll a[110];
ll ans[110],cnt;
inline ll min(ll a,ll b){return a<b?a:b;}
int main()
{
    //freopen("D-large.in","r",stdin);
    //freopen("D-large.out","w",stdout);
    ll i,j;
    int k,c,s;
    int t,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&k,&c,&s);
        printf("Case #%d:",++cases);
        if(c==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            for(i=1;i<=k;i++) printf(" %d",i);
            printf("\n");
            continue;
        }
        if(k==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            printf(" 1\n");continue;
        }
        cnt=0;
        a[0]=1;a[1]=k;
        for(i=2;i<=c;i++)
            a[i]=a[i-1]*(ll)k;
        for(i=1;i<=k;)
        {
            ll tmp=0;
            for(j=-1;j<=c-2;j++)
            {
                if(i+j+1<=k)
                    tmp+=(i+j)*a1;
                else
                    tmp+=(k-1)*a1;
            }
            ans[++cnt]=tmp+1;
            i+=min(c,k-i+1);
        }
        if(s<cnt) {printf(" IMPOSSIBLE\n");continue;}
        for(i=1;i<=cnt;i++) printf(" %I64d",ans[i]);
        printf("\n");
    }

    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>