首页 > 代码库 > POJ 1590 Palindromes 肯爹题

POJ 1590 Palindromes 肯爹题

本题就是专门肯人的题目,给出的列子也是故意误导人的。

其实就考一点:没有mirror的字母存在的时候就可以判定整个字符串不是mirror!

如下面的mirrored string的叙述:

A mirrored string is a string for which when each of the elements of the string is changed to its reverse (if it has a reverse) and the string is read backwards the result is the same as the original string. For example, the string "3AIAE" is a mirrored string because "A" and "I" are their own reverses, and "3" and "E" are each others‘ reverses. 

愣是没说没有mirror的时候如何判断,要自己猜测。

题意重要,聪明地判断题意也很重要。高端人才,各种陷阱,各种细节都要考虑到极致了。

本来找Palindrome的题目做做,看到这么简单本来不想做的,花了几分钟敲出代码来,居然WA,没想到也学到东西了。不能小看任何所谓“水”题啊。

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

bool mirror, palin;
char tbl[256];

void initTable()
{
	memset(tbl, 0, sizeof(tbl));
	tbl['A'] = 'A';
	tbl['E'] = '3';
	tbl['H'] = 'H';
	tbl['I'] = 'I';
	tbl['J'] = 'L';
	tbl['L'] = 'J';
	tbl['S'] = '2';
	tbl['M'] = 'M';
	tbl['O'] = 'O';
	tbl['T'] = 'T';
	tbl['U'] = 'U';
	tbl['V'] = 'V';
	tbl['W'] = 'W';
	tbl['X'] = 'X';
	tbl['Y'] = 'Y';
	tbl['1'] = '1';
	tbl['Z'] = '5';
	tbl['2'] = 'S';
	tbl['3'] = 'E';
	tbl['5'] = 'Z';
	tbl['8'] = '8';
}

void getPalinMirror(string &s)
{
	palin = true;
	for (int i = 0, j = (int)s.size()-1; i < j && palin; i++, j--)
	{
		if (s[i] != s[j]) palin = false;

	}
	mirror = true;
	for (int i = 0, j = (int)s.size()-1; i <= j && mirror; i++, j--)
	{
		if (!tbl[s[i]] || s[i] != tbl[s[j]]) mirror = false;
	}
}

int main()
{
	string s;
	initTable();
	while (cin>>s)
	{
		getPalinMirror(s);
		printf("%s", s.c_str());
		if (!palin && !mirror) puts(" -- is not a palindrome.");
		else if (palin && !mirror) puts(" -- is a regular palindrome.");
		else if (!palin && mirror) puts(" -- is a mirrored string.");
		else if (palin && mirror) puts(" -- is a mirrored palindrome.");
		putchar('\n');
	}
	return 0;
}