Codeforces Beta Round #7

A

水题

1 #include
      
        2 using namespace std; 3 #define lson l,mid,rt<<1 4 #define rson mid+1,r,rt<<1|1 5 #define sqr(x) ((x)*(x)) 6 #define maxn 1000010 7 typedef long long ll; 8 /*#ifndef ONLINE_JUDGE 9         freopen("1.txt","r",stdin);10 #endif */11 12 string str[15];13 int book[15][15];14 15 int Check1(int x){
    //lie16     for(int i=0;i<8;i++){17         if(str[i][x]!='B') return 0;18     }19     int ans=0;20     for(int i=0;i<8;i++){21         if(book[i][x]==0) book[i][x]=1,ans=1;22     }23     return ans;24 }25 26 int Check2(int x){27     for(int i=0;i<8;i++){28         if(str[x][i]!='B') return 0;29     }30     int ans=0;31     for(int i=0;i<8;i++){32         if(book[x][i]==0) book[x][i]=1,ans=1;33     }34     return ans;35 }36 37 38 int main(){39     #ifndef ONLINE_JUDGE40         freopen("1.txt","r",stdin);41     #endif42     std::ios::sync_with_stdio(false);43     for(int i=0;i<8;i++) cin>>str[i];44     int ans=0;45     for(int i=0;i<8;i++){46         ans+=Check1(i);47     }48     for(int i=0;i<8;i++){49         ans+=Check2(i);50     }51     cout<
       
        <
       
      

B

模拟题

1 #include
      
         2 using namespace std;  3 #define lson l,mid,rt<<1  4 #define rson mid+1,r,rt<<1|1  5 #define sqr(x) ((x)*(x))  6 #define maxn 1000010  7 typedef long long ll;  8 /*#ifndef ONLINE_JUDGE  9         freopen("1.txt","r",stdin); 10 #endif */ 11  12 int t,n,m; 13 int book[105]; 14 struct sair{ 15     int first,last; 16     int flag,pos; 17 }a[105]; 18  19 bool Check(int pos){ 20     int i; 21     if(pos+n>m+1) return false; 22     for(i=pos;i
       
        b.flag; 34 } 35  36 bool cmp2(sair a,sair b){ 37     return a.pos
        
         >t>>m; 46     string str; 47     int co=1; 48     int i; 49     for(int i=1;i<=100;i++){ 50         a[i].flag=0; 51         a[i].pos=i; 52     } 53     while(t--){ 54         cin>>str; 55         if(str=="alloc"){ 56             cin>>n; 57             for(i=1;i<=m;i++){ 58                 if(Check(i)){ 59                   //  cout<
         
          <<" "<
          <<"hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh"<
           
            >n; 75 if(n<1||n>101){ 76 cout<<"ILLEGAL_ERASE_ARGUMENT"<
           
         
        
       
      

 

C

扩展欧几里德模板题

1 #include
      
        2 using namespace std; 3 #define lson l,mid,rt<<1 4 #define rson mid+1,r,rt<<1|1 5 #define sqr(x) ((x)*(x)) 6 #define maxn 1000010 7 typedef long long ll; 8 /*#ifndef ONLINE_JUDGE 9         freopen("1.txt","r",stdin);10 #endif */11 12 void gcd(long long a,long long b,long long &d,long long &x,long long &y){13     if(!b){14         d=a;15         x=1;16         y=0;17     }18     else{19         gcd(b,a%b,d,y,x);20         y-=x*(a/b);21     }22 }23 int main(){24     #ifndef ONLINE_JUDGE25         freopen("1.txt","r",stdin);26     #endif27     long long a,b,c,d,x,y;28     scanf("%lld%lld%lld",&a,&b,&c);29     gcd(a,b,d,x,y);30     if(c%d)31         printf("-1\n");32     else33         printf("%lld %lld\n",-x*c/d,-y*c/d);34 35 }
      

 

D

字符串hash（好题）

思路：把字符串的前缀正着hash和倒着hash，比较hash值

1 #include
      
        2 using namespace std; 3 #define lson l,mid,rt<<1 4 #define rson mid+1,r,rt<<1|1 5 #define sqr(x) ((x)*(x)) 6 #define maxn 1000010 7 typedef long long ll; 8 /*#ifndef ONLINE_JUDGE 9         freopen("1.txt","r",stdin);10 #endif */11 12 char str[5000005];13 ll dp[5000005];14 int main(){15     #ifndef ONLINE_JUDGE16         freopen("1.txt","r",stdin);17     #endif18     scanf("%s",str+1);19     ll ans=0;20     ll t1=0,w1=0,p=121,num=1;21     int len=strlen(str+1);22     for(int i=1;i<=len;i++){23         t1=t1*p+str[i];24         w1=num*str[i]+w1;25         num*=p;26         if(t1==w1){27             dp[i]=dp[i/2]+1;28             ans+=dp[i];29         }30     }31     printf("%lld\n",ans);32 }