云南旅游网站建设公司,家庭网站建设,珠海做网站多少钱,为什么学网站开发题目#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id4319 如果字符集有 5e5 那么大的话#xff0c;挨个填上去就行了。但只有26个字符#xff0c;所以要贪心地尽量填和上一次一样的字符。 按 sa[ ] 的顺序从小到大填字符#xff0c;判断这个位置 x 能否填上…题目https://www.lydsy.com/JudgeOnline/problem.php?id4319 如果字符集有 5e5 那么大的话挨个填上去就行了。但只有26个字符所以要贪心地尽量填和上一次一样的字符。 按 sa[ ] 的顺序从小到大填字符判断这个位置 x 能否填上一次在 y 填的字符的条件就是 rk[ x1 ] rk[ y1 ]。 因为 x 的字典序比 y 大而 x 位置要填和 y 一样的字符所以 x 的后面应该比 y 大。发现后面部分也是两个后缀所以利用“接下来会使它们合法”这一限制就能判断 x 位置填什么了。 自己的思路有待锻炼要尝试归纳限制条件 #includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N5e55;
int n,sa[N],rk[N];
char a[N];
int rdn()
{int ret0;bool fx1;char chgetchar();while(ch9||ch0){if(ch-)fx0;chgetchar();}while(ch0ch9) retret*10ch-0,chgetchar();return fx?ret:-ret;
}
int main()
{nrdn();for(int i1;in;i)sa[i]rdn(),rk[sa[i]]i;int i,p0;a[sa[1]]0;for(i2;in;i){if(rk[sa[i]1]rk[sa[i-1]1])a[sa[i]]p;else {a[sa[i]]p;if(p26)break;}}if(in)puts(-1);else {for(int i1;in;i)putchar(a[i]a);puts();}return 0;
} 转载于:https://www.cnblogs.com/Narh/p/10079748.html
