「BZOJ2145」悄悄话

2014年10月23日5,2389

试题来源

　　2011中国国家集训队命题答辩

问题描述

　　在这个有话不直说的年代，密码学越来越被广泛接受。
我们引用经典的“凯撒密码”。
在英文中，凯撒加密只对26个字母生效（分大小写）
我们按照a到z来排字母。
凯撒加密的原理就是把原文的每一个字母都按顺序往后移K位。这个K将被作为密钥。（’a’往后移变成’b’，’z’往后移会变成’a’）

（0≤K≤25）
现在给出一系列用凯撒加密的英文句子，请你编写程序逐句翻译。
也就是说，请你确定一个密钥，使得解码以后的文字最符合英文的规则与规范。
数据保证存在唯一的解码方案，使得明码是完全可以分辨的英文句子。

输入格式

　　输入一定包括10行
每一行都是用同一密钥加密的英文。

输出格式

　　输出10行，为解密结果。不允许格式上有任何不同。

样例输入

Welcome to the test. This is the 1st sample test case.
Vdkbnld sn sgd sdrs. Sghr hr sgd 2mc rzlokd sdrs bzrd.
Welcome to the test. This is the 3rd sample test case.
Nvctfdv kf kyv kvjk. Kyzj zj kyv 4ky jrdgcv kvjk trjv.
Govmywo dy dro docd. Drsc sc dro 5dr ckwzvo docd mkco.
Nvctfdv kf kyv kvjk. Kyzj zj kyv 6ky jrdgcv kvjk trjv.
Jrypbzr gb gur grfg. Guvf vf gur 7gu fnzcyr grfg pnfr.
Ucjamkc rm rfc rcqr. Rfgq gq rfc 8rf qyknjc rcqr ayqc.
Ckriusk zu znk zkyz. Znoy oy znk 9zn ygsvrk zkyz igyk.
Xfmdpnf up uif uftu. Uijt jt uif mbtu tbnqmf uftu dbtf.

样例输出

Welcome to the test. This is the 1st sample test case.
Welcome to the test. This is the 2nd sample test case.
Welcome to the test. This is the 3rd sample test case.
Welcome to the test. This is the 4th sample test case.
Welcome to the test. This is the 5th sample test case.
Welcome to the test. This is the 6th sample test case.
Welcome to the test. This is the 7th sample test case.
Welcome to the test. This is the 8th sample test case.
Welcome to the test. This is the 9th sample test case.
Welcome to the test. This is the last sample test case.

数据说明

　　数据将从不同的方面考察。请尽量保证程序的准确性。
每一行长度不会太短(不少于3个单词的完整句)。没有全角字符和其他语言符号，可能包含半角空格和标点。
单个测试点不超过5kB。

题解

按照字母和单词的出现频率来估价。。

字母出现最多的是a sin to err

最少是zxvpbjkq 输入法告诉我是只需旁边几块钱

单词就随便写几个

95分，真是无能为力了。。。

然后我研究了下数据，发现有些坑点

Just do it！

How do you do？

Madam，I‘m Adam

然后我机智的修改了参数

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int T=10,l,ans,mx;
string a[26];
string ch[20]={"you","it","he","do","they","we","if","and","but","how","was",
			   "is","are","the","on","in","of","to","all","a"};
char t1[8]={'a','s','i','n','t','o','e','r'};
char t2[8]={'z','q','j','x','z','q','j','x'};
int val[26],typ[10005];
int cal(int x)
{
    int sum=0;
    for(int i=0;i<l;i++)
		if(a[x][i]>='a'&&a[x][i]<='z')
		{
			sum+=val[a[x][i]-'a'];
			if(a[x][i]=='i'&&typ[i]==1)sum+=5;
		}
    for(int i=0;i<l;i++)
		if(!i||typ[i-1]==2)
			for(int k=0;k<20;k++)
			{
				int t=ch[k].length();
				if(typ[i+t]==2)
				{
					string tmp="";
					for(int s=0;s<t;s++)
						tmp+=a[x][i+s];
					if(tmp==ch[k])
					{
						sum+=4;break;
					}
				}
			}
    return sum;
}
int main()
{
    for(int i=0;i<8;i++)
		val[t1[i]-'a']++,val[t2[i]-'a']--;
    while(T--)
    {
		mx=0;memset(typ,0,sizeof(typ));
		getline(cin,a[0]);
		l=a[0].length();typ[l]=2;
		for(int i=0;i<l;i++)
			if(a[0][i]>='A'&&a[0][i]<='Z')
			{
				typ[i]=1;a[0][i]=a[0][i]-'A'+'a';
			}
			else if(a[0][i]=='\'')typ[i]=-1;
			else if(a[0][i]<'a'||a[0][i]>'z')typ[i]=2;
		for(int i=1;i<26;i++)
		{
			a[i]="";
			for(int j=0;j<l;j++)
				if(a[0][j]>='a'&&a[0][j]<='z')
					a[i]+=(char)(((int)a[0][j]-'a'+i)%26+'a');
				else a[i]+=a[0][j];
		}
		for(int i=0;i<26;i++)
		{
			int t=cal(i);
			if(t>=mx)
				ans=i,mx=t;
		}
		for(int i=0;i<l;i++)
			if(typ[i]==1)a[ans][i]=a[ans][i]-'a'+'A';
		cout<<a[ans]<<endl;
    }
    return 0;
}

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int T=10,l,ans,mx;

string a[26];

string ch[20]={"you","it","he","do","they","we","if","and","but","how","was",

"is","are","the","on","in","of","to","all","a"};

char t1[8]={'a','s','i','n','t','o','e','r'};

char t2[8]={'z','q','j','x','z','q','j','x'};

int val[26],typ[10005];

int cal(int x)

{

int sum=0;

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

if(a[x][i]>='a'&&a[x][i]<='z')

{

sum+=val[a[x][i]-'a'];

if(a[x][i]=='i'&&typ[i]==1)sum+=5;

}

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

if(!i||typ[i-1]==2)

for(int k=0;k<20;k++)

{

int t=ch[k].length();

if(typ[i+t]==2)

{

string tmp="";

for(int s=0;s<t;s++)

tmp+=a[x][i+s];

if(tmp==ch[k])

{

sum+=4;break;

}

return sum;

}

int main()

{

for(int i=0;i<8;i++)

val[t1[i]-'a']++,val[t2[i]-'a']--;

while(T--)

{

mx=0;memset(typ,0,sizeof(typ));

getline(cin,a[0]);

l=a[0].length();typ[l]=2;

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

if(a[0][i]>='A'&&a[0][i]<='Z')

{

typ[i]=1;a[0][i]=a[0][i]-'A'+'a';

}

else if(a[0][i]=='\'')typ[i]=-1;

else if(a[0][i]<'a'||a[0][i]>'z')typ[i]=2;

for(int i=1;i<26;i++)

{

a[i]="";

for(int j=0;j<l;j++)

if(a[0][j]>='a'&&a[0][j]<='z')

a[i]+=(char)(((int)a[0][j]-'a'+i)%26+'a');

else a[i]+=a[0][j];

}

for(int i=0;i<26;i++)

{

int t=cal(i);

if(t>=mx)

ans=i,mx=t;

}

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

if(typ[i]==1)a[ans][i]=a[ans][i]-'a'+'A';

cout<<a[ans]<<endl;

}

return 0;

}

「CFgym100514R」6227020800 »

conic

你有这道题数据吧？QWQ

hzwer

没有。我在青橙测的

hzwer

噢。。我后来好像找某位神犇要了。。。

conic

731428136@qq.com ← ← 能发给我吗

翁家翌

http://110.90.118.124/OnlineJudge/Data/1591/

conic

好评

conic

可是为什么不能在这个OJ上注册账号..

hzwer

福州一中内部OJ

bzoj 2145 悄悄话一道比较有意思的题 | Chenyao's blog

[…] 是在hzwer的博客上看到这道题的,发现他用是枚举’位移长度’.把常用单词,常用字母字母和不常用字母给一个权值,计算句子总权值,进行估价选择最优句子. […]

hzwer.com _ Home | http://hzwer.com

「BZOJ2145」悄悄话

分类目录

热门文章

Myfriends

近期评论