首页 > itarticle > neuq-acm 2019年11月训练 题解

neuq-acm 2019年11月训练 题解

admin 11月 11, 2020 0

NEUQ 消除恐惧的最好办法就是

A

题意

给出一个图，对每个节点涂三种颜色中任一种，给出每个节点涂每种颜色的代价，要求任意三个相连的点所涂颜色互不相同，求最小代价。不能实现要求则输出-1

题解

只有给出的图是一条链时才能满足给定的要求，所以先判断每个点的度数，存在度数大于2的节点直接输出-1

然后从度数为1的点得到该图的路径，对6中颜色的排列逐一算出结果取最小值就行

时间复杂度：$mathcal{O} (6n)$

代码

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
 

#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
struct  {
	int fr,to,nxt;
	Node(){}
	Node(int _f,int _t,int _n):fr(_f),to(_t),nxt(_n) {}
};
int op[6][3]={{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}};
Node a[200005];
int head[100005];
ll v[100005][3];
vector<int>ve;
int du[100005];
int Ans[100005],Tmp[100005];
void build(int o,int fr,int to){
	a[o]=Node(fr,to,head[fr]);
	head[fr]=o;
	du[fr]++;
}
void solve(){
	ve.clear();
	int n;
	scanf("%d",&n);
	MS(v,0);
	MS(head,-1);
	for (int i=0;i<3;i++){
		for (int j=1;j<=n;j++)
			scanf("%lld",&v[j][i]);
	}
	for (int i=0;i<n-1;i++){
		int fr,to;
		scanf("%d%d",&fr,&to);
		build(i<<1,fr,to);
		build(i<<1|1,to,fr);
	}
	int fa=0,now;
	for (int i=1;i<=n;i++){
		if (du[i]>2){
			printf("-1n");
			return;
		}
		else if (du[i]==1)
			now=i;
	}
	int m=n;
	while (m--){
		ve.push_back(now);
		for (int i=head[now];i!=-1;i=a[i].nxt){
			int p=a[i].to;
			if (p==fa)
				continue;
			fa=now;
			now=p;
			break;
		}
	}
	int si=ve.size();
	ll ans=LLONG_MAX;
	for (int i=0;i<6;i++){
		int p=0;
		ll tmp=0;
		for (int j=0;j<si;j++){
			tmp+=v[ve[j]][op[i][p]-1];
			Tmp[ve[j]]=op[i][p];
			p++;
			p%=3;
		}
		if (tmp<ans){
			for (int j=1;j<=n;j++)
				Ans[j]=Tmp[j];
			ans=tmp;
		}
	}
	printf("%lldn",ans);
	for (int i=1;i<=n;i++)
		printf("%d ",Ans[i]);
	printf("n");
}
int main(){
	solve();
	return 0;
}

B

题意

给出$n$个城市的坐标，每两个城市之间的距离为曼哈顿距离，对于每个城市，可以选择在城市建一座发电站，费用为c。也可以选择修建电缆到有电的城市，在城市$x$和城市$y$修建电缆的费用为$(k_x+k_y)times d_{xto y}$

求使所有城市有电的最小费用

题解

最小生成树

由于每棵树中只需要修一个发电站就行，所以维护每棵树中修建发电站的最小费用。
在判断是否连边时加判边的费用是否小于两棵树中任一一棵中修发电站的最小费用。

时间复杂度：$mathcal{O} (n^2log {n^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
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
 

#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
struct  {
	int x,y;
};
Node a[2005];
struct Edge {
	int fr,to;
	ll v;
	Edge(){}
	Edge(int _f,int _t,ll _v):fr(_f),to(_t),v(_v) {}
	bool operator<(const Edge &A)const {
		return v<A.v;
	}
};
Edge g[4000005];
int fa[2005];
ll c[2005],k[2005];
vector<pair<int,int> >Ans;
void make_fa(int n){
	for (int i=1;i<=n;i++)
		fa[i]=i;
}
int find_fa(int x){
	return x==fa[x]?x:fa[x]=find_fa(fa[x]);
}
void Union(int x,int y){
	int fx=find_fa(x),fy=find_fa(y);
	if (c[fx]<c[fy])
		fa[fy]=fx;
	else
		fa[fx]=fy;
}
void solve(){
	int n;
	Ans.clear();
	scanf("%d",&n);
	make_fa(n);
	for (int i=1;i<=n;i++)
		scanf("%d%d",&a[i].x,&a[i].y);
	for (int i=1;i<=n;i++)
		scanf("%lld",&c[i]);
	for (int i=1;i<=n;i++)
		scanf("%lld",&k[i]);
	int N=0;
	for (int i=1;i<n;i++){
		for (int j=i+1;j<=n;j++){
			g[N++]=Edge(i,j,(k[i]+k[j])*(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)));
		}
	}
	sort(g,g+N);
	ll ans=0;
	for (int i=0;i<N;i++){
		int x=find_fa(g[i].fr),y=find_fa(g[i].to);
		if (x==y)
			continue;
		if (g[i].v<c[x]||g[i].v<c[y]){
			Union(x,y);
			ans+=g[i].v;
			Ans.push_back(MP(g[i].fr,g[i].to));
		}
	}
	map<int,ll>M;
	for (int i=1;i<=n;i++){
		int x=find_fa(i);
		M[x]=c[x];
	}
	for (auto k:M)
		ans+=k.second;
	printf("%lldn",ans);
	int si=M.size();
	printf("%dn",si);
	for (auto k:M)
		printf("%d ",k.first);
	si=Ans.size();
	printf("n%dn",si);
	for (auto k:Ans)
		printf("%d %dn",k.first,k.second);
}
int main(){
	solve();
	return 0;
}

C

题意

给出一个初始的括号序列，要求更换两个字符的位置（可以是同一位置，即不更换）使得通过左移或右移一个循环所能形成的合法括号序列数量最大

题解

简单版本，暴力就行

左右括号数目不相等一定不能形成合法括号序列，之间输出0
之后暴力找到一个开头然后暴力判就行
将左右括号分别视为1和-1，求一个前缀和，最小值的下一个括号就是开头了

时间复杂度：$mathcal{O} (n^3)$

代码

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
 

#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
char s[505];
int judge(int n){
	int tmp=0,mtmp=0,op=0;
	for (int i=0;i<n;i++){
		if (s[i]=='(')
			tmp++;
		else
			tmp--;
		if (tmp<mtmp){
			op=i+1;
			mtmp=tmp;
		}
	}
	int ans=0;
	for (int i=0;i<n;i++){
		int p=(op+i)%n;
		if (s[p]=='(')
			tmp++;
		else
			tmp--;
		if (tmp==0)
			ans++;
	}
	return ans;
}
void solve(){
	int n;
	scanf("%d%s",&n,s);
	int tmp=0;
	for (int i=0;i<n;i++){
		if (s[i]=='(')
			tmp++;
		else
			tmp--;
	}
	if (tmp!=0){
		printf("0n1 1n");
		return;
	}
	pair<int,int>ans=MP(1,1);
	int Ans=judge(n);
	for (int i=0;i<n;i++){
		if (s[i]=='('){
			for (int j=0;j<n;j++){
				if (s[j]==')'){
					swap(s[i],s[j]);
					int t=judge(n);
					if (t>Ans){
						Ans=t;
						ans=MP(i+1,j+1);
					}
					swap(s[i],s[j]);
				}
			}
		}
	}
	printf("%dn%d %dn",Ans,ans.fi,ans.se);
}
int main(){
	solve();
	return 0;
}

D

题意

给定$n(nle 200)$个区间，但要求每个点只能被不超过$k$个区间覆盖。
输出需要删除的最小区间数及对应区间编号

题解

简单版本，暴力就行

先将所有区间按右端点大小排序，右端点大的在前

从左往右对每个点进行判断，如果当前点所覆盖区间数$a$大于$k$,则代表至少要删除$a-k$个经过该点的区间，自然是优先选择右端点大的区间删

时间复杂度：$mathcal{O} (n^3)$

代码

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
 

#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
struct  {
	int l,r,pos;
	bool flag;
	bool operator<(const Node &A)const {
		return r>A.r;
	}
};
Node a[205];
int b[205];
vector<int>Ans;
void solve(){
	Ans.clear();
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=0;i<n;i++){
		scanf("%d%d",&a[i].l,&a[i].r);
		a[i].pos=i+1;
		a[i].flag=true;
		for (int j=a[i].l;j<=a[i].r;j++)
			b[j]++;
	}
	sort(a,a+n);
	for (int i=1;i<=200;i++){
		if (b[i]>k){
			int num=b[i]-k;
			for (int j=0;j<n;j++){
				if (num==0)
					break;
				if (a[j].flag&&a[j].l<=i&&a[j].r>=i){
					a[j].flag=false;
					for (int k=a[j].l;k<=a[j].r;k++)
						b[k]--;
					num--;
					Ans.push_back(a[j].pos);
				}
			}
		}
	}
	int ans=Ans.size();
	printf("%dn",ans);
	for (auto k:Ans)
		printf("%d ",k);
	printf("n");
}
int main(){
	solve();
	return 0;
}

E

题意

给定$n(nle 2times 10^5)$个区间，但要求每个点只能被不超过$k$个区间覆盖。
输出需要删除的最小区间数及对应区间编号

题解

整体思路与$D$题相似

对区间的排序改成左端点小的在前。用线段树维护区间情况，并在线段树叶子节点用vector来维护右端点在该位置的区间编号，线段树的值代表该区间数

从左往右对每个点就行判断，先将所有左端点小于等于当前点的区间根据右端点加入到线段树中，然后对当前点上一个点的线段树内所有值清空（线段树内存的区间右端点），这样当前线段树内的区间就都是经过当前点的区间了，如果大于$k$从右往左删相应数量的区间就行

由于删区间是区间修改，清空上一个点是单点修改，所以可以将把区间加入答案的操作放到update里面进行，两种修改就不会出现冲突了

时间复杂度：$mathcal{O} (nlog 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
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
 

#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
struct  {
	int l,r,pos;
	bool operator<(const Node &A)const {
		return r<A.r;
	}
};
Node a[200005];
vector<int>Ans;
vector<int>ve[200005];
int vep[200005];
int sg[800005],lazy[800005];
void pushup(int o){
	sg[o]=sg[Ls]+sg[Rs];
}
void update(int o,int v,int l,int r){
	sg[o]-=v;
	lazy[o]+=v;
	if (l==r){
		for (int i=0;i<v;i++)
			Ans.push_back(ve[l][vep[l]++]);
	}
}
void pushdown(int o,int l,int r){
	if (lazy[o]){
		int mid=MID;
		int R=min(lazy[o],sg[Rs]);
		if (lazy[o]>sg[Rs])
			update(Ls,lazy[o]-sg[Rs],l,mid);
		update(Rs,R,mid+1,r);
		lazy[o]=0;
	}
}
void change1(int o,int l,int r,int v){
	if (v<=sg[o]){
		update(o,v,l,r);
		return;
	}
	pushdown(o,l,r);
	int mid=MID;
	int Rv=min(v,sg[Rs]);
	if (v>sg[Rs])
		change1(Ls,l,mid,v-sg[Rs]);
	change1(Rs,mid+1,r,Rv);
	pushup(o);
}
void change2(int o,int l,int r,int p,int v){
	if (l==r){
		if (v==-1){
			ve[l].clear();
			sg[o]=0;
		}
		else {
			ve[l].push_back(v);
			sg[o]++;
		}
		return;
	}
	pushdown(o,l,r);
	int mid=MID;
	if (p<=mid)
		change2(Ls,l,mid,p,v);
	else
		change2(Rs,mid+1,r,p,v);
	pushup(o);
}
bool cmp(Node aa,Node bb){
	if (aa.l==bb.l)
		return aa.r<bb.r;
	return aa.l<bb.l;
}
void solve(){
	int n,k;
	scanf("%d%d",&n,&k);
	MS(sg,0);
	MS(lazy,0);
	for (int i=0;i<n;i++){
		ve[i].clear();
		vep[i]=0;
		scanf("%d%d",&a[i].l,&a[i].r);
		a[i].pos=i+1;
	}
	sort(a,a+n,cmp);
	int p=0;
	int L=1,R=200000;
	for (int i=L;i<=R+1;i++){
		while (p<n&&a[p].l<=i){
			change2(1,L,R,a[p].r,a[p].pos);
			p++;
		}
		if (i>1)
			change2(1,L,R,i-1,-1);
		if (sg[1]>k)
			change1(1,L,R,sg[1]-k);
	}
	int ans=Ans.size();
	printf("%dn",ans);
	for (auto k:Ans)
		printf("%d ",k);
	printf("n");
}
int main(){
	solve();
	return 0;
}

F

题意

有$n$个人总共$k$个团队出去玩，要求租若干辆车，车的费用等于车的座位数$times$车的数量。要求同一辆车最多只能有2个队的人，且同一队的人不能在不同车。

确定车的座位数，求租车的最小费用

题解

枚举座位数量暴力算取最小就行

正常这个思路应该是1s左右过的，但judge里的L和R如果是long long的话可能会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
 
#include<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
ll v[8005];
ll n,k;
ll judge(ll m){
	int L=1,R=k;
	ll ans=k;
	while (L<R){
		if (v[L]+v[R]<=m){
			L++;
			ans--;
		}
		R--;
	}
	return ans*m;
}
void solve(){
	MS(v,0);
	scanf("%lld%lld",&n,&k);
	for (int i=0;i<n;i++){
		int t;
		scanf("%d",&t);
		v[t]++;
	}
	if (k==1){
		printf("%lldn",n);
		return;
	}
	sort(v+1,v+k+1);
	ll ans=LLONG_MAX;
	ll maxn=v[k]+v[k-1];
	for (ll i=v[k];i<=maxn;i++){
		ll tmp=judge(i);
		ans=min(ans,tmp);
	}
	printf("%lldn",ans);
}
int main(){
	solve();
	return 0;
}

G

题意

给出$a,b,c$三种人的数量，a不能和c分在同一小组
要求分成三组，使三组中人数最多的组尽可能少

题解

最简单的一道题，分三种情况推公式就行

时间复杂度：$mathcal{O} (1)$

代码

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
 
#include<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
void solve(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	if (c<a)
		swap(a,c);
	int ans;
	if (a>=(b+c+1)/2)
		ans=a;
	else if (a+b<=(c+1)/2)
		ans=(c+1)/2;
	else
		ans=(a+b+c+2)/3;
	printf("%dn",ans);
}
int main(){
	int t;
	scanf("%d",&t);
	while (t--)
		solve();
	return 0;
}

H

题意

电路板上有若干点和$n$条线，每次可以更改一条线的的个连接点，要求更改最少使所有线连通，并输出更改

题解

dfs找到第一个连通图，然后随便选择图上一点$p$
之后dfs找到其他各个连通图的最后一个访问点（修改该点原图必定依然连通），都改成$p$就行了

时间复杂度：$mathcal{O} (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
 
#include<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
struct Edge {
	int fr,to,nxt,num;
	bool flag;
	Edge(){}
	Edge(int _f,int _t,int _n,int _nu,bool _fl=false):fr(_f),to(_t),nxt(_n),num(_nu),flag(_fl) {}
};
Edge a[200005];
map<int,int>head,vis;
vector<pair<int,pair<int,int> > >Ans;
pair<int,pair<int,int> >tmp;
void build(int o,int fr,int to){
	if (head.find(fr)==head.end())
		head[fr]=-1;
	a[o]=Edge(fr,to,head[fr],(o>>1)+1);
	head[fr]=o;
}
void check_dfs(int o){
	vis[o]=1;
	for (int i=head[o];i!=-1;i=a[i].nxt){
		int p=a[i].to;
		if (vis.find(p)==vis.end())
			check_dfs(p);
	}
}
void dfs(int o,int t){
	vis[o]=1;
	bool flag=true;
	for (int i=head[o];i!=-1;i=a[i].nxt){
		int p=a[i].to;
		if (vis.find(p)==vis.end()){
			flag=false;
			dfs(p,a[i].num);
		}
	}
	if (flag){
		pair<int,int>T=MP(o,head.begin()->fi);
		tmp=MP(t,T);
	}
}
void solve(){
	head.clear();
	vis.clear();
	Ans.clear();
	int n;
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		int fr,to;
		scanf("%d%d",&fr,&to);
		build(i<<1,fr,to);
		build(i<<1|1,to,fr);
	}
	check_dfs(head.begin()->fi);
	for (auto k:head){
		if (vis.find(k.fi)==vis.end()){
			dfs(k.fi,-1);
			Ans.push_back(tmp);
		}
	}
	int si=Ans.size();
	printf("%dn",si);
	for (auto k:Ans)
		printf("%d %d %dn",k.fi,k.se.fi,k.se.se);
}
int main(){
	int t;
	scanf("%d",&t);
	while (t--)
		solve();
	return 0;
}

I

题意

给出$n$（$n$保证为奇数）个员工和你所拥有的资金$s$，以及所有员工的工资区间，需要在各个区间内选择一个数作为该员工的实际工资，要求所有员工的实际工资在你付得起薪水情况下中位数尽可能大，输出中位数

题解

二分判断

判断时，如果区间在当前中位数内则令其实际工资等于中位数，否则等于区间最小值，如果总金额超出$s$，则根据大于中位数或小于中位数的人数进行调整

时间复杂度：$mathcal{O} (nlog 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
 
#include<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
pair<ll,ll>a[200005];
int n;
ll s;
bool judge(ll m){
	ll ans=0;
	int tmp=0;
	for (int i=0;i<n;i++){
		if (a[i].fi<=m&&a[i].se>=m)
			ans+=m;
		else {
			ans+=a[i].fi;
			if (a[i].se<m)
				tmp++;
		}
	}
	if (tmp>n/2)
		return false;
	if (ans<=s)
		return true;
	for (int i=0;i<n;i++){
		if (tmp>=n/2)
			return false;
		if (a[i].fi<m&&a[i].se>=m){
			ans+=a[i].fi-m;
			tmp++;
		}
		if (ans<=s)
			return true;
	}
	return false;
}
ll binary(ll l,ll r){
	if (l==r)
		return l;
	ll mid=(l+r)/2;
	if (judge(mid))
		return binary(mid+1,r);
	return binary(l,mid);
}
void solve(){
	scanf("%d%lld",&n,&s);
	for (int i=0;i<n;i++){
		ll f,e;
		scanf("%lld%lld",&f,&e);
		a[i]=MP(f,e);
	}
	sort(a,a+n);
	ll ans=binary(1,s+1)-1;
	printf("%lldn",ans);
}
int main(){
	int t;
	scanf("%d",&t);
	while (t--)
		solve();
	return 0;
}

J

题意

你要参与一个选举，每个人都会在支持你的人数达到一定数量时选择支持你，或者可以付出一定代价被收买而支持你。给出每个人选择支持你的目标人数或被收买的代价，求出让所有人都支持你的最小代价

题解

简单版本，暴力就行

先将所有人按目标人数从小到大排序

每次根据当前人数for一遍将所有人分成若干个小组，如果A与B相邻且A在前面，当A支持你的情况下人数可以让B也支持你，那么就视A和B处于同一组。每次无法通过目标人数让别人支持你时只需要找到最后一组中收买代价最低的人收买就行

时间复杂度：$mathcal{O} (n^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
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<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
struct  {
	ll p;
	bool vis;
	int m;
	bool operator<(Node &A)const {
		return m<A.m;
	}
};
Node a[5005];
void solve(){
	int n;
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		scanf("%d%lld",&a[i].m,&a[i].p);
		a[i].vis=false;
	}
	sort(a,a+n);
	ll ans=0;
	int now=0;
	for (int i=0;i<n;i++){
		if (a[i].vis)
			continue;
		if (now<a[i].m){
			while (now<a[i].m){
				int num=now;
				int t=i;
				for (int j=i;j<n;j++){
					if (a[j].vis)
						continue;
					if (a[j].m>num||a[j].p<a[t].p)
						t=j;
					num++;
				}
				a[t].vis=true;
				now++;
				ans+=a[t].p;
			}
			if (a[i].vis)
				continue;
		}
		now++;
		a[i].vis=true;
	}
	printf("%lldn",ans);
}
int main(){
	int t;
	scanf("%d",&t);
	while (t--)
		solve();
	return 0;
}

K

题意

给出一个$ntimes n$的正方形区域和$a_{1to n},b_{1to n}$序列，任一点$(x,y)$的值为$a_x+b_y$，有$q$次询问，每次给出两个坐标，判断两个坐标间是否存在一条路路径上的值都是偶数。

题解

设两坐标为$(x_1,y_1),(x_2,y_2)$，要求可转换为判断$a_{x_1to x_2}$和$b_{y_1to y_2}$是否同时为偶数或同时为奇数（偶数等于偶数+偶数或奇数+奇数）

需要维护两个序列，序列值为奇数则对应点为1，序列值为偶数则对应点为0，判断区间是否都是奇数或偶数就是判断区间和是否等于区间长度或为0就行

由于没有修改，用前缀和维护就行

时间复杂度：$mathcal{O} (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
 
#include<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
int a[2][100005],b[2][100005];
void solve(){
	int n,q;
	scanf("%d%d",&n,&q);
	for (int i=0;i<2;i++){
		for (int j=1;j<=n;j++){
			scanf("%d",&a[i][j]);
			b[i][j]=b[i][j-1]+a[i][j]%2;
		}
	}
	while (q--){
		int x1,x2,y1,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		int x=min(x1,x2),xx=max(x1,x2);
		int y=min(y1,y2),yy=max(y1,y2);
		int ansx=b[0][xx]-b[0][x-1],ansy=b[1][yy]-b[1][y-1];
		if ((ansx==0&&ansy==0)||(ansx==xx-x+1&&ansy==yy-y+1))
			printf("YESn");
		else
			printf("NOn");
	}
}
int main(){
	solve();
	return 0;
}

L

题意

给出$n$座岛屿，要求建两栋长宽一样的矩形建筑。可以在同一座岛上建也可以在不同岛上建，要求建筑面积最大，求最大面积

题解

在同一座岛上建的情况可以在输入时就计算出来

考虑在不同岛上建的情况：
对于$x_1times y_1,x_2times y_2(x_nle y_n)$来说，建筑的最大面积等于$min(x_1,x_2)times min(y_1,y_2)$

利用二维偏序的思想来考虑的话，对于把任一岛屿$i$的宽$x_i$作为建筑物的宽，我们需要找到一个岛屿$j$使得$x_ile x_j$且$y_j$尽可能大，建筑物的面积就等于$x_itimes min(y_i,y_j)$

所以对所有岛屿将$x$从大到小排序，遍历时维护一个$y$的最大值计算就行

顺便。。。精度有毒，直接用double会WA，改成bool判断是否有0.5才过

时间复杂度：$mathcal{O} (nlog 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
 
#include<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
struct Node {
	ll l,r;
	bool operator<(Node &A)const {
		return l>A.l;
	}
};
Node a[100005];
void solve(){
	int n;
	scanf("%d",&n);
	ll ans=0;
	bool fans=false;
	for (int i=0;i<n;i++){
		scanf("%lld%lld",&a[i].l,&a[i].r);
		if (a[i].r<a[i].l)
			swap(a[i].l,a[i].r);
		ll tmp=a[i].l*a[i].r/2;
		bool ft=(tmp*2!=a[i].l*a[i].r);
		if (tmp>ans||(tmp==ans&&ft&&!fans)){
			ans=tmp;
			fans=ft;
		}
	}
	sort(a,a+n);
	ll maxn=0;
	for (int i=0;i<n;i++){
		ll tmp=a[i].l*min(a[i].r,maxn);
		if (tmp>ans){
			ans=tmp;
			fans=false;
		}
		maxn=max(maxn,a[i].r);
	}
	printf("%lld.%dn",ans,fans?5:0);
}
int main(){
	solve();
	return 0;
}

M

题意

给定一个长度为$n$的序列，其中只包含有字符$A,B$

一共$q$次查询，分两种

1 L R

代表将序列中$[L,R]$区间内的$A$修改为$B$，$B$修改为$A$

2 L R A B

从左往右遍历序列的$[L,R]$区间，遇到字符$A$则执行$A=A+B$，遇到字符$B$则执行$B=A+B$，并输出执行操作后$A,B$的值

题解

线段树维护矩阵乘法，跟利用矩阵快速幂计算斐波那契的思路一样

矩阵$A$为

1 0
1 1

矩阵$B$为

1 1
0 1

操作2结果就等于矩阵$bigl[begin{matrix} A&B end{matrix}bigr]$乘以区间矩阵积
操作1就是将修改区间$(0,0),(1,1)$位互换，$(0,1),(1,0)$位互换就行

时间复杂度：$mathcal{O} (8nlog 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
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
 
#include<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
const ll MOD=1e9+7;
struct Node {
	ll a[2][2];
	Node(){
		a[0][0]=1;
		a[0][1]=0;
		a[1][0]=0;
		a[1][1]=1;
	}
	Node(char c){
		a[0][0]=1;
		a[0][1]=0;
		a[1][0]=1;
		a[1][1]=1;
		if (c=='B')
			swap(a[0][1],a[1][0]);
	}
	Node operator*(const Node &A){
		Node t;
		t.a[0][0]=0;
		t.a[1][1]=0;
		for (int i=0;i<2;i++){
			for (int j=0;j<2;j++){
				for (int k=0;k<2;k++){
					t.a[i][j]+=a[i][k]*A.a[k][j]%MOD;
					t.a[i][j]%=MOD;
				}
			}
		}
		return t;
	}
	Node operator!(){
		swap(a[0][1],a[1][0]);
		swap(a[0][0],a[1][1]);
		return *this;
	}
};
struct M {
	ll a,b;
	M operator*(const Node &A){
		M t;
		t.a=(a*A.a[0][0]%MOD+b*A.a[1][0]%MOD)%MOD;
		t.b=(a*A.a[0][1]%MOD+b*A.a[1][1]%MOD)%MOD;
		return t;
	}
};
Node sg[400005];
bool lazy[400005];
char s[100005];
void pushup(int o){
	sg[o]=sg[Ls]*sg[Rs];
}
void update(int o){
	sg[o]=!sg[o];
	lazy[o]=!lazy[o];
}
void pushdown(int o){
	if (lazy[o]){
		update(Ls);
		update(Rs);
		lazy[o]=false;
	}
}
void build(int o,int l,int r){
	lazy[o]=false;
	if (l==r){
		sg[o]=Node(s[l]);
		return;
	}
	int mid=MID;
	build(Ls,l,mid);
	build(Rs,mid+1,r);
	pushup(o);
}
void change(int o,int l,int r,int L,int R){
	if (L<=l&&r<=R){
		update(o);
		return;
	}
	pushdown(o);
	int mid=MID;
	if (L<=mid)
		change(Ls,l,mid,L,R);
	if (R>mid)
		change(Rs,mid+1,r,L,R);
	pushup(o);
}
Node query(int o,int l,int r,int L,int R){
	if (L<=l&&r<=R)
		return sg[o];
	pushdown(o);
	int mid=MID;
	Node ans1,ans2;
	if (L<=mid)
		ans1=query(Ls,l,mid,L,R);
	if (R>mid)
		ans2=query(Rs,mid+1,r,L,R);
	ans1=ans1*ans2;
	return ans1;
}
void solve(){
	int n,q;
	scanf("%d%d%s",&n,&q,s+1);
	build(1,1,n);
	while (q--){
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		if (op==1)
			change(1,1,n,l,r);
		else {
			M t;
			scanf("%lld%lld",&t.a,&t.b);
			Node tmp=query(1,1,n,l,r);
			t=t*tmp;
			printf("%lld %lldn",t.a,t.b);
		}
	}
}
int main(){
	solve();
	return 0;
}

N

题意

给一棵以1节点为根的树，问树上各个节点为根的子树的重心

题解

代码

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
 
#include<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
struct Edge {
	int fr,to,nxt;
	Edge(){}
	Edge(int _f,int _t,int _n):fr(_f),to(_t),nxt(_n) {}
};
Edge a[300005];
int head[300005];
void build(int o,int fr,int to){
	a[o]=Edge(fr,to,head[fr]);
	head[fr]=o;
}
int ans[300005],sum[300005],fa[300005];
void dfs(int o){
	sum[o]=1;
	for (int i=head[o];i!=-1;i=a[i].nxt){
		int p=a[i].to;
		fa[p]=o;
		dfs(p);
		sum[o]+=sum[p];
	}
	ans[o]=o;
	for (int i=head[o];i!=-1;i=a[i].nxt){
		int p=a[i].to;
		if (sum[p]*2>sum[o])
			ans[o]=ans[p];
	}
	while ((sum[o]-sum[ans[o]])*2>sum[o])
		ans[o]=fa[ans[o]];
}
void solve(){
	int n,q;
	MS(head,-1);
	scanf("%d%d",&n,&q);
	for (int i=2;i<=n;i++){
		int fr;
		scanf("%d",&fr);
		build(i-2,fr,i);
	}
	dfs(1);
	while (q--){
		int t;
		scanf("%d",&t);
		printf("%dn",ans[t]);
	}
}
int main(){
	solve();
	return 0;
}

O

题意

题解

代码

1
2


P

题意

给出一个$ntimes m$的矩形，给每个格子涂上黑色或白色，相连的黑色和白色格子不能超过两个，问有多少种涂法

题解

除了一排全部都是黑白相间的情况以外，其他的涂色方法其实在涂完第一排就已经确定下来了，所以只用算涂一排的情况

接着考虑黑白相间的情况，可以发现在涂完第一列后其实整个涂色的方法同样也被确定下来了，所以再加上涂一列的情况

最后会出现两种情况重复了（所有格子都是黑白相间的两种情况），所以减去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
37
38
39
40
41
42
43
44
45
46
 
#include<bits/stdc++.h>
#define ll long long
#define MS(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define Ls o<<1
#define Rs o<<1|1
#define MID (r-l)/2+l
#define MP(a,b) make_pair(a,b)
using namespace std;
const ll MOD=1e9+7;
ll dp[100005][2][2];
void solve(){
	int n,m;
	scanf("%d%d",&n,&m);
	int l=max(n,m);
	dp[0][1][0]=1;
	dp[0][0][1]=1;
	dp[0][0][0]=0;
	dp[0][1][1]=0;
	for (int i=1;i<l;i++){
		for (int j=0;j<2;j++){
			for (int k=0;k<2;k++){
				if (j==k)
					dp[i][j][k]=dp[i-1][!j][j];
				else
					dp[i][j][k]=(dp[i-1][j][j]+dp[i-1][!j][j])%MOD;
			}
		}
	}
	ll ans=0;
	for (int i=0;i<2;i++){
		for (int j=0;j<2;j++){
			ans+=dp[n-1][i][j];
			ans%=MOD;
			ans+=dp[m-1][i][j];
			ans%=MOD;
		}
	}
	ans=((ans-2)%MOD+MOD)%MOD;
	printf("%lldn",ans);
}
int main(){
	solve();
	return 0;
}
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能