`
暴风雪
  • 浏览: 374989 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

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

 

 

1
0
分享到:
评论

相关推荐

    CF题解DIV2

    Oops! Google Chrome could not connect to codeforces.com Try reloading: codeforces.­com Additional suggestions: Access a cached copy of codeforces.­com Search on Google:

    CSS:Div高度、宽度自应等技巧演示文件集合。

    更多详细,请见: http://hi.baidu.com/xpnew/blog/item/3504685973c9cf2d2934f07e.html

    Educational Codeforces Round 83 (Rated for Div. 2) D

    今天CF被D恶心到了,写个题解重新整理下思路,(20开始想,25写完暴力代码,1.30才过,优化后的。。 核心思路就是在暴力的基础上进行组合数等差加速。 C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -&gt; m 我们发现内层...

    显示div层js.txt

    DIV弹出层 ******************************/ var cTime; function OpenDivLayer(tag) { var divBackground = document.getElementById('divBackground'); var divShow = document.getElementById('divShow'...

    Firefox下div层被Flash遮住的解决方法

    2.注意&lt;embed中的 wmode=transparent… 代码 复制代码代码如下: &lt;object classid=”clsid:D27CDB6E-AE6D-11cf-96B8-444553540000″ codebase=”...

    jQuery实现的分页功能示例

    &lt;div class=g-cf&gt; &lt;div xss=removed class=g-pager&gt; &lt;/div&gt; &lt;/div&gt; 2、CSS样式文件 .g-cf:after {clear: both;content: ;display: table;} .g-cf {zoom:1;} /*分页*/ .g-pager{ text-align:center; color: #...

    CF Submission Count-crx插件

    div2d比div2c更容易。 你错过了它只是因为你在静态网站上并忘记检查提交数量。 不再。 很多人喜欢在静态网站上寻找Codeforces竞赛。 它是快速和分心的。 唯一的问题是我们需要在网站之间跳转,以便我们不会错过提交...

    Codeforces Round #633 (Div. 2) A. Filling Diamonds(找规律)

    传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)

    网上图书销售数据库+ASP

    Const adOpenDynamic = 2 Const adOpenStatic = 3 '---- CursorOptionEnum Values ---- Const adHoldRecords = &H00000100 Const adMovePrevious = &H00000200 Const adAddNew = &H01000400 Const adDelete = &H...

    CF-Kate and imperfection

    题目来源:Codeforces Round #632 (Div. 2) 题目链接:F. Kate and imperfection 大致题意 给出一个数n,S为从1到n的集合,寻找长度为2,3,4…一直到长度为n的子集中任意两个数的最大公约数的最小值。举个例子有一...

    Xudong0722#Algorithm_template#codeforces思维题训练合集1

    lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done

    flvplayer.swf

    &lt;table border="2"&gt; &lt;td&gt;&lt;object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" width="1024" height="768"&gt; ...

    图片播放器

    &lt;div style="width:765px; margin:0px auto;"&gt; &lt;object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=9,0,28,0...

    圣诞节 祝福网站 全部源码

    document.write('&lt;object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=7,0,19,0" width="'+ swf_width +'" ...

    flash相册 照片墙

    &lt;DIV align="center" &gt; &lt;object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=7,0,19,0" width="800" height=...

    网页模板_flash_flower

    &lt;div align="center"&gt;&lt;object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://active.macromedia.com/flash2/cabs/swflash.cab#version=4,0,0,0" id=text-load width=760 height=480&gt;&lt;!-...

    flash 相册效果/特效

    &lt;object classid="clsid:D27CDB6E-AE6D-11cf-96B8-444553540000" codebase="http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=7,0,19,0" width="800" height="600"&gt; ...

    淘宝装修代码大全

     &lt;div id="Layer2"&gt; height=100% width=100%&gt;  &lt;iframe width=0 height=0&gt;&lt;/iframe&gt;  &lt;/div&gt;  &lt;div id="Layer1"&gt;  &lt;iframe height=100% width=100%&gt;&lt;/iframe&gt;  &lt;/div&gt;

    8086寻址方式及指令系统

    A.OF=0、CF=0 B.OF=0、CF=1 C.OF=1、CF=0 D.OF=1、CF=1 22.设AX=3762H,CL=5,执行“SHR AX,CL”后,AX=( )。 A.0376H B.01BBH C.01BB D.0376 23.若要在BUF缓冲区中寻找与AL中不相等的数据,应使用( ...

Global site tag (gtag.js) - Google Analytics