您的位置: 首页 > IT文章 > 11.29杭电校赛

11.29杭电校赛

分类: IT文章 • 2022-05-28 18:44:13

1001、搬砖

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

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

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

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

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

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

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

code.现求

#include<iostream>
#include<stdio.h>
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
",dfs(N));
    }
    return 0;
}

View Code

code2.打表

#include<iostream>
#include<stdio.h>
using namespace std;

const int MAXN=10000010;
int ans[MAXN];

void f(){
    ans[0]=0;
    ans[1]=0;
    for(int i=2;i<MAXN;++i){
        if(i&1){
            ans[i]=ans[i/2]+ans[i/2+1]+1;
        }
        else{
            ans[i]=ans[i/2]+ans[i/2];
        }
    }
}

int main(){
    f();
    int T;
    int N;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        printf("%d
",ans[N]);
    }
    return 0;
}

View Code

1002、投币洗衣机

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

求这n天洗衣服花的钱。

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

#include<iostream>
#include<stdio.h>
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<b){
                sum=0;
                ans+=2;
            }
            else if(b<=sum&&sum<c){
                sum=0;
                ans+=3;
            }
            else if(c<=sum){
                sum=0;
                ans+=4;
            }
        }
        printf("%d
",ans);
    }
    return 0;
}

View Code

1003、玩骰子

s.枚举即可

#include<iostream>
#include<stdio.h>
#include<algorithm>
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
");
            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
",ans);
    }

    return 0;
}

View Code

1004、质方数

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

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

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

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
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)<abs(prime[i]-k)?i-1:i;
    }
    return -1;
}

int main(){
    getPrime();
    int i;
    for(i=1;i<=prime[0];++i)
        prime[i]=prime[i]*prime[i];
    //cout<<prime[0]<<endl;
    //cout<<prime[prime[0]]<<endl;

    int T;
    int N;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&N);
        printf("%d
",prime[_search(N)]);
    }
    return 0;
}

View Code

1005、ACM组队安排

s.递推，

假设是第n 个人

它有三种组队方法

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

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

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

#include<iostream>
#include<stdio.h>
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
",ans[n]);
    }
    return 0;
}

View Code

1006、逆袭指数

s.暴力搜索即可

#include<iostream>
#include<stdio.h>
#include<math.h>
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<factNum;++i)
            factor[i]=factor2[i];
    }
}

int main(){

    int N;
    while(~scanf("%d",&N)){
        factNum=0;
        int k=sqrt(N)+1;
        for(int i=2;i<=k;++i)
            dfs(i,N,0);

        if(factNum==0){
            printf("1
");
            printf("%d
",N);
        }
        else{
            printf("%d
",factNum);
            for(int i=0;i<factNum-1;++i)
                printf("%d*",factor[i]);
            printf("%d
",factor[factNum-1]);
        }
    }
    return 0;
}

View Code

1007、油菜花王国

s.并查集

#include<iostream>
#include<stdio.h>
#include<string.h>
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<MAXM;++i){
        fi[i]=fi[i-1]+fi[i-2];
    }
}

bool isfi(int n){
    for(int i=0;i<MAXM;++i)
        if(fi[i]==n)return true;
    return false;
}

int fa[MAXN];
int set_find(int d){
    if(fa[d]<0)return d;
    return fa[d]=set_find(fa[d]);
}

void set_join(int x,int y){
    vis[x]=true;
    vis[y]=true;
    x=set_find(x);
    y=set_find(y);
    if(x!=y){
        fa[x]=y;
        sum[y]+=sum[x];
    }
}

int main(){
    f();
    //cout<<fi[MAXM-1]<<endl;
    int n,m;
    int k;
    int u,v;

    while(~scanf("%d%d",&n,&m)){
        memset(vis,false,sizeof(vis));
        memset(fa,-1,sizeof(fa));
        memset(sum,0,sizeof(sum));

        for(int i=1;i<=n;++i){
            scanf("%d",&k);
            if(isfi(k))
                sum[i]=1;
        }
        for(int i=0;i<m;++i){
            scanf("%d%d",&u,&v);
            set_join(u,v);
        }

        int ma=sum[1];
        for(int i=2;i<=n;++i){
            if(sum[i]>ma)ma=sum[i];
        }
        printf("%d
",ma);
    }
    return 0;
}

View Code

1008、游乐场

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

#include<iostream>
#include<stdio.h>
#include<algorithm>

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<n;++i)
            scanf("%d",&x[i]);

        __int64 tsum=0;
        for(int i=0;i<m;++i){
            scanf("%d",&pi[i]);
            tsum+=x[pi[i]-1];
            x[pi[i]-1]=0;
        }

        if(k<tsum)printf("-1
");
        else{
            int tol=m;
            sort(x,x+n);
            for(int i=m;i<n;++i){
                if(tsum+x[i]>k){
                    break;
                }
                else{
                    tsum+=x[i];
                    ++tol;
                }
            }
            printf("%d
",tol);
        }

    }
    return 0;
}

View Code

11.29杭电校赛

相关推荐