#C231107B. 残片(garbage)

Trie树 判环 图论转化 拓扑排序
题目
发布日期:   2023-11-07
更新日期:   2024-09-23
文章字数:   1.9k
阅读时长:   10 分

#C231107B. 残片(garbage)

标签（Label）

  • Trie树
  • 判环
  • 图论转化
  • 拓扑排序

前言（Front talk)

$\qquad$这道题也是绝笔，我打了半天，结果发现自己的实现非常的复杂，反正今天的题总是因为想出来但是实现的太慢导致没有做对。(→_→)

$\qquad$做题前先想好思路，然后想好用什么打，写好提纲！！！

$\qquad$结果下来 $20min$ 就打出了正解，哎，对题目的理解还是不够清晰。

同时，看到和字符串有关的问题，就只有三种处理方式：

  • $KMP$ 字符串匹配
  • $Trie$ 树
  • $AC$ 自动机

哈希和 $Z$ 函数（ $KMP$ 扩展 ）用的还是比较的少，而且哈希不会太直接的考（要考思维）。

网址（Website）

题目详情 - 残片(garbage) - Super

题解 - 残片(garbage) - Super

题解（Solution）

$\qquad$这道题很明显就是建个 $Trie$ 树处理，对于每一个字符串，如果要选择其为最小的，那么就一定使该层其他的字符都要大于当前字符，于是乎，我们可以很容易地得到很多类似 $a<b$ 的等量关系，类比图论转化思想，如果最后得到的关系式不成立，当且仅当在建立一条 $a\to b$ 的边之后，该图出现环，则在最后用 $tarjan$ 或 拓扑排序 或 $SPFA$ 判环即可。

$\qquad$建立单向边可以不按上述要求建，因为方向的反并不会影响判环。

$\qquad$注意： 如果当前字符串包括了其他的字符串，那么这个字符串一定不是最小的，要特判。（见代码第 $39$ 行）

$\qquad tarjan$ 太长了 ，关于$SPFA$ ，它死了，还是拓扑好用（按个人喜好，不喜勿喷）。

备注：

  1. 此题还可以用 传递闭包 来做，详见 cx 大佬的代码。

    cx大佬 的博客网址： Huasushis ‘s Blog

  2. 附有此题的 $tarjan$ 做法 ，感谢 dzr 大佬的贡献。

    dzr 大佬的博客网址： DZhearMins

代码（Code）

我的代码

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
inline int input(){int x;return cin>>x,x;}
const int N = 30123;
const int L = 301234; 

string a[N];
int n;

//Trie树 
int t[L][26],idx;
int v[L];
void insert(string s,int id){
	int p=0,c,ln=s.length();
	For(i,0,ln-1){
		c=s[i]-'a';
		if(!t[p][c]) t[p][c]=++idx;
		p=t[p][c];
	}v[p]++;
}

vector<int> ft[26];
queue<int> q;
int inn[N],cnt;
inline bool check(string s){
	//初始化 
	For(i,0,25) ft[i].clear(),inn[i]=0;
	while(q.size()) q.pop();cnt=0;
	//建边 
	int p=0,c,ln=s.length();
	For(i,0,ln-1){
		c=s[i]-'a';
		For(j,0,25) if(j!=c && t[p][j])
			ft[c].emplace_back(j),inn[j]++;
		if(v[p]) return false;//注意这个点一开始没有加 
		p=t[p][c];
	}	
	//拓扑排序判断环，有环则无解 
	For(i,0,25) if(inn[i]==0) q.push(i);
	while(q.size()){
		int x=q.front();q.pop();cnt++; 
		for(auto y:ft[x]){
			if(--inn[y]==0) q.push(y);
		}
	}return cnt==26;
}

vector<int> Ans;
signed main(){
	ios::sync_with_stdio(false);
	string str("garbage");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>n;For(i,1,n){
		cin>>a[i];insert(a[i],i);
	}For(i,1,n){
		if(check(a[i])){
			Ans.emplace_back(i);
		}
	}cout<<Ans.size()<<'\n';
	for(auto k:Ans) cout<<a[k]<<'\n';
	return 0;
}

cx的代码

$\qquad$cx大佬 的博客网址： Huasushis ‘s Blog

#include <bits/stdc++.h>
#define N 30010
#define M 300010
using namespace std;
char sbase[M << 1], *s[N];
int n;
int len[N];
void rd(int x) {
  static int ptr = 0;
  s[x] = sbase + ptr;
  scanf("%s", s[x]);
  len[x] = strlen(s[x]);
  ptr += len[x] + 1;
}
int ch[M][26];
bool ans[N];
int bo[M];
int tot;
void add(char *s, int len, int id) {
  static int cnt = 1;
  int u = 1;
  for (int i = 0; i < len; ++i) {
    if (!ch[u][s[i] - 'a']) {
      ch[u][s[i] - 'a'] = ++cnt;
    }
    u = ch[u][s[i] - 'a'];
  }
  bo[u] = id;
}
void dfs(int u, vector<int> xz) {
  if (bo[u]) {
    ans[bo[u]] = 1;
    ++tot;
    return;
  }
  int js = 0, zong = 0;
  for (int i = 0; i < 26; ++i) {
    if (ch[u][i]) js |= xz[i], zong |= (1 << i);
  }
  for (int i = 0; i < 26; ++i) {
    if (ch[u][i] && !((js >> i) & 1)) {
      auto son = xz;
      son[i] |= zong ^ (1 << i);
      auto tmp = zong ^ (1 << i);
      while (tmp) {
        int v = tmp & -tmp;
        son[i] |= son[__builtin_ctz(v)];
        tmp ^= tmp & -tmp;
      }
      for (int j = 0; j < 26; ++j) 
        ((son[j] >> i) & 1) && (son[j] |= son[i]);
      dfs(ch[u][i], son);
    }
  }
}
int main() {
  freopen("garbage.in", "r", stdin);
  freopen("garbage.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    rd(i);
    add(s[i], len[i], i);
  }
  dfs(1, vector<int>(26));
  printf("%d\n", tot);
  for (int i = 1; i <= n; ++i) {
    if (ans[i]) {
      printf("%s\n", s[i]);
    }
  }
  return 0;
}

dzr的代码

$\qquad$dzr 大佬的博客网址： DZhearMins

#include<bits/stdc++.h>
using namespace std;
#define fi(l,r) for(int i=l;i<=r;++i)
#define ff(x,l,r) for(int x=l;x<=r;++x)
#define ll long long
#define lp ll
#define lson(x) ((x)<<1)
#define rson(x) (lson(x)|1)
#define Lson(x) tr[lson(x)]
#define Rson(x) tr[rson(x)]
#define mod %P
#define nC 28
#define N 30005
#define nS 150005
#define S 400005
int n;
char s_c[S],*si[N],*it;
int son[S][nC],cnt,acnt;
int able[N];
int tot,fir[nC],nxt[nS],to[nS],val[S],ed[N];
void add(int x,int y){
	nxt[++tot]=fir[x];
	fir[x]=tot;
	to[tot]=y;
};
bool insert(char*s,int ii){
	int x=0;
	for(char *ch=s;*(ch);++ch){
		int c=(*ch)-'a';
		if(son[x][c]==0)son[x][c]=++cnt;
		x=son[x][c];
	}
	++val[x];
	ed[ii]=x;
	return true;
}
int dfn[nC],dfc,low[nC],stk[nC],stl;
bool ins[nC];
bool tarjan(int x){
	dfn[x]=low[x]=++dfc;
	ins[x]=1;
	stk[++stl]=x;
	for(int e=fir[x];e;e=nxt[e]){
		int u=to[e];
		if(dfn[u]==0){
			tarjan(u);
			low[x]=min(low[x],low[u]);
		}else if(ins[u])low[x]=min(low[x],dfn[u]);
	}
	if(dfn[x]==low[x]){
		if(stk[stl]!=x)return false;
		ins[x]=0;--stl;
	}
	return true;
}
bool query(char*s,int ii){
//	printf("Qring %s\n",s);
	int x=0;
	fi(1,tot)nxt[i]=0;
	tot=0;dfc=0;stl=0;
	memset(ins,0,sizeof ins);
	memset(fir,0,sizeof fir);
	memset(dfn,0,sizeof dfn);
	memset(low,0,sizeof low);
	for(char*ch=s;*(ch);++ch){
		int c=(*ch)-'a';
		fi(0,26){
			if(i!=c&&son[x][i]!=0){
				add(i,c);
			}
		}
//		printf("\tx=%d ed=%d val=%d\n",x,ed[ii],val[x]);
		if(val[x]>=1)return false;
		x=son[x][c];
	}
	if(val[x]>1)return false;
	fi(0,26){
		if(dfn[i]==0){
			if(tarjan(i)==false)return false;
		}
	}
	return true;
}
int main(){
	freopen("garbage.in","r",stdin);
	freopen("garbage.out","w",stdout);
	scanf("%d",&n);
	char ch=getchar();
	it=si[0]=s_c;
	fi(1,n){
		++it;
		si[i]=++it;//下标从 0 开始！
		while(ch<'a'||ch>'z')ch=getchar();
		while(ch>='a'&&ch<='z'){
			*it=ch;
			++it;
			ch=getchar();
		}
	}
	fi(1,n)if(insert(si[i],i)==false){able[i]=-1;};
	fi(1,n)if(able[i]!=-1&&query(si[i],i)){
		able[i]=1;++acnt;
	}
	printf("%d\n",acnt);
	fi(1,n)if(able[i]==1)printf("%s\n",si[i]);
}
文章作者: WolfDeer
文章链接: https://wolfdeer62456.github.iohttps://wolfdeer62456.github.io/2023/11/07/C231107B-%E6%AE%8B%E7%89%87-garbage/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 WolfDeer !
Trie树 判环 图论转化 拓扑排序
赏
  目录