- 构造类题目.
仔细看样例解释能发现点东西?
- 结论:答案只可能是 (Impossible,1,2) .
- (Impossible:) 有 (n) 个或 (n-1) 个相同的字母,显然无法拼出另一个回文串.
(样例3)
- (1:) (Cut) (1) 次,相当于是做了原串的一个循环排列. (O(n^2)) 对所有循环排列验证是否符合要求即可.
(样例4)
- (2:) 在原串中找出一段 (len<n/2) 的前缀以及与它等长的后缀,将它们 (Cut) 出后交换.若所有的前缀与对应交换后都不符合要求,则一定是 (Impossible) 对应的两种局面,否则至少有一个前缀 (pre) 满足 (pre!=inverse(pre)),即它对应的 (suf) ,交换两者即得一个合法的解.
(样例1)
- 只需判断是否为前 (2) 种情况,时间复杂度为 (O(n^2)) .
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
{
int x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
const int MAXN=5e3+10;
int n;
char s[MAXN];
int t[MAXN];
bool judge_imp()
{
for(int i=1;i<=n;++i)
if(++t[s[i]]>=n-1)
return true;
return false;
}
char curs[MAXN];
bool judge_palindrome()
{
for(int i=1;i<=n/2;++i)
if(curs[i]!=curs[n+1-i])
return false;
return true;
}
bool judge_unique()
{
for(int i=1;i<=n;++i)
if(curs[i]!=s[i])
return true;
return false;
}
bool judge_one()
{
for(int pos=2;pos<=n;++pos)// s[pos] is the first element
{
int p=0;
for(int i=pos;i<=n;++i)
curs[++p]=s[i];
for(int i=1;i<pos;++i)
curs[++p]=s[i];
if(judge_palindrome() && judge_unique())
return true;
}
return false;
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
if(judge_imp())
return puts("Impossible")&0;
if(judge_one())
return puts("1")&0;
puts("2");
return 0;
}