I always love dashie
0%

Posted on Edited on In

这里存一些被淘汰掉的板子之类的东西

2021-04-03

FFT

复数类操作:

1
2
3
complex<double>m;
m.real();m.imag();//获取实部虚部的值
m.real(114);m.imag(514);//为实部虚部赋值

需要继续理解迭代算法.现在这就是个板子

被卡常时记得别用long double

调用FFT(A,1)将\(A\)变为\(A\)的\(DFT\),调用FFT(A,-1)求\(DFT^{-1}\).

\(A\)是复数数组,其实部初始是多项式系数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
typedef double ld;
typedef complex<ld> cld;
typedef vector<cld> Poly;
const int maxn = 8E6+10;
const ld PI = acos(-1.0);
int rev[maxn];
void init(Poly & A,int n){
	int size = 1;
	while(size <= n)size *= 2;
	A.assign(size*2,0);
}
void FFT_init(int n){
	int S = log2(n);
	for(int i = 0;i < n;i++)rev[i] = (rev[i>>1] >> 1) | ((i & 1) << (S - 1));
}
void FFT(Poly & A,int type){
	int n = A.size();
	for(int i = 0;i < n;i++)if(i < rev[i])swap(A[i],A[rev[i]]);
	for(int i = 1;i < n;i *= 2){
		cld Wn(cos(PI/i),type*sin(PI/i));
		for(int j = 0;j < n;j += i*2){
			cld W(1,0);
			for(int k = 0;k < i;k++){
				cld facx = A[j+k],facy = W*A[j+k+i];
				A[j+k] = facx + facy;
				A[j+k+i] = facx - facy;
				W *= Wn;
			}
		}
	}
    if(type == -1)for(int i = 0;i < (int)A.size();i++)A[i].real((int)(A[i].real()/A.size() + 0.5));
}

卷积

\[ C[i] = \sum_{j = 0}^iA[j]B[i-j] \]

卷积等同于多项式乘积

输入两个多项式\(A,B\)的系数,求出其乘积:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	int n,m;
	cin >> n >> m;
	int d = n+m;
	Poly A,B;
	init(A,max(n,m));
	init(B,max(n,m));
	FFT_init(A.size());
	for(int i = 0;i <= n;i++)cin >> A[i]; 
	for(int i = 0;i <= m;i++)cin >> B[i];
	FFT(A,1);
	FFT(B,1);
	for(int i = 0;i < (int)A.size();i++)A[i] *= B[i];
	FFT(A,-1);
	for(int i = 0;i <= d;i++)cout << (int)(A[i].real()/A.size() + 0.5)<< " ";
	return 0;
}

手写复数类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct node{
    double x, y ;
    node (double xx = 0, double yy = 0){
        x = xx, y = yy ;
    }
};
node operator * (node J, node Q){
    return node(J.x * Q.x - J.y * Q.y , J.x * Q.y + J.y * Q.x);
}
node operator + (node J, node Q){
    return node(J.x + Q.x , J.y + Q.y);
}
node operator - (node J, node Q){
    return node(J.x - Q.x , J.y - Q.y );
}

NTT

从OI-wiki抄来的, 用法和上面的FFT一致. 记得自己手写一遍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef vector<int> Poly;
int rev[maxn];
void init(vector<int> & x,int n){
	int size = 1;
	while(size <= n)size *= 2;
	x.assign(size*2,0);
}
void NTT_init(int lim){
	for (int i = 0; i < lim; ++i) rev[i] = (i & 1) * (lim >> 1) + (rev[i >> 1] >> 1);
}
void NTT(vector<int> & A, int opt) {
	int lim = A.size();
 	int i, j, k, m, gn, g, tmp;
 	for(i = 0; i < lim; ++i)if (rev[i] < i) swap(A[i], A[rev[i]]);
 	for(m = 2; m <= lim; m <<= 1) {
	    k = m >> 1;
	    gn = Pow(3,(p - 1) / m);//998244353的原根是3
	    for(i = 0; i < lim; i += m) {
	    	g = 1;
	    	for (j = 0; j < k; ++j, g = 1ll * g * gn % p) {
	    	    tmp = 1ll * A[i + j + k] * g % p;
	    	    A[i + j + k] = (A[i + j] - tmp + p) % p;
	     	 	A[i + j] = (A[i + j] + tmp) % p;
	    	}
		}
	}
	if(opt == -1){
		auto it = A.begin();it++;
    	reverse(it,A.end());
    	int inv = Pow(lim,p-2);
    	for(i = 0; i < lim; ++i) A[i] = 1ll * A[i] * inv % p;
	}
}

与FFT的区别在点值表示法相乘时, NTT需要取模. 另外注意原根需与模数对应

1
for(int i = 0;i < (int)A.size();i++)A[i] = 1ll*A[i]*B[i]%p;

Posted on In

题意

设\(p\)为从\(\sum\)到\(\sum\)的双射(\(\sum = \{a,b,...,z\})\). 给出两个字符串\(s,t\)(由于个人习惯,此处s,t的含义和原题相反)且满足\((1 \leq |t| \leq |s| \leq 2 \cdot10^5)\). 求对于\(s\)的每个长度为\(|t|\)的子串\(s'\), \(s'\)与\(t\)是否匹配. 输出一个长为\(|s| - |t| + 1\)的01串, 其中第\(i\)位为1表示\(s[i...i+|t| - 1]\)与\(t\)匹配.

匹配在此题定义为: 设两个长度相等的串\(s',t\), 对全部\(i = 0...|t|-1\), 有\(s'[i] == t[i]\) 或\(s'[i] == p(t[i])\)

题解

首先我们设匹配函数 \[ F(x) = \sum_{i = x,j = i - x}^{|t| + x - 1}(s[i] - t[j])^2(s[i] - f(t[j]))^2 \] 容易看出, 当且仅当\(F(x) == 0\)时, \(s[x...x+|t| - 1]\)与\(t\)匹配. 将和式内部展开后化简, 可以发现展开后每一项都可化为 \(\sum_{i,j = 1}^na_ib_j\)的形式. 我们用经典套路把\(t\)反转后, 便可化为卷积形式用FFT求解.

但是这个式子好像要做七次DFT和IDFT, 太麻烦. 我们尝试乱搞一下: \[ G(x) = \sum_{i = x,j = i-x}^{|t| + x - 1}(s[i] - t[j])(s[i] - f(t[j])) \] 展开后有: \[ G(x) = \sum_{i = x}^{|t| + x - 1}s[i]^2 - \sum_{i = x,j = i-x}^{|t| + x - 1}s[i]\cdot f(t[j]) - \sum_{i = x,j = i-x}^{|t| + x - 1}s[i]\cdot t[j] + \sum_{j = 0}^{|t| - 1} t[j] \cdot f(t[j]) \]

首项和末项用前缀和处理, 剩下两项可以分别进行一次卷积求出.

把平方去掉后由于存在负数项, 因而某些不能被匹配的位置也可能有\(G(x) = 0\). 我们将a-z随机赋上一个权值后再进行计算, 便能大大减少冲突的概率. (我不知道这种做法实际上是否正确, 更不能保证不会被卡, 但这种做法足够通过此题). 由于FFT在计算时会损失精度, 我们使用NTT进行求解.

时间复杂度\(|s|\log |s|\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxn = 6e6+10;
const int p = 998244353;
int Pow(int x,int d){
	int tans = 1;
	if(d == 0)return 1%p;
	int a = Pow(x,d/2);
	tans = 1ll*a*a%p;
	if(d%2)tans = 1ll*tans*x%p; 
	return tans%p;
}
int rev[maxn];
void init(vector<int> & x,int n){
	int size = 1;
	while(size <= n)size *= 2;
	x.assign(size*2,0);
}
void NTT_init(int lim){
	for (int i = 0; i < lim; ++i) rev[i] = (i & 1) * (lim >> 1) + (rev[i >> 1] >> 1);
}
void NTT(vector<int> & A, int opt) {
	int lim = A.size();
 	int i, j, k, m, gn, g, tmp;
 	for(i = 0; i < lim; ++i)if (rev[i] < i) swap(A[i], A[rev[i]]);
 	for(m = 2; m <= lim; m <<= 1) {
	    k = m >> 1;
	    gn = Pow(3,(p - 1) / m);
	    for(i = 0; i < lim; i += m) {
	    	g = 1;
	    	for (j = 0; j < k; ++j, g = 1ll * g * gn % p) {
	    	    tmp = 1ll * A[i + j + k] * g % p;
	    	    A[i + j + k] = (A[i + j] - tmp + p) % p;
	     	 	A[i + j] = (A[i + j] + tmp) % p;
	    	}
		}
	}
	if(opt == -1){
		auto it = A.begin();it++;
    	reverse(it,A.end());
    	int inv = Pow(lim,p-2);
    	for(i = 0; i < lim; ++i) A[i] = 1ll * A[i] * inv % p;
	}
}
typedef vector<int> Poly;
Poly A,B;
int per[30];
int w[maxn][5];
int rnd[30];
int ans[maxn];
mt19937 Rand(19260817);
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s,t;
	srand(time(NULL));
	for(int i = 0;i < 26;i++)cin >> per[i],per[i]--,rnd[i] = Rand()%p;
	cin >> t >> s;
	int n = s.size(),m = t.size();
	Poly A,B;
	init(A,s.size());
	init(B,s.size());
	NTT_init(A.size());
	for(int i = 0;i < n;i++)w[i][0] = (1ll*rnd[s[i] - 'a']*rnd[s[i] - 'a']%p + (i?w[i-1][0]:0))%p;
	for(int i = 0;i < m;i++)w[i][3] = (1ll*rnd[t[i] - 'a']*rnd[per[t[i] - 'a']]%p + (i?w[i-1][3]:0))%p;
	for(int i = 0;i < n;i++)A[i] = rnd[s[i] - 'a'];
	for(int i = 0;i < m;i++)B[m - i - 1] = rnd[t[i] - 'a'];
	NTT(A,1);
	NTT(B,1);
	for(int i = 0;i < (int)A.size();i++)A[i] = (1ll*A[i]*B[i])%p;
	NTT(A,-1);
	for(int i = 0;i < (int)A.size();i++)w[i][1] = A[i];
	init(A,s.size());
	init(B,s.size());
	for(int i = 0;i < n;i++)A[i] = rnd[s[i] - 'a'];
	for(int i = 0;i < m;i++)B[m - i - 1] = rnd[per[t[i] - 'a']];
	NTT(A,1);
	NTT(B,1);
	for(int i = 0;i < (int)A.size();i++)A[i] = (1ll*A[i]*B[i])%p;
	NTT(A,-1);
	for(int i = 0;i < (int)A.size();i++)w[i][2] = A[i];
	for(int i = m-1;i < n;i++){
		ll A = (w[i][0] - (i - m >= 0?w[i-m][0]:0) + p)%p,D = w[m-1][3]%p;
		ll B = w[i][1],C = w[i][2];
		if((((A -  B + p)%p - C + p) % p + D)%p == 0)cout << "1";
		else cout << "0";
	}
	return 0;
}

Posted on Edited on In

孩子的第一道卷积题

题意

假设两个相等长度的字符串\(u,v\). 每次可以进行一次操作将\(u,v\)中某种字符同时全部变为另一种字符, 设\(F(u,v)\)为使得\(u,v\)相等的最小操作次数.

现在给出两个字符串\(s,t\), 且保证\(|s| \geq |t|\). 求对于\(s\)的全部长度为\(|t|\)的子串\(s'\), \(F(s',t)\)的值各为多少.

保证\(\sum = \{\text{a,b,c,d,e,f}\}\), \(1 \leq |t| \leq |s| \leq 1.25\cdot 10^5\)

题解

首先求解\(F(u,v)\). 我们建一张图, 图中节点为字母\(a...f\). 对所有的\(i = 1...|u|\), 连边\((u[i],v[i])\). 显然答案最小值为该图任意生成树边的数目, 可以简单地用并查集求解. 暴力求解复杂度为\(O(|s|^2)\).

考虑优化. 设\(n = |s|,m = |t|.\) 设\(f[c][d][idx]\)为\(s[idx- m + 1...idx]\)中字符\(c\)与\(t\)中字符\(d\)下标(从0开始)一一对应的数目. 例如\(s = \text{bbcdefa}, t = \text{ddcb}\). 则\(f['b']['d'][3] = 2\).

求出\(f[c][d][idx]\)后, 对于每个\(f[c][d][idx] > 0\), 从\(c\)向\(d\)连一条边, 再按\(F(u,v)\)的方法求解, 便能求出每个\(idx\)的答案.

下面是FFT处理这类字符串匹配问题的套路做法:

假设我们需要求\(f[c][d]\). 设多项式\(g,h\). 令\(g(i) = [s[i] == c],h(i) = [t[j] == d]\). 此后将\(h\)翻转, 我们发现\(g\)与\(h\)的卷积: \[ (g \ast h)[i] = \sum_{j = 0}^i g[j]\cdot h[i-j] \] 恰好是我们想要的\(f[c][d][]\).

枚举每个\(c,d \in \sum\), 便能高效求解问题. 时间复杂度\(|\sum|^2n\log n\)

优化: 容易发现\(g\)和\(h\)各只有\(6\)种, 因此我们只需做\(12\)次(而非\(36\)次)DFT. 并且\(c == d\)的情况显然对答案没有贡献, 无需考虑.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
typedef double ld;
typedef complex<ld> cld;
typedef vector<cld> Poly;
const int maxn = 6e6+10;
const ld PI = acos(-1.0);
int rev[maxn];
void init(Poly & A,int n){
	A.clear();
	A.shrink_to_fit();
	int size = 1;
	while(size <= n)size *= 2;
	A.assign(size*2,0);
}
void FFT_init(Poly A){
	int n = A.size();
	int S = log2(n);
	for(int i = 0;i < n;i++)rev[i] = (rev[i>>1] >> 1) | ((i & 1) << (S - 1));
}
void FFT(Poly & A,int type){
	int n = A.size();
	for(int i = 0;i < n;i++)if(i < rev[i])swap(A[i],A[rev[i]]);
	for(int i = 1;i < n;i *= 2){
		cld Wn(cos(PI/i),type*sin(PI/i));
		for(int j = 0;j < n;j += i*2){
			cld W(1,0);
			for(int k = 0;k < i;k++){
				cld facx = A[j+k],facy = W*A[j+k+i];
				A[j+k] = facx + facy;
				A[j+k+i] = facx - facy;
				W *= Wn;
			}
		}
	}
	if(type == -1)for(int i = 0;i < (int)A.size();i++)A[i].real((int)(A[i].real()/A.size() + 0.5));
}
vector<int>f[10][10];
Poly DFTA[10],DFTB[10];
int father[10];
void init(){
	for(int i = 0;i < 10;i++)father[i] = i;
}
int findset(int e){
	return father[e] == e?e:father[e] = findset(father[e]);
}
inline void un(int x,int y){
	father[findset(x)] = findset(y);
}
bool check(int u,int v){
	return findset(u) == findset(v);
}
int n,m;
int cal(int idx){
	init();
	int cnt = 0;
	for(int i = 'a';i <= 'f';i++){
		for(int j = 'a';j <= 'f';j++)if(i != j){
			int u = i - 'a',v = j - 'a';
			if(f[u][v][idx] <= 0)continue;
			if(!check(u,v))cnt++;
			un(u,v);
		}
	}
	return cnt;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s,t;
	cin >> s >> t;
	Poly A,B;
	n = s.size(),m = t.size();
	init(A,n);
	FFT_init(A);
	for(char c = 'a';c <= 'f';c++){
		init(DFTA[c - 'a'],n);
		init(DFTB[c - 'a'],n);
		for(int i = 0;i < n;i++)if(s[i] == c)DFTA[c - 'a'][i] = 1;
		for(int j = 0;j < m;j++)if(t[j] == c)DFTB[c - 'a'][m - j - 1] = 1;
		FFT(DFTA[c - 'a'],1);
		FFT(DFTB[c - 'a'],1);
	}
	for(char c = 'a';c <= 'f';c++){
		for(char d = 'a';d <= 'f';d++)if(c != d){
			A = DFTA[c - 'a'],B = DFTB[d - 'a'];
			for(int i = 0;i < (int)A.size();i++)A[i] *= B[i];
			FFT(A,-1);
			for(int i = 0;i < (int)A.size();i++)f[c - 'a'][d - 'a'].push_back((int)A[i].real());
		}
	}
	for(int i = m-1;i < n;i++)cout << cal(i) << " ";
	return 0;
}

Posted on In

题意

给出一个带权无向图\((1 \leq n \le 100, 1 \le m \le 500)\), 设的最小生成树为\(G\).

对于每条边\(e\), 设\(G'\)为必须包含\(e\)的最小生成树. 定义\(H(e)\)为存在于\(G\)但不存在于\(G'\)的边的数目.

求\(\sum_{i = 1}^mH(e_i)\)

题解

考虑转化原问题.

对于某条边\(e\), 设权值比它小的边的集合为\(E'\). 显然只有\(E'\)才会影响到\(e\)是否在最小生成树中. 而要确保\(e\)被添加到最小生成树中, \(E'\)组成的图中\(e\)的两端必须不连通. 至此问题转化为最小割, 求\(m\)次最小割即可求解.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxn = 105;
const int maxm = maxn*maxn*2;
const int INF = 1e9+1;
struct Edge{
	int from,to,next,w,cap,flow;
	Edge(int from = 0,int to = 0,int w = 0):from(from),to(to),w(w){}
	bool operator < (const Edge & X)const{
		return w < X.w;
	}
}edge[maxm],edge2[maxm];
int head[maxn],deep[maxn],vis[maxn],cur[maxn];
int n,m,cnt;
void addedge(int from,int to,int cap,int flow){
	edge[cnt].from = from;
	edge[cnt].to = to;
	edge[cnt].cap = cap;
	edge[cnt].flow = flow;
	edge[cnt].next = head[from];
	head[from] = cnt++;
}
bool BFS(int s,int t){
	memset(vis,0,sizeof(vis));
	for(int i = 1;i <= n;i++)cur[i] = head[i];
	queue<int>q;
	q.push(s);
	vis[s] = 1;
	deep[s] = 0;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].to;
			if(!vis[v] and edge[i].cap > edge[i].flow){
				vis[v] = 1;
				deep[v] = deep[u] + 1;
				q.push(v);
			}
		}
	}
	return vis[t];
}
int DFS(int u,int t,int approve){
	if(u == t or approve == 0)return approve;
	int flow = 0,delta = 0;
	for(int i = cur[u];~i;i = edge[i].next){
		cur[u] = i;
		int v = edge[i].to;
		if(deep[u] + 1 == deep[v] and (delta = DFS(v,t,min(approve,edge[i].cap - edge[i].flow))) > 0){
			edge[i].flow += delta;
			edge[i^1].flow -= delta;
			flow += delta;approve -= delta;
			if(!approve)break; 
		}
	}
	return flow;
}
int Dinic(int s,int t){
	int flow = 0;
	while(BFS(s,t)){
		flow += DFS(s,t,INF);
	}
	return flow;
}
signed main(){
	ios::sync_with_stdio(0);
	memset(head,-1,sizeof(head));
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int f,t,w;
		cin >> f >> t >> w;
		edge2[i] = Edge(f,t,w);
	}
	sort(edge2+1,edge2+m+1);
	int ans = 0;
	for(int i = 1;i <= m;i++){
		cnt = 0;
		for(int j = 1;j <= n;j++)head[j] = -1,deep[j] = 0;
		int s = edge2[i].from,t = edge2[i].to;
		for(int j = 1;j < i;j++)if(edge2[j].w < edge2[i].w){
			int f = edge2[j].from,t = edge2[j].to;
			addedge(f,t,1,0);
			addedge(t,f,0,0);
			addedge(t,f,1,0);
			addedge(f,t,0,0);
		}
		ans += Dinic(s,t);
	}
	cout << ans;
	return 0;
}

Posted on In

题意

给出一个\(n\)个点, \(m\)条边, 不含自环, 重边的带权无向图, 定义一条路径\(<v_1,v_2,...v_k>\)的权值为 \[ \sum_{i = 1}^k w_{v_i} - \max_{i = 1}^k\{w_{v_i}\} + \min_{i = 1}^k\{w_{v_i}\} \] 求从点1到其他所有点路径的最小权值

\(2 \leq n \leq 2e5,1 \leq m \leq 2e5,1 \leq w \leq 1e9\)

思路

原问题要求在权值中减去边权最大值, 加上边权最小值. 我们考虑将问题约束放宽: 可以减去和加上任意一条边的边权.

可以发现, 在最短路径中, 减去的必定是边权最大值, 而加上的必定是边权最小值(可用反证法证明), 即放宽后的问题与原问题等价.

求解该问题可以用分层图最短路. 由于必须加上和减去一条边的边权, 故求解最短路径时可能有以下三种情况:

  1. 先减去边X(图A), 再加上边Y(图B)
  2. 先加上边X(图C), 再减去边Y(图D)
  3. 加上和减去同一条边X (图S, 相当于原图最短路)
pic1.png

建图时每层原图为无向边，连接两层图之间的边为有向边, 具体细节见代码. 从1开始跑Dijkstra, 图S, B , D的最小值即为答案.

时间复杂度: \(O(m\log n)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> node;
#define endl '\n'
const int N = 2e5+1;
const int maxn = N*6+10;
const int maxm = maxn*6;
const ll INF = 1e17;
int head[maxn],cnt;
bool vis[maxn];
ll dis[maxn];
struct Edge{
	int f,t;
	ll w;
	int next;
	Edge(int f = 0,int t = 0,ll w = 0,int next = 0):f(f),t(t),w(w),next(next){}
}edge[maxm];
void addedge(int f,int t,ll w){
	edge[cnt] = Edge(f,t,w,head[f]);
	head[f] = cnt++;
}
void dijkstra(int s){
	for(int i = 1;i < maxn;i++)dis[i] = INF;
	dis[s] = 0;
	priority_queue<node,vector<node>,greater<node> >pq;
	pq.push({0,s});
	while(!pq.empty()){
		int u = pq.top().second;
		pq.pop();
		if(vis[u])continue;
		vis[u] = 1;
		for(int i = head[u];~i;i = edge[i].next){
			int v = edge[i].t;
			ll w = edge[i].w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				if(!vis[v]){
					pq.push({dis[v],v});
				}
			}
		}
	}
}
void add(int f,int t,int w){
	addedge(f,t,w);
	addedge(t,f,w);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(head,-1,sizeof(head));
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int f,t,w;
		cin >> f >> t >> w;
		//+0:ori
		//+N:sub first
		//+2*N:sub -> add
		//+3*N:add first
		//+4*N:add -> sub
		add(f,t,w);
		add(f+N,t+N,w);
		add(f+2*N,t+2*N,w);
		add(f+3*N,t+3*N,w);
		add(f+4*N,t+4*N,w);
		addedge(f,t+N,0);//sub
		addedge(t,f+N,0);
		addedge(f+N,t+2*N,2*w);//add
		addedge(t+N,f+2*N,2*w);
		addedge(f,t+3*N,2*w);//add
		addedge(t,f+3*N,2*w);
		addedge(f+3*N,t+4*N,0);//sub
		addedge(t+3*N,f+4*N,0);
	}
	dijkstra(1);
	for(int i = 2;i <= n;i++){
		cout << min({dis[i+2*N],dis[i+4*N],dis[i]}) << " ";
	}
	return 0;
}

Posted on Edited on

单调队列

O(n)求 最大值-最小值 <= k的子序列个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int getNum(int target)
{
    if(nums.empty())
        return 0;
    deque<int> qmin;    //保存窗口内的最小值，递增  front保存最小的元素位置
    deque<int> qmax;    //保存窗口内的最大值，递减  front保存最大的元素位置
    int i = 0, j = 0;   //nums[i..j]表示数组的范围
    int res = 0;        //表示满足条件的子数组数量
    //依次找到以nums[0],nums[1]...nums[N - 1]作为第一元素的子数组中满足条件的数量有多少个，累加
    while(i < nums.size())
    {
        while(j < nums.size())   // j向右拓展，直到不满足条件
        {
            while(!qmin.empty() && nums[qmin.back()] >= nums[j]) // 更新qmin中最小值的index
                qmin.pop_back();
            qmin.push_back(j);
            while(!qmax.empty() && nums[qmax.back()] <= nums[j]) // 更新qmax中最大值的index
                qmax.pop_back();
            qmax.push_back(j);
            if(nums[qmax.front()] - nums[qmin.front()] > target) //如果出现不满足条件的，那么包含以nums[i]起始的窗口的所有子数组都不满足条件
                break;
            j++;
        }
        if(qmin.front() == i)  // 如果窗口为 0 ，直接弹出
            qmin.pop_front();
        if(qmax.front() == i)  // 如果窗口为 0 ，直接弹出
            qmax.pop_front();
        res += j - i;          //如果nums[i..j]满足条件，则其子数组都满足条件， 一共 (j - i)个子数组
        i++;                   //继续寻找以nums[i]为起始点的子数组
    }
    return res;
}

单调栈

求全为1的最大子矩形面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int cal() {
    ans = 0;
    stack<int> st;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= m + 1; j++) {
            if (st.empty() || s[j] >= s[st.top()]) {
                st.push(j);
            } else {
                int top;
                while (!st.empty() && s[j] < s[st.top()]) {
                    top = st.top();
                    st.pop();
                    int tmp = (j - top) * s[top];
                    ans = max(ans, tmp);
                }
                st.push(top);
                s[top] = s[j];
            }
        }
    }
    return ans;
}

基础

最长上升子序列

nlogn做法

二分

\(f[i]\)表示长度为\(i\)的最长上升子序列中, 最小的末尾数值. \(siz\)为最长上升子序列长度.

1
2
3
4
5
6
7
8
9
f[1] = raw[1];
int siz = 0;
for(int i = 2;i <= n;i++){
    if(f[siz] < raw[i])f[++siz] = raw[i];
    else{
        int idx = lower_bound(f+1,f+siz+1,raw[i]) - f;
        f[idx] = min(f[idx],raw[i]);
    }
}

悬线法

同样用来求最大子矩形问题, 时间复杂度\(O(nm)\)

设\(l[x][y],r[x][y],u[x][y]\)为点\((x,y)\)可向左/右/上移动的最大距离. (其中向上扩展的最大距离即为"悬线"长度)

求出以上距离后, 再令\(L[x][y],R[x][y]\)为\((x,y)\)的悬线可以向左/右扩展的最大距离. 有: \[ L[x][y] = \begin{cases} \min(l[x-1][y],L[x][y]) & (x-1,y)合法\\ l[x][y] & (x-1,y)非法 \end{cases} \] 再统计\(\max(u[x][y] \cdot (L[x][y] + R[x][y] - 1))\)即为答案.

状压dp

TSP问题

(变体):给出一个带权完全无向图, 求恰好经过每一点的最短简单路径

1
2
3
4
5
6
7
8
9
10
11
12
int f[1<<20][20];
memset(f,0x3f3f3f3f,sizeof(f));
for(int i = 1;i <= k;i++)f[1<<(i-1)][i] = 1;
for(int S = 1;S < (1<<k);S++){
    for(int i = 1;i <= k;i++)if(S&(1<<(i-1))){
        for(int j = 1;j <= k;j++)if(j != i and S&(1<<(j-1))){
            f[S][i] = min(f[S][i],f[S ^ (1<<(i-1))][j] + dis[i][j]);
        }
    }
}
ll ans = INF;
for(int i = 1;i <= k;i++)ans = min(ans,f[(1<<k)-1][i]);

求无向图简单环个数

设\(f[S][i]\)表示状态为\(S\), 终点是\((1<<i)\), 起点是\(lowbit(S)\)的链的个数:

由于是无向图, 需要减去边的个数后除以2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int ans = 0;
for(int i = 0;i < n;i++)f[(1<<i)][i] = 1;
for(int S = 1;S < (1<<n);S++){
	for(int u = 0;u < n;u++)if((S >> u) & 1){
		for(int v:G[u]){
			int l = lowbit(S);
			if((1<<v) < l)continue;
			if((1<<v) > l and !((S >> v) & 1)){
				f[S | (1<<v)][v] += f[S][u];
			}
			else if((1<<v) == l)ans += f[S][u];
		}
	}
}
ans -= m;
cout << ans / 2;

数位dp

感觉这个神秘板子部分就数位dp有用啊?

例题1

定义一个正整数的价值是把这个数的十进制写出来之后，最长的等差子串的长度。

求\([l,r]\)范围内数字价值的总和。

板子来源

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m,len,a[20];
ll l,r,dp[20][15][25][25][20];
ll dfs(int pos,int pre,ll st,ll sum,int d,int lead,int limit){
	//pos搜到的位置
	//pre前一位数
	//st当前公差最大差值
	//sum整个数字的最大价值
	//d公差
	//lead判断是否有前导0
	//limit判断是否有最高位限制
	if(pos>len) return sum;//dp结束 
	//记录状态（计划搜索）
	//注意d有负数，最小可以到-9，所以记录时数组下标是d+10 
	if((dp[pos][pre][st][sum][d+10]!=-1&&(!limit)&&(!lead))) return dp[pos][pre][st][sum][d+10]; 
	ll ret=0;
	int res=limit?a[len-pos+1]:9;//最高位最大值 
	for(int i=0;i<=res;i++){
		//有前导0且这位也是前导0，一切不变只有位数变化 
		if((!i)&&lead) ret+=dfs(pos+1,0,0,0,-38,1,limit&&(i==res));
		//有前导0但这位不是前导0（这位是数字的最高位）开始有前一位，一个数形成等差数列 
		else if(i&&lead) ret+=dfs(pos+1,i,1,1,-38,0,limit&&(i==res));
		//之前刚搜到1位还没有共差，两位数形成等差数列，记录共差 
		else if(d<-9) ret+=dfs(pos+1,i,2ll,2ll,i-pre,0,limit&&(i==res));
		//搜到2位以后，共差若与前两位相同当前等差数列长度增加，若公差变化则更新整个数字的最大价值，等差数列长度又变为2 
		else if(d>=-9) ret+=dfs(pos+1,i,(i-pre==d)?st+1:2,max(sum,(i-pre==d)?st+1:2),(i-pre==d)?d:i-pre,0,limit&&(i==res));
	}
	//没有前导0和最高限制时可以直接记录当前dp值以便下次搜到同样的情况可以直接使用。 
	return (!limit&&!lead)?dp[pos][pre][st][sum][d+10]=ret:ret;
}
ll part(ll x){
	len=0;
	while(x) a[++len]=x%10,x/=10;
	memset(dp,-1,sizeof dp);
	return dfs(1,0,0,0,-38,1,1);//-38是随便赋的其实赋成-10就行了…… 
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld",&l,&r);
		//l是0的时候要特别注意！
	    printf("%lld\n",l?(part(r)-part(l-1)):(part(r)-part(l)+1));
	}
	return 0;
}

例题2

求不含前导零且相邻两个数字之差至少为\(2\)的正整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[15][15],ans;//dp[i][j]表示搜到第i位，前一位是j，的！limit方案totnum；
int a[15],len;
long long L,R;
ll dfs(int pos,int pre,int st,int limit)//pos当前位置,pre前一位数,st判断前面是否全是0,limit最高位限制 
{
	if(pos>len) return 1;//搜完了 
	if(!limit&&dp[pos][pre]!=-1) return dp[pos][pre];//没有最高位限制，已经搜过了
	ll ret=0;
	int res=limit?a[len-pos+1]:9;//当前位最大数字 
	for(int i=0;i<=res;i++)//从0枚举到最大数字 
	{
		if(abs(i-pre)<2) continue;//不符合题意，继续 
		if(st&&i==0) ret+=dfs(pos+1,-2,1,limit&&i==res);//如果有前导0，下一位随意 
		else ret+=dfs(pos+1,i,0,limit&&i==res);//如果没有前导0，继续按部就班地搜 
	}
	if(!limit&&!st) dp[pos][pre]=ret;//没有最高位限制且没有前导0时记录结果 
	return ret;
}
void part(ll x)
{
	len=0;
	while(x) a[++len]=x%10,x/=10;
	memset(dp,-1,sizeof dp);
	ans=dfs(1,-2,1,1);
}
int main()
{
    scanf("%lld%lld",&L,&R);
    part(L-1);ll minn=ans;
	part(R);  ll maxx=ans;
	printf("%lld",maxx-minn);
	return 0;
}

优化

斜率优化

维护\(y_i = k_i x + b_i\)的最小值. update(\(k,b\))需要保证斜率\(k\)单调递减. 其他情况自己推一下即可.

原理如下图. 插入时, line存构成当前下凸壳的直线, point[i]代表直线line[i]和line[i-1]的交点横坐标. 新加入一条直线(\(l_3)\)时, 设\(l_3\)和\(l_2\)交于\(B\), \(l_2\)和\(l_1\)交于\(A\). 若\(B.x < A.x\)则显然\(l_2\)不再组成下凸壳, 将其删去. 使用单调栈维护这一过程即可. 查询时在point上二分即可找到对应直线.

image-20220824102152715

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
const ll INF = 1e18;//
int sgn(int x){return (x > 0) - (x < 0);}
struct Frac{
	int u,d;
	Frac(int a,int b){
		ll sg = sgn(a) * sgn(b);
		if(a < 0)a = -a;
		if(b < 0)b = -b;
		//ll g = __gcd(a,b);
		//if(g > 1)a /= g,b /= g;
		u = sg * a,d = b;
	}
	bool operator < (const Frac & x) const{
		return (__int128)u * x.d < (__int128)d * x.u; 
	}
	bool operator <= (const Frac & x) const{
		return (__int128)u * x.d <= (__int128)d * x.u; 
	}
	bool operator == (const Frac & x) const{
		return u == x.u and d == x.d;
	}
};
struct Line{
	int k,b;
	Line(int k = 0,int b = 0):k(k),b(b){}
	int operator () (int x){
		return k * x + b;
	}
	Frac operator ^ (const Line & B)const{//return intersection.x
		return {B.b - b,k - B.k};
	}
};
vector<Line>line;
vector<Frac>inter;//intersector.x
void update(int k,int b){
	Frac x = {-INF,1};
	Line cur = Line(k,b);
	while(line.size() and (x = line.back() ^ cur) <= inter.back()){
		line.pop_back(),inter.pop_back();
	}
	line.push_back(cur);
	inter.push_back(x);
}
int query(int x){
	Frac v = {x,1};
	int idx = upper_bound(ALL(inter),v) - inter.begin() - 1;
	return line[idx](x);
}

Posted on Edited on In

大整数

1
2
比较大小: a.compareTo(b): 小于返回-1,等于返回0,大于返回1
int/long转换: BigIntger a = BigInteger.valueOf(114514);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
//来自https://blog.csdn.net/dlx_handsome/article/details/102529307
import java.util.*;
import java.math.BigInteger;
import java.math.*;
public class Main{
    public static void main(String[] args) {
    	//随便打的两个数,不过用生成随机大整数不是更香嘛
    	BigInteger number1=new BigInteger("347238462384523623645237465237415234165234615246742354");
    	BigInteger number2=new BigInteger("42673547263541874637462394142837645");
    	//返回一个BigInteger，其值为该BigInteger的绝对值。
    	System.out.println("abs():"+number1.abs().toString());
    	//返回值为BigInteger (this / val)。
    	System.out.println("divide():"+number1.divide(number2));
    	//返回值为的BigInteger (this % val)。
    	System.out.println("remainder():"+number1.remainder(number2));
    	//返回值为的BigInteger (this + val)。
    	System.out.println("add():"+number1.add(number2).toString());
    	//返回值为的BigInteger (this << n)。
    	System.out.println("shiftLeft():"+number1.shiftLeft(1));
    	//返回值为的BigInteger (this >> n)。
    	System.out.println("shiftRight():"+number1.shiftRight(1));
    	//返回此BigInteger的signum函数 返回-1,0,1作为BigInteger的符号
    	System.out.println("signum():"+number1.signum());
    	//返回此BigInteger的整数平方根。
    	System.out.println("sqrt():"+number1.sqrt());
    	//返回值为的BigInteger (this & val)。
    	System.out.println("and():"+number1.and(number2));
    	//返回值为的BigInteger (this & ~val)。
    	System.out.println("andNot():"+number1.andNot(number2));
    	//返回此BigInteger的二进制补码表示形式中不同于其符号位的位数.
    	//此方法在此BigInteger，从它的符号位不同的补码表示返回的比特数
    	System.out.println("bitCount():"+number1.bitCount());
    	//	返回此BigInteger的最小2补码表示形式中的位数，不包括符号位。
    	System.out.println("bitLength():"+number1.bitLength());
    	//将其转换BigInteger为byte，以检查是否丢失了信息。如果超出了,会丢出一个ArithmeticException异常
    	//System.out.println("byteValueExact():"+number1.byteValueExact());
    	//返回一个BigInteger，其值等于该BigInteger，并且清除了指定的位。
    	System.out.println("clearBit:"+number2.clearBit(0));
    	//将此BigInteger与指定的BigInteger进行比较。
    	System.out.println("compareTo():"+number1.compareTo(number2));
    	
    	//返回两个BigIntegers组成的数组，其中包含(this / val) 后跟(this % val)。
    	System.out.println("divideAndRemainder():"+Arrays.toString(number1.divideAndRemainder(number2)));
    	//将此BigInteger转换为double。
    	System.out.println("doubleValue():"+number1.doubleValue());
    	//将此BigInteger转换为float。
    	System.out.println("floatValue():"+number1.floatValue());
//    	返回此BigInteger和的最大值val。
    	System.out.println("max():"+number1.max(number2));
    	//返回此BigInteger和的最小值val。
    	System.out.println("min():"+number1.min(number2));
    	//返回值为的BigInteger (this mod m)。
    	System.out.println("mod():"+number1.mod(number2));
    	//返回值为(this-1 的BigInteger mod m)。
    	System.out.println("modInverse():"+number1.modInverse(number2));
    	//返回值为的BigInteger 。(thisexponent mod m)
    	System.out.println("modPow():"+number1.modPow(BigInteger.valueOf(1), number2));
    	//返回值为的BigInteger (this * val)。
    	System.out.println("multiply():"+number1.multiply(number2));
    	//返回值为的BigInteger (-this)。 
    	System.out.println("negate():"+number1.negate());
    	//将此BigInteger与指定的Object比较是否相等。
    	System.out.println("equals()就不说了,大家都明白....");
    	//返回一个BigInteger，其值等于该BigInteger的指定位被翻转。
    	System.out.println("flipBit():"+number1.flipBit(1));  	
    	//返回一个BigInteger，其值是abs(this)和的最大公约数 abs(val)。
    	System.out.println("gcd():"+number1.gcd(number2));
    	//返回此BigInteger中最右边（最低位）的一位的索引（最右边一位的右边的零位数）。
    	System.out.println("getLowestSetBit():"+number1.getLowestSetBit());
    	//返回此BigInteger的哈希码。
    	System.out.println("hashCode():"+number1.hashCode());
    	//将此BigInteger转换为int。
    	System.out.println("intValue():"+number1.intValue());
    	//	将此转换BigInteger为int，以检查是否丢失了信息。
    	//System.out.println("intValueExact():"+number1.intValueExact());
    	//true如果此BigInteger可能是质数，false则返回， 如果它绝对是复合的。
    	System.out.println("isProbablePrime():"+number1.isProbablePrime(10));
    	//将此BigInteger转换为long。
    	System.out.println("longValue():"+number1.longValue());
    	//将其转换BigInteger为long，以检查是否丢失了信息。
    	//System.out.println("longValueExact()"+number1.longValueExact());
    	//将其转换BigInteger为short，以检查是否丢失了信息。
    	//System.out.println("shortValueExact"+number1.shortValueExact());
    	
    	//返回大于此BigInteger可能是质数的第一个整数。
    	System.out.println("nextProbablePrime():"+number1.nextProbablePrime());
    	//返回值为的BigInteger (~this)。
    	System.out.println("not():"+number1.not());
    	//返回值为的BigInteger (this | val)。
    	System.out.println("or():"+number1.or(number2));
    	//返回值为的BigInteger 。(thisexponent)
    	System.out.println("pow():"+number1.pow(2));
    	//返回带有指定bitLength的正BigInteger（可能是素数）。
    	System.out.println("probablePrime():"+number1.probablePrime(10, new Random(10)));

    

    	//返回一个BigInteger，其值与此指定位设置的BigInteger等效。
    	System.out.println("setBit():"+number1.setBit(5));
    	
    	//分别返回包含整数平方根两个BigInteger的平方根 s的this和它的其余部分this - s*s。
    	BigInteger[] arr1=number1.sqrtAndRemainder();
    	System.out.println(arr1[0]+" "+arr1[1]);
    	//返回值为的BigInteger (this - val)。    	
    	System.out.println("subtract():"+number1.subtract(number2));
    	//	true仅当设置了指定位时返回。
    	System.out.println("testBit():"+number1.testBit(1));
    	//	返回一个字节数组，其中包含此BigInteger的二进制补码表示形式
    	System.out.println("toByteArray():"+Arrays.toString(number1.toByteArray()));
    	//返回此BigInteger的十进制String表示形式。
    	System.out.println("toString()不多说了....");
    	//以给定的基数返回此BigInteger的String表示形式。
    	//返回此BigInteger在给定的基数的字符串表示形式。如果基数是从Character.MIN_RADIX到Character.MAX_RADIX包容的范围内，它会默认为10(因为Integer.toString的情况下)。注释链接：
    	https://www.yiibai.com/java/math/biginteger_tostring_radix.html
		//说白了就是修改进制...
    	System.out.println("toString(int radix):"+number1.toString(10));
    	//返回一个BigInteger，其值等于指定的long。
    	System.out.println("valueOf():"+BigInteger.valueOf(8));
    	//返回值为的BigInteger (this ^ val)
    	System.out.println("xor(BigInteger val):"+number1.xor(number2));
    	
    }
}

使用例(国王游戏)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;
import java.math.*;
class Node implements Comparable <Node>{
    public BigInteger a,b,w;
    Node(long A,long B){
        a = BigInteger.valueOf(A);
        b = BigInteger.valueOf(B);
        w = a.multiply(b);
    }
    public int compareTo(Node X){
        return w.compareTo(X.w);
    }
}
class Main{
    static int maxn = (int)1e5+10;
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        Node [] node = new Node[maxn];
        int n = sc.nextInt();
        for(int i = 0;i <= n;i++){
            long a,b;
            a = sc.nextLong();b = sc.nextLong();
            node[i] = new Node(a,b);
        }
        Arrays.sort(node,1,n+1);
        BigInteger ans = new BigInteger("-1");
        BigInteger pre = node[0].a;
        for(int i = 1;i <= n;i++){
            ans = ans.max(pre.divide(node[i].b));
            pre = pre.multiply(node[i].a);
        }
        System.out.println(ans);
    }
}

\[ \frac{1}{2} \cdot (-4)^n + \frac{1}{4}\cdot16^n \]

Posted on In

题意

给出\(n\)个字符串, 将字符串按顺序拼接. 拼接时删除后面字符串的前缀与前面字符串的后缀中的最长相同部分.

例如sample与please拼接成为samplease

\(1 \leq n \leq 10^5\), \(\sum|s_i| \leq 10^6\)

题解

设将\(u\)和\(v\)拼接在一起, 用KMP求出\(s = v|u\)(|是任意分隔符)的失配数组\(next[]\).由于失配数组代表前后缀的最长长度, \(next[|s|]\)即为\(v\)的前缀与\(u\)的后缀相同部分的最长长度.

注意到这个最长长度不会超过\(|v|\), 因此我们只需把\(u\)的最后\(|v|\)个字符接到分隔符后. 时间复杂度\(O(\sum|s_i|)\)

赛时十分傻逼地忘了用分隔符把\(u,v\)分隔开, 疯狂WA到怀疑人生...顺便吐槽一句这个数据真的弱

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//我  是  傻  逼
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
int Next[4000010];
void getFail(string & P){
	for(int i = 0;i <= (int)P.size();i++)Next[i] = 0;
	int p_size = P.size();
	Next[0] = Next[1] = 0;
	for(int i = 1;i < p_size;i++){
		int j = Next[i];
		while(j and P[i] != P[j])j = Next[j];
		Next[i+1] = (P[j] == P[i]?j+1:0);
	}
}
string process(string & u,string & v){
	string x = v;
	x += '|';
	for(int i = max(0,(int)(u.size() - v.size()));i < (int)u.size();i++)x += u[i];
	getFail(x);
	string tans = "";
	for(int i = Next[x.size()];i < (int)v.size();i++)tans += v[i];
	return tans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	string ans = "";
	string u,v;
	if(n == 1){
		cin >> u;
		cout << u;
		return 0;
	}
	cin >> u >> v;
	ans = u + process(u,v);
	for(int i = 3;i <= n;i++){
		cin >> v;
		ans += process(ans,v);
	}
	cout << ans;
	return 0;
}

Posted on In

小清新构造题

题意

交互题.

有一个长度为\(n\)的数列\(\{a_i\}\), 满足\(a_i \in [0,n-1], n \in [4,2^{16}], n = 2^k\)

你可以进行最多\(n+1\)次询问, 询问分三种:

AND i j 返回\(a_i \& a_j\)的值

OR i j 返回\(a_i | a_j\)的值

XOR i j 返回\(a_i \oplus a_j\)的值

均需满足\(1 \leq i,j \leq n\)且\(i \ne j\)

当确定答案后, 你需要输出!然后在同一行内输出这个数组.

题解

首先一个显而易见的结论: 询问\(a_1\)与\(a_2...a_n\)的异或(共\(n-1\)次询问), 再在两次询问内求出\(a_1\)的值就能还原整个数组. 问题转化为如何求出\(a_1\),

因为数列长度为\(n\)值域为\([0,n-1]\), 由鸽巢原理可得:

  1. 数列中至少有两个数字相同

    分为两种情况:

    1. \(a_1\)与其他至少一个数字相同.

      表现为至少一个异或询问\(a_1 \oplus a_i\)的答案为\(0\). 一次AND 1 i询问即可求出\(a_1\)的值.

    2. \(a_i\)与\(a_j\)相同(\(i,j \ne 1\)).

      此时至少两个异或询问的答案相等(\(a_1 \oplus a_i = a_1 \oplus a_j\)), 即\(a_i = a_j\). 通过一次AND i j可求出\(a_i\)的值, 再由\(a_1 \oplus a_i \oplus a_i = a_1\)求出\(a_1\)

  2. 数列中全部数字均不相同.

    由于\(n = 2^k\)且\(n \ge 4\), \(k\)位二进制的每一种情况均会出现, 故必存在\(a_1 \oplus a_i = 1\). 显然\(a_1\)与\(a_i\)只有最后一位不同. 这时一次AND 1 i可获得\(a_1\)除了最后一位外的信息. 同理存在\(a_1 \oplus a_j = 2\), AND 1 j可获得\(a_1\)最后一位的信息. 两者综合起来即可求出\(a_1\)

以上无论何种情况, 询问次数都不超过\(n+1\)

时间复杂度\(O(n\log n)\) (因为有一次不必要的排序来去重)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//E
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define endl '\n'
const int maxn = 2e5+10;
int Xor[maxn],ans[maxn];
struct Node{
	int w,idx;
	Node(int w = 0,int idx = 0):w(w),idx(idx){}
	bool operator < (const Node & x) const{
		return w < x.w;
	}
}node[maxn];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 2;i <= n;i++){
		cout << "XOR 1 " << i << endl;
		int x;
		cin >> x;
		Xor[i] = x;
		node[i] = Node(x,i);
	}
	sort(node+2,node+n+1);
	int idx = 0;
	for(int i = 3;i <= n;i++)if(node[i].w == node[i-1].w)idx = i;
	if(!node[2].w){
		cout << "AND 1 " << node[2].idx << endl;
		int x;
		cin >> x;
		ans[1] = x;
	}
	else if(idx){
		int l = node[idx].idx,r = node[idx-1].idx;
		cout << "AND " << l << " " << r << endl;
		int x;
		cin >> x;
		ans[1] = Xor[l]^x;
	}
	else{
		int bit_0 = 0,bit_1 = 0;
		for(int i = 2;i <= n;i++){
			if(Xor[i] == 1){
				cout << "AND 1 " << i << endl;
				int x;
				cin >> x;
				bit_0 = x;
			}
			else if(Xor[i] == 2){
				cout << "AND 1 " << i << endl;
				int x;
				cin >> x;
				bit_1 = x;
			}
		}
		if(bit_0 & 1)bit_0--;
		if(bit_1 & 1)bit_0++;
		ans[1] = bit_0;
	}
	for(int i = 2;i <= n;i++)ans[i] = Xor[i]^ans[1];
	cout << "! ";
	for(int i = 1;i <= n;i++)cout << ans[i] << " ";
	cout << endl;
	return 0;
}