2018"百度之星"程序设计大赛 - 资格赛杭电oj 6344-6345

╰半夏微凉° 2022-05-17 03:00 164阅读 0赞

链接：[点我][Link 1]

1001：状态压缩，枚举二进制状态  
杭电oj 题目链接:[点我][Link 2]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=1010;
    char ch[maxn][12]; 
    int xiong[maxn];
    int count[1<<10];
    int main(){
        int t,n,m,k;
        scanf("%d",&t);
        for(int q=0;q<t;q++){
            scanf("%d%d%d",&n,&m,&k);
            getchar(); 
            for(int i=1;i<=n;i++){
                scanf("%s",&ch[i]);
            }
            if(n*(n-1)/2<k){
                printf("Case #%d: 0\n",q+1);
                continue;
            }
            int total=0;
            for(int i=1;i<(1<<m);i++){
                for(int j=1;j<=n;j++){
                    int cnt=0;
                    for(int t=0;t<m;t++){
                        if(i>>t&1&&ch[j][t]=='B'){
                            cnt+=(1<<t);
                        }    
                    }
                    xiong[j]=cnt;
                    count[cnt]=0;
                }
                int num=0;
                for(int j=1;j<=n;j++){
                    int tot=++count[xiong[j]];
                    num+=j-tot;
                }
                if(num>=k){
                    total++;
                }    
            }
            printf("Case #%d: %d\n",q+1,total);
        }
        return 0;
    }

1002：莫队

#include <bits/stdc++.h>
    using namespace std;
    struct question {
        int l;
        int r;
        int id;
    } qst[100100];         //请求
    int R[100100];
    inline int comp(const question & a,const question & b) {
        return R[a.l]==R[b.l] ? a.r<b.r : R[a.l]<R[b.l];
    }                        //请求排序
    
    int ma[30];
    inline void pls(char ch){
        ma[ch-'A']++;
    }
    inline void mns(char ch){
        ma[ch-'A']--;
    }
    int ans[100100];
    char str[100100];
    int main(){
        int t;
        scanf("%d",&t);
        for(int k=1;k<=t;k++) {
            int l=1,r=0;
            int m,n;
            for(int i=0;i<=26;i++){
                ma[i]=0;
            }
            scanf("%d%d",&n,&m);
            getchar();
            scanf("%s",str+1); 
            int size=sqrt(1.0*n);
            for(int i=1;i<=n;i++) R[i]=i/size;
            for(int i=1; i<=m; i++) {
                scanf("%d%d",&qst[i].l,&qst[i].r);
                qst[i].id=i;
            }
            sort(qst+1,qst+m+1,comp);           //以l为第一关键字，以r为第二关键字 排序
            for(int i=1; i<=m; i++){
                while(r<qst[i].r)
                    r++,pls(str[r]);
                while(r>qst[i].r)
                    mns(str[r]),r--;
                while(l<qst[i].l)
                    mns(str[l]),l++;
                while(l>qst[i].l)
                    l--,pls(str[l]);
                //因为r和l的初始值的原因，while循环内部顺序不可改变
                 for(int j=0;j<=26;j++){
                    if(ma[j]>0){
                        ans[qst[i].id]=ma[j];
                        break;
                    } 
                }
            }
            printf("Case #%d:\n",k);
            for(int i=1; i<=m; i++)
                printf("%d\n",ans[i]);
        }
        return 0;
    }

前缀和

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int sum[100000+10][27];
    struct node{
    	int l,r;
    };
    node querry[100000+10];
    int main(){
    	int t;
    	scanf("%d",&t);
    	int n,q,l,r;
    	string str;
    	for(int c=1;c<=t;c++){
    		scanf("%d%d",&n,&q);
    		cin>>str;
    		for(int j=0;j<q;j++){
    			scanf("%d%d",&l,&r);
    			querry[j].l=l;
    			querry[j].r=r;
    			
    		} 
    		int len=str.length();
    		for(int i=0;i<len;i++){
    			++sum[i+1][str[i]-'A'];
    			for(int j=0;j<=26;j++){   //得到前缀和 
    				sum[i+2][j]=sum[i+1][j];
    			}
    		}
    		
    	/*	for(int i=1;i<=len;i++){
    			for(int j=0;j<10;j++){
    				printf("%d ",sum[i][j]);
    			}
    			printf("\n");
    		}*/
    		printf("Case #%d:\n",c);
    		for(int j=0;j<q;j++){
    			for(int i=0;i<=26;i++){
    				if(sum[querry[j].r][i]-sum[querry[j].l-1][i]>0){
    					printf("%d\n",sum[querry[j].r][i]-sum[querry[j].l-1][i]);
    				    break;
    				}
    			}
    		}
    	}
    }

[Link 1]: http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=820
[Link 2]: http://acm.hdu.edu.cn/showproblem.php?pid=6344