[BDOI Round 1] 题解

本场题目难度 ： 黄绿蓝紫（乱序

本场比赛暴力分 ： 40+30+100+30 = 210
本场比赛暴力+错解分：80+50+100+40 = 270

这个地方留给出锅之后

很好T3锅了，打 std 的时候忘排序了

update

13:42 p.m. 撤下 Elevator 简化题意
13:53 p.m. lh T4 喜提 10pts 目前 rank1
14:18 p.m.大便小便T2 30pts 同居 rank 1
14:24 p.m. Ocean T2 20pts rank3 让我们看看他是否会对自己的答案进行对拍
14:25 p.m. sgl T1 40pts rank1 终于有人打暴力了
14:26 p.m. 恭喜林彤首A T3 终于有人切了签到题
14:29 p.m. 背锅人 T2 30pts ! 神之子居然真的跳过了T1！！！
14:40 p.m. lhd T2 30 pts
14:52 p.m. wcc T1接近正解 50 pts tql%%%
14:56 p.m.鸡哥T4 70pts （注意取模啊兄弟们
15:12 p.m. 恭喜 fzy T4 首A
15:28 p.m 分奶茶力（喜）但是为什么不是大杯的
15:30 p.m. lyh T1 80 pts ! 太强了（突然发现T1数据好水
16:06 p.m lyh 对 T2 进行了一个暴力的打 获得 30 pts rank1成功易主
16:41 p.m lyh 再次进行暴力 得到 T4 10 pts 稳居 rank 1

大水题

非常抱歉这题锅了（）
不使用贪心直接按照节点编号从小到大删除即可通过此题

关于此题正解

使用重载运算符对每个节点所连的可进行删除的点排序，然后贪心从大到小进行删除即可。
注意这里有个细节：对一个节点的叶子进行删除之后要先把当前节点取出来再丢回去，不然会导致排序出问题

现在题面已修改

这是本场比赛最简单的一题（）

因为太简单了所以故意把题目出的很绕

这题其实就是选择广义叶子节点然后删掉 ， 直到不能选出足够的叶子为止

那么我们就需要支持对一个节点进行边的删除 , 这个可以使用 set 实现

细节有点多 , 配合代码辅助理解

#include 
const int N = 2e5+10;

using namespace std;
int n,k,m;
set<int> e[N];
set<int> leaf;

void solve(){
//	cout << n << " " << m << " " << k << endl;
	for(int i = 1;i <= n; i++) e[i].clear();
	leaf.clear();
	for(int i =1;i <= m; i++){
		int u,v;
		cin >> u >> v;
		e[u].insert(v);
		e[v].insert(u); 
	}
	for(int i = 1; i <= n; i++){
		if(e[i].size() == 1) leaf.insert(i);
	}
	int cnt = 0;
	while(leaf.size() >= k){
		vector<int> nw;
		for(int i = 1 ;i <= k; i++){
			if(leaf.size() == 0){
				cout << cnt << endl;
				return;
			}
			int v = *leaf.begin();
			leaf.erase(v);
			int fa = *e[v].begin();
			e[fa].erase(v);
			e[v].erase(fa);
			if(leaf.count(fa)) leaf.erase(fa);
			if(e[fa].size() == 1){
				nw.push_back(fa);
			} 
//			cout << v << " ";
 		}
// 		cout << endl;
		for(int fa : nw){
			leaf.insert(fa);
		}
		cnt++;
	}
	cout << cnt << endl;
}
int main(){
//	freopen("dst.in","r",stdin);
//	freopen("dst.ans","w",stdout);
	while(cin >> n >> m >> k && n) solve();
	return 0;
}
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

多测不清空，爆零两行泪

签到题

打过 OL 2022 的应该看出原题是什么了罢
幸好我不会打SPJ不然就纯原了

这题数据好像很水，错解得到了80分的好成绩

简化题意

给一堆集合 , 求是否存在两个集合有交集但是不是包含关系

思考两个集合之间会有什么关系：

1. 无交集
2. 包含
3. 有交但不是包含

集合交并这些可以 bitset 实现拿部分分这个我就不细说了

考虑暴力怎么实现 , 遍历两个集合暴力判断即可

但是显然这样的复杂度是 $n^4$ 的

枚举类暴力复杂度降低的一大核心在于减少枚举次数 , 思考如何减少枚举次数

减少枚举次数肯定是先从去掉不必要的枚举下手 ，可以发现存在三个大小递增的集合，且有两个集合存在包含关系的时候 ， 这两个集合可以合并掉，只剩一个大集合；还有一种情况就是最大的集合包含两个小集合 ， 但是两个小集合符合条件

那么是不是就这样从小到大合并过去就可以了？似乎复杂度还是有问题 ， 正确性也有点问题需要处理。

换种角度思考 ， 判断两个集合是否符合条件第一个要看的就是两个集合是否存在共同元素 ， 第二个要看的才是是否是完全包含。 如果挨个枚举每个集合， 我们就需要快速的找出和这个集合有交集的集合也就是判断某个元素是否存在于其他的集合之中。 其实这个可以使用并查集

先对集合进行排序 ， 从小到大枚举每个集合，枚举每个集合中的每个元素， 使用并查集判断是否存在于其他集合中， 如果是， 那就合并这两个集合。 不难发现， 如果两个集合不满足条件， 合并结束之后的集合大小一定不会大于当前集合，如果出现了，就说明存在符合条件的集合

#include 
const int N = 2e6+10;

using namespace std;
int fa[N],siz[N];
int n,t;
struct Node{
	vector<int> v;
	int k;
	int id;
}a[N];
bool cmp(Node x, Node y){
	return x.k < y.k;
}
int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int vis[N];
void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		scanf("%d",&a[i].k);
		a[i].id = i;
		a[i].v.clear();
		for(int j = 1;j <= a[i].k; j++){
			int x;
			scanf("%d",&x);
			a[i].v.push_back(x+1000000);
		}
	}
	sort(a+1,a+1+n,cmp);
	for(int i = 1;i <= n; i++){
		fa[i] = i;
		siz[i] = 0;
	}
	for(int i = 1000000+1; i <= n+1000000; i++){
		fa[i] = i;
		siz[i] = 1;
	}
	int ansa=0,ansb=0;
	for(int i = 1;i <= n; i++){
		for(int j : a[i].v){
			int fj = find(j),fi = find(i);
			if(fj != fi){
				siz[fj] += siz[fi];
				fa[fi] = fj;
			}
		}
		int fi = find(i);
		if(siz[fi] > a[i].k){
			ansa = i;
			break;
		}
	}
	if(ansa){
		puts("YES");
	}else{
		puts("NO");
	}
}
int main(){
//	freopen("sign.in","r",stdin);
//	freopen("sign.out","w",stdout);
	cin >> t;
	while(t--) solve();
	return 0;
}
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

Seg Treap

这题的原名叫 线段树 ， 但是由于提示性过于明显就改名了

这题学过平衡树的应该第一反应就是文艺平衡树， 确实， 这很像， 但是我也不知道平衡树能不能写， 因为我不会

看到题目上的一堆 $2^i$ 想到二进制，想到倍增， 在结合前面的平衡树， 应该很自然能想到线段树罢

可以发现交换两个区间可以直接把这两个区间拿出来在树上重新挂一下就行， 区间翻转可以通过一堆区间交换来实现

代码难度不大，长的和普通线段树差不多

但是，显然出这么简单会挨骂的

所以代码上有点细节，个人认为数据造的还是很好的，细节没注意的给了20分，暴力给了30分

在交换的时候，有些人只注意了 pushdown 但是没有 pushup ， 有的人 pushup 了但是又没有完全 pushup , 有的人完全 pushup 了但是忘了一种类似 pushdown 的东西

别问我怎么知道这么多，因为这些东西在有了这个 idea 之后自己打标程的时候一个一个踩雷踩过去搞了一晚上

细节上，要注意每次把区间在树上重新挂了之后，要一直 pushup 到两个区间的 LCA， 而且要记得交换两个区间的父亲节点标记

某些常规 pushdown 和 pushup 忘记的这种就喜闻乐见了

#include 
#define int long long
const int N = 20;

using namespace std;
struct Node{
	int sum;
	int ls, rs,fa;
	bool rvs;
}node[1<<N];
int a[1<<N],n,m;
void push_up(int pos){
	node[pos].sum = node[node[pos].ls].sum + node[node[pos].rs].sum;
}
void build(int pos, int l, int r){
	if(l == r){
		node[pos].sum = a[l];
		return;
	}
	int mid = (l+r) >> 1;
	node[pos].ls = pos << 1;
	node[pos].rs = pos << 1 | 1;
	build(pos<<1,l,mid);
	build(pos<<1|1, mid+1, r);
	node[node[pos].ls].fa = node[node[pos].rs].fa = pos;
	push_up(pos);
}
void push_down(int pos){
	if(node[pos].rvs){
		swap(node[pos].ls, node[pos].rs);
		node[node[pos].ls].rvs ^= 1;
		node[node[pos].rs].rvs ^= 1;
		node[pos].rvs = 0;
	}
}
void modify(int pos, int l, int r,int x, int y){
	if(l == r){
		node[pos].sum = y;
		return;
	}
	push_down(pos);
	int mid = (l+r) >> 1;
	if(x <= mid){
		modify(node[pos].ls,l,mid,x,y);
	}else{
		modify(node[pos].rs, mid+1, r, x, y);
	}
	push_up(pos);
}
void reverse(int pos, int l, int r, int x, int y){
	if(l == x && r == y){
		node[pos].rvs ^= 1;
		return;
	}
	push_down(pos);
	int mid = (l+r) >> 1;
	if(x <= mid){
		reverse(node[pos].ls,l,mid,x,y);
	}else{
		reverse(node[pos].rs,mid+1,r,x,y);
	}
}
void find(int pos, int l, int r, int x, int y,int &fa, int &son){
	if(l == x && r == y){
		return;
	}
	push_down(pos);
	int mid = (l+r) >> 1;
	fa = pos;
	if(x <= mid){
		son = 0;
		find(node[pos].ls,l,mid,x,y,fa,son);
	}else{
		son = 1;
		find(node[pos].rs, mid+1,r,x,y,fa,son);
	}
}
void swp(int x, int y, int k){
	if(x == y) return;
	int fax,fay,sonx,sony;
	find(1,1,n,(x)*(1<<k)+1,(x+1)*(1<<k),fax,sonx);
	find(1,1,n,(y)*(1<<k)+1,(y+1)*(1<<k),fay,sony);
//	cout << fax << " " << sonx << " " << fay << " " << sony << endl;
	sonx == 1 ? node[node[fax].rs].fa = fay : node[node[fax].ls].fa = fay;
	sony == 1 ? node[node[fay].rs].fa = fax : node[node[fay].ls].fa = fax;
	
	swap((sonx == 1 ? node[fax].rs : node[fax].ls) , (sony == 1 ? node[fay].rs : node[fay].ls));
	while(fax != fay){
		push_up(fax);
		push_up(fay);
		fax = node[fax].fa;
		fay = node[fay].fa;
	}
	push_up(fax);
}
int query(int pos, int l, int r, int x, int y){
	if(x <= l && r <= y){
		return node[pos].sum;
	}
	int mid = (l+r) >> 1;
	push_down(pos);
	int res = 0;
	if(x <= mid){
		res += query(node[pos].ls, l, mid, x,y); 
	}
	if(mid < y){
		res += query(node[pos].rs, mid+1, r, x, y);
	}
	push_up(pos);
	return res;
}
signed main(){
	freopen("seg15.in","r",stdin);
	freopen("seg15.out","w",stdout);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	build(1,1,n);
	while(m--){
		int op;
		cin >> op;
		if(op == 1){
			int x,k;
			cin >> x >> k;
			modify(1,1,n,x,k);
		} 
		if(op == 2){
			int x, k;
			cin >> x >> k;
			reverse(1,1,n,x*(1<<k)+1,(x+1)*(1<<k));
		}
		if(op == 3){
			int x,y,k;
			cin >> x >> y >> k;
			swp(x,y,k);
		}
		if(op == 4){
			int l,r;
			cin >> l >> r;
			cout << query(1,1,n,l,r) << endl;
		}
	}
	return 0;
}
/*
8 10
1 2 3 4 5 6 7 8
4 3 5
2 1 1
4 3 3
4 4 5
3 1 2 1
4 6 8
3 0 1 0
4 2 3
1 1 8
4 1 2
*/

/*
4 9
1 4 3 2 
2 1 1
3 2 0 0
2 1 0
4 2 4
3 1 2 0
2 0 2
2 1 1
1 4 5
3 0 0 1

*/
/*
8 10
1 5 2 5 2 4 5 1 
3 7 2 0
4 5 8
3 0 5 0
4 5 8
3 1 2 1
4 5 8
3 0 0 1
4 5 8
3 0 4 0
4 5 8
*/

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

Elevator

这题可以说是纯原罢

题面灵感来自 1508 的传统娱乐项目抢电梯

有些人看到什么期望和排列就直接放弃这题了， 但其实这题不复杂，也和期望没关系 简化题意都特地没写期望了

看到数据范围，某男子就跳出来说了这不是一眼状压DP 。

道理我都懂，但是这题真的是状压DP

出的最轻松的一题， 不用担心暴力会不会没被卡掉而且数据还是手搓的

首先考虑最大前缀和有什么特点：

1. 最大前缀和的后缀一定都大于等于0
2. 去掉最大前缀后剩下的部分不存在大于0的前缀

看起来好麻烦，而且似乎这样一种状态不好记录

那怎么办？

那就分开DP跑两遍

对于前缀，从后往前加数， 对于去掉前缀后的前缀， 从前往后加数， f[s]/g[s]表示当所选数字集合为s时符合要求的方案数

那么最后答案就是 $sum[s]\ast f[s]\ast g[Uxors]$

欸但是这样交上去发现只有40分 , 仔细观察可以发现漏掉了最大前缀本身就为负的情况

那又怎么办

多开一维不就好了

#include 
#define int long long
const int mod = 998244353;
using namespace std;
int sum[1<<21],f[1<<21][2],g[1<<21];
int n, a[21];

signed main(){
//	freopen("Elevator2.in","r",stdin);
//	freopen("Elevator2.out","w",stdout);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
//	for(int i =1;i <= n; i++) a[i] = -a[i];
	for(int i = 1;i < (1 << n); i++){
		for(int j = 0; j < n; j++){
			if(i & (1 << j)){
				sum[i] += a[j+1];
			}
		}
	}
	for(int i =1;i <= n; i++){
		if(a[i] < 0){
			f[1 << (i-1)][0] = 1;
		}else{
			f[1 << (i-1)][1] = 1;
		}
	}
	for(int i = 1;i < (1 << n); i++){
		int s = i;
		for(int j = 0; j < n; j++){
			if(s & (1 << j)) continue;
			int t = s | (1 << j);
			if(sum[t] >= 0){
				f[t][1] = (f[t][1] + f[s][1]) % mod;
			}else{
				f[t][0] = (f[t][0] + f[s][1]) % mod;
			}
		}
	}	
	g[0] = 1;
	for(int i = 0; i < ( 1 << n); i++){
		int s = i;
		if(!g[s]) continue;
		for(int j = 0; j < n; j++){
			if(s & (1 << j)) continue;
			int t = (s | (1 << j));
			if(sum[t] < 0) g[t] = (g[t] + g[s]) % mod;
		}
	}
	int u = (1 << n) -1;
	int ans = 0;
	for(int i = 1; i <= u; i++){
		ans = (ans + (sum[i] % mod + mod) % mod * (f[i][0]+f[i][1]) % mod*g[u^i] % mod) % mod;
	}
	cout << ans;
	return 0;
}

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