首页 > 其他分享 >csp模拟<反思>3

csp模拟<反思>3

时间:2023-08-15 20:33:25浏览次数:40  
标签:ch int tr tot len Yes csp 模拟

csp模拟21

ARC141F

首先上结论:如果一个串能用其他串消完那么这个串可以删去;

剩下的串中有 \(S_i\) 是 \(S_j\) 的子串,那么答案是 Yes;

如果存在 \(S_i=A+B\) 和 \(S_j=B+C\),且 \(A \neq C\) 则答案是 Yes.

第一部分:如何判断一个串 \(S_i\) 是否能被消完。

建 AC 自动机,预处理 \(mark\) 表示其点 fail 树祖先上的某一个终止节点。开一个栈,栈里存在树上的编号,每压入一个点,从这个点跳 \(mark\) 匹配到终止节点,在栈中删去串的长度。匹配到最后如果栈中没元素,则此串可以删去,如果有元素且小于原始长度,则答案 Yes。

第二部分,对筛选出来的串在 AC自动机里跑一边,记录每个点被经历的次数和被谁经历。如果经历次数大于 1,则答案为 Yes。

设 \(f_{i,t}(t\le len_i)\)表示 \(S_i\) 长为 \(t\) 的后缀,可以匹配到的某一个 \(S_j\) 的前缀。可以对每个串跳 \(fail\) 求出。

接着对于每个 \(j=f_{i,t}\),只要存在 \(len_i \neq len_j\) 或 \(f_{j,len_{i-t}}==i\) 那么这就是坏串,则答案为 \(Yes\)。

不为 Yes 则为 No。

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2*1e6+10;
string s[N];
int tr[N][4],tot=0,fail[N],en[N],len[N],rk[N],d[N],idx[N],pk[N];
map<int,int>f[N];
int b[N];
bool vis[N];
int st[N],top;
int head[N],nex[N],ver[N],tot_node=0,mark[N][2];
queue<int> q;
void add(int x,int y){
	ver[++tot_node]=y;nex[tot_node]=head[x],head[x]=tot_node;
}
void insert(string s1,int id){
	int u=0;
	for(int i=0;s1[i];i++){
		int ch=s1[i]-'A';
		if(!tr[u][ch]) tr[u][ch]=++tot;
		d[tr[u][ch]]=d[u]+1;
		u=tr[u][ch];
	}
	en[u]++;
	rk[id]=u;
}
void build(){
	for(int i=0;i<4;i++){
		if(tr[0][i]){
			add(0,tr[0][i]);
			q.push(tr[0][i]); 
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			if(tr[u][i]){
				fail[tr[u][i]]=tr[fail[u]][i];
				add(fail[tr[u][i]],tr[u][i]);
				q.push(tr[u][i]); 
			}
			else{
				tr[u][i]=tr[fail[u]][i];
			}
		}
	}
}
void dfs(int x,int f){
	mark[x][0]=mark[f][0];
	if(en[x]){
		mark[x][0]=x;
		mark[x][1]=mark[f][0];	
	}
	for(int i=head[x];i;i=nex[i]){
		int y=ver[i];
		if(y==f) continue;
		dfs(y,x);
	}
}

void ask(string s1,int id){
	int u=0;
	for(int i=0;s1[i];i++){
		int ch=s1[i]-'A';
		u=tr[u][ch];
		pk[u]=id;
		idx[u]++;
	}
} 
void clear(int x){
	tot=0,tot_node=0;
	memset(tr,0,sizeof(tr));
	memset(fail,0,sizeof(fail));
	memset(mark,0,sizeof(mark));
	memset(en,0,sizeof(en));
	memset(len,0,sizeof(len));
	memset(rk,0,sizeof(rk));
	memset(d,0,sizeof(d));
	memset(idx,0,sizeof(idx));
	memset(pk,0,sizeof(pk));
	memset(head,0,sizeof(head));
	memset(nex,0,sizeof(nex));
	memset(ver,0,sizeof(ver));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=x;i++){
		f[i].clear();
	}
}

int main(){
	int T=1;
	while(T--){
		int n;
		scanf("%d",&n);
		clear(n);
		for(int i=1;i<=n;i++){
			cin>>s[i];
			len[i]=s[i].size();
			insert(s[i],i);
		}
		build();
		dfs(0,0);
		int getans=0;
		for(int k=1;k<=n;k++){
			int u=0;
			top=0;
			for(int i=0;i<len[k];i++){
				u=tr[st[top]][s[k][i]-'A'];
				st[++top]=u;
				if(rk[k]!=u && mark[u][0]) top-=d[mark[u][0]];
				if(rk[k]==u && mark[u][1]) top-=d[mark[u][1]];
			}
			if(top==0) vis[k]=1;
			if(top && top<len[k]){
				printf("Yes\n");
				getans=1;
				break;
			}
		}
		if(getans) continue;
		for(int i=1;i<=n;i++){
			if(vis[i]) continue;
			ask(s[i],i);
		}
		for(int i=1;i<=n;i++){
			if(vis[i]) continue;
			int tmp=rk[i];
			int last=0;
			while(fail[tmp]){
				tmp=fail[tmp];
				if(last==d[tmp]){
					printf("Yes\n");
					getans=1;
					break;
				}
				f[i][d[tmp]]=pk[tmp];
				last=d[tmp];
			}
			if(getans) break;
		}
		if(getans) continue;
		for(int i=1;i<=n;i++){
			if(vis[i]) continue;
			int tmp=rk[i];
			while(fail[tmp]){
				tmp=fail[tmp];
				int t=d[tmp];
				int j=f[i][t];
				if(!j) continue;
				if(len[i]!=len[j] ||f[j][len[i]-t]!=i){
					printf("Yes\n");
					getans=1;
					break;
				}
			}
			if(getans) break;
		}
		if(getans) continue;
		printf("No\n");
	}
}

标签:ch,int,tr,tot,len,Yes,csp,模拟
From: https://www.cnblogs.com/jinjiaqioi/p/17632365.html

相关文章

  • 1003 Reasoning(大模拟)
    translation现有一个推理系统,有如下符号组成:圆括号:\((\)和\()\)逻辑连词:\(\lnot\)和\(\to\)全称量词:\(\forall\)变量:\(u-z\)常量:\(a-e\)函数:\(f-h\)谓词:\(P-T\)这个推理系统还包括项(term)、公式(formula)、自由出现(freeoccurrence)和替换(replacement)等概念。基于这些......
  • HDU 5499(模拟)
    SDOITimeLimit:2000/1000MS(Java/Others)    MemoryLimit:131072/131072K(Java/Others)TotalSubmission(s):500    AcceptedSubmission(s):210ProblemDescriptionn(n≤100) peoplecomestotheSelectandthereis m(m≤50) people......
  • cf 583 B. Robot's Task(模拟)
    链接:http://codeforces.com/problemset/problem/583/B//求改变的方向次数//直接模拟题目是从1开始所以从左到右从右到左#include<stdio.h>#include<algorithm>usingnamespacestd;inta[1000+10];intvis[1000+10];intmain(){intn,t=0;scanf("%d",&n);......
  • Mysql中使用存储过程插入decimal和时间数据递增的模拟数据
    场景Mysql插入数据从指定选项中随机选择、插入时间从指定范围随机生成、Navicat使用存储过程模拟插入测试数据:https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/129179745在上面的基础上,如何使用存储过程构造坐标数据规律递增以及时间递增的模拟数据。表结构如下......
  • 2023北京/上海/广州/深圳CSPM-3国标项目管理中级认证报名
    CSPM-3中级项目管理专业人员评价,是中国标准化协会(全国项目管理标准化技术委员会秘书处),面向社会开展项目管理专业人员能力的等级证书。旨在构建多层次从业人员培养培训体系,建立健全人才职业能力评价和激励机制的要求,培养我国项目管理领域复合型人才。 【证书含金量】 ·竞聘优先·......
  • 8.14 模拟赛小结
    前言最喜欢的一集T1儒略历题意化简:给你一个长度为\(n\)的序列需要挑选\(4\)个数下标为\(A,B,C,D\),满足\(A<B<C<D\)\(A\timesB\timesC=D\)\(n\leq10^4\)这个很简单枚举\(C\)预处理\(A*B\)再枚举\(D\)时间复杂度\(O(n^2)\)能过Code#include<bits/stdc......
  • 2023-08-14 CSP-J模拟联考 游记
    8:00 赶到 FZ,9:00正式开考。开考前先洗了一把脸。9:00~9:15开T1,原本没有思路,但后来想到可以贪心,每次找到<n 的最大的斐波那契数。于是打了个斐波那契的表,就过了。9:15~10:00T2写了45分钟我是什么东西。一开始想法是把每一个字符的数量统计起来,如果相差<1就满足要求,否......
  • CSP模拟 21
    GetOnYourWay.木偶戏你看台上台下角色跟着反转大红的衣衫配上滑稽妆扮一唱一和多少人在围观乌鸦跟着鼓掌笑风水轮流转两语三言拉扯我的五感衣带要系紧不得有碍观瞻木偶提线怪事又成一桩美谈A.[CEOI2016]kangaroo神奇的DP,从未涉及的领域。观察题意,一......
  • PCIe卡设计方案:631-单路12Gsps 3G 带宽模拟信号源PCIe卡
     一、板卡概述    单路3G带宽模拟信号源卡由DA子卡和PCIe底板组成,二者通过标准FMC连接器互联,可以实现将PCIe总线数据转换为一路高速的模拟量输出。北京太速科技该板可广泛用于雷达、通信、光电领域的噪声信号、毛刺、脉冲信号模拟产生等领域。 二、性能指标 板卡功能......
  • 2023年CSPM-3国标项目管理中级认证报名推荐这家
    CSPM-3中级项目管理专业人员评价,是中国标准化协会(全国项目管理标准化技术委员会秘书处),面向社会开展项目管理专业人员能力的等级证书。旨在构建多层次从业人员培养培训体系,建立健全人才职业能力评价和激励机制的要求,培养我国项目管理领域复合型人才。  【证书含金量】 ·竞聘优先......