ZOJ 1799 - Crypto Columns 解题报告-阿里云开发者社区

开发者社区> 安全> 正文
登录阅读全文

ZOJ 1799 - Crypto Columns 解题报告

简介: 题目:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=799          题目大意是解密密文。加密过程是,根据一个关键字(keyword)进行加密,假设关键字是“BATBOY”,明文是“MEET ME BY THE OLD OAK TREE”。

         题目:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=799

         题目大意是解密密文。加密过程是,根据一个关键字(keyword)进行加密,假设关键字是“BATBOY”,明文是“MEET ME BY THE OLD OAK TREE”。因为关键字由6个字母组成,因此我们把明文(忽略空格和标点)写成6列的形式(在结尾处补齐一些随机字母):

          MEETME
          BYTHEO
          LDOAKT
          REENTH

         这里我们在结尾处补了“NTH”,现在根据关键字给定的列次序生成密文,关键字表示了选取列的顺序,关键字是“BADBOY”,因为最小字母A位于第二列,因此我们先提取明文中的第2列,即“EYDE”放入密文,下一个最小字母是B(并且含有两个B,我们先选择靠前的列),位于第一列,因此再提取“MBLR”放入密文,然后是第4列,第3列,第5列,第6列。即提取的列顺序是2,1,4,5,3,6,因此组成的密文是“EYDEMBLRTHANMEKTETOEEOTH”:

          EYDE

          MBLR

          THAN

          MEKT

          ETDE

          EOTH

         现在依次给出关键字和密文,要求输出明文。并且有,关键字和密文都是大写字母组成,关键字不超过10个字符,密文不超过100字符。

 

         [简单分析]

         一道经典简单题,读完题目我就已经知道这道题一定可以AC了,还能解释什么呢?思路很简单,一个字符数组存储密文,另一个字符数组存储明文,但在逻辑上我们把它们都看作“二维数组”,例如上面的明文看过是plaintext[4][6], 而密文看作是line[6][4];

         假设有char s[M][N];

         则 s[i][j] 换算为一维数组就是 s[i*N+j];

         解密时,我们依次处理密文的每一行,先从关键字中选取出最小且最靠前的字母在关键字中的索引“index”,然后把密文的 【当前行】 转复制到明文的“index”列。为了处理重复性的字母,我们还需引入一个flag数组标记该字母是否已经选取过。

         所有代码如下:

 

img_1c53668bcee393edac0d7b3b3daff1ae.gifimg_405b18b4b6584ae338e0f6ecaf736533.gifCode_1799_Crypto_Columns
/*ZOJ 1799 - Crypto Columns 解密 */

#include 
<stdio.h>
#include 
<string.h>
#include 
<stdlib.h>

/*键盘映射,不超过10个字符,全部大写字母组成!*/
char keys[11];
char flag[11];/*表示这一列是否已经被处理过*/
char line[101];/*密文*/
char plaintext[101];/*明文*/

/*解密密文*/
void Decrypt()
{
    
int i,index,column, count,keysLength, lineLength;
    
char c;
    
/*清空flag*/
    memset(flag, 
0sizeof(flag));
    
/*每次需要处理的字符个数*/
    lineLength
=strlen(line);/*密文总字符数*/
    keysLength
=strlen(keys);/*键个数,即列数*/
    count
=lineLength/keysLength;
    
    plaintext[lineLength]
=0;/* null - terminated */
    
    
/*找出最小的字母*/
    
for(column=0;column<keysLength;column++)
    {
        c
='Z'+1;
        
for(i=0;i<keysLength;i++)
            
if(flag[i]==0 && keys[i]<c)
                c
=keys[i],index=i;
    
        
/*设置该列已经被处理过的标记*/
        flag[index]
=1;
        
/*处理index列!*/
    
        
/*把密文的这一行复制到明文的index列*/
        
for(i=0;i<count;i++)
        {
            
/*明文的第index列*/
            plaintext[keysLength
*+ index]=line[count*column+i];
        }
    }    
}

int main()
{
    
while(1)
    {
        gets(keys);
        
if(strcmp(keys,"THEEND")==0break;
        gets(line);
        Decrypt();
        printf(
"%s\n", plaintext);
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

云安全开发者的大本营

其他文章