BZOJ2145 - [2011国家集训队命题答辩]悄悄话

2017/03/08

不是很懂出这种题为啥还要卡字典。

题目

给十个字符串,一行一个,都是凯撒移位过的,求原串。

不难想到先枚举移位的 offset ,然后通过频率分析和关键词来乱搞一个 voting。

日常经验: 1. 上 Tsinsen 做这道题可以看到每个点的详细情况。 2. 使用 hzwer 大爷的字典。

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <deque>
#include <set>
#include <cctype>
#include <cstring>
using namespace std;

deque<string> L;
set<string> StopWord;
int wei[26];

#define SW(x) StopWord.insert(x)
#define WE(x, w) wei[x - 'a'] = w
void init() {
    // art.
    SW("an");
    SW("the");

    // prep.
    SW("in"); SW("on"); SW("with"); SW("by");
    SW("for"); SW("at"); SW("about"); SW("under");
    SW("of"); SW("from"); SW("to");

    // be
    SW("am"); SW("is"); SW("are"); SW("was"); SW("were");

    // pron.
    SW("you"); SW("we"); SW("it"); SW("he"); SW("she"); SW("they");

    // hzwer
    SW("how"); SW("do"); SW("all"); SW("but"); SW("adam"); SW("madam");
    SW("if"); SW("and");

    WE('a', 1); WE('s', 1); WE('i', 1); WE('n', 1); WE('t', 1);
    WE('o', 1); WE('e', 2); WE('r', 1);
    WE('j', -5); WE('q', -5); WE('x', -5); WE('z', -5);
}

bool isSW(const string &s) {
    return StopWord.find(s) != StopWord.end();
}

void tokenize(string s) {
    int _ = s.size();
    string cur;
    for(int i=0;i<_;i++) {
        if(s[i] == ' ' || s[i] == '\n' || ispunct(s[i])) {
            if(!cur.empty()) {
                L.push_back(cur);
                cur.clear();
            }
            if(ispunct(s[i])) L.push_back(string("") + s[i]);
        } else {
            cur = cur + s[i];
        }
    }

}

string shift(const string &s, int offs) {
    string a = s;
    int _ = s.size();
    for(int i=0;i<_;i++) {
        if(a[i] >= 'a' && a[i] <= 'z') {
            int code = a[i] - 'a';
            code = (code + offs) % 26;
            a[i] = char(code + 'a');
        }

        if(a[i] >= 'A' && a[i] <= 'Z') {
            int code = a[i] - 'A';
            code = (code + offs) % 26;
            a[i] = char(code + 'A');
        }
    }

    return a;
}

string lowercase(const string &s) {
    string a = s;
    int _ = s.size();
    for(int i=0;i<_;i++) {
        if(a[i] >= 'A' && a[i] <= 'Z') {
            a[i] = a[i] - 'A' + 'a';
        }
    }

    return s;
}

int score(int offs) {
    typedef deque<string>::iterator It;
    int sc = 0;
    for(It i=L.begin();i!=L.end();++i) {
        string sft = shift(*i, offs);
        string cur = lowercase(sft);
        if(isSW(cur)) sc += 7;
        if(sft == "I") sc += 7;

        int _ = cur.size();
        for(int j=0;j<_;j++) {
            if(islower(cur[j])) {
                sc += wei[cur[j] - 'a'];
            }
        }
    }
    return sc;
}

int main() {
    init();

    for(int i=0;i<10;i++) {
        L.clear();
        string ln;
        getline(cin, ln);

        tokenize(ln);

        int ans = 0, anssc = 0, tmp;
        for(int offset=0;offset<26;offset++) {
            tmp = score(offset);
            if((tmp) > anssc) {
                ans = offset;
                anssc = tmp;
            }
        }

        cout << shift(ln, ans) << endl;
    }
}