【HDU 5716】带可选字符的多字符串匹配

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5716
神犇题解:http://www.cnblogs.com/clrs97/p/5985648.html

解题报告

这货$KMP$是不可做的,于是考虑用$bitset$来优化暴力
定义$v[i][j]$为文本串第$i$位是否能匹配模式串第$j$位
定义$f[i][j]$为第$i$种字符能否匹配模式串第$j$位
那么$v[i][j] = v[i – 1][j – 1] \ and \ f[s[i]][j]$
然后数组第二维用$bitset$优化,时间复杂度:$O(\frac{nm}{64})$

Code

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

const int N = 2000009;
const int M = 600;
const int SGZ = 100;

char s[N], sgz[SGZ];
bitset<M> v, f[SGZ];

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;
}

inline int id(char c) {
	if ('0' <= c && c <= '9') {
		return c - '0' + 1;
	} else if ('a' <= c && c <= 'z') {
		return c - 'a' + 11;
	} else if ('A' <= c && c <= 'Z'){
		return c - 'A' + 37;
	} else {
		return 0;
	}
}

int main() {
	while (gets(s + 1)) {
		int n = strlen(s + 1), m = read();
		v.reset();
		for (int i = 0; i < SGZ; i++) {
			f[i].reset();
		}
		for (int i = 1; i <= m; i++) {
			int SGZ = read();
			scanf("%s", sgz + 1);
			for (int j = 1; j <= SGZ; j++) {
				f[id(sgz[j])][i] = 1;
			}
		}
		bool CantMatch = 1;
		for (int i = 1; i <= n; i++) {
			v = (v << 1) & f[id(s[i])];
			v[1] = f[id(s[i])][1];
			if (v[m]) {
				printf("%d\n", i - m + 1);
				CantMatch = 0;
			}
		}
		if (CantMatch) {
			puts("NULL");
		}
		getchar();
	}
	return 0;
}

—————————— UPD 2017.7.3 ———————————
这题的简单拓展:http://www.lydsy.com/JudgeOnline/problem.php?id=4924

【日常小测】友好城市

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

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

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

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

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

【Codeforces 781D】Axel and Marston in Bitland

相关链接

题目传送门:http://codeforces.com/contest/781/problem/D

解题报告

话说这个题,你看他的路径定义多么奇怪
构造方式就是倍增嘛!

那我们也来倍增吧!
于是搞一个bitset记录哪些点可以到达就可以辣!
时间复杂度:$O(\frac{n^3 \log 10^{18}}{64})$

Code

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

const int N = 501;
const int M = N * N;
const LL INF = 1000000000 * 1000000000ll;

bitset<N> f[60][N][2],ans,pre; 
int n,m;

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;
}

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<=m;i++) {
		u = read(); v = read();
		f[0][u][read()][v] = 1; 
	}
	for (int s=0;s<59;s++) {
		for (int i=1;i<=n;i++) {
			for (int t=0;t<=1;t++) {
				for (int j=1;j<=n;j++) {
					if (f[s][i][t][j]) {
						f[s+1][i][t] |= f[s][j][t^1];
					}
				}
			}
		}
	}
	ans[1] = 1; LL vout = 0;
	for (int s=59,t=0;~s;s--) {
		pre = ans; ans.reset();
		for (int i=1;i<=n;i++) 
			if (pre[i]) ans |= f[s][i][t];
		if (ans.count()) {
			vout += 1ll << s;
			t ^= 1; 
		} else ans = pre;
	} 
	printf("%lld\n",vout>INF?-1:vout);
	return 0;
}

【BZOJ 4713】迷失的字符串

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4713

解题报告

这题拿bitset搞一搞就好了
f[i]表示前缀匹配,g[i]表示后缀匹配
然后暴力更新
时间复杂度:$O(\frac{n^2}{64})$

Code

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

const int M = 16;
const int SGZ = 26;
const int N = 30000+9;

int head[N],nxt[N<<1],to[N<<1],col[N<<1],sz[N],hvy[N];
int n,m,tot,beg[N],ed[N],id[N],pool[M],top; char s[N];
bitset<N> vout,ans,ve,vis[SGZ],vs[SGZ],f[M],g[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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, int c) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c;
}

void DFS1(int w, int f) {
	sz[w] = 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS1(to[i], w);
			sz[w] += sz[to[i]];
			if (sz[hvy[w]]<sz[to[i]]) 
				hvy[w] = to[i];
		}
	}
}

inline void init(int w) {
	id[w] = pool[top--];
	f[id[w]].reset();
	g[id[w]] = ve;	
}

inline void solve(int x, int y, int c) {
	int ix = id[x], iy = id[y];
	f[iy] <<= 1; f[iy] &= vis; f[iy] |= vs;
	g[iy] = g[iy] & vis;
	vout |= g[iy];
	g[iy] >>= 1;
	ans |= f[ix] & g[iy];
	ans |= g[ix] & f[iy];
	f[ix] |= f[iy];
	g[ix] |= g[iy];
	pool[++top] = iy;
}

void DFS2(int w, int f) {
	if (hvy[w]) DFS2(hvy[w], w);
	init(w);
	for (int i=head[w];i;i=nxt[i]) if (to[i] == hvy[w]) 
		solve(w, hvy[w], col[i]);
	for (int i=head[w];i;i=nxt[i]) if (to[i] != hvy[w] && to[i] != f) 
		DFS2(to[i], w), solve(w, to[i], col[i]);
} 

int main() {
	for (int i=top=M-1;~i;i--) pool[i] = i;
	for (int i=n=read(),u,v;i>1;i--) {
		u = read(); v = read(); 
		scanf("%s",s);
		Add_Edge(u, v, s[0]-'a');
	}
	for (int i=m=read(),len;i;i--) {
		scanf("%s",s); len = strlen(s); 
		vs[s[0]-'a'][beg[m-i+1]=tot+1] = 1; 
		for (int j=0;j<len;j++) vis[s[j]-'a'][++tot] = 1;
		ve[ed[m-i+1]=tot] = 1; 
	}
	DFS1(1, 1); 
	DFS2(1, 1);
	for (int i=1,tag=0;i<=m;i++,tag=0) {
		if (vout[beg[i]]) tag = 1;
		for (int j=beg[i];j<=ed[i]&&!tag;j++) if (ans[j]) tag = 1;
		puts(tag?"YES":"NO");
	}
	return 0;
}

后记

这题似乎之前听谁说过有点分的做法?
不过想不起怎么做了 _(:з」∠)_
会的神犇可不可以给我讲一讲怎么做啊 QwQ

【BZOJ 4644】经典傻逼题

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4644
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5734792.html
神犇题解Ⅱ:http://blog.csdn.net/neither_nor/article/details/53997223

解题报告

首先,如果我们把边权异或到点上
原问题就可以转化为:选一些点,使NIM和最大
于是就是线性基的锅了,时间复杂度:$ \frac{{nm{L^2}}}{{{\rm{64}}}}$

然后我们发现这么做会T
于是对时间进行分治
这样的话,复杂度优化到:$ \frac{{m\log m{L^2}}}{{{\rm{64}}}}$

然后Claris还说可以用Method of Four Russians
这样话,复杂度就变成了:$ \frac{{m\log m{L^2}}}{{{\rm{64logL}}}}$

【NOIP十连测】[D1T2] Tourist Attractions

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/10/noip_test1_statements.pdf

解题报告

虽然没能A掉
但明明是70分的dp却交成了40分的暴力
仍然不高兴 >︿<

四个点的话,就是三条边
考虑枚举中间的那一条边
则其对答案的贡献就是两点入度的乘积
但3元环不符合题意
于是搞一搞bitset可以在O(n/32)的时间复杂度内统计三元环

Code

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

const int N = 1500+9;

LL vout; 
int n,in[N];
bitset<N> edg[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;
}

int main(){
	n = read(); char pat[N];
	for (int j=1;j<=n;j++) {
		scanf("%s",pat+1);
		for (int i=1;i<=n;i++) 
			edg[j][i] = pat[i] - '0',
			in[i] += pat[i] - '0';
	}
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (edg[i][j]) {
		vout += (LL)(in[i] - 1) * (in[j] - 1);
		vout -= (edg[i] & edg[j]).count();
	}
	printf("%lld\n",vout);
	return 0;
}

最后来撸一发Claris的手写bitset:http://paste.ubuntu.com/23262667/
想一想好像这么写很优越的样子!