The 10th Zhejiang Provincial Collegiate Programming Contest

Applications http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5008

string set 专场

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
const double eps=1e-8;
const int M=10000;
set<int> A,B;
set<string> xiaosai[4];
int defen[]={0,36,27,18};
char op[32];
struct G{
    double val;
    string name;
    friend bool operator <(const G &a,const G &b){
        return a.val>b.val||(fabs(a.val-b.val)<eps&&a.name<b.name);
    }
}p[512];
int pri[M],mark[M],pricnt;//mark[i]存i的最小因子，素数时mark[i]==i
void sieve_primes() { //筛素数
    pricnt=0;
    mt(mark,0);
    mark[0]=mark[1]=1;
    for(int i=2; i<M; i++) {
        if(!mark[i]) pri[pricnt++]=mark[i]=i;
        for(int j=0; pri[j]*i<M; j++) {
            mark[i*pri[j]]=pri[j];
            if(!(i%pri[j])) break;
        }
    }
}
int rat[1024];
int main(){
    sieve_primes();
    int t,n,m,q,c,tmp,id;
    while(~scanf("%d",&t)){
        while(t--){
            scanf("%d%d%d",&n,&m,&q);
            A.clear();
            while(q--){
                scanf("%d",&tmp);
                A.insert(tmp);
            }
            scanf("%d",&q);
            B.clear();
            while(q--){
                scanf("%d",&tmp);
                B.insert(tmp);
            }
            scanf("%d",&q);
            for(int i=0;i<4;i++){
                xiaosai[i].clear();
            }
            while(q--){
                scanf("%s%d",op,&id);
                xiaosai[id].insert((string)op);
            }
            for(int i=0;i<n;i++){
                p[i].val=0;
                scanf("%s",op);
                p[i].name=(string)op;
                scanf("%s",op);
                for(int j=1;j<=3;j++){
                    if(xiaosai[j].count((string)op)){
                        p[i].val+=defen[j];
                        break;
                    }
                }
                scanf("%s",op);
                if(op[0]=='F') p[i].val+=33;
                scanf("%d%d",&q,&c);
                while(q--){
                    scanf("%d",&tmp);
                    if(A.count(tmp)){
                        p[i].val+=2.5;
                        continue;
                    }
                    if(B.count(tmp)){
                        p[i].val+=1.5;
                        continue;
                    }
                    if(mark[tmp]==tmp){
                        p[i].val+=1;
                        continue;
                    }
                    p[i].val+=0.3;
                }
                for(int j=0;j<c;j++){
                    scanf("%d",&rat[j]);
                }
                sort(rat,rat+c);
                if(c>2){
                    p[i].val+=max(0.0,(rat[c-3]-1200.0)/100.0)*1.5;
                }
            }
            sort(p,p+n);
            for(int i=0;i<m;i++){
                cout<<p[i].name;
                printf(" %.3f
",p[i].val);
            }
        }
    }
    return 0;
}

 Break Standard Weight http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5009

set

#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
set<int> my;
int solve(int x,int y){
    int res=0;
    for(int i=1;i+i<=x;i++){
        my.clear();
        int a=i,b=x-i,c=y;
        my.insert(a);
        my.insert(b);
        my.insert(c);
        my.insert(abs(a+b));
        my.insert(abs(a-b));
        my.insert(abs(a+c));
        my.insert(abs(a-c));
        my.insert(abs(b+c));
        my.insert(abs(b-c));
        my.insert(abs(a+b+c));
        my.insert(abs(a+b-c));
        my.insert(abs(a-b+c));
        my.insert(abs(a-b-c));
        my.erase(0);
        int cnt=my.size();
        res=max(res,cnt);
    }
    return res;
}
int main(){
    int t,x,y;
    while(~scanf("%d",&t)){
        while(t--){
            scanf("%d%d",&x,&y);
            printf("%d
",max(solve(x,y),solve(y,x)));
        }
    }
    return 0;
}

 Density of Power Network http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5011

set

#include<cstdio>
#include<set>
using namespace std;
const int M=512;
struct P{
    int x,y;
    friend bool operator <(const P &a,const P &b){
        return a.x<b.x||(a.x==b.x&&a.y<b.y);
    }
}p[M];
set<P> my;
int main(){
    int t,n,m;
    while(~scanf("%d",&t)){
        while(t--){
            scanf("%d%d",&n,&m);
            for(int i=0;i<m;i++){
                scanf("%d",&p[i].x);
            }
            for(int i=0;i<m;i++){
                scanf("%d",&p[i].y);
            }
            my.clear();
            for(int i=0;i<m;i++){
                if(p[i].x>p[i].y) swap(p[i].x,p[i].y);
                my.insert(p[i]);
            }
            printf("%.3f
",my.size()*1.0/n);
        }
    }
    return 0;
}

Friends http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5013

暴力加边

#include<cstdio>
#include<cstring>
#define mt(a,b) memset(a,b,sizeof(a))
const int M=128;
bool mat[M][M];
void add(int u,int v){
    mat[u][v]=mat[v][u]=true;
}
int main(){
    int t,n,m,K,u,v;
    while(~scanf("%d",&t)){
        while(t--){
            scanf("%d%d%d",&n,&m,&K);
            mt(mat,0);
            while(m--){
                scanf("%d%d",&u,&v);
                add(u,v);
            }
            int ans=0;
            bool flag=true;
            while(flag){
                flag=false;
                for(int i=0;i<n;i++){
                    for(int j=i+1;j<n;j++){
                        if(!mat[i][j]){
                            int sum=0;
                            for(int k=0;k<n;k++){
                                if(k!=i&&k!=j&&mat[i][k]&&mat[k][j]){
                                    sum++;
                                }
                            }
                            if(sum>=K){
                                ans++;
                                flag=true;
                                add(i,j);
                            }
                        }
                    }
                }
            }
            printf("%d
",ans);
        }
    }
    return 0;
}

 Hard to Play http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5015

求最大最小值

#include<cstdio>
int solve(int point,int times,int &combo){
    int res=0;
    for(int i=0;i<times;i++,combo++){
        res+=point*(combo*2+1);
    }
    return res;
}
int main(){
    int t,a,b,c,combo,big,sma;
    while(~scanf("%d",&t)){
        while(t--){
            scanf("%d%d%d",&a,&b,&c);
            combo=sma=0;
            sma+=solve(300,a,combo);
            sma+=solve(100,b,combo);
            sma+=solve(50,c,combo);
            combo=big=0;
            big+=solve(50,c,combo);
            big+=solve(100,b,combo);
            big+=solve(300,a,combo);
            printf("%d %d
",sma,big);
        }
    }
    return 0;
}

 In 7-bit http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5016

注意la==0

#include<cstdio>
#include<cstring>
const int M=3000010;
char a[M];
int main(){
    int t;
    while(~scanf("%d",&t)){
        getchar();
        while(t--){
            gets(a);
            int la=strlen(a);
            if(la==0){
                puts("00");
                continue;
            }
            int len=la;
            while(len>0){
                int now=len%128;
                len/=128;
                if(len) now|=128;
                printf("%02X",now);
            }
            for(int i=0;i<la;i++){
                printf("%02X",a[i]);
            }
            puts("");
        }
    }
    return 0;
}

 Java Beans  http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5017

n个人坐成环，求连续m个和最大

#include<cstdio>
#include<algorithm>
using namespace std;
const int M=410;
int a[M];
int main(){
    int t,n,m;
    while(~scanf("%d",&t)){
        while(t--){
            scanf("%d%d",&n,&m);
            for(int i=0;i<n;i++){
                scanf("%d",&a[i]);
                a[i+n]=a[i];
            }
            int ans=0;
            for(int i=0;i<n;i++){
                int sum=0;
                for(int j=0;j<m;j++){
                    sum+=a[i+j];
                }
                ans=max(ans,sum);
            }
            printf("%d
",ans);
        }
    }
    return 0;
}

end