Codeforces Round #592 (Div.2)

Posted on | In

纪念一下人生首次$CF$翻车（雾

$A$

判断是否$\lceil \frac{a}{c}\rceil+\lceil\frac{b}{d}\rceil\leq k$即可

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int main () {
	register int T; scanf("%d",&T);
	while(T--) {
		register int a,b,c,d,f,g,k;
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		f=(a-1)/c+1,g=(b-1)/d+1;
		if(f+g>k) puts("-1");
		else printf("%d %d\n",k-g,g);
	}
	return 0;
}

$B$

如果没有楼梯使得上下两层房间连通，显然答案为$n$

如果有楼梯使得上下两层房间连通，可以考虑贪心

显然从两边往中间寻找楼梯，答案一定最优（雾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
char s[1001];
int main () {
	register int T; scanf("%d",&T);
	while(T--) {
		register int n,flag=false; scanf("%d%s",&n,s+1);
		for(register int i=0;i<=(n-1)/2;++i)
		    if(s[i+1]=='1'||s[n-i]=='1') {
		    	printf("%d\n",(n-i)<<1);
		    	flag=true; break ;
			}
		if(!flag) printf("%d\n",n);
	}
	return 0;
}

$C$

先吐槽一句这道题，真$TM$拖节奏+崩心态

一眼扩展欧几里得解同余方程，但是早就忘得差不多了

直接拿了之前的板子，大力调一波交上去就$WA$

发现可能会爆$long$ $long$，改成__$int128$怒提一发$CE$

最后改成暴力枚举就过了？？？不过最后评测的时候还是$TLE$

这道题前前后后总共花了大概$1h$，最后还没做出来

回过头来看看这道题，发现还是比较妙的

先扔一个结论，如果方程有解，那么在$y \leq w$范围内一定有解

考虑证明，假设存在$y’=aw+b(a \ge 1,0 \leq b < w)$使得$xw+y’d=p$

即$xw+(aw+b)d=xw+awd+bd=(x+ad)w+bd$

观察这个式子左右两项，左边的系数和为$x+aw+b$，右边的系数为$x+ad+b$

因为$w>d$，所以在$y \leq w$范围内$x+y$一定最小，得证

在$[0,w)$范围内枚举$y$，计算是否存在合法的$x$即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main () {
	register long long n,p,w,d,z=0;
	scanf("%lld%lld%lld%lld",&n,&p,&w,&d);
	for(register long long i=0;i<w;++i)
	    if((p-i*d)%w==0) {
	    	register long long x=(p-i*d)/w;
	    	if(x>=0&&x+i<=n) printf("%lld %lld %lld\n",x,i,n-x-i);
	    	else puts("-1"); z=1; break ;
		}
	if(!z) puts("-1");
	return 0;
}

$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
#include<bits/stdc++.h>
using namespace std;
const int maxn=200001;
long long ans,tmp;
int n,num,fir,seco,third;
int c[maxn],in[maxn],to[maxn],re[maxn];
int from[maxn],head[maxn],C[maxn][4];
inline void add (int u,int v) {
	from[++num]=head[u];
	to[num]=v;
	head[u]=num;
}
inline void dfs (int now,int fa,int pre) {
	c[now]=6-c[fa]-c[pre],tmp+=C[now][c[now]];
	if(ans>tmp&&in[now]==1) {
		for(register int i=1;i<=n;++i) re[i]=c[i];
		ans=tmp; return ;
	}
	for(register int i=head[now];i;i=from[i])
	    if(to[i]!=fa) dfs(to[i],now,fa);
}
int main () {
	scanf("%d",&n); ans=1e18;
	for(register int i=1;i<=n;++i) scanf("%d",&C[i][1]);
	for(register int i=1;i<=n;++i) scanf("%d",&C[i][2]);
	for(register int i=1;i<=n;++i) scanf("%d",&C[i][3]);
	for(register int i=1;i<n;++i) {
		register int u,v; scanf("%d%d",&u,&v);
		add(u,v),add(v,u); ++in[u],++in[v];
	}
	for(register int i=1;i<=n;++i)
	    if(in[i]>=3) { puts("-1"); return 0; }
	for(register int i=1;i<=n;++i)
	    if(in[i]==1) { fir=i; break ; }
	seco=to[head[fir]];
	for(register int i=head[seco];i;i=from[i])
	    if(to[i]!=fir) third=to[i];
	c[fir]=1,c[seco]=2,tmp=C[fir][c[fir]]+C[seco][c[seco]],dfs(third,seco,fir);
	c[fir]=1,c[seco]=3,tmp=C[fir][c[fir]]+C[seco][c[seco]],dfs(third,seco,fir);
	c[fir]=2,c[seco]=1,tmp=C[fir][c[fir]]+C[seco][c[seco]],dfs(third,seco,fir);
	c[fir]=2,c[seco]=3,tmp=C[fir][c[fir]]+C[seco][c[seco]],dfs(third,seco,fir);
	c[fir]=3,c[seco]=1,tmp=C[fir][c[fir]]+C[seco][c[seco]],dfs(third,seco,fir);
	c[fir]=3,c[seco]=2,tmp=C[fir][c[fir]]+C[seco][c[seco]],dfs(third,seco,fir);
	printf("%lld\n",ans);
	for(register int i=1;i<=n;++i) printf("%d ",re[i]);
	printf("\n");
	return 0;
}

$E$

将$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
#include<bits/stdc++.h>
using namespace std;
const int maxn=200001;
int a[maxn],b[maxn],c[maxn];
int main () {
	register int n; register long long K; scanf("%d%lld",&n,&K);
	for(register int i=1;i<=n;++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1); register int tot=0;
	for(register int i=1;i<=n;++i) {
		if(a[i-1]==a[i]) ++c[tot];
		else b[++tot]=a[i],++c[tot];
	}
	register int l=1,r=tot,L=c[l],R=c[r];
	while(l<r) {
		if(L<R) {
			register int tmp=b[l+1]-b[l];
			if((long long)L*tmp<=K)
				K-=(long long)L*tmp,L+=c[++l];
			else { b[l]+=K/L; break ; }
		}
		else {
			register int tmp=b[r]-b[r-1];
			if((long long)R*tmp<=K)
			    K-=(long long)R*tmp,R+=c[--r];
			else { b[r]-=K/R; break ; }
		}
	}
	printf("%d\n",b[r]-b[l]);
	return 0;
}

$F$

不难发现一些性质，对于每个点来说

如果它第一次不需要改变，那么它以后都不需要改变

如果它第$x(x \ge 2)$次不需要改变，那么它相邻的两个点第$x+1$次不需要改变

从第一次不需要改变的点开始递推，注意特判一些变化的情况即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
char s[200001];
int vis[200001];
queue < int > Q ;
int main () {
	register int k,n; scanf("%d%d%s",&n,&k,s);
	memset(vis,-1,sizeof(vis));
	for(register int i=0;i<n;++i)
	    if(s[i]==s[(i+n-1)%n]||s[i]==s[(i+1)%n]) vis[i]=0,Q.push(i);
	while(!Q.empty()) {
		register int x=Q.front(); Q.pop();
		if(vis[(x+n-1)%n]==-1) vis[(x+n-1)%n]=vis[x]+1,Q.push((x+n-1)%n);
		if(vis[(x+1)%n]==-1) vis[(x+1)%n]=vis[x]+1,Q.push((x+1)%n);
	}
	for(register int i=0;i<n;++i)
	    if(vis[i]==-1||vis[i]>k) (k&1)?putchar('B'+'W'-s[i]):putchar(s[i]);
		else (vis[i]&1)?putchar('B'+'W'-s[i]):putchar(s[i]);
	printf("\n");
	return 0;
}

$G$

考虑怎么构造排列使得$sum$最大/小

显然，当$p_i=q_i$时$sum$最小

贪心一下，发现当$p_i+q_i=n+1$时$sum$最大

如果$k<(n+1)*n/2$，那么无解

如果$k \ge (n+1)*n/2$，考虑如何构造一种合法方案

首先使$p_i=i,q_i=i$，那么当前的$sum=(n+1)*n/2$

贪心一下，每次在未被交换的值中选取最大的和最小的交换

这样交换，每次$sum$的增长一定最大

特判最后一次交换时$sum>k$的情况即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int p[1000001],q[1000001];
int main () {
	register int n; register long long k; scanf("%d%lld",&n,&k);
	register long long minl=(long long)(n+1)*n/2,maxn=(n&1)?-(n/2+1):0;
	for(register int i=n/2+1;i<=n;++i) maxn+=(i<<1);
	if(k<minl) { puts("-1"); return 0 ;}
	register long long ans=min(k,maxn),tmp=minl;
	for(register int i=1;i<=n;++i) p[i]=i,q[i]=i;
	for(register int i=n;i>(n+1)/2;--i) {
		register int x=(i<<1)-(n+1);
		if(ans>x+tmp) tmp+=x,swap(q[i],q[n-i+1]);
		else { swap(q[i],q[tmp-ans+i]); break ; }
	}
	printf("%lld\n",ans);
	for(register int i=1;i<=n;++i) printf("%d ",p[i]); printf("\n");
	for(register int i=1;i<=n;++i) printf("%d ",q[i]); printf("\n");
	return 0;
}