“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 CSL的字符串

“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 CSL的字符串

题目链接：

解题思路：遍历字符串，模拟获取最大子串的过程。

用一个栈来模拟。

如果当前字符比栈顶字符小，且栈顶字符不是字符串中最后一位该字符时，把栈顶字符踢掉。直到踢到不能在踢。然后把当前遍历字符入栈。

不过，前提是当前遍历字符没有在栈中出现过。

说不清怎么证明，只是学到了一种模拟的思路。

以后写写其他题有思路了再来补充一下。

代码：

#include<cstdio>
#include<cstring>
#define idx(i) s[i]-32
#define alp(i) sta[i]+32const int N = 1e5+5;char s[N];
int sta[100],cnt[100];
bool vis[100];int main()
{while (~scanf("%s",s)){memset(vis,false,sizeof vis);int len = strlen(s);for (int i=0;i<len;i++) cnt[idx(i)]++;int top = -1;for (int i=0;i<len;i++){cnt[idx(i)]--;if (!vis[idx(i)]){while (top>=0 && idx(i)<sta[top] && cnt[sta[top]]>0){vis[sta[top--]] = false;}sta[++top] = idx(i);}vis[idx(i)] = true;}for (int i=0;i<=top;i++) printf("%c",alp(i));printf("n");}return 0;
}