BZOJ 2145: 悄悄话 （打表）

BZOJ 2145

题解

直接代词，所有格，常用副词，助动词，冠词，常用词打表 比较出现次数的多少来决定循环位移了几位。

CODE

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5200;

const int p = 137;

typedef unsigned long long ULL;

map<int,bool>vis;

inline ULL hsh(const char *s) {

	ULL re = 0; int i = 0;

	while(s[i])

		re = re * p + (ULL)s[i++];

	return re;

}

inline void ins(const char *s) { vis[hsh(s)] = 1; }

inline void dictionary() {

	ins("his");

	ins("her");

	ins("is");

	ins("are");

	ins("who");

	ins("whom");

	ins("whose");

	ins("whoever");

	ins("was");

	ins("were");

	ins("i");

	ins("we");

	ins("you");

	ins("they");

	ins("them");

	ins("me");

	ins("go");

	ins("and");

	ins("no");

	ins("please");

	ins("or");

	ins("but");

	ins("so");

	ins("because");

	ins("although");

	ins("good");

	ins("bad");

	ins("well");

	ins("happy");

	ins("a");

	ins("the");

	ins("at");

	ins("i'm");

	ins("in");

	ins("on");

	ins("by");

	ins("my");

	ins("your");

	ins("rather");

	ins("than");

	ins("little");

	ins("few");

	ins("fewer");

	ins("what");

	ins("how");

	ins("when");

	ins("where");

	ins("be");

	ins("also");

	ins("make");

	ins("do");

	ins("did");

	ins("done");

	ins("up");

	ins("down");

	ins("of");

	ins("had");

	ins("has");

	ins("have");

	ins("since");

	ins("it");

	ins("its");

	ins("think");

	ins("thought");

	ins("thinking");

	ins("their");

	ins("for");

	ins("find");

	ins("with");

	ins("been");

	ins("better");

	ins("worse");

	ins("more");

	ins("less");

	ins("fine");

	ins("set");

	ins("you're");

	ins("right");

	ins("can");

	ins("could");

	ins("should");

	ins("would");

	ins("that");

	ins("this");

	ins("those");

	ins("these");

	ins("against");

	ins("back");

	ins("about");

	ins("many");

	ins("much");

	ins("as");

	ins("now");

	ins("own");

	ins("our");

	ins("from");

	ins("work");

	ins("will");

	ins("worst");

	ins("best");

	ins("never");

	ins("ever");

	ins("since");

	ins("hit");

	ins("within");

	ins("before");

	ins("after");

	ins("if");

	ins("whether");

	ins("something");

	ins("someone");

	ins("somebody");

	ins("anything");

	ins("anyone");

	ins("anybody");

	ins("nothing");

	ins("nobody");

	ins("none");

	ins("whatever");

	ins("however");

	ins("wherever");

	ins("finally");

	ins("home");

	ins("very");

	ins("quite");

	ins("an");

	ins("only");

	ins("not");

	ins("while");

	ins("off");

	ins("out");

	ins("you're");

}

char s[5005], tmp[5005];

int l[5005], r[5005];

inline char solve(char x, int k) {

	if(!isalpha(x)) return x;

	if(x >= 'A' && x <= 'Z') return 'a' + (x-'A'+k)%26;

	else return 'a' + (x-'a'+k)%26;

}

inline bool chk(char x) { return x == ' '|| x == ',' || x == '.' || x == '?' || x == '!' || x == ';' || x == '\n'; }

inline void get(char *S) {

	char ch; int i = 0;

	while((ch=getchar())=='\n');

	S[i++] = ch;

	while((ch=getchar())!='\n')S[i++]=ch;

	S[i] = 0;

}

int main () {

	dictionary();

	int T = 10;

	while(T--) {

		int cur = 0, n;

		get(s); n = strlen(s);

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

			if(i == 0 || chk(s[i-1])) l[++cur] = i;

			if(i == n-1 || chk(s[i+1])) r[cur] = i;

		}

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

			if(s[r[i]] == '.' || s[r[i]] == '?' || s[r[i]] == '!' || s[r[i]] == ';' || s[r[i]] == ',') --r[i];

		int mx = 0, ans = 0;

		for(int k = 0; k <= 25; ++k) {

			int now = 0;

			for(int i = 1; i <= cur; ++i) {

				for(int j = l[i]; j <= r[i]; ++j)

					tmp[j-l[i]] = solve(s[j], k);

				tmp[r[i]-l[i]+1] = 0;

				now += vis[hsh(tmp)];

			}

			if(now > mx) mx = now, ans = k;

		}

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

			if(!isalpha(s[i])) putchar(s[i]);

			else putchar(s[i] = (s[i] >= 'A' && s[i] <= 'Z') ? 'A' + (s[i]-'A'+ans) % 26 : 'a' + (s[i]-'a'+ans) % 26);

		}

		if(T) puts("");

	}

}