4.15 省选模拟赛 编码 trie树 前缀和优化建图 2-sat

好题 np.

对于20分 显然可以爆搜。

对于50分 可以发现每个字符串上的问号要么是0,要么是1.考虑枚举一个字符串当前是0还是1 这会和其他字符串产生矛盾。

所以容易 发现这是一个2-sat问题。

拆点 把任意两个产生矛盾的字符串进行连边。然后最后判矛盾即可。

n^2枚举 建图 判断矛盾时使用字符串hash 要分类讨论4种情况。

using namespace std;
const int MAXN=1010,maxn=500010,cc1=19260817,cc2=114514;
int n,mark,cnt,top,id,len;
string a[MAXN];
int flag[MAXN],c[MAXN<<1],low[MAXN<<1],dfn[MAXN<<1],s[MAXN<<1];
int lin[MAXN<<1],ver[MAXN*MAXN<<2],nex[MAXN*MAXN<<2],w[MAXN];
vector<int>h0[MAXN];//表示为0时的前缀hash值 或者表示什么都不是的前缀hash值.
vector<int>h1[MAXN];//表示为1时的前缀hash值
struct wy
{
	int len,id;
}t[MAXN];
inline int cmp(wy a,wy b){return a.len<b.len;}
inline void dfs(int x)
{
	low[x]=dfn[x]=++cnt;
	s[++top]=x;
	go(x)
	{
		if(!dfn[tn])
		{
			dfs(tn);
			low[x]=min(low[x],low[tn]);
		}
		else if(!c[tn])low[x]=min(low[x],dfn[tn]);
	}
	if(dfn[x]==low[x])
	{
		int y=0;++id;
		while(y!=x)
		{
			y=s[top--];
			c[y]=id;
		}
	}
}
inline void add(int x,int y)
{
	ver[++len]=y;
	nex[len]=lin[x];
	lin[x]=len;
}
int main()
{
	freopen("code.in","r",stdin);
	freopen("code.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n;
	if(n<=1000)
	{
		rep(1,n,i)
		{
			cin>>a[i];
			t[i]=(wy){a[i].size(),i};
		}
		rep(1,n,i)
		{
			ll w0=0,w1=0;
			rep(0,((int)a[i].size())-1,j)
			{
				w0=w0*P%mod;
				w1=w1*P%mod;
				if(a[i][j]==‘?‘)
				{
					flag[i]=j+1;
					w0=(w0+cc1)%mod;
					w1=(w1+cc2)%mod;
				}
				else
				{
					if(a[i][j]==‘0‘)w1=(w1+cc1)%mod,w0=(w0+cc1)%mod;
					else w1=(w1+cc2)%mod,w0=(w0+cc2)%mod;
				}
				h0[i].pb(w0);
				h1[i].pb(w1);
			}
		}
		//x表示这个点选择0 x+n表示这个点选择1.
		sort(t+1,t+1+n,cmp);
		rep(1,n,i)
		{
			int x=t[i].id;//x.len<=y.len
			int xx=t[i].len;
			rep(i+1,n,j)
			{
				int y=t[j].id;
				if(!flag[x]&&(!flag[y]||flag[y]>xx))
				{
					if(h0[x][xx-1]==h0[y][xx-1])
					{
						puts("NO");
						return 0;
					}
					continue;
				}
				if(!flag[x]&&flag[y]<=xx)
				{
					if(h0[x][xx-1]==h0[y][xx-1])add(y,y+n);
					if(h0[x][xx-1]==h1[y][xx-1])add(y+n,y);
					continue;
				}
				if(flag[x]&&(!flag[y]||flag[y]>xx))
				{
					if(h0[x][xx-1]==h0[y][xx-1])add(x,x+n);
					if(h1[x][xx-1]==h0[y][xx-1])add(x+n,x);
				}
				if(flag[x]&&flag[y]<=xx)
				{
					if(h0[x][xx-1]==h0[y][xx-1])add(x,y+n),add(y,x+n);
					if(h0[x][xx-1]==h1[y][xx-1])add(x,y),add(y+n,x+n);
					if(h1[x][xx-1]==h0[y][xx-1])add(x+n,y+n),add(y,x);
					if(h1[x][xx-1]==h1[y][xx-1])add(x+n,y),add(y+n,x);
				}
			}
		}
		rep(1,n+n,i)if(!dfn[i])dfs(i);
		rep(1,n,i)if(c[i]==c[i+n]){puts("NO");return 0;}
		puts("YES");
	}
	return 0;
}

考虑100分。

我考试的时候想了一波trie树 但是当时思考没有在这个暴力的基础上思考 所以 建图也很麻烦 所以弃疗了。

可以发现我们拆过点后 把这些串给放到trie树上。

可以发现连边的时候 使用前缀和连边 即可优化建图了。

对于某个节点存放多个节点 这个时候 对这个节点内部再进行一次前缀和优化建图。

对于某个节点不存在? 考虑子树内和链上上的节点都需要自己向自己的对立连边 这个使用懒标记即可。

上传标记和 标记的时候注意判断不合法的情况。

这个优化建图还是很精髓的。充分的利用了trie树的性质。

注意空间不要开小了 计算不了点数可以开到空间上界小一点。

const int MAXN=500010*3;
int n,sum,cnt=1,top,id,len,last=1,mark;
string a[MAXN];
int t[MAXN][2],ne[MAXN],pos[MAXN];
int flag[MAXN],c[MAXN<<3],low[MAXN<<3],dfn[MAXN<<3],s[MAXN<<3],w1[MAXN],w2[MAXN];
int lin[MAXN<<3],ver[MAXN<<3],nex[MAXN<<3],add1[MAXN],add2[MAXN];
vector<int>g[MAXN];
inline void dfs(int x)
{
	low[x]=dfn[x]=++cnt;
	s[++top]=x;
	go(x)
	{
		if(!dfn[tn])
		{
			dfs(tn);
			low[x]=min(low[x],low[tn]);
		}
		else if(!c[tn])low[x]=min(low[x],dfn[tn]);
	}
	if(dfn[x]==low[x])
	{
		int y=0;++id;
		while(y!=x)
		{
			y=s[top--];
			c[y]=id;
		}
	}
}
inline void add(int x,int y)
{
	ver[++len]=y;
	nex[len]=lin[x];
	lin[x]=len;
}
inline void insert(int x,int op)
{
	int p=1,c=min(x,ne[x]);
	for(ui i=0;i<a[c].size();++i)
	{
		int w=a[c][i]-‘0‘;
		if(!t[p][w])t[p][w]=++cnt;
		p=t[p][w];
	}
	if(op)g[p].pb(x);
	else
	{
		if(add1[p])mark=1;
		add1[p]=1,add2[p]=1;
	}
	pos[x]=p;
}
inline void dfs(int x,int fa)
{
	int s1=++sum,s2=++sum;
	if(w1[fa])add(s1,w1[fa]);//w1[x]表示当前点向前缀所有的点的相反点的连边
	if(w2[fa])add(w2[fa],s2);//w2[x]表示前缀所有的点向当前点的连边.
	int c1=++sum,c2=++sum,cc1,cc2;//c1表示当前这个点对前缀和的相反点的连边.
	//c2表示前缀和的所有点对当前点的连边.
	for(ui i=0;i<g[x].size();++i)
	{
		int tn=g[x][i];
		//cout<<tn<<endl;
		add(tn,c1);
		cc1=++sum;
		add(cc1,c1);
		add(cc1,ne[tn]);
		c1=cc1;
		add(c2,ne[tn]);
		cc2=++sum;
		add(c2,cc2);
		add(tn,cc2);
		c2=cc2;
		if(w1[fa])add(tn,w1[fa]);
		if(w2[fa])add(w2[fa],ne[tn]);
		add(s1,ne[tn]);
		add(tn,s2);
	}
	//puts("ww");
	w1[x]=s1;w2[x]=s2;
	if(t[x][0])add1[t[x][0]]|=add1[x],dfs(t[x][0],x);//传递子树标记
	if(t[x][1])add1[t[x][1]]|=add1[x],dfs(t[x][1],x);
	if(add2[x]&&add2[t[x][0]])mark=1;
	if(add2[x]&&add2[t[x][1]])mark=1;
	add2[x]|=add2[t[x][0]];//传递链上标记.
	add2[x]|=add2[t[x][1]];
}
int main()
{
	freopen("code.in","r",stdin);
	freopen("code.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n;//cout<<1<<endl;
	rep(1,n,i)cin>>a[i];
	rep(1,n,i)
	{
		ne[i]=i+n;ne[i+n]=i;
		for(ui j=0;j<a[i].size();++j)if(a[i][j]==‘?‘){flag[i]=j+1;break;}
		if(flag[i])
		{
			a[i][flag[i]-1]=‘0‘;
			insert(i,1);
			a[i][flag[i]-1]=‘1‘;
			insert(i+n,1);
		}
		else insert(i,0);
	}
	sum=2*n;dfs(1,0);
	if(mark){puts("NO");return 0;}
	rep(1,2*n,i)if(add1[pos[i]]||add2[pos[i]])if(pos[i])add(i,ne[i]);
	rep(1,2*n,i)if(!dfn[i])dfs(i);
	rep(1,n,i)if(c[i]==c[i+n]){puts("NO");return 0;}
	puts("YES");
	return 0;
}

原文地址:https://www.cnblogs.com/chdy/p/12706592.html

时间: 04-15

4.15 省选模拟赛 编码 trie树 前缀和优化建图 2-sat的相关文章

4.4 省选模拟赛 拉格朗日计数 树状数组+容斥.

像这种计数 问题什么的 是最讨厌的了... 考虑是环往环后面再续一段 暴力枚举前两个数字 树状数组统计第三个数的个数 n^2log. 考虑只枚举第个数 发现由于边界问题什么的很难处理. 再将枚举直接放到环上 发现边界问题没有了 不过存在 枚举第二个数之后 有 123 231 312 这三种形式. 第一种形式很好统计 预处理一下左边有多少个数字比自己小即可. 考虑第二种和第三种形式 很难在枚举2的时候统计出来这两种形式 考虑容斥 231=XX1-321. 312=3XX-321. 发现XX1和3X

4.9 省选模拟赛 圆圈游戏 树形dp set优化建图

由于圆不存在相交的关系 所以包容关系形成了树的形态 其实是一个森林 不过加一个0点 就变成了树. 考虑对于每个圆都求出最近的包容它的点 即他的父亲.然后树形dp即可.暴力建图n^2. const int MAXN=100010; int n,m,len; struct wy { ll x,y,r,w; inline int friend operator <(wy a,wy b){return a.r<b.r;} }t[MAXN]; int f[MAXN]; int lin[MAXN],ver

4.3 省选模拟赛 石子游戏 树上博弈

注意观察题目 每个点都只能将石子给自己的两个儿子 且石子个数>=1. 显然 这是一个阶梯NIM. 只有和最后一层的奇偶性相同的层才会有贡献 证明也很显然. 那么这其实就是近乎NIM游戏了 胜负自然取决于所有有贡献的石子堆的异或和. 但是 上午我傻了的一点 没有分清SG函数和NIM游戏的联系. 在NIM游戏中SG函数其实就是每个有贡献的石子堆的石子数. 再来看这道题 由于异或和一定 暴力枚举移动哪一堆石子 判断是否可行即可. 这个操作其实是 NIM游戏的证明问题了.解决的方案是 观察一下移动后造成

@省选模拟赛03/16 - T3@ 超级树

目录 @description@ @solution@ @accepted code@ @details@ @description@ 一棵 k-超级树(k-SuperTree) 可按如下方法得到:取一棵深度为 k 的满二叉树,对每个节点向它的所有祖先连边(如果这条边不存在的话). 例如,下面是一个 4-超级树: 请统计一棵 k-超级树 中有多少条不同的简单有向路径,对 mod 取模. input 一行两整数 k, mod. output 一行一整数表示答案. example input1: 2

【数据结构】字典树/Trie树/前缀树 - 字符串的统计、排序和保存

字典树 描述 字典树,又称单词查找树.Trie树.前缀树,是一种树形结构,是一种哈希树的变种. 典型应用是用于统计.排序和保存大量的字符串(但不仅限于字符串). 常见操作有插入和查找,删除操作少见. 性质 根节点不包含字符 除根节点外每一个节点都只包含一个字符 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串 每个节点的所有子节点包含的字符都不相同 优点 利用字符串的公共前缀来减少查询时间 最大限度地减少无谓的字符串比较 查询效率比哈希树高 自带字典序排序 直接判断重复,或者记

2018.3.10 省选模拟赛

从这里开始 概况 Problem A 三元组 Problem B 攻略 Problem C 迂回 概况 这是省选T1合集?还是欢乐AK赛? 全班一半以上的人三道题都会做qwq. Doggu还剩一小时时以为自己AK了,然后玩了一小时.虽然最终被卡了20分的常数. ZJC 1个半小时AK?Excuse me? 我这条大咸鱼到最后10分钟才敲完了T1,然后发现线段树要T掉. 发自内心鄙视垃圾出题人卡常数,本来的欢乐AK变成280. 教练给我们考4个小时的试,题面上也这么写的,看题解,woc,考试时间3

2018.2.12 省选模拟赛

题目大意 (题目很简洁了,不需要大意) 其实显而易见地可以发现,当被卡一次后后面的路程都是固定了的. 可以用类似动态规划的思想来进行预处理.现在的问题就是怎么知道在某个位置刚等完红灯然后出发会在哪个路口再次被卡. 尝试画一画图: 其中横轴表示位置,纵轴表示时间,长方体表示红灯时段.有用的部分长度只有$r + g$,所以在模意义下弄一下就可以减少很多重复和无用状态: 但是这样仍然不好处理上面提到的问题,考虑让线段横着走,第一个撞着的长方形就是答案.为了实现这个目标,就每个长方形向下移动一段(移动的

xjoi省选模拟赛_14

T1 发现 对于当前 投出 奇数次向上的概率为 p 那么 若加入一个 pi=0.5 的骰子 发现  p奇 +1=p奇 * 0.5+p偶 * 0.5 = p偶+1  也就是说 只要方案中存在一个 p=0.5 的骰子 这个方案必然合法  : 1 #include <bits/stdc++.h> 2 #define N 100 3 #define eps 1e-7 4 using namespace std; 5 typedef long double ldb; 6 int t,n; 7 ldb A

2016年11月15日noip模拟赛

苟.. 1.谜题 1 /* 2 考虑这题,该怎么xjb搞 3 嗯我说出了题解xjb搞.. 4 由题意 易得 N个 二位数字(一位数加个0) 如果是连续的,那么就成立. 5 反过来做. 6 7 方法2:n<4有解,其他无解 8 */ 9 #include <iostream> 10 #include <cmath> 11 #include <stdio.h> 12 #include <string> 13 #include <string.h>