1001、

description.刚开始一堆砖，共N块；任务是要把它分成N堆，每堆1块。

分的过程中，每次可将一堆分成两堆，耗费的体力是分完之后的两堆砖的数目的差值。

求完成任务需要耗费的最小的体力。

solution.贪心：每次分完之后的这两堆的数目差值越小，耗费的体力越小。

即每次分成差值最小的两堆，保证最后的耗费最小。

证明：（1）贪心选择性质：学的渣。。。不大会啊。

（2）最优子结构性质：~~~

code.现求

#include
      
       #include
       
        using namespace std;int dfs(int n){    if(n==1)return 0;    if(n&1)return dfs(n/2)+dfs(n/2+1)+1;//奇数    return dfs(n/2)*2;//偶数}int main(){    int T;    int N;    scanf("%d",&T);    while(T--){        scanf("%d",&N);        printf("%d\n",dfs(N));    }    return 0;}
       
      

code2.打表

#include
      
       #include
       
        using namespace std;const int MAXN=10000010;int ans[MAXN];void f(){    ans[0]=0;    ans[1]=0;    for(int i=2;i
       
      

 

1002、

d.题意比较简单，给出过去n天每天换下的衣服数目。在每一天，如果 a<=衣服数目<b ，花费2去洗；如果 b<=衣服数目<c ，花费3去洗；如果 c<=衣服数目 ，花费4去洗。

求这n天洗衣服花的钱。

s.模拟：从第一天开始，模拟到最后就可以了。

c.

#include
      
       #include
       
        using namespace std;int main(){    int n,a,b,c;    int sum,t;    int ans;    while(~scanf("%d%d%d%d",&n,&a,&b,&c)){        sum=0;        ans=0;        while(n--){            scanf("%d",&t);            sum+=t;            if(a<=sum&&sum
       
      

 

1003、

d.

s.枚举即可

c.

#include
      
       #include
       
        #include
        
         using namespace std;int ntype,atype;//1散牌，2对子，3三条bool win(int n[],int a[]){    if(ntype>atype)return true;    if(ntype==atype){        if(ntype==1){            if(n[2]>a[2])return true;            if(n[2]==a[2]){                if(n[1]>a[1])return true;                if(n[1]==a[1]){                    if(n[0]>a[0])return true;                }            }            return false;        }        if(ntype==2){            if(n[1]>a[1])return true;            if(n[1]==a[1]){                int ntemp,atemp;                if(n[0]==n[1])ntemp=n[2];                else ntemp=n[0];                if(a[0]==a[1])atemp=a[2];                else atemp=a[0];                if(ntemp>atemp)return true;            }            return false;        }        if(ntype==3){            if(n[0]>a[0])return true;            return false;        }    }    return false;}int main(){    int T;    int n[3],a[3];    int n2[3];    scanf("%d",&T);    while(T--){        scanf("%d%d%d",&n[0],&n[1],&n[2]);        scanf("%d%d%d",&a[0],&a[1],&a[2]);        sort(n,n+3);        sort(a,a+3);        if(n[0]!=n[1]&&n[0]!=n[2]&&n[1]!=n[2])ntype=1;        else if(n[0]==n[1]&&n[1]==n[2])ntype=3;        else ntype=2;        if(a[0]!=a[1]&&a[0]!=a[2]&&a[1]!=a[2])atype=1;        else if(a[0]==a[1]&&a[1]==a[2])atype=3;        else atype=2;        if(win(n,a)){            printf("1.000\n");            continue;        }        double ans=0;//胜率        for(int i=0;i<3;++i){            int num=0;//胜利次数            for(int j=1;j<=6;++j){
    //cout<<"@";                for(int k=0;k<3;++k){                    n2[k]=n[k];                }                n2[i]=j;                if(n2[0]!=n2[1]&&n2[0]!=n2[2]&&n2[1]!=n2[2])ntype=1;                else if(n2[0]==n2[1]&&n2[1]==n2[2])ntype=3;                else ntype=2;                sort(n2,n2+3);                if(win(n2,a))++num;            }            if((double)num/6>ans)ans=(double)num/6;        }        printf("%.3f\n",ans);    }    return 0;}
        
       
      

 

1004、

d.质数的平方命名为“质方数”。

距离一个正整数N最接近的质方数是多少？

s.打表，搜索即可。二分搜索都没用到，因为质方数就1000多个。。

c.

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;/*素数筛选，存在小于等于MAXN的素数prime[0]存的是素数的个数*/const int MAXN=11000;int prime[MAXN+1];void getPrime(){    memset(prime,0,sizeof(prime));    int i,j;    for(i=2;i<=MAXN;++i){        if(!prime[i])prime[++prime[0]]=i;        for(j=1;j<=prime[0]&&prime[j]<=MAXN/i;++j){            prime[prime[j]*i]=1;            if(i%prime[j]==0)break;        }    }}int _L,_m;int _search(int k){    if(k<=prime[1])return 1;    for(int i=2;i<=prime[0];++i){        if(prime[i]==k)return i;        if(prime[i]>k)return abs(prime[i-1]-k)
         
        
       
      

 

1005、

d.

s.递推，

假设是第n 个人

它有三种组队方法

1.他自己组队--ans[n-1]

2.他和他之前的n-1个人中挑出一个和他组队--(n-1)*ans[n-2]

3.他和他之前的n-1个人中挑出两个和他组队--C(2,n-1)*ans[n-3]

c.

#include
      
       #include
       
        using namespace std;int main(){    __int64 ans[25];    ans[1]=1;    ans[2]=2;    ans[3]=5;    for(int i=4;i<25;++i)        ans[i]=ans[i-1]+(i-1)*ans[i-2]+(i-1)*(i-2)/2*ans[i-3];    int n;    while(~scanf("%d",&n)){        if(n==0)break;        printf("%I64d\n",ans[n]);    }    return 0;}
       
      

 

1006、

d.

s.暴力搜索即可

c.

#include
      
       #include
       
        #include
        
         using namespace std;int factor[1024],factor2[1024],factNum;void dfs(int k,int n,int num){    if(n%k==0){        factor2[num]=k;        dfs(k+1,n/k,num+1);    }    else if(num>factNum){        factNum=num;        for(int i=0;i
        
       
      

 

1007、

d.

s.并查集

c.

#include
      
       #include
       
        #include
        
         using namespace std;const int MAXN=1024;const int MAXM=46;int fi[MAXM];bool vis[MAXN];int sum[MAXN];void f(){    fi[0]=fi[1]=1;    for(int i=2;i
         
          ma)ma=sum[i];        }        printf("%d\n",ma);    }    return 0;}
         
        
       
      

 

1008、

d.

s.贪心：优先选费用小的

c.

#include
      
       #include
       
        #include
        
         using namespace std;int main(){    int x[10005];    int pi[10005];    int T;    int n,m,k;    scanf("%d",&T);    while(T--){        scanf("%d%d%d",&n,&m,&k);        for(int i=0;i
         
          k){                    break;                }                else{                    tsum+=x[i];                    ++tol;                }            }            printf("%d\n",tol);        }    }    return 0;}