【算法课OJ】密码实验

Author Avatar
source. 10月 20, 2018
  • 在其它设备中阅读本文章

君子生非异也，善假於物也。

链接：http://192.168.173.163/JudgeOnline/contest.php?cid=1113

密码：123654

问题 A: 凯撒加密法

题目描述

凯撒加密法，或称恺撒加密、恺撒变换、变换加密，是一种最简单且最广为人知的加密技术。它是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。
例如，当偏移量是左移3的时候：
​ 明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
​ 密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC
使用时，加密者查找明文字母表中需要加密的消息中的每一个字母所在位置，并且写下密文字母表中对应的字母。需要解密的人则根据事先已知的密钥反过来操作，得到原来的明文。例如：
​ 明文：THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
​ 密文：WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
现在给定你一个字符串S（长度不会超过1000000）和一个整数k（-1000000000<=k<=1000000000），分别代表接受者收到的密文和在加密该密文时向后的偏移量，你的任务是计算出原来的明文
注意：只有字母在加密时才会发生偏移，其它字符保持不变

输入

输入包含多组数据，其中第一行为数据组数T（T<=10）
每组数据第一行为一个字符串S，由数字、字母以及常见字符组成（不含空格），第二行为一个整数k代表加密时向后的偏移量（|S|<=1000000,-1000000000<=k<=1000000000）

输出

对每组数据，输出一行字符串，代表输入中的密文对应的明文。

样例输入

1
DEFGHIJKLMNOPQRSTUVWXYZABC
3

样例输出

ABCDEFGHIJKLMNOPQRSTUVWXYZ

题意

凯撒加密，给你一个密文和偏移量，要求明文。

思路

Water，模拟。注意区分大小写字母。

输入偏移量n后即处理n %= 26;

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn = 1e6 + 5;
int main()
{
    int t,n,len;
    char str[maxn];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s %d",str,&n);
        n %= 26;
        len = strlen(str);
        for(int i = 0; i < len; i++)
        {
            if(str[i] >= 'A' && str[i] <= 'Z')
                str[i] = 'A'+(str[i]-'A'-n+26)%26;
            else if(str[i] >= 'a' && str[i] <= 'z')
                str[i] = 'a'+(str[i]-'a'-n+26)%26;
        }
        printf("%s\n",str);
    }
    return 0;
}

问题 B: Vigenère 密码

题目描述

16 世纪法国外交家 Blaise de Vigenère 设计了一种多表密码加密算法——Vigenère 密码。Vigenère 密码的加密解密算法简单易用，且破译难度比较高，曾在美国南北战争中为南军所广泛使用。

在密码学中，我们称需要加密的信息为明文，用 MM 表示；称加密后的信息为密文，用 CC 表示；而密钥是一种参数，是将明文转换为密文或将密文转换为明文的算法中输入的数据，记为 kk。 在 Vigenère 密码中，密钥 k 是一个字母串，k=k1k2…kn。当明文 M = m1m2…mn 时，得到的密文 C = c1c2…cn ，其中 ci = mi® ki，运算 ® 的规则如下表所示：

img

Vigenère 加密在操作时需要注意：

  1. ® 运算忽略参与运算的字母的大小写，并保持字母在明文 MM 中的大小写形式；
  2. 当明文 M 的长度大于密钥 k 的长度时，将密钥 kk 重复使用。 例如，明文 M=M=Helloworld，密钥 k=abc时，密文 C=Hfnlpyosnd。

img

输入

第一行为一个字符串，表示密钥 k，长度不超过 100100，其中仅包含大小写字母。

第二行为一个字符串，表示经加密后的密文，长度不超过 10001000，其中仅包含大小写字母。

输出

输出共 11 行，一个字符串，表示输入密钥和密文所对应的明文。

样例输入

CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm

样例输出

Wherethereisawillthereisaway

题意

维吉尼亚密码。输入密钥K和密文C，输出明文M。

思路

观察第一张图给的表，找出规律。

怎么对K重复利用？模K的长度即可。

结果与K的大小写无关，一开始把它全部转化为小写（或大写）方便处理。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn = 1e6 + 5;
int main()
{
    int lk,lc;
    char k[105],c[1005];
    scanf("%s %s",k,c);
    lk = strlen(k);
    lc = strlen(c);
    for(int i = 0; i < lk; i++)     //k to all lowwer
    {
        if(k[i] >= 'A' && k[i] <= 'Z')
            k[i] = k[i]-'A'+'a';
    }
    for(int i = 0; i < lc; i++)
    {
        if(c[i] >= 'A' && c[i] <= 'Z')
            c[i] = 'A'+(c[i]-'A'-k[i%lk]+'a'+26)%26;
        else
            c[i] = 'a'+(c[i]-'a'-k[i%lk]+'a'+26)%26;
    }
    printf("%s\n",c);
    return 0;
}

问题 C: 简单的密码

题目描述

密码是按特定法则编成，用以对通信双方的信息进行明密变换的符号。密码是隐蔽了真实内容的符号序列。其实就是把用公开的、标准的信息编码表示的信息通过一种变换手段，将其变为除通信双方以外其他人所不能读懂的信息编码，这种独特的信息编码就是密码。
现在我们定义一种非常简单的密码，它的长度固定为n（n<=30）并且每一位只能由数字0或者数字1组成，但是有一个特殊的要求：一个密码序列中至少要有连续的3个0出现才可以，否则就是无效的。现在给定你密码序列的长度n，你的任务是计算长度为n的序列能产生多少种不同的并且有效的密码？

输入

输入包含多组数据，每组数据只有一个正整数n（1<=n<=30）代表密码序列的长度，单独占一行。

输出

对每组数据，输出一个整数，代表长度为n的序列能产生的不同密码的种类数。

样例输入

4
5
6

样例输出

3
8
20

题意

给定长度n，每位只有0和1，且必须包含连续3个0，求符合条件的序列有多少个。

思路

这题真的让我想了好久！

一直没想到合适的方法！

思路：dfs

当前面已经出现连续3个0了，那后面就随便填写，每一位都可以填0或者1两种，当前层数为d，那么对于比d大的i，dp[i] += (1<<(i-d));。

当你写了一个程序TLE了，但是你确定结果就是对的，不妨把答案打成一个表，输入了直接查表输出就好了（而且这题n最大30），时间复杂度O(1)！

思路：递推

先给出递推式：f[i] = 2*f[i-1]+(1<<(i-4))-f[i-4];

为什么呢？

  1. 2*f[i-1]上一步如果已经有连续3个0了，那这一步可0可1；
  2. (1<<(i-4))-f[i-4]什么时候会有除上一种情况之外的解呢？答案是当上一步最后3位为100的时候，这三位（i-1位、i-2位、i-3位）已经定死了，那我们只要考虑到i-4位时不符合条件的数量，即总的减去符合条件的（2i-4-f[i-4]）。

思路：dp

其实我觉得这是最简单想到的思路。

开一个二维数组dp[i][j]。

首先，定义非解情况：前i位中不存在连续3个0。

dp[i][0]代表最后一位为1的非解情况。

dp[i][1]代表最后一位为0（最后两位为10）的非解情况。

dp[i][2]代表最后两位为00（最后三位为100）的非解情况。

dp[i][3]代表解情况。

则可由i-1推i，有：

dp[i][0] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2];

  • 所有上一步非解情况后面补1都可以得到

dp[i][1] = dp[i-1][0];

  • 上一步非解且最后一位是1后面补0得到

dp[i][2] = dp[i-1][1];

  • 上一步非解且最后一位是0（最后两位为10）后面补0得到

dp[i][3] = dp[i-1][2]+dp[i-1][3]*2;

  • 上一步非解且最后两位是00（最后三位为100）或者上一步就是解后面补0或1得到

主函数每输入一个n，输出dp[n][3]。

代码(TLE)

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int ans;
int dp[32];
void dfs(int pre,bool ok,int d)
{
    if(ok)
    {
        for(int i = d; i <= 30; i++)
        {
            dp[i] += (1<<(i-d));
        }
        return;
    }
    if(d == 30) return;
    dfs(pre+1,ok||(pre+1 >= 3)?true:false,d+1);
    dfs(0,ok,d+1);
}
int main()
{
    int n;
    dfs(0,false,0);
    while(~scanf("%d",&n))
    {
        printf("%d\n",dp[n]);
    }
    return 0;
}

代码(TLE的结果打一张表存数组里)

#include<iostream>
#include<stdio.h>
using namespace std;
int dp[32] = {0,0,0,1,3,8,20,47,107,238,520,1121,2391,5056,10616,22159,46023,95182,196132,402873,825259,1686408,3438828,6999071,14221459,28853662,58462800,118315137,239186031,483072832,974791728};
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        printf("%d\n",dp[n]);
    }
    return 0;
}

代码(递推，找规律)

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
int f[32] = {0,0,0,1};
int main()
{
    for(int i = 4; i <= 30; i++)
    {
        f[i] = 2*f[i-1]+(1<<(i-4))-f[i-4];
    }
    int n;
    while(~scanf("%d",&n))
    {
        printf("%d\n",f[n]);
    }
    return 0;
}

代码(dp)

#include<iostream>
#include<stdio.h>
using namespace std;
int dp[33][4];
void init()
{
    dp[1][0] = 1;   //非解且最后一位是1
    dp[1][1] = 1;   //非解且最后一位是0
    dp[1][2] = 0;   //非解且最后两位是0
    dp[1][3] = 0;   //解
    for(int i = 2; i <= 30; i++)
    {
        dp[i][0] = dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
        dp[i][1] = dp[i-1][0];
        dp[i][2] = dp[i-1][1];
        dp[i][3] = dp[i-1][2]+dp[i-1][3]*2;
    }
}
int main()
{
    init();
    int n;
    while(~scanf("%d",&n))
    {
        printf("%d\n",dp[n][3]);
    }
    return 0;
}

问题 D: 有趣的素数

题目描述

素数被广泛地应用于密码学中，所谓的公钥就是将想要传递的信息在编码时加入砠数，编码之后传给收信人，任何人收到此信息之后，若没有此收信人所拥有的秘钥，则在解密的过程中将会因为分解质因数过久而无法破解信息，可见素数在密码学中的重要性。
现在给你n（2<=n<=16）个正整数1,2,3…n，你的任务是把这n个正整数组成一个环，使得任意相邻的两个整数之和为一个素数，输出有多少种合法方案。

输入

多组输入数据，每组数据只有一个正整数n（2<=n<=16）代表有n个正整数 1,2,3…n

输出

对每组数据，输出一个整数，代表有多少种不同的可行方案数。

样例输入

6
8

样例输出

2
4

提示

对于输入样例中的6，有以下2种合法方案（首尾相连构成一个环）

1 4 3 2 5 6

1 6 5 2 3 4

对于输入样例中的8，有以下4种合法方案（首尾相连构成一个环）

1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

题意

素数环问题，dfs+回溯，是个排列树问题，注意约束剪枝。

思路

当层数等于n时跳出（往回走，即回溯） 判断下首尾加起来是不是素数，若是，则ans++; 否则什么也不做。

中间约束剪枝就是判断当前和前面一个加起来是不是素数，不是的话就直接剪。

普通的素数判定方法可能会TLE，所以判断素数最好打个表。原问题n最大是16，所以打30多的表就够了（16＋15==31） 。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int n,ans,last;
bool visited[32];
bool isPrime[40]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0};
void pc(int cur)
{
    if(cur == n && isPrime[1+last])
    {
        ans++;
        return;
    }
    for(int i = 2; i <= n; i++)
    {
        if(!visited[i] && isPrime[last+i])
        {
            int t = last;
            last = i;
            visited[i] = true;
            pc(cur+1);
            visited[i] = false;
            last = t;
        }
    }
}
int main()
{
    while(~scanf("%d",&n))
    {
        memset(visited,0,sizeof(visited));
        ans = 0;
        last = 1;
        pc(1);
        printf("%d\n",ans);
    }
    return 0;
}

问题 E: 数据加密

题目描述

密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码以获取通信情报的，称为破译学，总称密码学。密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为脱密变换。密码在早期仅对文字或数码进行加、脱密变换，随着通信技术的发展，对语音、图像、数据等都可实施加、脱密变换。
现在要求你用下面给定的方法对数据实现加密。给定长度为n的字符串S（1<=n<=2000,S中只有大写字母）作为明文，要求构造一个字符串T作为密文，起初T是一个空串，之后反复执行以下任意操作

1.从S的头部删除一个字符，加入到T的尾部
2.从S的尾部删除一个字符，加入到T的尾部

最后S会变成空串，T会变成一个长度为n的字符串作为密文。当然并非所有的构造方案都是符合条件的，我们要求构造出的密文T的字典序尽可能小，你能找出这个字典序最小的密文吗？

输入

输入包含多组数据，每组数据占两行，第一行为一个整数n（1<=n<=2000）代表字符串S的长度，第二行为一个长度为n的字符串S代表明文，保证S中只有大写字母

输出

对每组数据，输出一行字符串，代表构造出的字典序最小的密文T

样例输入

6
ACDBCB

样例输出

ABCBCD

提示

字典序是指从前往后比较两个字符串大小的方法。首先比较第1个字符，如果不同则第1个字符更小的字符串更小，如果相同则继续比较第2个字符……如此继续，来比较整个字符串的大小

题意

输入一个字符串S，要构造一个新字符串T，怎么构造呢？

每次选取S的头或尾，放到T的最后，最后输出字典序最小的T。

思路

当头和尾不等的时候好选，关键就是头和尾一样怎么办？

仔细想想，容易发现，假设头指针为i，尾指针为j，如果相同，则比较i+1和j-1，如果再相同，继续下去……

我们可以写个循环，如果相同继续比较，不同就跳出。头小flag置为true，否则置为false。

其实T字符串根本不用存，直接输出即可。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
    int n;
    char str[2005],ans[2005];
    while(~scanf("%d",&n))
    {
        scanf("%s",str);
        int i = 0,j = n-1;
        while(i <= j)
        {
            bool flag = false;
            for(int k = 0; i+k < j-k; k++)
            {
                if(str[i+k] < str[j-k])
                {
                    flag = true;
                    break;
                }
                if(str[i+k] > str[j-k]) break;
            }
            if(flag) printf("%c",str[i++]);
            else printf("%c",str[j--]);
        }
        printf("\n");
    }
    return 0;
}

本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/10/20/algorithm-meets-crypt/

Powered by Hexo
Theme - Material