自动搬运

查看原文

来自洛谷，原作者为

	Luxe877 已 AFO，再见 ||欢迎各位博士入团（arknights）：https://www.luogu.com.cn/team/91919

搬运于2025-08-24 21:39:54，当前版本为作者最后更新于2023-08-15 19:53:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接：P2636 密码破解者

本题是一道比较水简单字符串模拟题，题意也比较好理解。

大致题意

给你经过 $n$ 重加密的密文，以及密文的加密顺序及种类 $K$，让你反推原始明文并输出。

1.栅栏密码

其加密方式如下：以栏数 $X=2$ 为例，设原明文为 DistortedFate，其长度为 $len=13$。

将该明文分为 $2$ 个一段（其中最后一段若不能分为 $2$ 个一段，则独立成段）,即 Di st or te dF at e。

然后对于每段，每次选出第 $1$ 个字母加入到密文字符串中，即得 明文剩余部分：i t r e F t，密文：Dsotdae。

以此类推，经过 $2$ 次选取后该明文便被加密为密文 DsotdaeitreFt。

我们给密文的每一个字符标上它们在明文中的下标，如下：

密文字符：D s o t d  a  e i t r e  F t
对应下标：1 3 5 7 9 11 13 2 4 6 8 10 12 

我们可以发现，下标的增长是有规律的，以原先加密时选取的次数为段,下标呈等差数列形式增长，公差为 $X$，下标增长到 $\ge len$ 时换为下一段，每段的第一个字符的下标在区间 $\lbrack1,X\rbrack$ 之间。

因此，根据这样推断的结果，我们可以写出解栅栏密码的程序如下：

void fenceup(int x)
{
	int len=strlen(pw+1);
	char solve[10002];
	int duan=1;
	int p=duan;
	for(int i=1;i<=len;i++)
	{
		solve[p]=pw[i];
		p+=x;
		if(p>len)
		{
			duan++;
			p=duan;
		}
	}
	for(int i=1;i<=len;i++)
	{
		pw[i]=solve[i];
	}
}

2.维吉尼亚(Vigenère) 密码

其加密方式见此题：P1079 [NOIP2012 提高组] Vigenère 密码

由加密方式倒推，可以得到解密方式如下：

密文字符-密钥字符=明文字符

自然，和原加密时一样，解密时可能会导致减出来的 ASCII 码值小于字母，导致破译失败，因此在减的时候要同时 $+26$ 与取模，便可得出以下代码：

void vigne(char scw[])
{
	int len=strlen(pw+1),l=strlen(scw),tmp=0;
	char uncode[10002];
	bool upb;
	for(int i=1;i<=len;i++)
	{
		upb=false;
		if(pw[i]>='A'&&pw[i]<='Z')
		{
			upb=true;
			pw[i]=pw[i]-'A'+'a';
		}
		if(scw[tmp]>='A'&&scw[tmp]<='Z')
		{
			scw[tmp]=scw[tmp]-'A'+'a';
		}
		uncode[i]=(pw[i]-scw[tmp]+26)%26+'a';
		if(upb)
		{
			uncode[i]=uncode[i]-'a'+'A';
		}
		tmp=(tmp+1)%l;
	}
	for(int i=1;i<=len;i++)
	{
		pw[i]=uncode[i];
	}
}

3.QWE 键盘码

其加密方式较为简单，由键盘上 Q 键开始为 A， W 键为 B，以此类推至全部字母键，只需要提前写好对应密文的数组访问即可，代码如下：

void keybd()
{
	char word[52]={'k','x','v','m','c','n','o','p','h','q','r','s','z','y','i','j','a','d','l','e','g','w','b','u','f','t'};
	int len=strlen(pw+1);
	bool upb;
	for(int i=1;i<=len;i++)
	{
		upb=false;
		if(pw[i]>='A'&&pw[i]<='Z')
		{
			pw[i]=pw[i]-'A'+'a';
			upb=true;
		}
		pw[i]=word[pw[i]-'a'];
		if(upb)
		{
			pw[i]=pw[i]-'a'+'A';
		}
	}
}

最后，处理好输入输出即可得出正解。代码如下：

#include<bits/stdc++.h>
using namespace std;
int n;
char pw[10002];
struct nd{
	int type;
	char spw[1002];
	int mvw;
}uns[1012];
void fenceup(int x)//分 X 段 
{
	int len=strlen(pw+1);
	char solve[10002];
	int duan=1;//段数
	int p=duan;//密文下标
	for(int i=1;i<=len;i++)
	{
		solve[p]=pw[i];
		p+=x;
		if(p>len)//下标超过明文长度时换为下一行统计
		{
			duan++;
			p=duan;
		}
	}
	for(int i=1;i<=len;i++)
	{
		pw[i]=solve[i];
	}
//	cout<<pw+1<<endl;
}
void vigne(char scw[])
{
	int len=strlen(pw+1),l=strlen(scw),tmp=0;
	char uncode[10002];
	bool upb;
	for(int i=1;i<=len;i++)
	{
		upb=false;
		if(pw[i]>='A'&&pw[i]<='Z')//大小写处理
		{
			upb=true;
			pw[i]=pw[i]-'A'+'a';
		}
		if(scw[tmp]>='A'&&scw[tmp]<='Z')//大小写处理
		{
			scw[tmp]=scw[tmp]-'A'+'a';
		}
		uncode[i]=(pw[i]-scw[tmp]+26)%26+'a';//解密(注意不要忘了+26、%26、+'a')
		if(upb)//大小写处理
		{
			uncode[i]=uncode[i]-'a'+'A';
		}
		tmp=(tmp+1)%l;
	}
	for(int i=1;i<=len;i++)
	{
		pw[i]=uncode[i];
	}
//	cout<<pw+1<<endl;
}
void keybd()
{
	char word[52]={'k','x','v','m','c','n','o','p','h','q','r','s','z','y','i','j','a','d','l','e','g','w','b','u','f','t'};//存储对应密文
	int len=strlen(pw+1);
	bool upb;//大写区分 
	for(int i=1;i<=len;i++)
	{
		upb=false;
		if(pw[i]>='A'&&pw[i]<='Z')//大小写处理
		{
			pw[i]=pw[i]-'A'+'a';
			upb=true;
		}
		pw[i]=word[pw[i]-'a'];
		if(upb)//大小写处理
		{
			pw[i]=pw[i]-'a'+'A';
		}
	}
//	cout<<pw+1<<endl;
}
int main()
{
	cin>>n>>pw+1;
	for(int i=1;i<=n;i++)
	{
		cin>>uns[i].type;
		if(uns[i].type==1)
		{
			cin>>uns[i].mvw;
			continue;
		}
		if(uns[i].type==2)
		{
			cin>>uns[i].spw+1;
		}
	}
	for(int i=n;i>=1;i--)
	{
		if(uns[i].type==1)
		{
			fenceup(uns[i].mvw);
			continue;
		}
		if(uns[i].type==2)
		{
			vigne(uns[i].spw+1);
			continue;
		}
		if(uns[i].type==3)
		{
			keybd();
			continue;
		}
	}
	cout<<pw+1<<endl;
	return 0;
}

注意事项（坑点）

• 1. 大小写要注意转换，解密时要化为同一形式。
• 2. Vigenère 密码解密时要加和取模 $26$。
• 3. 不要输错 QWE 键盘码的对应密文。
• 4. 建议使用 char a[] 类型存储明文和密文，不建议使用 string 类型（本人的悲伤遭遇）。

后记

本题解为萌新的首篇题解，$LateX$ 在编辑的时候加载得不太好，审核大大求过。