夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

某金牌训练营Day16

2021-03-01 14 min read

A

首先要看出问题是2-sat....李队秒了...

怎么优化建图啊

首先字符串总长和前缀可以知道建立trie

然后观察发现我们相当于一条链只能选择一个点

也就是说一个点要想所有祖先连边,然后同时向所有儿子连边

这个怎么做呢?考虑把整棵树定向,拆成内向树和外向树两棵树,然后对于这个点上的代表的所有串,把他们拿出来连向一个虚点,再从虚点向内向树的父亲而外向树的儿子连边即可

然后你连样例都过不去

观察发现一个点上的串之间也会有冲突情况,但是他们本质相同

因此我们把他们建立一些前缀点,连接向反点,然后建立一些后缀点,连接向反点一个点就很容易得知连接的是两个前后缀点了

对于一个没有?的字符串,我们钦定她只能选正,因此加入正之后让反点连向他即可

建图部分写对了就是对的

//点数8n
//边数13n
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

const int MAXN = 2e6 + 7;//1/2n,但是不参与tarjan
const int MAXM = 1e7 + 3e6 + 7;//2m,所有参与tarjan的

int n, T, rc;
char s[MAXN], a[MAXN], b[MAXN];
int ch[MAXN][3], avi[MAXN];
vector<int> ed[MAXN];

int ccnt, home[MAXM], nxt[MAXM], to[MAXM];

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

inline void ins(string s, int m, int c) {
	int u = 1;
	for(int i = 0; i < m; ++i) {
		int t = s[i] - '0';
		if(!ch[u][t])ch[u][t] = ++T;
		u = ch[u][t];
	}
	ed[u].pb(rc + c * n);
	return ;
}
/*
一条链只能选择一个点
拆成前后缀
点编号分配如下:
1~n号点为选择1
n+1~2n号点为选择2
2n+1~2n+T为所有出边点
2n+1+T~2n+2T为所有前缀点
2n+2T+1~2n+3T为所有后缀点
所有前缀点向之前的前缀点连前缀边
后缀点同理向所有儿子连边!!
所有前后缀点向反点连边
所有正点向出边点连边
所有正点向对应前缀点的父亲连边
所有正点向对应后缀点的儿子连边
5n...wc
2n+3T+1~3n+3T为所有一个点内的前缀点
4n+3T+1~5n+3T为所有一个点内的后缀点
分别向对应的反点连边
然后每个正点再向对应前缀前一个点后缀后一个点
8n个点
13n条边
冲
*/

inline int trs(int x) {
	return x > n ? (x - n) : x + n;
}

inline void dfs(int u, int bck) {
	if(!ed[u].empty()) {
		for(int i = 0; i < (int)ed[u].size(); ++i) {
			int v = ed[u][i];
			ct(v, 2 * n + u); //正常的点...
			ct(2 * n + 3 * T + v, trs(v));
			ct(4 * n + 3 * T + v, trs(v));
			if(i != 0) {
				ct(2 * n + 3 * T + v, 2 * n + 3 * T + ed[u][i - 1]);
				ct(v, 2 * n + 3 * T + ed[u][i - 1]);
			}
			if(i != (int)ed[u].size() - 1) {
				ct(4 * n + 3 * T + v, 4 * n + 3 * T + ed[u][i + 1]);
				ct(v, 4 * n + 3 * T + ed[u][i + 1]);
			}
			ct(2 * n + T + u, trs(v));
			ct(2 * n + 2 * T + u, trs(v));
		}
		if(bck) {
			ct(2 * n + u, 2 * n + bck + T);
			ct(2 * n + u + T, 2 * n + bck + T);
			ct(2 * n + bck, 2 * n + u + 2 * T);
			ct(bck + 2 * n + 2 * T, u + 2 * T + 2 * n); //父
		}
		if(ch[u][0])dfs(ch[u][0], u);
		if(ch[u][1])dfs(ch[u][1], u);
	} else {
		if(ch[u][0])dfs(ch[u][0], bck);
		if(ch[u][1])dfs(ch[u][1], bck);
	}
}

int dfn[MAXM], low[MAXM], st[MAXM], fl[MAXM], depp, bel[MAXM], tp;

inline void tarjan(int x) {
	dfn[x] = low[x] = ++depp;
	st[++tp] = x;
	fl[x] = 1;
	for(int i = home[x]; i; i = nxt[i]) {
		int v = to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[x] = min(low[x], low[v]);
		} else if(!fl[v])continue;
		low[x] = min(low[x], dfn[v]);
	}
	if(low[x] == dfn[x]) {
		while(st[tp] != x) {
			int v = st[tp]; --tp;
			bel[v] = x;
			fl[v] = 0;
		}
		fl[x] = 0;
		bel[x] = x;
		--tp;
	}
	return ;
}

int main() {
	freopen("code.in", "r", stdin);
	freopen("code.out", "w", stdout);
	scanf("%d", &n);
	T = 1;
	for(int i = 1; i <= n; ++i) {
		scanf("%s", s);
		int m = strlen(s);
		for(int j = 0; j < m; ++j) {
			if(s[j] == '?') {
				a[j] = '1', b[j] = '0';
				avi[i] = 1;
			} else a[j] = b[j] = s[j];
		}
		rc = i;
		if(avi[i])ins(a, m, 1);
		ins(b, m, 0);
		if(!avi[i])ct(i + n, i); //只能选正
	}
	dfs(1, 0);
	for(int i = 1; i <= 5 * n + 3 * T; ++i) {
		if(!dfn[i])tarjan(i);
	}
	bool flg = 1;
	for(int i = 1; i <= n; ++i) {
		if(bel[i] == bel[i + n]) {
			flg = 0;
			break;
		}
	}
	if(flg)puts("YES");
	else puts("NO");
	return 0;
}

B

首先我们想要tarjan是不行的,因为会遍历所有边而TLE

所以要kosaraju

这个做法是首先建立反图,然后得到反图的dfs序,然后再在正图上dfs,删除所有我们遍历到的点,这样的点形成了一个强联通分量

这个算法的原理是什么?

反图的dfs序是正图的拓扑序的反序

所以我们一定对于一个缩点后的DAG,先访问那些拓扑序最靠后的出度为0的点,再去访问那些出度不为0的点,那么我们每次访问到的所有没经过的点,就一定是一个强联通分量里面的

因此我们只需要知道邻接矩阵的信息,然后保证每次只访问那些没有经过的节点,复杂度就和m无关了!

怎么只访问那些没经过的?bitset优化即可

我们用莫队得到正图和反图的邻接矩阵,然后每次卡到一组询问的时候,直接kosaraju一遍回答即可,然后此时的复杂度就是O(qn2w+mq)O(q\frac{n^2}{w}+m\sqrt q)

移动总次数为O(mB∗m+qB)O(\frac{m}{B}*m+qB)

块长取mq\frac{m}{\sqrt q}最优

md我数组开小了挂了几发

#include<bits/stdc++.h>
using namespace std;
const int MAXM = 6e5 + 7;
const int MAXN = 155;

int n, m, q, bel[MAXM], B, tot, L[MAXM], R[MAXM], ans[MAXM];
struct rec {
	int x, y, id;
	bool operator<(const rec &w)const {
		return bel[x] == bel[w.x] ? y < w.y : x < w.x;
	}
} e[MAXM], a[MAXM];

inline void init() {
	B = (m / sqrt(q));
	tot = 1;
	L[tot] = 1;
	for(int i = 1; i <= m; ++i) {
		if(i % (B + 1) == 0) {
			R[tot] = i - 1;
			++tot;
			L[tot] = i;
		}
		bel[i] = tot;
	}
	R[tot] = m;
	return ;
}

bitset<MAXN> G[MAXN], G1[MAXN], __G[MAXN], __G1[MAXN]; //邻接矩阵
int _G[MAXN][MAXN], _G1[MAXN][MAXN];

inline void add(int i) {
	if(!_G[e[i].x][e[i].y])G[e[i].x].set(e[i].y);
	_G[e[i].x][e[i].y]++;
	if(!_G1[e[i].y][e[i].x])G1[e[i].y].set(e[i].x);
	_G1[e[i].y][e[i].x]++;
}

inline void del(int i) {
	if(_G[e[i].x][e[i].y] == 1)G[e[i].x][e[i].y] = 0;
	_G[e[i].x][e[i].y]--;
	if(_G1[e[i].y][e[i].x] == 1)G1[e[i].y][e[i].x] = 0;
	_G1[e[i].y][e[i].x]--;
}

int dfn[MAXM], tp;
bitset<MAXN> vis;
int cnt;

inline void dfs1(int x) {
	vis.reset(x);
	while(G1[x].any()) {
		G1[x] &= vis;
		if(G1[x]._Find_first() == MAXN)break;
		dfs1(G1[x]._Find_first());
	}
	dfn[++tp] = x;
	return ;
}

inline void dfs(int x) {
	vis.reset(x);
	cnt++;
	while(G[x].any()) {
		G[x] &= vis;
		if(G[x]._Find_first() == MAXN)break;
		dfs(G[x]._Find_first());
	}
	return ;
}

inline void kosaraju(int x) {
	for(int i = 1; i <= n; ++i) {
		__G[i] = G[i];
		__G1[i] = G1[i];
	}
	vis.set();
	tp = 0;
	for(int i = 1; i <= n; ++i)if(vis.test(i))dfs1(i);//得到反图dfs序
	vis.set();
	for(int i = tp; i >= 1; --i) {
		if(vis.test(dfn[i])) {
			cnt = 0;
			dfs(dfn[i]);
			ans[x] += cnt * (cnt - 1) / 2;
		}
	}
	for(int i = 0; i <= n; ++i) {
		G[i] = __G[i];
		G1[i] = __G1[i];
	}
	return ;
}

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= m; ++i)scanf("%d%d", &e[i].x, &e[i].y);
	for(int i = 1; i <= q; ++i)scanf("%d%d", &a[i].x, &a[i].y), a[i].id = i;
	init();
	sort(a + 1, a + q + 1);
	int L = 1, R = 0;
	for(int i = 1; i <= q; ++i) {
		while(R < a[i].y) {
			++R;
			add(R);
		}
		while(L > a[i].x) {
			--L;
			add(L);
		}
		while(R > a[i].y) {
			del(R);
			--R;
		}
		while(L < a[i].x) {
			del(L);
			++L;
		}
		kosaraju(a[i].id);
	}
	for(int i = 1; i <= q; ++i)printf("%d\n", ans[i]);
	return 0;
}

C

根据期望线性性,我们想求出两点(u,v)在选u时和v连通的概率,答案就是这些的和

树

第i个点和第j个点被第几次抽走都是O(1n)O(\frac{1}{n})

也就是说(u,v)路径上的点都要在u,v之后抽

概率就是1dis(u,v)+1\frac{1}{dis(u,v)+1}

先枚举一个距离,我们要求路径某种长度的有多少条,可以经典点分治

这个是把所有分治重心下的点的dep加入,然后加上总的,减去单独w子树的信息

先看第一部分,这个式子是什么?

cntk=∑u+v==kcntu∗cntvcnt_{k}=\sum_{u+v==k}cnt_{u}*cnt_{v}

卷积

再看第二部分,你会发现等价于每个东西自己卷积

第二部分显然不会比第一部分慢,总时间复杂度是O(nlog2n)O(nlog^2n)

就是树的做法啦

基环树

第一步找到这个环,然后分类讨论

对于两个需要经过环上的点的路径,他们有相同的起点终点

容斥!

第一条连通概率为1d1+1\frac{1}{d_1+1},第二条连通的1d2+1\frac{1}{d_2+1}

如果直接加起来,会把两个都连通的算重了,所以还要减去

1d1+1+1d2+1−1d3\frac{1}{d_1+1}+\frac{1}{d_2+1}-\frac{1}{d_3}

其中d3=depu+depv+lend_3=dep_u+dep_v+len

第三部分?两个深度的加和看成常数,我们可以直接用u,v来自不同子树的卷积部分来解决,注意NTT模长不要写太大了

否则断开一条边,对于任意两点u,v,如果经过断开边为d2d2,否则为d1d1

此时dis1(u,v)=depu+depv+idv−idudis1(u,v)=dep_u+dep_v+id_v-id_u

我们钦定v<uv<u

经过断边的长度还要考虑

dis2(u,v)=depu+depv−idu+idv+lendis2(u,v)=dep_u+dep_v-id_u+id_v+len

同样v<uv<u

你会发现dis1dis1和其余子树的答案加起来就是原来定义的整棵树的答案,可以断开这条边之后点分治一起算!

第二类因为权值不同我们要考虑分治

第一种权值是dep+iddep+id,第二种为dep−iddep-id

钦定u<vu<v,从siz最平均的位置分治(不是中间点)

使得au+bv=ka_u+b_v=k

其中a,b数组都可以根据两类权值构造,具体的aua_u应该是depu+idudep_u+id_u,另一个是depv−idv+lendep_v-id_v+len

这两个分治FFT卷起来即可

但是直接做多项式长度不对,可能会一车0项让整个多项式次数很多,也就是说只有最后的几项才不为0

因此我们构造的时候应该是dep+id−ldep+id-l和dep−id+len−rdep-id+len-r

这样就没有非0项了

Powered by Gridea RSS