cipher_lzx.cpp

第四届百度杯预赛解题报告 武汉大学20090315

#include <iostream>
#include <cstdio>
#include <cassert>
using namespace std;

char table[8][8];
int used[64], hash[64][2];

string prev(const string& x) {
	string p = "";
	for (unsigned int i = 0; i < x.size(); ++i) {
        if (x[i] == 'j' || x[i] == 'J') {
            p += 'I';
        }
        else if (x[i] >= 'a' && x[i] <= 'z') {
			p += x[i] - 'a' + 'A';
		}
        else if (x[i] >= 'A' && x[i] <= 'Z') {
			p += x[i];
		}
	}
	return p;
}

void playfair_table(const string& key) {
    memset(table, 0, sizeof(table));
    memset(used, -1, sizeof(used));
    memset(hash, -1, sizeof(hash));
    used['J' - 'A'] = true;
    int cnt = 0;
    for (unsigned int i = 0; i < key.size(); ++i) {
        if (used[key[i] - 'A'] == 1) {
            continue;
        }
        else {
            table[cnt / 5][cnt % 5] = key[i];
            hash[key[i] - 'A'][0] = cnt / 5, hash[key[i] - 'A'][1] = cnt % 5;
            used[key[i] - 'A'] = 1;
            ++cnt;
        }
    }
    for (unsigned int i = 0; i < 26; ++i) {
        if (used[i] == -1) {
            used[i] = 1;
            table[cnt / 5][cnt % 5] = i + 'A';
            hash[i][0] = cnt / 5, hash[i][1] = cnt % 5;
            ++cnt;
        }
    }
    for (int i = 0; i < 5; ++i) {
        table[i][5] = '\0';
//        cout << table[i] << endl;
    }
    hash['J' - 'A'][0] = hash['I' - 'A'][0], hash['J' - 'A'][1] = hash['I' - 'A'][1];
//    for (int i = 0; i < 26; ++i) {
//        printf("%c %d %d\n", i + 'A', hash[i][0], hash[i][1]);
//    }
}

string encrypt(const string& temp) {
    string res = "";
    for (unsigned int i = 0; i < temp.size(); i += 2) {
        assert(temp[i] != temp[i + 1]);
        int x0 = hash[temp[i] - 'A'][0], y0 = hash[temp[i] - 'A'][1];
        int x1 = hash[temp[i + 1] - 'A'][0], y1 = hash[temp[i + 1] - 'A'][1];
        if (x0 == x1) {
            res += table[x0][(y0 + 1) % 5];
            res += table[x1][(y1 + 1) % 5];
        }
        else if (y0 == y1) {
            res += table[(x0 + 1) % 5][y0];
            res += table[(x1 + 1) % 5][y1];
        }
        else {
            res += table[x0][y1]; res += table[x1][y0];
        }
    }
    return res;
}

int main() {
	string key, message, line;
	int T;
    cin >> T;
    getline(cin, line);
    while (T--) {
        getline(cin, key);
		getline(cin, message);
		key = prev(key); message = prev(message);
		playfair_table(key);
		string temp = "";
		unsigned int i = 0;
		while (i < message.size()) {
			if (message[i] == temp[temp.size() - 1]) {
				temp += 'X';
			}
			else {
				temp += message[i++];
			}
		}
		if (temp.size() % 2 == 1) temp += 'X';
		cout << encrypt(temp) << endl;
	}
	return 0;
}