首页 > 代码库 > CUGBACM_Summer_Tranning1

CUGBACM_Summer_Tranning1

总体感觉:这个组队赛收获还挺多的,自从期末考试以后已经有一个多月没有 做过组队赛了吧,但是这暑假第一次组队赛就找回了以前的感觉。还挺不错的!继续努力!!

改进的地方:这次组队赛开始的时候题目比较难读懂,然后就感觉题目应该比较难吧,觉得应该是区域赛难度的题目。虽然A题和B题自己都感觉能自己A的,但是可能对自己不太自信,所以让队友大帝敲了。要是当时自己敢敲一下的话,兴许会更快的A掉吧。


A题:二进制枚举

其实这题当时听宝一提醒,就知道可以用二进制枚举来做了,不过大帝也是二进制枚举,然后队友敲了好多代码才A。我当时感觉用二进制枚举代码就十几行啊,在大帝怎么会写那么多代码呢,然后还以为自己的想法错了呢。刚才分析了下,因为n<20,所以复杂度也就10^6再乘以一个for循环二进制模拟数,最多也就10^7。3秒肯定过了,然后几分钟敲了下,耗时1009ms AC,要是题目是1ms的话,可以机智一点AC。

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n,k,s;
    while(scanf("%d%d%d",&n,&k,&s)&&(n||k||s))
    {
        int sum1=0,i,j;
        for(i=2;i<(1<<(n+1));i++)
        {
            if(i&1) continue;
            int sum=0,ans=0;
            for(j=1;j<=n;j++)
                if(i&(1<<j)) sum+=j,ans++;
            if(sum==s&&ans==k) sum1++;
        }
        printf("%d\n",sum1);
    }
    return 0;
}