2020-2021:teams:legal_string:contest4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:contest4 [2020/07/07 10:59] jxm2001 |
2020-2021:teams:legal_string:contest4 [2020/07/07 11:07] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 541: | 行 541: | ||
| cout<<ans[i]<<endl; | cout<<ans[i]<<endl; | ||
| return 0; | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== J. First! ===== | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | $\text{Trie}$ 建树，然后询问每个单词结点，如果他是某个单词结点的子结点，一定不合法。 | ||
| + | |||
| + | 沿路把 $\text{Trie}$ 的其他分支代表的字母向该路径代表字母连单向边，最后跑一下 $26$ 个字母的拓扑，看看合不合法。 | ||
| + | |||
| + | <hidden 赛后代码> | ||
| + | <code cpp> | ||
| + | #include <iostream> | ||
| + | #include <cstdio> | ||
| + | #include <cstdlib> | ||
| + | #include <algorithm> | ||
| + | #include <string> | ||
| + | #include <sstream> | ||
| + | #include <cstring> | ||
| + | #include <cctype> | ||
| + | #include <cmath> | ||
| + | #include <vector> | ||
| + | #include <set> | ||
| + | #include <map> | ||
| + | #include <stack> | ||
| + | #include <queue> | ||
| + | #include <ctime> | ||
| + | #include <cassert> | ||
| + | #define _for(i,a,b) for(int i=(a);i<(b);++i) | ||
| + | #define _rep(i,a,b) for(int i=(a);i<=(b);++i) | ||
| + | #define mem(a,b) memset(a,b,sizeof(a)) | ||
| + | using namespace std; | ||
| + | typedef long long LL; | ||
| + | inline int read_int(){ | ||
| + | int t=0;bool sign=false;char c=getchar(); | ||
| + | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| + | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| + | return sign?-t:t; | ||
| + | } | ||
| + | inline LL read_LL(){ | ||
| + | LL t=0;bool sign=false;char c=getchar(); | ||
| + | while(!isdigit(c)){sign|=c=='-';c=getchar();} | ||
| + | while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();} | ||
| + | return sign?-t:t; | ||
| + | } | ||
| + | inline char get_char(){ | ||
| + | char c=getchar(); | ||
| + | while(c==' '||c=='\n'||c=='\r')c=getchar(); | ||
| + | return c; | ||
| + | } | ||
| + | inline void write(LL x){ | ||
| + | register char c[21],len=0; | ||
| + | if(!x)return putchar('0'),void(); | ||
| + | if(x<0)x=-x,putchar('-'); | ||
| + | while(x)c[++len]=x%10,x/=10; | ||
| + | while(len)putchar(c[len--]+48); | ||
| + | } | ||
| + | inline void space(LL x){write(x),putchar(' ');} | ||
| + | inline void enter(LL x){write(x),putchar('\n');} | ||
| + | const int MAXS=3e5+5,MAXN=3e5+5; | ||
| + | int ch[MAXS][26],val[MAXS],cnt; | ||
| + | char temp[MAXN],*buf[MAXN]; | ||
| + | void Insert(char *s){ | ||
| + | int len=strlen(s),pos=0; | ||
| + | _for(i,0,len){ | ||
| + | int c=s[i]-'a'; | ||
| + | if(!ch[pos][c]) | ||
| + | ch[pos][c]=++cnt; | ||
| + | pos=ch[pos][c]; | ||
| + | } | ||
| + | val[pos]++; | ||
| + | } | ||
| + | int a[26][26],in[26],vis[26]; | ||
| + | bool topu(){ | ||
| + | mem(in,0); | ||
| + | _for(i,0,26) | ||
| + | _for(j,0,26){ | ||
| + | if(a[i][j]) | ||
| + | in[j]++; | ||
| + | } | ||
| + | queue<int> q; | ||
| + | _for(i,0,26){ | ||
| + | if(!in[i]) | ||
| + | q.push(i); | ||
| + | } | ||
| + | while(!q.empty()){ | ||
| + | int u=q.front();q.pop(); | ||
| + | _for(i,0,26){ | ||
| + | if(a[u][i]){ | ||
| + | in[i]--; | ||
| + | if(!in[i]) | ||
| + | q.push(i); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | _for(i,0,26) | ||
| + | if(in[i]) | ||
| + | return false; | ||
| + | return true; | ||
| + | } | ||
| + | bool query(char *s){ | ||
| + | mem(a,0); | ||
| + | int len=strlen(s),pos=0; | ||
| + | _for(i,0,len){ | ||
| + | if(val[pos]) | ||
| + | return false; | ||
| + | int c=s[i]-'a'; | ||
| + | _for(j,0,26){ | ||
| + | if(j==c||ch[pos][j]==0) | ||
| + | continue; | ||
| + | a[j][c]=1; | ||
| + | } | ||
| + | pos=ch[pos][c]; | ||
| + | } | ||
| + | return topu(); | ||
| + | } | ||
| + | bool ok[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(); | ||
| + | _for(i,0,n){ | ||
| + | gets(temp); | ||
| + | buf[i]=(char*)malloc(strlen(temp)+1); | ||
| + | strcpy(buf[i],temp); | ||
| + | } | ||
| + | _for(i,0,n) | ||
| + | Insert(buf[i]); | ||
| + | int tot=0; | ||
| + | _for(i,0,n) | ||
| + | ok[i]=query(buf[i]),tot+=ok[i]; | ||
| + | enter(tot); | ||
| + | _for(i,0,n) | ||
| + | if(ok[i]) | ||
| + | puts(buf[i]); | ||
| + | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/contest4.1594090749.txt.gz · 最后更改: 2020/07/07 10:59 由 jxm2001
