ccf 201903-3 损坏的RAID5

9月份考ccf，暑假打算做一些往年的真题。。。

这个题，一开始真是把我给看晕了

传说中的大模拟，果然不简单QAQ

首先读懂题目就是一个大难点，特别是对于我这种题目一长就看不进去的人来说

读懂题目之后，思路就好想了，下面简单说一下我的思路：

　　首先定义一个字符数组ss[N][M]，然后用ss[i]存入编号为 i 的硬盘后面的字符串，

　　在后面处理的时候就可以用sscanf函数直接获取ss[i]中相应位置的十六进制数（输入用"%8x"，输出用"%08X"）。

　　再一个比较烧脑的地方就是根据输入的块的编号b确定该块所在的硬盘和条带编号

　　　　条带编号k=b/s/(n-1); 结合图从左到右读这个式子就能想明白

　　　　所在硬盘编号t=n-1+k*(n-1)+b/s%(n-1)+1; t%=n; 其中n-1是条带编号为0对应的校验盘位置，条带编号+1,校验盘-1（等价于+(n-1)）； b/s%(n-1)是块所在硬盘相对校验盘的偏移量。（这是先前的版本，对的，但是很复杂。。。后来发现其实可以很简单，直接 t=b/s%n; 就出来了）

一开始我输入语句是这样写的：

     for(int i=;i<l;i++){

         int x;

         scanf("%d",&x);

         scanf("%s",ss[x]);

     }

然后就是各种超时，哪怕我想方设法优化代码，怎么搞也只有70分

我就纳闷了，这时间复杂度我满打满算也不过1e7啊，咋就超时了呢？

百思不得其解，于是毅然百度。。。

然后发现很多几个题解都是用的很c++风格的代码，算法复杂度和我没什么区别，而且用的cin，居然还比scanf快？？？

于是乎，我发现了一条神奇的代码

1   ios::sync_with_stdio(false);

据说它可以关闭c++的流同步，防止cin超时

于是乎，我试着把所有的标准输入换成了cin，加上那句我看不懂的玩意儿，居然还真过了！！！

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 const int M=*+;

 const int N=;

 char ss[N][M];

 int main()

 {

     //freopen("in.txt","r",stdin);

     ios::sync_with_stdio(false);

     int n,s,l;

     cin>>n>>s>>l;//scanf("%d%d%d",&n,&s,&l);

     for(int i=;i<l;i++){

         int x;

         cin>>x;//scanf("%d",&x);

         cin>>ss[x];//scanf("%s",ss[x]);

     }

     int m;

     cin>>m;//scanf("%d",&m);

     while(m--){

         ll b;

         cin>>b;//scanf("%lld",&b);

         ll t=n-+b/s/(n-)*(n-)+b/s%(n-)+,k=(b/s/(n-)*s+b%s)*;t%=n;

         if(k>=M||ss[t][]==&&l<n-||ss[][k]==&&ss[][k]==&&ss[t][k]==){

             printf("-\n");

             continue;

         }

         if(ss[t][]==){

             ll ans=;

             for(int i=;i<n;i++){

                 if(i==t)continue;

                 ll x;

                 sscanf(ss[i]+k,"%8x",&x);

                 ans^=x;

             }

             printf("%08X\n",ans);

         }

         else{

             ll ans;

             sscanf(ss[t]+k,"%8x",&ans);

             printf("%08X\n",ans);

         }

     }

     return ;

 }

但是scanf超时超在哪呢？？？

直到之后又看到一篇博客，我才知道字符串输入用scanf会超时，因为最后三组数据40kb的数据长度，意味着一个字符串最多有80kb个字符要输入，而一次最多有1000个字符串待输入，输入数据量贼大

于是改用专门的字符串输入函数gets或fgets就没问题了（不过据说gets大势已去，建议尽量用fgets）

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 const int M=*+;

 const int N=;

 char ss[N][M];

 int main()

 {

     //freopen("in.txt","r",stdin);

     int n,s,l;

     scanf("%d%d%d",&n,&s,&l);

     for(int i=;i<l;i++){

         int x;

         scanf("%d%*c",&x);

         fgets(ss[x],M,stdin);//gets(ss[x]);

     }

     int m;

     scanf("%d",&m);

     while(m--){

         ll b;

         scanf("%lld",&b);

         ll t=b/s%n,k=(b/s/(n-)*s+b%s)*;

         if(k>=M||ss[t][]==&&l<n-||ss[][k]==&&ss[][k]==&&ss[t][k]==){

             printf("-\n");

             continue;

         }

         if(ss[t][]==){

             ll ans=;

             for(int i=;i<n;i++){

                 if(i==t)continue;

                 ll x;

                 sscanf(ss[i]+k,"%8x",&x);

                 ans^=x;

             }

             printf("%08X\n",ans);

         }

         else{

             ll ans;

             sscanf(ss[t]+k,"%8x",&ans);

             printf("%08X\n",ans);

         }

     }

     return ;

 }

巴特西

ccf 201903-3 损坏的RAID5

最新文章

热门文章