UVALive 6661

题目[点击即可]

解题思路：首先要求子集，子集的要求是无序的，也就是说｛1，2｝和｛2，1｝是同一个子集，用二进制法把所有的子集求出来；因为0< n <=20，所以子集最多为2的20次方，再通过子集求和与子集中的元素个数来判断是否满足条件；时间方面，求子集的时间复杂度为O(2的n次方) ；

AC代码

#include<iostream>
#include<cmath>
using namespace std;
const int maxn=;
int a[maxn];
int n,k,S,d;
void sub(int m,int s)   
{
     int sum=,d1=;
        for(int i=;i<m;i++)
            if(s&(<<i))
            {
                sum+=a[i];  //先求和；
                d1++;       //记录子集元素个数；
            }
            if(sum==S&&d1==k)//判断是否满足条件；
                d++;        
}
int main()
{
    while(cin>>n>>k>>S&&n!=&&k!=&&S!=)
    {
        d=;
        for(int j=;j<=n;j++)
            a[j]=j+;
        for(int i=;i<(<<n);i++)
            sub(n,i);
        cout<<d<<endl;
    }
    return ;
}
           

第一次写的时候的代码：

这个代码不但长而且运行时间也长，主要是用了个栈来判断子集元素个数，当时脑子不清醒，想了好久才把代码改成上面AC的代码。

#include<iostream>
#include<stack>
using namespace std;
const int maxn=;
int a[maxn];
int n,k,S,d;
stack<int>st;
void sub(int m,int s,int k,int sum) 
{

    while(!st.empty())
        st.pop();
        for(int i=;i<m;i++)
                if(s&(<<i))
                st.push(i);
        if(st.size()==k)
             {
                 int  Sum=;
                 for(int i=;i<k;i++)
                 {
                      Sum+=a[st.top()];
                      st.pop();
                 }
                 if(Sum==sum)
                     d++;
             }
}
int main()
{
    while(cin>>n>>k>>S&&n!=&&k!=&&S!=)
    {
         d=;
        for(int j=;j<=n;j++)
            a[j]=j+;
        for(int i=;i<(<<n);i++)
            sub(n,i,k,S);
        cout<<d<<endl;
    }
    return ;
}