栈练习之——codevs 1051 接龙游戏

接龙游戏"/>

栈练习之——codevs 1051 接龙游戏

乍一眼看，Trie 树裸题，然后就顺手写了个Trie，然后……MLE 或 RE……codevs上能过8个左右的点，不过数组小玄学，空间用到了110M+，好可怕……
蒟蒻的Trie……

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#define to(c) c - 'a'
using namespace std;
const int MAXN = 24000;
const int Alpha = 26;
const int C = 50;
int map[MAXN * C + 10][Alpha];
int sz;
bool flag[MAXN * C + 10];
int root;
bool find(char *c,int l)
{int now = 0;for(int i = 0;i < l;i ++){if(!map[now][to(c[i])])return false;now = map[now][to(c[i])];}return flag[now];
}
void insert(char *c,int l)
{int now = root;for(int i = 0;i < l;i ++){if(!map[now][to(c[i])])map[now][to(c[i])] = ++sz;now = map[now][to(c[i])];}flag[now] = true;return;
}
int ans;
void dfs(int x,int tot)
{if(!x){ans = max(ans,tot);return;}tot += flag[x];for(int i = 0;i < 26;i ++)dfs(map[x][i],tot);tot -= flag[x];return;
}
char s[MAXN];
int n;
int main()
{scanf("%d",&n);for(int i = 1;i <= n;i ++){scanf("%s",s);insert(s,strlen(s));}for(int i = 0;i < 26;i ++)dfs(map[0][i],flag[0]);printf("%d\n",ans);return 0;
}

那么怎么办呢

有一种神奇的数据结构，叫做栈（天梯石栈相勾连之类的……）
我可以先sort一下，然后开点黑科技（利用下它完全前缀匹配的性质（是这么叫么2333））
然后……然后就解决啦！！！
栈顶为当前string的前缀时，push()，否则，pop(),pop(),pop()……直到能扔进去的时候停
恩恩
解决了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
using namespace std;
const int MAXN = 1e5 + 5;
stack <string> s;
string c[MAXN];
bool can(string a,string b)
{if(a == b)return false;if(a.length() > b.length())return false;return a == b.substr(0,a.length());
}
int cnt;
void make_can(string a)
{while(!s.empty() && !can(s.top(),a))s.pop(),cnt--;s.push(a);cnt++;return;
}
int ans;
int n;
int main()
{scanf("%d",&n);for(int i = 1;i <= n;i ++)cin >> c[i];sort(c + 1,c + n + 1);n = unique(c + 1,c + n + 1) - (c + 1);for(int i = 1;i <= n;i ++)if(s.empty() || can(s.top(),c[i]))s.push(c[i]),ans = max(ans,++cnt);elsemake_can(c[i]);printf("%d\n",ans);return 0;
}

转载于: