A

选择一个点\(B(x,0)\)使得\(|dis(A,B)-x|=k.\)

题目实际上就是找到一个最接近\(n\)的数，使得它可以分成两个数\(a,b,\)使\(a-b=k.\)

我们考虑先分成一个可能的最小的数：\(0+k.\)这时两边\(+2\)就可以保证一定可以分成两个数\(a,b\)使得\(a-b=k.\)

那么我们直接对\(n-k\)的奇偶性讨论即可。如果\(k>n\)直接输出\(k-n\)即可。

#include<bits/stdc++.h>

using namespace std;

int T,n,k;

int main(){

	scanf("%d",&T);

	while(T--){

		scanf("%d%d",&n,&k);

		if(k>n)printf("%d\n",k-n);

		else{

			if((n-k)&1)puts("1");

			else puts("0");

		}

	}

	return 0;

}

B

考虑贪心：\(a\)中的\(2\)先消耗\(b\)中的\(1,\)剩下的用\(a\)中的\(0\)尽量消耗。剩下的\(a\)中的\(1\)和\(b\)中的\(2\)匹配即可。

#include<bits/stdc++.h>

using namespace std;

int T;

int a[4],b[4];

int main(){

	scanf("%d",&T);

	while(T--){

		int ans=0;

		scanf("%d%d%d",&a[0],&a[1],&a[2]);

		scanf("%d%d%d",&b[0],&b[1],&b[2]);

		int num=min(a[2],b[1]);

		ans+=2*num;a[2]-=num,b[1]-=num;

		num=min(a[0],b[2]);a[0]-=num,b[2]-=num;

		num=min(a[0],b[1]);a[0]-=num,b[1]-=num;

		num=min(a[0],b[0]);a[0]-=num,b[0]-=num;

		//a[0]finish

		num=min(a[1],b[1]);a[1]-=num;b[1]-=num;

		num=min(a[1],b[0]);a[1]-=num,b[0]-=num;

		num=min(a[2],b[2]);a[2]-=num;b[2]-=num;

		num=min(a[1],b[2]);ans-=num*2,a[1]-=num,b[2]-=num;

		cout<<ans<<endl;

	}

	return 0;

}

C

由于题目中说的是最大公约数的序列中的最小数，且不会改变数字。所以，我们直接把可以换位置的数提出来，排好序再插进去，看看操作完的序列是不是单调不降序列即可。

#include<bits/stdc++.h>

using namespace std;

int T,n,a[200010],vis[200010];

int main(){

	scanf("%d",&T);

	while(T--){

		scanf("%d",&n);

		int fg=0,mi=(1<<30);

		for(int i=1;i<=n;++i){

			scanf("%d",&a[i]);

			mi=min(mi,a[i]);

		}

		for(int i=2;i<=n;++i){

			if(a[i]<a[i-1]){

				fg=1;

				break;

			}

		}

		if(!fg){

			puts("YES");

			for(int i=1;i<=n;++i)vis[i]=a[i]=0;

			continue;

		}

		fg=0;

		for(int i=1;i<=n;++i){

			if(a[i]%mi==0)vis[i]=1;

		}

		vector<int>v;v.clear();

		for(int i=1;i<=n;++i){

			if(vis[i])v.push_back(a[i]);

		}

		sort(v.begin(),v.end());

		vector<int>rev;rev.clear();

		while((int)v.size()){

			rev.push_back(v.back());

			v.pop_back();

		}

		for(int i=1;i<=n;++i){

			if(vis[i])a[i]=rev.back(),rev.pop_back();

		}

		for(int i=2;i<=n;++i){

			if(a[i]<a[i-1]){

				fg=1;

				break;

			}

		}

		if(fg)puts("NO");

		else puts("YES");

		for(int i=1;i<=n;++i)a[i]=vis[i]=0;

	}

	return 0;

}

D

考虑贪心。因为给出了\(k\)的质因数分解结果，所以贪心显然思路是出现次数最大的边对应最大的质因子。

如果质因子数量小于\(n-1\)就补\(1,\)若大于则把最大的合并起来。

然后一遍\(dfs\)预处理\(siz\),注意次数\(siz*(n-siz)\)不能取模。这样会使得排序结果错误。

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int mod=1e9+7;

inline int add(int x,int y){return (x+y)%mod;}

inline int mul(int x,int y){return 1ll*x*y%mod;}

const int MAXN=2e5+10;

int siz[MAXN],tot,head[MAXN],S;

struct edge{

	int nxt,to;

}e[MAXN];

inline void link(int x,int y){

	e[++tot].to=y;e[tot].nxt=head[x];

	head[x]=tot;

}

int T,n,m,p[MAXN],ts[MAXN],t;

void dfs(int x,int fa){

	siz[x]=1;

	for(int i=head[x];i;i=e[i].nxt){

		int j=e[i].to;

		if(j==fa)continue;

		dfs(j,x);siz[x]+=siz[j];

		ts[++t]=siz[j]*(n-siz[j]);

		S++;

	}

}

void debug(){

	for(int i=1;i<n;++i)cout<<p[i]<<" ";

	puts("");

	for(int i=1;i<=t;++i)cout<<ts[i]<<" ";

	cout<<endl;

	for(int i=1;i<=n;++i)cout<<siz[i]<<" ";

	puts("");

	cout<<"*"<<S<<endl;

}

signed main(){

	scanf("%lld",&T);

	while(T--){

		scanf("%lld",&n);int ans=0;t=0,S=0;

		for(int i=1;i<n;++i){

			int x,y;

			scanf("%lld%lld",&x,&y);

			link(x,y);link(y,x);

		}

		dfs(1,0);

		sort(ts+1,ts+t+1);reverse(ts+1,ts+t+1);

		scanf("%lld",&m);

		for(int i=1;i<=m;++i)scanf("%lld",&p[i]);

		while(m<n-1)p[++m]=1;

		sort(p+1,p+m+1);

		if(m>n-1){for(int i=n;i<=m;++i)p[n-1]=mul(p[n-1],p[i]);}

		reverse(p+1,p+n);

		for(int i=1;i<n;++i)ans=add(ans,mul(ts[i],p[i]));

		printf("%lld\n",ans);

		tot=0;for(int i=1;i<=n;++i)head[i]=0,siz[i]=0;

		for(int i=1;i<n;++i)ts[i]=0;

		for(int i=1;i<=m;++i)p[i]=0;

	}

	return 0;

}

巴特西

【比赛记录】8.21 div2

A

B

C

D

最新文章

热门文章