2022春每日一题:Day 32
题目:[USACO12DEC]First! G
不太记得当时怎么想的了,但是显然,当一个字符串的前缀存在则他一定不是first,然后做法:对于每个字符串,把每个字符结尾跟他有相同前缀的单词的同元素建边,保证这个元素严格大于其他元素,然后判环,有环的话说明不能是first,反之则是。
代码:
#include
#include
#include
#include
#include
#include
#include
#include
const int N=3e4+5,M=3e5+5;
using namespace std;
int n,m,tot,num,ss[N],vis[N],rd[26];
string s,dic[N];
vector g[26];
namespace trietree
{
struct trie
{
int son[26],tag;
}e[M];
void insert(int len)
{
int p=0;
for(int i=0;i q;
while(!q.empty())
q.pop();
int cnt=0;
for(int i=0;i<26;i++)
if(!rd[i])
q.push(i);
while(!q.empty())
{
int now=q.front();
int len=g[now].size();
++cnt;
q.pop();
for(int i=0;i>n;
for(int i=1;i<=n;i++)
{
cin>>s;
ss[i]=s.length();
dic[i]=s;
insert(ss[i]);
}
for(int i=1;i<=n;i++)
clear(ss[i],i);
cout<