【BZOJ 3881】[COCI2015] Divljak

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3881
神犇题解:http://trinkle.is-programmer.com/2015/6/30/bzoj-3881.100056.html

解题报告

考虑把Alice的串建成AC自动机
那么每一次用Bob的串去匹配就是Fail树上一些树链的并
这个用BIT+虚树无脑维护一下就可以了

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 2000009;
const int LOG = 26;
const int SGZ = 26;

int in[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

class Ac_Automaton{
int root, cnt, ch[N][SGZ], fail[N], pos[N], dep[N];
int head[N], to[N], nxt[N], ot[N], fa[N][LOG];
class FenwickTree{
int mx, sum[N];
public:
	inline void init(int nn) {
		mx = nn;
	}
	inline void modify(int p, int d) {
		for (int i = p; i <= mx; i += lowbit(i)) {
			sum[i] += d;
		}
	}
	inline int query(int l, int r) {
		int ret = 0;
		for (int i = l - 1; i > 0; i -= lowbit(i)) {
			ret -= sum[i];
		}
		for (int i = r; i; i -= lowbit(i)) {
			ret += sum[i];
		}
		return ret;
	}
private:
}bit;
public:
	inline void insert(char *s, int nn, int id) {
		int w = root;
		for (int i = 1; i <= nn; i++) {
			int cc = s[i] - 'a';
			if (!ch[w][cc]) {
				ch[w][cc] = ++cnt;
			}
			w = ch[w][cc];
		} 
		pos[id] = w;
	}
	inline void build() {
		static queue<int> que;
		for (int i = 0; i < SGZ; i++) {
			if (ch[root][i]) {
				que.push(ch[root][i]);
			}
		}
		for (; !que.empty(); que.pop()) {
			int w = que.front();
			AddEdge(fail[w], w);
			for (int i = 0; i < SGZ; i++) {
				if (!ch[w][i]) {
					ch[w][i] = ch[fail[w]][i];
				} else {
					que.push(ch[w][i]);
					fail[ch[w][i]] = ch[fail[w]][i];
				}
			}
		}
		DFS(0, 0);
		for (int j = 1; j < LOG; j++) {
			for (int i = 0; i <= cnt; i++) {
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
			}
		}
		bit.init(cnt + 1);
	} 
	inline void match(char *s, int nn) {
		static vector<int> vt[N];
		static int que[N], stk[N], vis[N]; 
		int qtot = 0, stot = 0, vtot = 0;
		que[++qtot] = root;
		for (int i = 1, w = root; i <= nn; i++) {
			w = ch[w][s[i] - 'a'];
			que[++qtot] = w;
		}
		sort(que + 1, que + 1 + qtot);
		qtot = unique(que + 1, que + 1 + qtot) - que - 1;
		sort(que + 1, que + 1 + qtot, cmp);
		for (int i = 1; i <= qtot; i++) {
			if (stot) {
				int lca = LCA(que[i], stk[stot]);
				for (; stot && dep[stk[stot]] > dep[lca]; --stot) {
					if (stot > 1 && dep[stk[stot - 1]] >= dep[lca]) {
						vt[stk[stot - 1]].push_back(stk[stot]);
					} else {
						vt[lca].push_back(stk[stot]);
					}
				}
				if (stot && stk[stot] != lca) {
					stk[++stot] = lca;
					vis[++vtot] = lca;
				}
			} 
			stk[++stot] = que[i];
			vis[++vtot] = que[i];
		}
		for (; stot > 1; --stot) {
			vt[stk[stot - 1]].push_back(stk[stot]);
		}
		update(root, vt);
		for (int i = 1; i <= vtot; i++) {
			vt[vis[i]].clear();
		}
	}
	inline int query(int id) {
		return bit.query(in[pos[id]], ot[pos[id]]);
	}
private:
	inline void update(int w, vector<int> *vt) {
		for (int i = 0; i < (int)vt[w].size(); i++) {
			bit.modify(in[w], -1);
			bit.modify(in[vt[w][i]], 1);
			update(vt[w][i], vt);
		}
	}
	inline int LCA(int a, int b) {
		if (dep[a] < dep[b]) {
			swap(a, b);
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (dep[fa[a][j]] >= dep[b]) {
				a = fa[a][j];
			}
		}
		if (a == b) {
			return a;
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (fa[a][j] != fa[b][j]) {
				a = fa[a][j];
				b = fa[b][j];
			}
		}
		return fa[a][0];
	} 
	static bool cmp(int a, int b) {
		return in[a] < in[b];
	}
	inline void DFS(int w, int f) {
		static int tt = 0;
		in[w] = ++tt;
		dep[w] = dep[fa[w][0] = f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			DFS(to[i], w);
		}
		ot[w] = tt;
	}
	inline void AddEdge(int u, int v) {
		static int E = 1;
		to[++E] = v; nxt[E] = head[u]; head[u] = E;
	}
}ac;

int main() {
	static char ss[N];
	int n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%s", ss + 1);
		int len = strlen(ss + 1);
		ac.insert(ss, len, i);
	}
	ac.build();
	int m = read();
	for (int i = 1; i <= m; i++) {
		if (read() == 1) {
			scanf("%s", ss + 1);
			int len = strlen(ss + 1);
			ac.match(ss, len);
		} else {
			printf("%d\n", ac.query(read()));
		}
	}
	return 0;
}

【日常小测】相似子串

题目大意

给定一棵$n(n \le 10^5)$的无根树,每条边上有一个字符
定义$str_{u,v}$为从$u$走到$v$,将边上的字符按顺序写下来得到的字符串
给定$m(m \le 10^5)$个询问,每一次询问会定义$k_i$种形如$a,b$这样的等价关系,意义为将所有的$a,b$字符视为同一个字符(关系具有传递性)
对于每一个询问还会给定$u_1,v_1,u_2,v_2$四个点,请你回答$str_{u_1,v_1}$与$str_{u_2,v_2}$是否至多有一个位置不匹配

解题报告

这种奇怪的匹配题目除了$FFT$之外,似乎只能$Hash$了吧?

我们先来考虑没有等价类,且是一条链的情况

定义$Hash$函数$f_{i,u,v}$为对于第$i$种字符来讲,$str_{u,v}$的$Hash$值
更进一步,$f_{i,u,v}=\sum\limits_{j=u}^{v}{[char_j=i] \cdot G^{j-u+1}}$
那么这两个字符串的$Hash$值只能在两种字符下不同,且这两种字符差的$G$的次幂相等

考虑快速求得$Hash$值,这个很简单,做一个前缀和就好
考虑快速求的差值对应的$G$的次幂,这个我们先预处理一下,然后扔到一个$map$里去就可以了
至此我们已经能在$O(|\sum|+\log n)$的时间复杂度内回答单个询问了

现在考虑加入等价类,这个我们可以将整个等价类的$Hash$值加起来一起比较就可以了
至于不是链的情况,那我们求个到根前缀和就能够解决问题啦!
至此我们已经在$O(n \log n + m (|\sum| + \log n))$的时间复杂度内解决了这个问题

【日常小测】随机游走

题目大意

给定一棵$n(n \le 10^5)$个点的无根树,再给定$m(m \le 10^5)$个询问
每次询问给定起点和终点,从起点开始XJB走到终点的期望步数是多少?
定义XJB走为:每次完全随机选择一条出边走出去,可以走回头路

解题报告

如果定义$f_{u,v}$为当前在$u$点,最终走到$v$点的期望步数
那肯定搞一个高斯消元就可以了,但这题数据太大搞不了 QwQ

但我们仔细观察一下,这里的XJB走非常妙啊!目标点、来源点完全不影响决策
于是我们定义$f_u$为这个点走到父亲的期望步数,$g_u$为这个点的父亲走到它的期望步数
那我们就可以推出以下式子:
$$f_u=\deg u + \sum\limits_{v \in son_u}{f_v}$$
$$g_u=\deg fa_u + \sum\limits_{v \in son_{fa_u},v \ne u}{f_v} + g_{fa_{fa_u}}$$
于是我们DFS两遍,然后记个前缀和什么的
询问的时候求出lca然后加加减减就可以辣!
时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = N << 1;

int n,m,head[N],nxt[M],to[M];
int in[N],dep[N],fa[N][20];
LL f[N],g[N],PreF[N],PreG[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int u, int v) {
	static int E = 1; in[u]++; in[v]++;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline int LCA(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i=19;~i;i--) if (dep[fa[u][i]]>=dep[v]) u = fa[u][i];
	if (u == v) return u;
	for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}

void DFS1(int w, int anc) {
	fa[w][0] = anc;	f[w] = in[w]; 
	dep[w] = dep[anc] + 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != anc) {
			DFS1(to[i], w);
			f[w] += f[to[i]];
		}
	}
}

void DFS2(int w, int anc) {
	PreF[w] = PreF[anc] + f[w];
	PreG[w] = PreG[anc] + g[w];
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != anc) {
			g[to[i]] = f[w] - f[to[i]] + g[w];
			DFS2(to[i], w);
		}
	}	
}

int main() {
	n = read();
	for (int i=1;i<n;i++) AddEdge(read(),read());
	DFS1(1, 1);
	DFS2(1, 1);
	for (int j=1;j<20;j++) {
		for (int i=1;i<=n;i++) {
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}
	m = read();
	for (int i=1,u,v,lca;i<=m;i++) {
		u = read(); v = read(); lca = LCA(u, v);
		printf("%lld\n",PreF[u]-PreF[lca]+PreG[v]-PreG[lca]);
	}
	return 0;
}

【BZOJ 4144】[AMPPZ2014] Petrol

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4144
神犇题解:http://www.cnblogs.com/Tunix/p/4593049.html

解题报告

随便想一想,这题似乎除了有加油站的点之外,其他点似乎完全可以不用考虑?
再仔细想一想的话,我们似乎只要求出任意两个有加油站的点的最短路,然后再做一个MST就可以了!

现在的问题就是如何求出任意两点的最短路了
我们考虑放宽一点条件,求出一些最短路径的集合 $\{ e \}$ ,使其能够凑出任意两点的最短路
现在考虑两点之间最短路的性质:

定义$blg(x)$表示离$x$最近的关键点
那么对于 $a \to b$ 最短路上,一定是前一部分$blg(x)=a$,后一部分$blg(x)=b$
于是我们就可以通过枚举原图中的一条边$(x_1,x_2)$并且判断$blg(x_1)$是否等于$blg(x_2)$来找到所有中途不经过加油站的最短路

如何证明呢?考虑反证法:如果中途有一个点$blg(y)=c$那么先从$a \to b \to c$一定不比$a \to b$劣
这是因为如果我们走到y点后绕道到c点去加油,回来的时候油量一定不少于从a点到y点的油量

这样我们就可以找到一个边集 $\{ \varepsilon \}$使得 $\{ e\} \subset \{ \varepsilon \}$
于是我们把$\{ \varepsilon \}$拿出来,做一个最小生成树,然后查询的时候,在树上倍增一下就可以啦!

【BZOJ 2851】极限满月

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2851
数据生成器:http://paste.ubuntu.com/23321973/

这道题我真的是服了。 服气!
0_7uftv1i06u7jhr9

如果考虑{ai}为父亲集合的话
这货是个DAG
然后看一看{bi}中涉及到的∩操作
从顶端向下考虑的话,这™不就是支配点!
于是求一求灾难树,然后求一求路径并

话说这么巧妙的题目出题人是怎么想到的!
服! 真心服!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = N*200;

int head[N],nxt[M],to[M],n,m,in[N],out[N];
int que[N],fa[N][18],dep[N],num_cnt;
vector<int> G[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0; in[v]++;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline bool cmp(const int &a, const int &b) {
	return in[a] < in[b];
}

inline int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}	
	if (x == y) return y;
	for (int i=17;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

inline void solve(int w) {
	dep[w] = dep[fa[w][0]] + 1;
	if (w) G[fa[w][0]].push_back(w);
	for (int i=1;i<=17;i++) {
		fa[w][i] = fa[fa[w][i-1]][i-1];
	}
	
	for (int i=head[w];i;i=nxt[i]) {
		if (!~fa[to[i]][0]) {
			fa[to[i]][0] = w;
		} else {
			fa[to[i]][0] = lca(fa[to[i]][0], w);
		}
		
		if (!--in[to[i]]) solve(to[i]);
	}
}

void DFS(int w) {
	in[w] = ++num_cnt;
	for (int i=G[w].size()-1;~i;i--) {
		DFS(G[w][i]);
	}
	out[w] = num_cnt;
}

int main(){
	memset(fa,-1,sizeof(fa));
	n = read();
	for (int i=1;i<=n;i++) {
		for (int j=read();j;j--) {
			Add_Edge(read(),i);
		}
		if (!in[i]) {
			Add_Edge(0,i);
		}
	}
	
	fa[0][0] = 0;
	solve(0);
	DFS(0);
	
	m = read(); 
	for (int k=1,len,vout=0;k<=m;k++,vout=0) {
		len = read();
		for (int j=1;j<=len;j++) {
			que[j] = read();
		}
		
		sort(que+1,que+1+len,cmp);
		for (int i=1,pre=0;i<=len;i++) {
			vout += dep[que[i]];
			vout -= dep[lca(pre,que[i])];
			pre = que[i];
		}
		
		printf("%d\n",vout);
	}
	return 0;
}

—– UPD 2016.10.16 —–
今天发现这题数据范围有问题
关系数应该是小于2e6
点数应该是小于2e5

【BZOJ 2815】[ZJOI2012] 灾难

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2815
题面传送门:http://blog.csdn.net/flaze_/article/details/51334708

这题好好玩!
让我们来膜拜fanhq666:
http://fanhq666.blog.163.com/blog/static/8194342620124274154996/

这题把数学模型抽象出来就是:
给一个有向无环图,问每个节点删掉之后会导致多少个点不可达。
感觉还是挺有用的样子!

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000;
const int M = 1000000;

int head[N],to[M],nxt[M],fa[N][18];
int in[N],sz[N],dep[N],n; 
vector<int> G[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0; in[v]++;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

inline int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x,y);
	for (int i=17;~i;i--) {
		if (dep[fa[x][i]] >= dep[y]) {
			x = fa[x][i];
		}
	}
	if (x == y) return y;
	for (int i=17;~i;i--) {
		if (fa[x][i] != fa[y][i]) {
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}

void solve(int w) {
	dep[w] = dep[fa[w][0]] + 1;
	if (w) G[fa[w][0]].push_back(w);
	for (int i=1;i<=17;i++) {
		fa[w][i] = fa[fa[w][i-1]][i-1];
	}
	
	for (int i=head[w];i;i=nxt[i]) {
		if (fa[to[i]][0] == -1) {
			fa[to[i]][0] = w;
		} else {
			fa[to[i]][0] = lca(fa[to[i]][0],w);
		}
		
		if (--in[to[i]] == 0) {
			solve(to[i]);
		}
	}
}

void Get_Size(int w) {
	sz[w] = 1;
	for (int i=G[w].size()-1;~i;i--) {
		Get_Size(G[w][i]);
		sz[w] += sz[G[w][i]];
	}
}

int main(){
	memset(fa,-1,sizeof(fa));
	n = read();
	for (int i=1;i<=n;i++) {
		for (int j=read();j;j=read()) {
			Add_Edge(j,i);
		}
		if (!in[i]) {
			Add_Edge(0,i);
		}
	}
	
	fa[0][0] = 0;
	solve(0);
	Get_Size(0);
	
	for (int i=1;i<=n;i++) {
		printf("%d\n",sz[i] - 1);
	}
	return 0;
}

【BZOJ 4568】[Scoi2016] 幸运数字

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4568
数据生成器:http://paste.ubuntu.com/23202923/

《浅谈省选的时候还不会线性基的悲伤有多大》
今天重新看了一看,结果最开始写的是链剖,T到死 ←是男人就去ZGS的OJ上测,单点时限
后来重新写了LCA的版本,又T到死
于是暴力优化常数,最终5.9s勉强卡过

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 20000+9; 

int n,q,head[N],nxt[N*2],to[N*2];
LL arr[N];

inline int read(){char c=getchar(); int ret=0;while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}
inline LL readL(){char c=getchar(); LL ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

namespace LCA{
	int fa[N][16],dep[N];
	LL f[N][16][61],POW[61];

	void DFS(int w, int f) {
		fa[w][1] = f; fa[w][0] = w; dep[w] = dep[f] + 1; 
		for (int i=head[w];i;i=nxt[i]) if (to[i] != f) DFS(to[i],w);
	} inline void DFS(){DFS(1,1);for (int i=0;i<=60;i++) POW[i] = 1LL<<i;}
	
	inline void merge(LL *a, LL *b) {
		for (int i=60;~i;i--) if (b[i]) {
			LL w = b[i]; for (int j=60;~j;j--) if (w&POW[j]) {
				if (!a[j]) {a[j] = w; break;}
				else w ^= a[j];
			}
		} 
	}
	
	inline void init() {
		for (int j=1;j<=n;j++) for (int i=60;~i;i--) if (POW[i]&arr[j]) {f[j][0][i] = arr[j]; break;}
		for (int i=1;i<=n;i++) memcpy(f[i][1],f[i][0],sizeof(f[i][0])), merge(f[i][1],f[fa[i][1]][0]);
		for (int i=1;i<=n;i++) for (int j=2;j<=15;j++) 
			fa[i][j] = fa[fa[i][j-1]][j-1], 
			memcpy(f[i][j],f[i][j-1],sizeof(f[i][j])),
			merge(f[i][j],f[fa[i][j-1]][j-1]);
	}
	
	inline LL query(int x, int y) {
		static LL bas[61]; memset(bas,0,sizeof(bas));
		if (dep[x] < dep[y]) swap(x,y);
		for (int i=15;~i;i--) if (dep[fa[x][i]] > dep[y]) 
			merge(bas,f[x][i]), x = fa[fa[x][i]][1];
		if (x == y) merge(bas,f[x][0]);  
		else {
			for (int i=15;~i;i--)  if (fa[x][i] != fa[y][i])
				merge(bas,f[x][i]), merge(bas,f[y][i]), 
				x = fa[fa[x][i]][1], y = fa[fa[y][i]][1];
			merge(bas,f[x][0]); 
		} LL ret = 0;
		for (int i=0;i<=60;i++) if (bas[i]) 
		for (int j=i+1;j<=60;j++) if (bas[j]&POW[i]) bas[j] ^= bas[i];
		for (int i=0;i<=60;i++) ret ^= bas[i];
		return ret;
	}	
};

int main(){
	n = read(); q = read();
	for (int i=1;i<=n;i++) arr[i] = readL();
	for (int i=1;i<n;i++) Add_Edge(read(),read());
	LCA::DFS(); LCA::init(); 
	for (int i=1;i<=q;i++) printf("%lld\n",LCA::query(read(),read()));
	return 0;
}

另外,%Claris,直接上点分治:http://www.cnblogs.com/clrs97/p/5451814.html