2018"百度之星"程式設計大賽 - 資格賽 杭電oj 6344-6345

連結：點我

1001：狀态壓縮，枚舉二進制狀态

杭電oj 題目連結:點我

#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;
				}
			}
		}
	}
}