cf 283 div2

这一场给的数据量都不大，关键就是要敢暴力

a

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 1000;
int num[nMax];
int main(){
    int n,i,j,k,a,b,c;
    while(cin>>n){
        for(i=0;i<n;i++){
//            cin>>num[i];
            scanf("%d",&num[i]);
        }
        int ans = nMax;
        for(i=1;i<n-1;i++){
            int d = 0;
            for(j=1;j<n;j++){
                if(j==i)continue;
                if(j == i+1)c=num[j]-num[j-2];
                else c=num[j]-num[j-1];
                d = max(d,c);
            }
            ans = min(ans,d);
        }
        cout<<ans<<endl;
    }
    return 0;
}

?b，这里我用的是字符串最小表示法

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
const int nMax = 3000;
char str[nMax],tmp[nMax];
int next[nMax],lenp;
vector<string>sum;
void get_next(){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenp;i++){     
        while(j>-1&&str[j+1]!=str[i])j=next[j];
        if(str[j+1]==str[i])j++;
        next[i]=j;
    }
}

int minexp(char *s,int x) {
  int i=0,j=1,k=0,t;
   while(i<x&&j<x&&k<x) {
     t=s[(i+k)%x]-s[(j+k)%x];
      if(t==0) k++;
      else {
        if(t>0)  i+=k+1;
        else     j+=k+1;
        if(i==j) j++;
        k=0;
      }
   }
  return i<j?i:j;
}
bool cmp(string a ,string b){
    if(a<b)return 1;
    return 0;
}
int main(){
    int n,m,len,i,j,a;
    while(scanf("%d%s",&n,str)!=EOF){
        lenp = n;
        for(int t = 0; t < 10; t++){
            for(i=0;i<n;i++){
                str[i]+=1;
                if(str[i]>=10+‘0‘)str[i] = ‘0‘;
            }
            get_next();
            a = minexp(str,lenp);
            for(i=n;i<n*2;i++){
                str[i] = str[i-n];
            }
//            cout<<a<<" ";
            for(i = a,j=0;i<a+n;i++){
                tmp[j] = str[i];
                j++;
            }
            tmp[j]=‘\0‘;
//            cout<<tmp<<endl;
            string s = tmp;
            sum.push_back(s);
        }
        sort(sum.begin(),sum.end(),cmp);
        cout<<sum[0]<<endl;
    }
    return 0;
}

?

C，yy出了一个傻逼O(n^3)的算法，最后五分钟交题，没想到居然过了！！

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 400;
char str[nMax][nMax];
int num[nMax][nMax],next[nMax][nMax],sta[nMax];
int main(){
    int n,m,i,j,k,a,b,c;
    while(cin>>n>>m){
        for(i=0;i<n;i++){
            scanf("%s",str[i]);
        }
        if(n == 1){
            printf("0\n");
            continue;
        }
        for(i=1;i<n;i++){
            for(j=0;j<m;j++){
                if(str[i][j]>str[i-1][j]){
                    num[i][j] = 1;
                }
                else if(str[i][j]==str[i-1][j]){
                    num[i][j] = 0;
                }else{
                    num[i][j] = -1;
                }
            }
        }
//        for(i=1;i<n;i++){
//            for(j=0;j<m;j++){
//                cout<<num[i][j]<<" ";
//            }cout<<endl;
//        }
        memset(next,0,sizeof(next));
        memset(sta,0,sizeof(sta));
        for(i=1;i<n;i++){
            bool flag = 0;
            int pre;
            for(j=0;j<m;j++){
                if(num[i][j]!=0){
                    if(!flag){
                        pre = j;
                        sta[i] = j;
                    }else{
                        next[i][pre] = j;
                        pre = j;
                    }
                    flag = 1;
                }
            }
        }
//        for(i=1;i<n;i++){
//            cout<<sta[i]<<" ";
//        }cout<<endl;
        int ans = 0;
        for(i=0;i<m;i++){
            for(j = 1;j<n;j++){
                if(sta[j] == i && num[j][sta[j]] == -1){
//                    cout<<i<<endl;
                    ans++;
                    for(k=1;k<n;k++){
                        if(sta[k]==i){
//                                cout<<"change"<<" "<<k<<" to "<<next[k][sta[k]]<<endl;
                                sta[k] = next[k][sta[k]];
                        }
                    }
                    break;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

?

?

cf 283 div2

原文：http://bbezxcy.iteye.com/blog/2167323