可持久化线段树学习笔记 (二)

简介

本期主要简单介绍可持久化权值线段树 (即主席树).

前置知识

1. 线段树
2. 权值线段树
3. 普通的可持久化线段树

可持久化权值线段树 (主席树)

主席树是一种把数字的值或离散化后的位置当作左右端点 (即权值线段树) 的可持久化权值线段树.

这里我们通过一道模板题 静态区间第k小 来讲解. 这道题我们可以以权值线段树为单个树建立可持久化线段树. 我们可以运用前缀和的思想, 对于 \( root_i \) 的节点 \( a_{j,k} \) 表示 1 到 i 的数中大小在离散化后的数组中 \( [k,k] \) 的数的个数. 这样我们可以在 \( \log n \) 的时间里求出一个区间的第 k 小.

code

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

const int MAXN = 200010;

struct node{
	int l,r,cnt;
}tree[15000000];
int root[MAXN];
int endd = 0;
int num[MAXN];
int bucket[MAXN];
int siz;
int n, m;
int clone(int id){
	tree[++endd] = tree[id];
	return endd;
}
void buildtree(int p, int l, int r){
	if(l == r) return;
	tree[p].l = ++endd;
	tree[p].r = ++endd;
	int m = (l + r) >> 1;
	buildtree(tree[p].l, l, m);
	buildtree(tree[p].r, m + 1, r);
	return;
}
int add(int p, int l, int r, int w){
	p = clone(p);
	++tree[p].cnt;
	if(l == r) return p;
	int m = (l + r) >> 1;
	if(w <= bucket[m]){
		tree[p].l = add(tree[p].l, l, m, w);
	}
	else{
		tree[p].r = add(tree[p].r, m + 1, r, w);
	}
	return p;
}
int ask(int p1, int p2,int l,int r, int k){
	if(l == r) return bucket[l];
	int m = (l + r) >> 1;
	if(k <= tree[tree[p2].l].cnt - tree[tree[p1].l].cnt) return ask(tree[p1].l, tree[p2].l, l, m, k);
	else return ask(tree[p1].r, tree[p2].r, m + 1, r, k - (tree[tree[p2].l].cnt - tree[tree[p1].l].cnt));
}
int main() {
	n = read(), m = read();
	rep(i,1,n){
		num[i] = read();
		bucket[i] = num[i];
	}
	sort(bucket + 1, bucket + 1 + n);
	rep(i,1,n){
		if(siz == 0 || bucket[i] > bucket[siz])
			bucket[++siz] = bucket[i];
		else 
			bucket[siz] = bucket[i];
	}
	buildtree(0,1,siz);
	rep(i,1,n){
		root[i] = add(root[i - 1], 1, siz, num[i]);
	}
	rep(i,1,m){
		int l = read(), r = read(), k = read();
		printf("%d\n", ask(root[l - 1], root[r], 1, siz, k));
	}
	return 0;
}

可持久化线段树学习笔记 (一)

扯淡

新赛季在即, 便在高二放弃了四晚回家博客 (希望作业少一点吧) , 可能是OI生涯的最后一年了.

简介

本期主要简单介绍普通的可持久化线段树 (如可持久化数组).

前置知识

1. 线段树
2. 权值线段树

普通可持久化线段树 (可持久化数组)

众所周知, 线段树是一种十分优秀的区间修改区间查询的数据结构. 但是线段树有一个弊端就是不可持久化, 即无法回到某一历史版本 (如本题), 于是可持久化线段树应运而生. 简单来说, 可持久化线段树在每次操作时都构建了一棵新的线段树. 但是很显然如果每次都建立一棵完整的线段树, 无论是空间复杂度还是时间复杂度都将难以接受. 于是我们发现每次的修改只会改变根节点到叶子节点的 logn 个节点. 于是可持久化线段树也依照如此每次只修改 logn 个节点来使空间复杂度和时间复杂度都达到较优的水平.

不同于普通线段树, 为了更加灵活地添加节点, 可持久化线段树使用结构体来保存每一个节点, 每个节点保存当前节点的信息以及左右儿子的节点编号. 除此以外还需要建立 root 数组来记录每棵树的根节点, 每次修改只需从上一个树的根节点向下添加需要更新的节点, 并将新的根节点加入 root 数组. 查询时只需要从某一历史版本的根节点开始按照普通线段树的方式进行查询.

code

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

const int MAXN = 1000010;
const int MAXM = 1000010;

int n, m, endd;
struct node {
	int l,r,w;
};
int root[MAXM];
int num[MAXN];
struct node tree[25000000];
int clone(int p){
	tree[++endd] = tree[p];
	return endd;
}
void buildtree(int p,int l,int r){
	if(l == r){
		tree[p].w = num[l];
		return;
	}
	int m = (l + r) >> 1;
	tree[p].l = ++endd;
	tree[p].r = ++endd;
	buildtree(tree[p].l, l, m);
	buildtree(tree[p].r, m + 1, r);
	return;
}
int add(int p, int l, int r, int pp, int w){
	p = clone(p);
	if(l == r) {
		tree[p].w = w;
		return p;
	}
	int m = (l + r) >> 1;
	if(pp >= l && pp <= m) tree[p].l = add(tree[p].l, l, m, pp, w);
	else tree[p].r = add(tree[p].r, m + 1, r, pp, w);
	return p;
}
int ask(int p, int l, int r, int pp){
	if(l == r) return tree[p].w;
	int m = (l + r) >> 1;
	if(pp >= l && pp <= m) return ask(tree[p].l, l, m, pp);
	else return ask(tree[p].r, m + 1, r, pp);
}
int main() {
	n = read(), m = read();
	rep(i,1,n){
		num[i] = read();
	}
	buildtree(0,1,n);
	rep(i,1,m){
		int vi = read(), op = read(), p = read();
		if(op == 1){
			int x = read();
			root[i] = add(root[vi],1,n,p,x);
		}
		else{
			root[i] = root[vi];
			printf("%d\n", ask(root[vi], 1, n, p));
		}
	}
	return 0;
}

一些细节

1. 数组大小理论为 nlogn + mlogn , 实际代码中对于大部分题目都可以开 n*20 来防止溢出.
2. 修改节点复制后 p 要更新为新的节点编号.
3. 修改下传后要更新儿子节点的编号.

应用

刚才的例题中, 我们发现我们对非叶子节点的利用并不彻底, 只是简单的记录了左右端点. 实际上我们完全可以像线段树一样充分地利用每一个节点. 可持久化线段树的应用也不仅仅是在可持久化数组上. 我们发现在普通的线段树上可以 logn 的时间完成的操作, 在可持久化线段树上同样可以, 只是可持久化线段树支持历史版本的查询. 我们继续深究就会发现二者本质的不同在于维护的数据的类型数目不同. 普通线段树只是同时维护了左右端点以及节点 value , 而可持久化线段树除此以外多了一个类型即 root 数组. 在例题中是数组下标, 在别的题目中它可以有别的身份, 需要灵活地运用.

CF1481D AB Graph

题目

Your friend Salem is Warawreh's brother and only loves math and geometry problems. He has solved plenty of such problems, but according to Warawreh, in order to graduate from university he has to solve more graph problems. Since Salem is not good with graphs he asked your help with the following problem.


You are given a complete directed graph with n vertices without self-loops. In other words, you have n vertices and each pair of vertices u and v (u≠v) has both directed edges (u,v) and (v,u).

Every directed edge of the graph is labeled with a single character: either 'a' or 'b' (edges (u,v) and (v,u) may have different labels).

You are also given an integer m>0. You should find a path of length m such that the string obtained by writing out edges' labels when going along the path is a palindrome. The length of the path is the number of edges in it.

You can visit the same vertex and the same directed edge any number of times.

Input
The first line contains a single integer t (1≤t≤500) — the number of test cases.

The first line of each test case contains two integers n and m (2≤n≤1000; 1≤m≤105) — the number of vertices in the graph and desirable length of the palindrome.

Each of the next n lines contains n characters. The j-th character of the i-th line describes the character on the edge that is going from node i to node j.

Every character is either 'a' or 'b' if i≠j, or '*' if i=j, since the graph doesn't contain self-loops.

It's guaranteed that the sum of n over test cases doesn't exceed 1000 and the sum of m doesn't exceed 105.

Output
For each test case, if it is possible to find such path, print "YES" and the path itself as a sequence of m+1 integers: indices of vertices in the path in the appropriate order. If there are several valid paths, print any of them.

Otherwise, (if there is no answer) print "NO".

Example
inputCopy
5
3 1
*ba
b*b
ab*
3 3
*ba
b*b
ab*
3 4
*ba
b*b
ab*
4 6
*aaa
b*ba
ab*a
bba*
2 6
*a
b*
outputCopy
YES
1 2
YES
2 1 3 2
YES
1 3 1 3 1
YES
1 2 1 3 4 1 4
NO

思路

特判n=2；

n>2:找三个点（比如123点），一个方向上三边只有aab或aaa这种，然后分别讨论m%3==0||==1||==2。

==0：abaaba…

==1: baabaab…

==2: aabaa…

代码

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
124
125
126
127
128

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define frep(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
#define fdrep(i,a,b) for(int i=(a);i>(b);--i)
using namespace std;
ll read(){
	register ll a=0,b=1;
	register char c;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')b=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar()*b;
	}
	return a*b;
}
#define Qmin priority_queue<int,vector<int> ,less<int> >
#define Qmax priority_queue<int,vector<int> ,greater<int> >
int mylog(int a){
	int ans=0;
	if(a&0xffff0000){ans+=16;a>>=16;}
	if(a&0x0000ff00){ans+=8;a>>=8;}
	if(a&0x000000f0){ans+=4;a>>=4;}
	if(a&0x0000000c){ans+=2;a>>=2;}
	if(a&0x00000002){ans+=1;a>>=1;}
	return ans;
}
const int N=1e3;
int mapp[N+10][N+10];
int main(){
	int t=read();
	while(t--){
		int n=read(),m=read();
		rep(i,1,n){
			rep(j,1,n){
				if(i==j){
					char c;
					scanf("\n%c",&c);
				}
				else{
					char c;
					scanf("\n%c",&c);
					mapp[i][j]=(c=='a'?0:1);	
				}
			}
		}
		if(n==2){
			if(mapp[1][2]==mapp[2][1]){
				printf("YES\n");
				rep(i,1,m+1){
					printf("%d\n",(i&1)?1:2);
				}
			}
			else{
				if(m&1){
					printf("YES\n");
					rep(i,1,m+1){
						printf("%d\n",(i&1)?1:2);
					}
				}
				else{
					printf("NO\n");
				}
			}
		}
		else{
			printf("YES\n");
			int a,b,c;
			if(mapp[1][2]==mapp[2][3]){
				a=2;
				b=3;
				c=1;
			}
			else if(mapp[2][3]==mapp[3][1]){
				a=3;
				b=1;
				c=2;
			}
			else if(mapp[3][1]==mapp[1][2]){
				a=1;
				b=2;
				c=3;
			}
			if(m%3==0){
				while(m>0){
					printf("%d %d %d ",a,b,c);
					m-=3;
				}
				printf("%d\n",a);
			}
			else if(m%3==1){
				m-=1;
				printf("%d ",b);
				while(m>0){
					printf("%d %d %d ",c,a,b);
					m-=3;
				}
				printf("%d\n",c);
			}
			else{
				m-=2;
				printf("%d %d ",c,a);
				while(m>0){
					printf("%d %d %d ",b,c,a);
					m-=3;
				}
				printf("%d \n",b);
			}
		}
	}
	return 0;
}

NOIP2020 移球游戏

前言

此题位于t3位置，并且是noip第一次考构造题和special judge。考场上由于不会t2觉得t3更简单，并且常年在cf上打比赛觉得构造题十分熟悉而写了t3放弃t2。但由于不会使用spj导致代码漏洞百出（事实上自己写这个题spj非常简单）最后混了10分。其实考场上想出的思路也只能得40分。还是太菜了呀！

题目

题目链接

移球游戏

输入文件名：ball.in

输出文件名：ball.out

共 20 个测试点，每个测试点 5 分

每个测试点限时 1 秒，运行内存上限 512MB

小 C 正在玩一个移球游戏，他面前有 n + 1 根柱子，柱子从 1 ∼ n+1 编号，其中 1 号柱子、2 号柱子、…、n。n 号柱子上各有 m 个球，它们自底向上放置在柱子上，n+1 号柱子上初始时没有球。这 n×m 个球共有 n 种颜色，每种颜色的球各 m 个。

初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有限制。

小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。更具体地，将 xx 号柱子上的球移动到 y 号柱子上的要求为:

x 号柱子上至少有一个球;
y 号柱子上至多有 m−1m−1 个球;
只能将 x 号柱子最上方的球移到 y 号柱子的最上方。
小 C 的目标并不难完成，因此他决定给自己加加难度:在完成目标的基础上，使用的操作次数不能超过 820000。换句话说，小 C 需要使用至多 820000 次操作完成目标。

小 C 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种，你只需要给出任意一种，题目保证一定存在一个合法方案。

输入格式
输入文件名为 ball.in。

第一行两个用空格分隔的整数 n，m。分别表示球的颜色数、每种颜色球的个数。 接下来 n 行每行 m 个用单个空格分隔的整数，第 i 行的整数按自底向上的顺序依次给出了 i 号柱子上的球的颜色。

输出格式
输出文件名为 ball.out。

本题采用自定义校验器（special judge）评测。 你的输出的第一行应该仅包含单个整数 kk，表示你的方案的操作次数。你应保证 0 \leq k \leq 8200000≤k≤820000。

接下来 k 行每行你应输出两个用单个空格分隔的正整数 x,y，表示这次操作将 x 号柱子最上方的球移动到 y 号柱子最上方。你应保证 1 \leq x, y \leq n + 11≤x,y≤n+1 且 x \neq yx 

​    
 =y。

样例 1 输入
2 3
1 1 2
2 1 2
样例 1 输出
6
1 3
2 3
2 3
3 1
3 2
3 2

解法

40pts

每次将同种颜色的球移至一个柱子不断缩小问题。对于一个深度为\(m\)的球要想移到某个柱子只需要\(2m\)次（将他上方的m-1个球移走，将这个球移至一个柱子，将m-1个球移回来，再将这个球移至最终要放的目标柱）。平均下每个深度都有一个要移动的球，所以平均复杂度为\(O(nm^2)\)

code

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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define ll long long
#define ull unsigned long long
using namespace std;
int zhu[110][510];
int ci[510];
//int name[100];
int bz[820010][2];
int endd=0;
int n,m;
void print(int x,int y){
	bz[endd][0]=x;
	bz[endd++][1]=y;
	zhu[y][++zhu[y][0]]=zhu[x][zhu[x][0]--];
	return;
}
void mymove(int l,int d,int len,int zl){
	if(d==zhu[l][0]){
		print(l,len);
		return;
	}
	int i=1;
	for(;i<=len&&zhu[l][0]>=d;){
		if(i==l){
			++i;
			continue;
		}
		if(zhu[i][0]<m){
			print(l,i);
		}
		else{
			++i;
		}
	}
	if(i==len){
		if(l==1){
			print(len-1,l);
			print(len,len-1);
			i=len-1;
		}
		else{
			print(1,l);
			print(len,1);
			i=1;
		}
	}
	while(zhu[len][0]>0&&zhu[len][zhu[len][0]]!=zl){
		print(len,l);
	}
	print(i,len);
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		zhu[i][0]=m;
		for(int j=1;j<=m;++j){
			scanf("%d",&zhu[i][j]);
		}
	}
	n++;
	for(int i=0;i<n;++i){
		int len=n-i;
		if(len==2)break;
		int minp=zhu[1][zhu[1][0]];
		for(int j=1;j<len;++j){
			for(int k=zhu[j][0];k>=1;--k){
				if(zhu[j][k]==minp){
					int temp=zhu[j][0];
					mymove(j,k,len,minp);
					if(zhu[j][0]==temp)++k;
				}
			}
		}
		if(len>2){
			for(int j=1;j<len-1;){
				if(zhu[j][0]<m){
					print(len-1,j);
				}
				else{
					++j;
				}
			}
		}
	}
	printf("%d\n",endd);
	for(int i=0;i<endd;++i){
		printf("%d %d\n",bz[i][0],bz[i][1]);
	}
	return 0;
}

100pts

遇到这种题目正解一定要带一个log，只好往分治那方面想。所以可以把所有颜色一分两半，同类颜色在各自一半（并不要求同颜色连续）。

具体如何把颜色分类可用一个例子来说明。为方便描述，l表示左端点，r表示右端点，m表示中点这里用a表示要分类的柱子，b表示零时借用柱子，c表示空柱子。

1. b—a中的球的个数—>c
2. a—属于左边放b，否则放c—>b,c
3. b，c—原来在a的—>a
4. c—剩下的（原来是b的）—>b

现在我们有了r-l+1个相对有序的柱子，现在问题转化为如何将同色的一堆连续球放在一边。为方便表述z表示未完全分类的柱子左端点，同理y表示右端点。初始z=l，y=r

1. 若zy上属于左边的多，则利用空柱子几次反转使左边颜色在zy顶上。总之要把少的颜色放在顶上。假设这时左边颜色少。
2. z—左边颜色球—>c
3. y—左边颜色球—>c
4. z—剩下的且不超过y最大—y
5. —y
6. c——>z

这样y就缩小了，如此反复直至z==y-1==m

1. f(l,m) f(m+1,r)

这样问题就解决啦，复杂度大概为\(mnlog^n\)

code

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define frep(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
#define fdrep(i,a,b) for(int i=(a);i>(b);--i)
using namespace std;
int zhu[110][510];
int ci[510];
int bz[820010][2];
int name[60];
int endd=0;
int n,m;
int kong;
void print(int x,int y){
	zhu[name[y]][++zhu[name[y]][0]]=zhu[name[x]][zhu[name[x]][0]--];
	if(endd>0&&bz[endd-1][0]==name[y]&&bz[endd-1][1]==name[x]){
		--endd;
		return;
	}
	if(endd>0&&bz[endd-1][1]==name[x]){
		bz[endd-1][1]=y;
		return;
	}
	bz[endd][0]=name[x];
	bz[endd++][1]=name[y];
	return;
}
void mymove(int a,int b,int c,int l,int r){
	int con=0;
	rep(i,1,zhu[name[a]][0]){
		if(zhu[name[a]][i]>=l&&zhu[name[a]][i]<=r)++con;
	}
	rep(i,1,con){
		print(b,c);
	}
	drep(i,zhu[name[a]][0],1){
		if(zhu[name[a]][i]>=l&&zhu[name[a]][i]<=r)print(a,b);
		else print(a,c);
	}
	rep(i,1,con){
		print(b,a);
	}
	rep(i,1,m-con){
		print(c,a);
	}
	rep(i,1,con){
		print(c,b);
	}
	return;
}
void solve(int l,int r){
	if(l==r)return;
	int temp=(l==1)?2:1;
	int mm=(l+r)>>1;
	rep(p,l,r){
		if(p==temp)temp=1;
		mymove(p,temp,kong,l,mm);
	}
	int z=l,y=r;
	while(z<y){
		int con1=0,con2=0,con3=0,con4=0;
		rep(i,1,zhu[name[z]][0]){
			con1+=zhu[name[z]][i]<=mm?1:0;
			con2+=zhu[name[z]][i]<=mm?0:1;
		}
		rep(i,1,zhu[name[y]][0]){
			con3+=zhu[name[y]][i]<=mm?1:0;
			con4+=zhu[name[y]][i]<=mm?0:1;
		}
		if(con1+con3<con2+con4){
			if(zhu[name[z]][zhu[name[z]][0]]>mm){
				drep(i,zhu[name[z]][0],1){
					print(z,kong);
				}
				swap(name[z],name[kong]);
			}
			if(zhu[name[y]][zhu[name[y]][0]]>mm){
				drep(i,zhu[name[y]][0],1){
					print(y,kong);
				}
				swap(name[y],name[kong]);
			}
			while(zhu[name[z]][0]&&zhu[name[z]][zhu[name[z]][0]]<=mm)print(z,kong);
			while(zhu[name[y]][0]&&zhu[name[y]][zhu[name[y]][0]]<=mm)print(y,kong);
			while(zhu[name[z]][0]&&zhu[name[y]][0]<m)print(z,y);
			--y;
			while(zhu[name[kong]][0])print(kong,z);
		}
		else{
			if(zhu[name[z]][zhu[name[z]][0]]<=mm){
				drep(i,zhu[name[z]][0],1){
					print(z,kong);
				}
				swap(name[z],name[kong]);
			}
			if(zhu[name[y]][zhu[name[y]][0]]<=mm){
				drep(i,zhu[name[y]][0],1){
					print(y,kong);
				}
				swap(name[y],name[kong]);
			}
			while(zhu[name[z]][0]&&zhu[name[z]][zhu[name[z]][0]]>mm)print(z,kong);
			while(zhu[name[y]][0]&&zhu[name[y]][zhu[name[y]][0]]>mm)print(y,kong);
			while(zhu[name[y]][0]&&zhu[name[z]][0]<m)print(y,z);
			++z;
			while(zhu[name[kong]][0])print(kong,y);
		}
	}
	solve(l,mm);
	solve(mm+1,r);
	return;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		name[i]=i;
		zhu[i][0]=m;
		for(int j=1;j<=m;++j){
			scanf("%d",&zhu[i][j]);
		}
	}
	n++;
	kong=n;
	name[n]=n;
	solve(1,n-1);
	printf("%d\n",endd);
	for(int i=0;i<endd;++i){
		printf("%d %d\n",bz[i][0],bz[i][1]);
	}
	return 0;
}

P3977 [TJOI2015]棋盘

题目

题目描述

为了提高智商,ZJY去新世界旅游了。可是旅游过后的ZJY杯具的发现要打开通往原来世界的门,必须要解开门上面画的谜题。谜题是这样的:有个n行m列的棋盘,棋盘上可以放许多特殊的棋子。每个棋子的攻击范围是3行,p列。输入数据用一个3×p的矩阵给出了棋子攻击范围的模板,棋子被默认为模板中的第1行,第k列,则棋子能攻击到的位置是1,不能攻击到的位置是0。1≤p≤m,0≤k<p。输入数据保证第1行第k列的位置是1。打开门的密码就是,在要求棋子互相不能攻击到的前提下,摆放棋子的方案数。注意什么棋子都不摆放也算作一种可行方案。由于方案数可能很大,而密码为32位的二进制密码,所以ZJY仅需要知道方案数对2的32次方取余数的结果即可。

输入格式

输入数据的第一行为两个整数n和m,表示棋盘的大小。第二行为两个整数p和k,表示接下来的攻击范围模板的大小,以及棋子在模板中的位置。接下来三行,每行有P个数,表示攻击范围的模版。每个数字后有一个空格。

输出格式

输出数据仅有一行,一个整数,表示可行的方案数模2^32的余数。

输入输出样例

输入 #1

5 5
3 1
0 1 0
1 1 1
0 1 0

输出 #1

55447

说明/提示

数据范围

对于10%的pn，1 ≤ n ≤ 5，1 ≤ m ≤ 5

对于50%的pn，1 ≤ n ≤ 1000，1 ≤ m ≤ 6

对于100%的pn，1 ≤ n ≤ 1000000，1 ≤ m ≤ 6

解法

80stp：

普通状压dp，把每行情况存储，逐行转移。复杂度O($n*2^m$)。

100stp:

我们发现每行转移与行的位置无关，所以可以用矩阵快速幂加速。

代码

80stp：

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

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define ll long long
using namespace std;
int p, k;
int moban[3];
int end = 0;
ll dp[2][1 << 7];
int qk[1 << 7];
int gj[2][1 << 7];
vector<int> pr[1 << 7];
void inil(int js) {
    js = (1 << js);
    int now = 0;
    while (now < js) {
        bool flag = true;
        for (int i = 0; (now >> i) > 0; ++i) {
            if ((now >> i) & 1) {
                if (i < k && (((moban[1] >> (k - i)) & now) != 0)) {
                    flag = false;
                    break;
                } else if (((moban[1] << (i - k)) & now) != 0) {
                    flag = false;
                    break;
                }
            }
        }
        if (flag) {
            qk[end] = now;
            for (int i = 0; (now >> i) > 0; ++i) {
                if ((now >> i) & 1) {
                    if (i < k) {
                        gj[0][end] |= (moban[0] >> (k - i));
                        gj[1][end] |= (moban[2] >> (k - i));
                    } else {
                        gj[0][end] |= (moban[0] << (i - k));
                        gj[1][end] |= (moban[2] << (i - k));
                    }
                }
            }
            ++end;
        }
        ++now;
    }
    for (int i = 0; i < end; ++i) {
        for (int j = 0; j < end; ++j) {
            if ((gj[1][i] & qk[j]) == 0 && (gj[0][j] & qk[i]) == 0) {
                pr[j].push_back(i);
            }
        }
    }
    return;
}
ll mod = 1;
int main() {
    mod <<= 32;
    int n, m;
    scanf("%d%d", &n, &m);
    scanf("%d%d", &p, &k);
    k = p - k;
    --k;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < p; ++j) {
            moban[i] <<= 1;
            int a;
            scanf("%d", &a);
            moban[i] += a;
        }
    }
    moban[1] ^= (1 << k);
    inil(m);
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < end; ++j) {
            dp[i & 1][j] = 0;
            int size = pr[j].size();
            for (int k = 0; k < size; ++k) {
                dp[i & 1][j] += dp[(i - 1) & 1][pr[j][k]];
                dp[i & 1][j] %= mod;
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < end; ++i) {
        ans += dp[n & 1][i];
        ans %= mod;
    }
    printf("%lld", ans);
    return 0;
}

100stp:

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define ll long long
#define ull unsigned long long
using namespace std;
int p, k;
int moban[3];
int end = 0;
// ull dp[2][1<<7];
int qk[1 << 7];
int gj[2][1 << 7];  //上下攻击
vector<int> pr[1 << 7];
struct matrix {
    //矩阵
    ull num[1 << 7][1 << 7];
    void inil() { memset(num, 0, sizeof(num)); }
    void inil1() {
        for (int i = 0; i < (1 << 7); ++i) {
            num[i][i] = 1;
        }
    }
} yx;
ll mod = 1;
void inil(int js) {
    js = (1 << js);
    int now = 0;
    while (now < js) {
        bool flag = true;
        for (int i = 0; (now >> i) > 0; ++i) {
            if ((now >> i) & 1) {
                if (i < k && (((moban[1] >> (k - i)) & now) != 0)) {
                    flag = false;
                    break;
                } else if (((moban[1] << (i - k)) & now) != 0) {
                    flag = false;
                    break;
                }
            }
        }
        if (flag) {
            qk[end] = now;
            for (int i = 0; (now >> i) > 0; ++i) {
                if ((now >> i) & 1) {
                    if (i < k) {
                        gj[0][end] |= (moban[0] >> (k - i));
                        gj[1][end] |= (moban[2] >> (k - i));
                    } else {
                        gj[0][end] |= (moban[0] << (i - k));
                        gj[1][end] |= (moban[2] << (i - k));
                    }
                }
            }
            ++end;
        }
        ++now;
    }
    for (int i = 0; i < end; ++i) {
        for (int j = 0; j < end; ++j) {
            if ((gj[1][i] & qk[j]) == 0 && (gj[0][j] & qk[i]) == 0) {
                //				pr[j].push_back(i);
                yx.num[j][i] = 1;
            }
        }
    }
    return;
}
struct matrix mul(struct matrix a, struct matrix b) {
    struct matrix ans;
    ans.inil();
    for (int i = 0; i <= end; ++i) {
        for (int j = 0; j <= end; ++j) {
            for (int k = 0; k <= end; ++k) {
                a.num[i][k] %= mod;
                b.num[k][j] %= mod;
                ull temp = a.num[i][k] * b.num[k][j];
                temp %= mod;
                if (temp < 0) {
                    cout << a.num[i][k] << " " << b.num[k][j] << endl;
                }
                ans.num[i][j] += temp;
                ans.num[i][j] %= mod;
            }
        }
    }
    return ans;
}
struct matrix jzksm(struct matrix a, int n) {
    //矩阵快速幂
    if (n == 1)
        return a;
    struct matrix ans;
    ans.inil1();
    while (n != 0) {
        if (n & 1)
            ans = mul(ans, a);
        n >>= 1;
        a = mul(a, a);
    }
    return ans;
}
int main() {
    yx.inil();
    mod <<= 32;
    int n, m;
    scanf("%d%d", &n, &m);
    scanf("%d%d", &p, &k);
    k = p - k;
    --k;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < p; ++j) {
            moban[i] <<= 1;
            int a;
            scanf("%d", &a);
            moban[i] += a;
        }
    }
    moban[1] ^= (1 << k);
    inil(m);
    yx = jzksm(yx, n);
    //	dp[0][0]=1;
    //	for(int i=1;i<=n;++i){
    //		for(int j=0;j<end;++j){
    //			dp[i&1][j]=0;
    //			int size=pr[j].size();
    //			for(int k=0;k<size;++k){
    //				dp[i&1][j]+=dp[(i-1)&1][pr[j][k]];
    //				dp[i&1][j]%=mod;
    //			}
    //		}
    //	}
    ull ans = 0;
    for (int i = 0; i < end; ++i) {
        ans += yx.num[i][0];
        ans %= mod;
    }
    printf("%lld", ans);
    return 0;
}

CF1399D Binary-String-To-Subsequences

题目

D. Binary String To Subsequences
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given a binary string s consisting of n zeros and ones.

Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like "010101 ..." or "101010 ..." (i.e. the subsequence should not contain two adjacent zeros or ones).

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of "1011101" are "0", "1", "11111", "0111", "101", "1001", but not "000", "101010" and "11100".

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤2⋅104) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1≤n≤2⋅105) — the length of s. The second line of the test case contains n characters '0' and '1' — the string s.

It is guaranteed that the sum of n does not exceed 2⋅105 (∑n≤2⋅105).

Output
For each test case, print the answer: in the first line print one integer k (1≤k≤n) — the minimum number of subsequences you can divide the string s to. In the second line print n integers a1,a2,…,an (1≤ai≤k), where ai is the number of subsequence the i-th character of s belongs to.

If there are several answers, you can print any.

Example
inputCopy
4
4
0011
6
111111
5
10101
8
01010000
outputCopy
2
1 2 2 1 
6
1 2 3 4 5 6 
1
1 1 1 1 1 
4
1 1 1 1 1 2 3 4 

翻译

百度翻译结果.%0A%0ARecall%20that%20a%20subsequence%20is%20a%20sequence%20that%20can%20be%20derived%20from%20the%20given%20sequence%20by%20deleting%20zero%20or%20more%20elements%20without%20changing%20the%20order%20of%20the%20remaining%20elements.%20For%20example%2C%20subsequences%20of%20%221011101%22%20are%20%220%22%2C%20%221%22%2C%20%2211111%22%2C%20%220111%22%2C%20%22101%22%2C%20%221001%22%2C%20but%20not%20%22000%22%2C%20%22101010%22%20and%20%2211100%22.%0A%0AYou%20have%20to%20answer%20t%20independent%20test%20cases.)
百度翻译结果%20%E2%80%94%20the%20number%20of%20test%20cases.%20Then%20t%20test%20cases%20follow.%0A%0AThe%20first%20line%20of%20the%20test%20case%20contains%20one%20integer%20n%20(1%E2%89%A4n%E2%89%A42%E2%8B%85105)%20%E2%80%94%20the%20length%20of%20s.%20The%20second%20line%20of%20the%20test%20case%20contains%20n%20characters%20’0’%20and%20’1’%20%E2%80%94%20the%20string%20s.%0A%0AIt%20is%20guaranteed%20that%20the%20sum%20of%20n%20does%20not%20exceed%202%E2%8B%85105%20(%E2%88%91n%E2%89%A42%E2%8B%85105).%0A%0AOutput%0AFor%20each%20test%20case%2C%20print%20the%20answer%3A%20in%20the%20first%20line%20print%20one%20integer%20k%20(1%E2%89%A4k%E2%89%A4n)%20%E2%80%94%20the%20minimum%20number%20of%20subsequences%20you%20can%20divide%20the%20string%20s%20to.%20In%20the%20second%20line%20print%20n%20integers%20a1%2Ca2%2C%E2%80%A6%2Can%20(1%E2%89%A4ai%E2%89%A4k)%2C%20where%20ai%20is%20the%20number%20of%20subsequence%20the%20i-th%20character%20of%20s%20belongs%20to.%0A%0AIf%20there%20are%20several%20answers%2C%20you%20can%20print%20any.%0A%0AExample%0AinputCopy%0A4%0A4%0A0011%0A6%0A111111%0A5%0A10101%0A8%0A01010000%0AoutputCopy%0A2%0A1%202%202%201%20%0A6%0A1%202%203%204%205%206%20%0A1%0A1%201%201%201%201%20%0A4%0A1%201%201%201%201%202%203%204)

思路一

我们发现对于任意si，加入已有子序列bj的唯一要求就是si!=bj[end]。所以我们只需存储目前所有的bj[end]记为bj，对于任意si，遍历各个子序列结尾bj。若si!=bj，则加入；若所有子序列bj==si，则新建一个序列放入。最后结果为序列数

代码一（TLE）

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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
char s[200010];
int a[200010];
int b[200010];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int ans=0;
		memset(a,0,sizeof(a));
		int n;
		scanf("%d",&n);
		scanf("\n%s",s);
		for(int i=0;i<n;++i){
			a[i]=s[i]-'0';
		}
		for(int i=0;i<n;++i){
			bool flag=true;
			for(int j=1;j<=ans;++j){
				if(a[i]!=b[j]){
					a[i]=j;
					flag=false;
					b[j]+=1;
					b[j]%=2;
					break;
				}
			}
			if(flag){
				++ans;
				b[ans]=a[i];
				a[i]=ans;
			}
		}
		printf("%d\n",ans);
		for(int i=0;i<n;++i){
			printf("%d ",a[i]);
		}
		printf("\n");
	}
	return 0;
}
//	freopen("data.in","r",stdin);
//	freopen("test.out","w",stdout);

思路二

我们发现超时的原因主要在于搜索可放入序列bj过程耗时过多，最坏情况所有bj!=ai,时间复杂度将退化到O(n^2).由于sum(n)<=2*10^5，最坏情况下t=0，n=200000，时间复杂度为O(200000^2)。显然超时。

针对搜索可放入序列bj过程耗时过多，我们发现用两个数组一个存结尾为0，另一个存结尾为1。每次只需判断数组是否空即可。若不空，则加入序列，并将该序列移至另一数组，否则新建一个序列。进一步思考发现若将数组换位队列将更好操作，于是有了下面这份代码，简单观察可知时间复杂度为O(sum(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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
char s[200010];
int a[200010];
queue<int>b0;
queue<int>b1;
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		while(!b0.empty()){
			b0.pop();
		}
		while(!b1.empty()){
			b1.pop();
		}
		int ans=0;
		memset(a,0,sizeof(a));
		int n;
		scanf("%d",&n);
		scanf("\n%s",s);
		for(int i=0;i<n;++i){
			a[i]=s[i]-'0';
		}
		for(int i=0;i<n;++i){
			if(a[i]==0){
				if(!b0.empty()){
					a[i]=b0.front();
					b0.pop();
					b1.push(a[i]);
				}
				else{
					++ans;
					a[i]=ans;
					b1.push(ans);
				}
			}
			else{
				if(!b1.empty()){
					a[i]=b1.front();
					b1.pop();
					b0.push(a[i]);
				}
				else{
					++ans;
					a[i]=ans;
					b0.push(ans);
				}
			}
		}
		printf("%d\n",ans);
		for(int i=0;i<n;++i){
			printf("%d ",a[i]);
		}
		printf("\n");
	}
	return 0;
}
//	freopen("data.in","r",stdin);
//	freopen("test.out","w",stdout);

CF1399B Gifts Fixing

题目

B. Gifts Fixing
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You have n gifts and you want to give all of them to children. Of course, you don't want to offend anyone, so all gifts should be equal between each other. The i-th gift consists of ai candies and bi oranges.

During one move, you can choose some gift 1≤i≤n and do one of the following operations:

eat exactly one candy from this gift (decrease ai by one);
eat exactly one orange from this gift (decrease bi by one);
eat exactly one candy and exactly one orange from this gift (decrease both ai and bi by one).
Of course, you can not eat a candy or orange if it's not present in the gift (so neither ai nor bi can become less than zero).

As said above, all gifts should be equal. This means that after some sequence of moves the following two conditions should be satisfied: a1=a2=⋯=an and b1=b2=⋯=bn (and ai equals bi is not necessary).

Your task is to find the minimum number of moves required to equalize all the given gifts.

You have to answer t independent test cases.

Input
The first line of the input contains one integer t (1≤t≤1000) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1≤n≤50) — the number of gifts. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤109), where ai is the number of candies in the i-th gift. The third line of the test case contains n integers b1,b2,…,bn (1≤bi≤109), where bi is the number of oranges in the i-th gift.

Output
For each test case, print one integer: the minimum number of moves required to equalize all the given gifts.

Example
input
5
3
3 5 6
3 2 3
5
1 2 3 4 5
5 4 3 2 1
3
1 1 1
2 2 2
6
1 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1
3
10 12 8
7 5 4
output
6
16
0
4999999995
7
Note
In the first test case of the example, we can perform the following sequence of moves:

choose the first gift and eat one orange from it, so a=[3,5,6] and b=[2,2,3];
choose the second gift and eat one candy from it, so a=[3,4,6] and b=[2,2,3];
choose the second gift and eat one candy from it, so a=[3,3,6] and b=[2,2,3];
choose the third gift and eat one candy and one orange from it, so a=[3,3,5] and b=[2,2,2];
choose the third gift and eat one candy from it, so a=[3,3,4] and b=[2,2,2];
choose the third gift and eat one candy from it, so a=[3,3,3] and b=[2,2,2].

翻译

百度翻译结果%20integers.%0A%0AIn%20one%20move%2C%20you%20can%20choose%20two%20indices%20i%20and%20j%20(i%E2%89%A0j)%20such%20that%20the%20absolute%20difference%20between%20ai%20and%20aj%20is%20no%20more%20than%20one%20(%7Cai%E2%88%92aj%7C%E2%89%A41)%20and%20remove%20the%20smallest%20of%20these%20two%20elements.%20If%20two%20elements%20are%20equal%2C%20you%20can%20remove%20any%20of%20them%20(but%20exactly%20one).%0A%0AYour%20task%20is%20to%20find%20if%20it%20is%20possible%20to%20obtain%20the%20array%20consisting%20of%20only%20one%20element%20using%20several%20(possibly%2C%20zero)%20such%20moves%20or%20not.%0A%0AYou%20have%20to%20answer%20t%20independent%20test%20cases.%0A%0AInput%0AThe%20first%20line%20of%20the%20input%20contains%20one%20integer%20t%20(1%E2%89%A4t%E2%89%A41000)%20%E2%80%94%20the%20number%20of%20test%20cases.%20Then%20t%20test%20cases%20follow.%0A%0AThe%20first%20line%20of%20the%20test%20case%20contains%20one%20integer%20n%20(1%E2%89%A4n%E2%89%A450)%20%E2%80%94%20the%20length%20of%20a.%20The%20second%20line%20of%20the%20test%20case%20contains%20n%20integers%20a1%2Ca2%2C%E2%80%A6%2Can%20(1%E2%89%A4ai%E2%89%A4100)%2C%20where%20ai%20is%20the%20i-th%20element%20of%20a.%0A%0AOutput%0AFor%20each%20test%20case%2C%20print%20the%20answer%3A%20%22YES%22%20if%20it%20is%20possible%20to%20obtain%20the%20array%20consisting%20of%20only%20one%20element%20using%20several%20(possibly%2C%20zero)%20moves%20described%20in%20the%20problem%20statement%2C%20or%20%22NO%22%20otherwise.)

思路

自己想

代码

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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
int a[100];
int b[100];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		int mina=1000000010,minb=1000000010;
		for(int i=0;i<n;++i){
			scanf("%d",&a[i]);
			if(a[i]<mina)mina=a[i];
		}
		for(int i=0;i<n;++i){
			scanf("%d",&b[i]);
			if(b[i]<minb)minb=b[i];
		}
		long long con=0;
		for(int i=0;i<n;++i){
			int x=a[i]-mina,y=b[i]-minb;
			con+=max(x,y);
		}
		printf("%I64d\n",con);
	}
	return 0;
}
//	freopen("data.in","r",stdin);
//	freopen("test.out","w",stdout);

CF1399A Remove Smallest

题目

A. Remove Smallest

time limit per test:1 second

memory limit per test:256 megabytes

input:standard input

output:standard output

You are given the array a consisting of n positive (greater than zero) integers.

In one move, you can choose two indices i and j (i≠j) such that the absolute difference between ai and aj is no more than one (|ai−aj|≤1) and remove the smallest of these two elements. If two elements are equal, you can remove any of them (but exactly one).

Your task is to find if it is possible to obtain the array consisting of only one element using several (possibly, zero) such moves or not.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1≤t≤1000) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1≤n≤50) — the length of a. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤100), where ai is the i-th element of a.

Output

For each test case, print the answer: “YES” if it is possible to obtain the array consisting of only one element using several (possibly, zero) moves described in the problem statement, or “NO” otherwise.

Example

input

5
3
1 2 2
4
5 5 5 5
3
1 2 4
4
1 3 4 4
1
100

output

YES
YES
NO
NO
YES

Note

In the first test case of the example, we can perform the following sequence of moves:

choose i=1 and j=3 and remove ai (so a becomes [2;2]);
choose i=1 and j=2 and remove aj (so a becomes [2]).
In the second test case of the example, we can choose any possible i and j any move and it doesn’t matter which element we remove.

In the third test case of the example, there is no way to get rid of 2 and 4.

翻译

百度翻译结果%20integers.%0A%0AIn%20one%20move%2C%20you%20can%20choose%20two%20indices%20i%20and%20j%20(i%E2%89%A0j)%20such%20that%20the%20absolute%20difference%20between%20ai%20and%20aj%20is%20no%20more%20than%20one%20(%7Cai%E2%88%92aj%7C%E2%89%A41)%20and%20remove%20the%20smallest%20of%20these%20two%20elements.%20If%20two%20elements%20are%20equal%2C%20you%20can%20remove%20any%20of%20them%20(but%20exactly%20one).%0A%0AYour%20task%20is%20to%20find%20if%20it%20is%20possible%20to%20obtain%20the%20array%20consisting%20of%20only%20one%20element%20using%20several%20(possibly%2C%20zero)%20such%20moves%20or%20not.%0A%0AYou%20have%20to%20answer%20t%20independent%20test%20cases.%0A%0AInput%0AThe%20first%20line%20of%20the%20input%20contains%20one%20integer%20t%20(1%E2%89%A4t%E2%89%A41000)%20%E2%80%94%20the%20number%20of%20test%20cases.%20Then%20t%20test%20cases%20follow.%0A%0AThe%20first%20line%20of%20the%20test%20case%20contains%20one%20integer%20n%20(1%E2%89%A4n%E2%89%A450)%20%E2%80%94%20the%20length%20of%20a.%20The%20second%20line%20of%20the%20test%20case%20contains%20n%20integers%20a1%2Ca2%2C%E2%80%A6%2Can%20(1%E2%89%A4ai%E2%89%A4100)%2C%20where%20ai%20is%20the%20i-th%20element%20of%20a.%0A%0AOutput%0AFor%20each%20test%20case%2C%20print%20the%20answer%3A%20%22YES%22%20if%20it%20is%20possible%20to%20obtain%20the%20array%20consisting%20of%20only%20one%20element%20using%20several%20(possibly%2C%20zero)%20moves%20described%20in%20the%20problem%20statement%2C%20or%20%22NO%22%20otherwise.)

思路

自己想

代码

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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
int a[100];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;++i){
			scanf("%d",&a[i]);
		}
		sort(a,a+n);
		bool flag=true;
		for(int i=1;i<n;++i){
			if(a[i]-a[i-1]>1){
				flag=false;
				printf("NO\n");
				break;
			}
		}
		if(flag){
			printf("YES\n");
		}
	}
	return 0;
}
//	freopen("data.in","r",stdin);
//	freopen("test.out","w",stdout);

Codeforces Round #661 (Div. 3)

题号

A. Remove Smallest

B. Gifts Fixing

C. Boats Competition

D. Binary String To Subsequences

E1. Weights Division (easy version)

E2. Weights Division (hard version)

F. Yet Another Segments Subset

题解

A. Remove Smallest

B. Gifts Fixing

C. Boats Competition

D. Binary String To Subsequences

E1. Weights Division (easy version)

E2. Weights Division (hard version)

F. Yet Another Segments Subset

YBT1486 黑暗城堡

题目

1486：【例题1】黑暗城堡

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 1248 通过数: 431
【题目描述】
知道黑暗城堡有 N 个房间，M 条可以制造的双向通道，以及每条通道的长度。

城堡是树形的并且满足下面的条件：

设 Di为如果所有的通道都被修建，第 i 号房间与第 1 号房间的最短路径长度；

而 Si 为实际修建的树形城堡中第 i 号房间与第 1 号房间的路径长度；

要求对于所有整数 i(1≤i≤N)，有 Si=Di 成立。

你想知道有多少种不同的城堡修建方案。当然，你只需要输出答案对 231−1 取模之后的结果就行了。

【输入】
第一行为两个由空格隔开的整数 N,M;

第二行到第 M+1 行为 3 个由空格隔开的整数 x,y,l：表示 x 号房间与 y 号房间之间的通道长度为 l。

【输出】
一个整数：不同的城堡修建方案数对 231−1 取模之后的结果。

【输入样例】

4 6
1 2 1
1 3 2
1 4 3
2 3 1
2 4 2
3 4 1

【输出样例】

6

【提示】

样例说明

一共有 4 个房间，6 条道路，其中 1 号和 2 号，1 号和 3 号，1 号和 4 号，2 号和 3 号，2 号和 4 号，3 号和 4 号房间之间的通道长度分别为 1，2，3，1，2，1。

而不同的城堡修建方案数对 231−1 取模之后的结果为 6。

数据范围:

对于全部数据，1≤N≤1000，1≤M≤N(N−1)2,1≤l≤200。

解法

1. 用spfa求出点1到各个点的最短路径di
2. 对每个点搞出可实现最短路的方法ci
3. 乘法原理将ci相乘得到最终结果

代码

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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
int mod=1<<31;
struct line{
	int x;
	int l;
};
vector<struct line>road[1010];
int dis[1010];
queue<struct line>q;
int main(){
//	freopen("data.in","r",stdin);
//	freopen("test.out","w",stdout);
	int n,m;
	mod=~mod;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		struct line a;
		int b;
		scanf("%d%d%d",&b,&a.x,&a.l);
		road[b].push_back(a);
		swap(b,a.x);
		road[b].push_back(a);
	}
	memset(dis,0x3f,sizeof(dis));
	struct line temp;
	temp.x=1;
	temp.l=0;
	q.push(temp);
	while(!q.empty()){
		temp=q.front();
		q.pop();
		int x=temp.x;
		int l=temp.l;
		if(l<dis[x])dis[x]=l;
		else continue;
		for(int i=0;i<road[x].size();++i){
			temp=road[x][i];
			temp.l+=dis[x];
			q.push(temp);
		}
	}
	long long ans=1;
	for(int i=2;i<=n;++i){
		int con=0;
		for(int j=0;j<road[i].size();++j){
			if(dis[road[i][j].x]+road[i][j].l==dis[i])++con;
		}
		ans=((ans%mod)*(con%mod)%mod);
	}
	printf("%d",ans);
	return 0;
}