[COCI2013-2014#5] LOZINKA

前言

        又是一个刷题的好日子，我点击了洛谷的“随机跳题”功能，做起了今天的第一道题目(是道橙题)......

---

原链接[COCI2013-2014#5] LOZINKA - 洛谷https://www.luogu.com.cn/problem/P7672

---

题目描述

        给出一些长度为奇数的字符串，请你找出一个字符串，且它反转后的字符串也在给出的字符串中。例如字符串abcca，如果满足条件，则字符串accba 也必须出现在输入的字符串中。

        输出这个字符串的长度和它处于最中间的字符。

---

输入

输入共n+1行：

第1行，一个整数N，表示给出的字符串的个数；

第2至n+1行，每行一个字符串。

---

输出

        输出共1行，一个整数和一个字符，用空格隔开，分别表示符合要求的字符串的长度和它处于字符串中间的字符。

---

样例组

样例1
输入
4
las
god
psala
sal
输出
3 a
 
样例2
4
kisik
ptq
tttrp
tulipan
输出
5 s

---

解题思路1

        这道题目乍一看是一道非常简单的字符串题目。开一个数组S储存读入的每一个数，然后暴力枚举环i，开字符串变量ss储存翻转后的s[i]，再将j枚举一遍，判断ss与s[j]算法相等，若相等直接输出题目所要求的就行了。

        不一会就写完了：

#include
#define N 10006
using namespace std;
int n;string s[N];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s[i];
		string ss=s[i];
		reverse(ss.begin(),ss.end());
		for(int j=1;j<=i;j++)
		{
			if(ss==s[j])
			{
				cout<' '<2+1];
				return 0;
			}
		}
	}
	return 0; 
}

        样例都过了，可就是不知道为什么，测试数据却一个也没过......

---

解题思路2

        /*看来这道题目一点也不简单......

        既然暴力枚举是行不通的，那么还可以用字符串哈希的方法来做。正常的哈希表肯定是做不了的(下标是字符串)，要用这种方法做需要一个struct。

        但是相较于只有两个变量的struct，我更喜欢用STL里的pair。可是用pair写(自从把STL彻底学完后)，哪里比得上写一个map呢(只要看到下标是字符串，基本上就是map的题目)？*/ 

        这道题目应该用map做。首先读入字符串，翻转字符串，再判断map里面是否有这个字符串(以此为下标的那个值不是0)，如果不是0，输出(这里单独写一个输出函数)，否则将这个字符串存入map(a[x]++;)。

        输出函数只有一行(具体应该是两行)，十分简单：

void sc(string s)
{cout<size()<<' '<size()/2];}

---

正确思路

        但像刚才那样做似乎只能过第一个样例，而过不了第二个样例......

        为了解决这个问题(实际上是避免开S数组)，我们可以特殊处理当读入的字符串为回文串的情况。因此要解决这道题目可以写一个判回文串函数，从而使第二个样例通过(如果可以通过，直接输出；否则继续map操作)。

        判回文串函数特别简单，只需要借助reverse函数就可以实现：

bool hws(string s)
{
	string ss=s;
	reverse(ss.begin(),ss.end());
	if(ss==s) return 1;
	return 0;
}

        这样就可以AC了。

---

（具体代码见下篇)