Codeforces Round #592 (Div.2)

发表于 | 更新于 | 分类于 | 阅读次数：

赛场上被C题打自闭了。

A Pen and Pencil

讨论两组数相除向上取整是否小于铅笔盒的容量。

B Rooms and Staircases

题目描述

有两层楼梯，一层有$N$个房间，房间是互通的。输入一串01串，1表示当前房间可以通向楼上或者楼下。问一次不走回头路的走法最多可以到达几个房间。

Solution

手玩样例即可发现，如果在最左边和最右边的房间有楼梯，显然是可以走完$2N​$也就是所有的房间。这个楼梯每往中间缩一格，就会少到达2个房间。讨论楼梯对于答案的最大价值$T​$。$T​$就应该是离最左边或者最右边较小的那个值。用$(N-T+1)2​$便得到结果。

C Football Season

题目描述

给定四个数$n,p,d,w$$(d\ge w)$

求三个合理解$(x,y,z)$，其中$x,y,z\ge0$

使得

$xw+yd=p$

$x+y+z=n$

Solution

一开始拿扩欧做的。后来发现不好处理正整数解这一点。

后来采取暴力方法。

考虑到$d\ge w$所以把$p$分为几个$lcm(d,w)$大小的块，全部分配给$x$，最后余留的部分和1个$lcm$去暴力枚举$x$的取值，判断对应$y$是否有正整数解。

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
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
namespace Sonoda
{
	template<typename T> void swap(T &a,T &b)
	{
		T t;
		t=a;
		a=b;
		b=t;
	}
	template<typename T> T GCD(T a,T b)
	{
		if(b==0)
		{
			return a;
		}
		return GCD(b,a%b);
	}
	template<typename T>T Qpow(T a,T b,T p)
	{
		T res=1;
		while(b)
		{
			if(b&1)
			{
				res*=a;
				res%=p;
				b--;
			}
			else
			{
				a*=a;
				a%=p;
				b>>=1;
			}
		}
		return res;
	}
	template <typename T> void Ex_GCD(T a,T b,T &x,T &y)
	{
		if(b==0)
		{
			x=1;
			y=0;
			return;
		}
		Ex_GCD(b,a%b,x,y);
		T t=x;
		x=y;
		y=t-a/b*y;
	}
	template<typename T> inline T read()
	{
		T num = 0, w = 1;
		char c = 0;
		while (c != '-' && !isdigit(c)) c = getchar();
		if (c == '-') w = -1, c = getchar();
		while (isdigit(c)) num = num * 10 + c - '0', c = getchar();
		return num * w;
	}
	template<typename T> inline void write(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x / 10) write(x / 10);
		putchar(x % 10 + '0');
	}
}
long long cnt;
int main()
{
	long long a,b,c,d;
	a=Sonoda::read<long long>();
	b=Sonoda::read<long long>();
	c=Sonoda::read<long long>();
	d=Sonoda::read<long long>();
	long long gcd=Sonoda::GCD(c,d);
	long long lcm=c*d/gcd;
	long long blo=max(0LL,b/lcm-1);
	long long w,l,dr;
	w=lcm/c*blo;
	long long lef=b-blo*lcm;
	for(long long i=0;i<=a-w;i++)
	{
		if((lef-i*c)%d==0&&(lef-i*c)/d+w+i<=a)
		{
			dr=(lef-i*c)/d;
			if(w>=0&&dr>=0&&a-w-dr>=2)
			{
				printf("%lld %lld %lld",w+i,dr,a-w-i-dr);
				return 0;
			}
		}
		if(i>=10000000)
		{
			break;
		}
	}
	printf("-1");	
	return 0;
	
}

D Paint the Tree

题目描述

给定一棵节点数为$N$的无向树，对于每一个节点，有三种染色，每种染色所需要的代价为$V_{i,j},i\in{1,2,3},j\in[1,N]$。对于一颗树，一个合法的染色方法必须使得对于任意三元组$(x,y,z)$，其中$x$与$y$相连，$y$与$z$相连，保证$x,y,z$三者的颜色互不相同。问是否有合法染色方案，如果有，给出最小代价。

Solution

对性质进行分析，发现如果存在一个点有三个及以上的出度，显然不成立。所以，一个点最多只有两条出边。又因为原图为一棵树，所以一定是一条链。找到链首，以及第二个元素，枚举他们两者的颜色方案，此时整条链的染色方案也就定了下来，判断最小代价并在路径上存储答案即可。

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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
#include <bits/stdc++.h>
#include <climits>
#define INF INT64_MAX
using namespace std;
namespace Sonoda
{
	template<typename T> void swap(T &a,T &b)
	{
		T t;
		t=a;
		a=b;
		b=t;
	}
	template<typename T> T GCD(T a,T b)
	{
		if(b==0)
		{
			return a;
		}
		return GCD(b,a%b);
	}
	template<typename T>T Qpow(T a,T b,T p)
	{
		T res=1;
		while(b)
		{
			if(b&1)
			{
				res*=a;
				res%=p;
				b--;
			}
			else
			{
				a*=a;
				a%=p;
				b>>=1;
			}
		}
		return res;
	}
	template <typename T> void Ex_GCD(T a,T b,T &x,T &y)
	{
		if(b==0)
		{
			x=1;
			y=0;
			return;
		}
		Ex_GCD(b,a%b,x,y);
		T t=x;
		x=y;
		y=t-a/b*y;
	}
	template<typename T> inline T read()
	{
		T num = 0, w = 1;
		char c = 0;
		while (c != '-' && !isdigit(c)) c = getchar();
		if (c == '-') w = -1, c = getchar();
		while (isdigit(c)) num = num * 10 + c - '0', c = getchar();
		return num * w;
	}
	template<typename T> inline void write(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x / 10) write(x / 10);
		putchar(x % 10 + '0');
	}
}
const long long MAXN=1000006;
struct EDGE
{
	long long _next,to,from;
};
EDGE edge[MAXN];
long long head[MAXN],_count;
void Add_Line(long long a,long long b)
{
	_count++;
	edge[_count].to=b;
	edge[_count]._next=head[a];
	head[a]=_count;
}
long long outd[MAXN];
long long v1[MAXN],v2[MAXN],v3[MAXN];
long long pre[MAXN];
long long book[MAXN];
long long DFS(long long NowNode,long long color,long long lastcolor,long long fa)
{
	long long res=0;
	if(color==1)
	{
		res+=v1[NowNode];
	}
	if(color==2)
	{
		res+=v2[NowNode];
	}
	if(color==3)
	{
		res+=v3[NowNode];
	}
	for(long long i=head[NowNode];i;i=edge[i]._next)
	{
		long long NextNode=edge[i].to;
		if(fa==NextNode)
		{
			continue;
		}
		if(color==1&&lastcolor==2)
		{
			res+=DFS(NextNode,3,1,NowNode);
		}
		if(color==2&&lastcolor==1)
		{
			res+=DFS(NextNode,3,2,NowNode);
		}
		if(color==1&&lastcolor==3)
		{
			res+=DFS(NextNode,2,1,NowNode);
		}
		if(color==2&&lastcolor==3)
		{
			res+=DFS(NextNode,1,2,NowNode);
		}
		if(color==3&&lastcolor==1)
		{
			res+=DFS(NextNode,2,3,NowNode);
		}
		if(color==3&&lastcolor==2)
		{
			res+=DFS(NextNode,1,3,NowNode);
		}
	}
	return res;
}
void Get_Ans(long long NowNode,long long color,long long lastcolor,long long fa)
{
	if(color==1)
	{
		book[NowNode]=1;
	}
	if(color==2)
	{
		book[NowNode]=2;
	}
	if(color==3)
	{
		book[NowNode]=3;
	}
	for(long long i=head[NowNode];i;i=edge[i]._next)
	{
		long long NextNode=edge[i].to;
		if(fa==NextNode)
		{
			continue;
		}
		if(color==1&&lastcolor==2)
		{
			Get_Ans(NextNode,3,1,NowNode);
		}
		if(color==2&&lastcolor==1)
		{
			Get_Ans(NextNode,3,2,NowNode);
		}
		if(color==1&&lastcolor==3)
		{
			Get_Ans(NextNode,2,1,NowNode);
		}
		if(color==2&&lastcolor==3)
		{
			Get_Ans(NextNode,1,2,NowNode);
		}
		if(color==3&&lastcolor==1)
		{
			Get_Ans(NextNode,2,3,NowNode);
		}
		if(color==3&&lastcolor==2)
		{
			Get_Ans(NextNode,1,3,NowNode);
		}
	}
}
int main()
{
	long long N;
	N=Sonoda::read<long long>();
	for(long long i=1;i<=N;i++)
	{
		scanf("%I64d",v1+i);
	}
	for(long long i=1;i<=N;i++)
	{
		scanf("%I64d",v2+i);
	}
	for(long long i=1;i<=N;i++)
	{
		scanf("%I64d",v3+i);
	}	
	for(long long i=1;i<N;i++)
	{
		long long a=Sonoda::read<long long>();
		long long b=Sonoda::read<long long>();
		outd[a]++;
		outd[b]++;
		if(a<b)
		{
			swap(a,b);
		}
		Add_Line(a,b);
		Add_Line(b,a);
		pre[a]=b;
		pre[b]=a;
		if(outd[a]>2||outd[b]>2)
		{
			printf("-1");
			return 0;
		}
	}//必为链 
	long long st=0;
	for(long long i=1;i<=N;i++)
	{
		if(outd[i]==1)
		{
			st=i;
		}
	}
	long long nx=pre[st];
	long long ans=INF;
	long long now=v1[st]+DFS(nx,2,1,st);
	if(ans>now)
	{
		ans=now;
		Get_Ans(nx,2,1,st);
		book[st]=1;
	}
	now=v1[st]+DFS(nx,3,1,st);
	if(ans>now)
	{
		ans=now;
		Get_Ans(nx,3,1,st);
		book[st]=1;
	}
	now=v2[st]+DFS(nx,1,2,st);
	if(ans>now)
	{
		ans=now;
		Get_Ans(nx,1,2,st);
		book[st]=2;
	}
	now=v2[st]+DFS(nx,3,2,st);
	if(ans>now)
	{
		ans=now;	
		Get_Ans(nx,3,2,st);
		book[st]=2;
	}
	now=v3[st]+DFS(nx,1,3,st);
	if(ans>now)
	{
		ans=now;
		Get_Ans(nx,1,3,st);
		book[st]=3;
	}
	now=v3[st]+DFS(nx,2,3,st);
	if(ans>now)
	{
		ans=now;
		Get_Ans(nx,2,3,st);
		book[st]=3;
	}
	printf("%I64d\n",ans);
	for(long long i=1;i<=N;i++)
	{
		printf("%I64d ",book[i]);
	}
	return 0;
}

E Minimizing Difference

题目描述

给定$N$个数的序列与$K$次操作，其中，一次操作可以将某一个数$+1$或者$-1$。问在最多$K$次操作后，这$N$个数中的最大值与最小值的最小差是多少。

Solution

首先，很显然的贪心性质：要让最小的变大，最大的变小才会对答案有贡献。

那么考虑是让小的变大还是让大的变小。

先按大小排序，然后用两个指针从两头向中间扫，如果遇到和当前值相同的，就将每次需要付出的代价++，每跳到下一个数，便比较是最小的少，还是最大的少。选择少的去进行操作。

如果离下一个数太远不能到达，就尽可能往前走。

代码细节比较多，注意实现。

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
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
namespace Sonoda
{
	template<typename T> void swap(T &a,T &b)
	{
		T t;
		t=a;
		a=b;
		b=t;
	}
	template<typename T> T GCD(T a,T b)
	{
		if(b==0)
		{
			return a;
		}
		return GCD(b,a%b);
	}
	template<typename T>T Qpow(T a,T b,T p)
	{
		T res=1;
		while(b)
		{
			if(b&1)
			{
				res*=a;
				res%=p;
				b--;
			}
			else
			{
				a*=a;
				a%=p;
				b>>=1;
			}
		}
		return res;
	}
	template <typename T> void Ex_GCD(T a,T b,T &x,T &y)
	{
		if(b==0)
		{
			x=1;
			y=0;
			return;
		}
		Ex_GCD(b,a%b,x,y);
		T t=x;
		x=y;
		y=t-a/b*y;
	}
	template<typename T> inline T read()
	{
		T num = 0, w = 1;
		char c = 0;
		while (c != '-' && !isdigit(c)) c = getchar();
		if (c == '-') w = -1, c = getchar();
		while (isdigit(c)) num = num * 10 + c - '0', c = getchar();
		return num * w;
	}
	template<typename T> inline void write(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x / 10) write(x / 10);
		putchar(x % 10 + '0');
	}
}
typedef long long fhk;
const int MAXN=100005;
fhk a[MAXN];
fhk N,K;
fhk ans;
fhk nowl,nowr;
int main()
{
	N=Sonoda::read<fhk>();
	K=Sonoda::read<fhk>();
	for(int i=1;i<=N;i++)
	{
		a[i]=Sonoda::read<fhk>();
	}
	sort(a+1,a+1+N);
	fhk l=1;
	fhk r=N;
	nowl=1;
	nowr=1;
	fhk res=K;
	fhk lef=0;
	while(l<r&&res)
	{
		while(l<r&&a[l]==a[l+1])
		{
			nowl++;
			l++;
		}
		while(l<r&&a[r]==a[r-1])
		{
			nowr++;
			r--;
		}
		if(nowl<=nowr)
		{
			fhk cha=a[l+1]-a[l];
			if(res>=cha*nowl)
			{
				res-=cha*nowl;
				l++;
				nowl++;
			}
			else if(res<cha*nowl)
			{
				lef=res/nowl;
				res=0;
			}
			continue;
		}
		if(nowl>nowr)
		{
			fhk cha=a[r]-a[r-1];
			if(res>=cha*nowr)
			{
				res-=cha*nowr;
				r--;
				nowr++;
			}
			else if(res<cha*nowr)
			{
				lef=res/nowr;
				res=0;
			}
			continue;
		}
	}
	printf("%I64d",a[r]-a[l]-lef);
	return 0;
}