E. Ann and Half-Palindrome
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/557/problem/E
Description
On the last theoretical class the teacher introduced the notion of a half-palindrome.
String t is a half-palindrome, if for all the odd positions i () the following condition is held: ti = t|t| - i + 1, where |t| is the length of string t if positions are indexed from 1. For example, strings "abaa", "a", "bb", "abbbaa" are half-palindromes and strings "ab", "bba" and "aaabaa" are not.
Ann knows that on the exam she will get string s, consisting only of letters a and b, and number k. To get an excellent mark she has to find the k-th in the lexicographical order string among all substrings of s that are half-palyndromes. Note that each substring in this order is considered as many times as many times it occurs in s.
The teachers guarantees that the given number k doesn't exceed the number of substrings of the given string that are half-palindromes.
Can you cope with this problem?
Input
The first line of the input contains string s (1 ≤ |s| ≤ 5000), consisting only of characters 'a' and 'b', where |s| is the length of string s.
The second line contains a positive integer k — the lexicographical number of the requested string among all the half-palindrome substrings of the given string s. The strings are numbered starting from one.
It is guaranteed that number k doesn't exceed the number of substrings of the given string that are half-palindromes.
Output
Print a substring of the given string that is the k-th in the lexicographical order of all substrings of the given string that are half-palindromes.
Sample Input
abbabaab
7
Sample Output
abaa
HINT
题意
定义了半回文串，即奇数位置上的数是回文的
给你个字符串，在他的子串中，让你找到第k大的半回文子串
题解：
先暴力出回文串的子串
然后强行插入字典树，再强行dfs一下
超级大暴力就好了
代码来源于http://codeforces.com/contest/557/submission/11866823
代码
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) #define maxn 5005 #define mod 10007 #define eps 1e-9 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** struct trie { int cnt,ch[2]; }; int ok[maxn][maxn]; trie T[maxn*(maxn+1)/2]; trie null; char res[maxn]; string s; int k,ts,m=-1,root,n; int newnode() { T[++ts]=null; return ts; } void add(int i) { int cur=root; for(int j=i;j<n;j++) { if(T[cur].ch[s[j]-'a']==-1) T[cur].ch[s[j]-'a']=newnode(); cur=T[cur].ch[s[j]-'a']; if(ok[i][j]) T[cur].cnt++; } } void dfs(int cur) { k-=T[cur].cnt; if (k<=0) { printf("%s",res); exit(0); } if (T[cur].ch[0]!=-1) { res[++m]='a'; dfs(T[cur].ch[0]); res[m]=0;m--; } if (T[cur].ch[1]!=-1) { res[++m]='b'; dfs(T[cur].ch[1]); res[m]=0;m--; } } int main() { cin>>s>>k; n=s.size(); null.cnt=0,null.ch[0]=null.ch[1]=-1; root=newnode(); for(int len=1;len<=n;len++) { for(int i=0;i<=n-len;i++) { int j=i+len-1; if(j-i<=3) ok[i][j]=(s[i]==s[j]); else ok[i][j]=(s[i]==s[j])&&ok[i+2][j-2]; } } for(int i=0;i<n;i++) add(i); dfs(root); }