Codeforces Round #706 (Div. 2) 全部题解

2024-01-28 15:17:40

题目链接：https://codeforces.com/contest/1496

文章目录

A. Split it!

暴力，贪心
题目大意为给定一个字符串与数字k，要求判断能否将该字符串拆分成s=a1+a2+…+ak+ak+1+R(ak)+R(ak−1)+…+R(a1)的形式，其中R(ai)为ai的翻转形式。
考虑到R(ai)与ai为翻转关系，若将ai与R(ai)拼接，则结果为一个回文串，由题意得将s拆分的结果中ai与R(ai)处于对称的位置，所以除去中间的ak+1，其余部分均满足回文结构。从s两边往中间搜索满足回文结构的最长字符串长度，若长度大于等于k，则可以将前n个字符赋值给a1到ak，剩下的中间部分赋值给ak+1，否则不存在构造方式。

#include<bits/stdc++.H>
#define ll long long
#define next next_
#define y1 yy
#define set set_
using namespace std;
int _,n,k;
string s;
void work(){
	scanf("%d%d",&n,&k);
	cin>>s;
	int i;
	for(i=0;i<(n-1)/2;i++)
		if(s[i]!=s[n-i-1]) break;
	if(i<k) printf("NO\n");
	else printf("YES\n");
}
int main(){
	scanf("%d",&_);
	while(_--){
		work();
	}
	return 0;
}

B. Max and Mex

贪心，数学
题目大意为给定一个非负整数数列，进行k次操作，每次将(max+mex)/2加入到数列中，求k次之后数列中不同的数字个数，max为数列中最大值，mex为数列中从小到大第一个不存在的数。
若mex小于max，则每次加入的(max+mex)/2在mex与max之间，加入前后max与mex均不变，k次操作与1次操作的结果相同操作一次后计数一次即可。若mex大于max，则只有可能是mex=max+1的情况，每次操作之后数列元素加1，k次操作后数列元素增加了k个，输出n+k即可。
注意判断k==0的情况。

#include<bits/stdc++.H>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
ll _,n,k,a[100010];
void work(){
	set<ll> s;
	scanf("%lld%lld",&n,&k);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),s.insert(a[i]);
	sort(a+1,a+1+n);
	ll i,maxn=(*s.rbegin()),mexn;
	for(i=1;i<=n;i++)
		if(a[i]!=i-1){
			mexn=i-1;
			break;
		}
	if(i==n+1) printf("%lld\n",n+k);
	else{
		if(k){
			s.insert((maxn+mexn)/2+((maxn+mexn)%2!=0));
			printf("%lld\n",(ll)s.size());
		}
		else printf("%lld\n",(ll)s.size());
	}
}
int main(){
	scanf("%lld",&_);
	while(_--){
		work();
	}
	return 0;
}

C. Diamond Miner

贪心，排序
题目大意为给定n个在y轴上的矿工坐标与n个在x轴上的钻石坐标，将矿工与钻石一一配对，求各个矿工与所配对的钻石之间的距离的总和的最小值。
对于任意的两对坐标轴上的点，有两种情况，计算可得第二种情况下两段线段长度和小于第一种情况。
Codeforces Round #706 (Div. 2) 全部题解
Codeforces Round #706 (Div. 2) 全部题解
对于任意一个矿工与钻石，将其坐标关于原点对称后，其两点之间的距离不会改变，所以在输入时只需存放所有坐标的绝对值，再将两个坐标轴上的坐标按升序排序，并按排序后的下标一一配对即可。

#include<bits/stdc++.H>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
ll _,n;
double ans;
double dis(ll x,ll y){
	return sqrt(x*x+y*y);
}
void work(){
	ans=0;
	vector<ll> a,b;
	scanf("%lld",&n);
	for(ll i=1,x,y;i<=2*n;i++){
		scanf("%lld%lld",&x,&y);
		if(!x) a.push_back(abs(y));
		else b.push_back(abs(x));
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	for(ll i=0;i<n;i++) ans+=dis(a[i],b[i]);
	printf("%.10lf\n",ans);
}
int main(){
	scanf("%lld",&_);
	while(_--){
		work();
	}
	return 0;
}

D. Let’s Go Hiking

博弈
题目大意为Qingshan与Daniel在玩游戏，Qingshan先手，给定一个排列，两个人先后选定一个位置作为自己的起点。Qingshan每次一移动可以向相邻并且比自己小的数字移动，Daniel每次一移动可以向相邻并且比自己大的数字移动，最后不能移动的一方输。要求求出能使Qingshan胜利的初始位置数目。
因为Qingshan先手并且只能往数字小的方向走，假设我们选取了一段单调递增或者递减的位置作为Qingshan的起点，则Daniel可以将初始位置选取在Qingshan周围较小的数字上，Qingshan必输。
所以Qingshan的初始位置一定只能选取在“山峰”的最高点，我们记录所有数字大小先增后减的片段，用一个pair存储每个片段中最高点能向两边行走的最大步数。
考虑每一个山峰，若最高点向左右两边所能行走的最大步数不同，则Daniel可以将初始位置设置在较长一边距离最高点最远且与最高点之间相隔距离为偶数的位置，在这种情况下Qingshan若往较短一边行走则必输，若往较长一边行走，因为与Daniel相隔距离为偶数，Qingshan为先手，所以在两人相遇时Qingshan不能行走，也必输。
所以Qingshan获胜的情况只能是一个片段中最高点向左右两边所能行走的最大步数相等的情况。
若一个片段中最高点向左右两边所能行走的最大步数为奇数，则Daniel可以将初始位置设置在任意一边的最底部，和上一种情况同理，Qingshan无论朝哪个方向走都必输。
若一个片段中最高点向左右两边所能行走的最大步数为偶数，若除去该片段后，其余部位的最长上升（下降）子串长度都小于该片段中Qingshan能够走的最大步数，则无论若Daniel将初始位置设置在该片段的哪一个位置，Qingshan都必胜，反之Daniel可以将初始位置设置在该片段外的一个长度更长的子串底部，Qingshan必输。
所以只需记录所有数字大小先增后减的片段，找出向左右行走最大步数相等的片段并记录这个步数大小，再判断除去这个片段后剩余部分的最大上升（下降）子串长度与这个最大步数的大小即可。

#include<bits/stdc++.H>
#define ll long long
#define next next_
#define y1 yy
#define pii pair<int,int>
using namespace std;
int _,n,a[100010],ans,vis[100010];
void work(){
	ans=0;
	vector<int> q,d;
	vector<pii> sum;
	vector<int> b;
	int maxn=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);a[0]=a[n+1]=1e9+7;
	for(int i=2;i<=n-1;i++)
		if(a[i]>a[i-1]&&a[i]>a[i+1]) q.push_back(i);
		else if(a[i]<a[i-1]||a[i]<a[i+1]) d.push_back(i);
	for(auto i:q){
		int l=1e9+7,r=0;
		for(int j=i;j>=1;j--){
			if(a[j-1]<a[j]) maxn=max(maxn,i-j);
			else{
				l=min(l,i-j);
				r=max(r,i-j);
				maxn=max(maxn,i-j);
				break;
			}
		}
		for(int j=i;j<=n;j++){
			if(a[j]>a[j+1]) maxn=max(maxn,j-i);
			else{
				l=min(l,j-i);
				r=max(r,i-j);
				maxn=max(maxn,j-i);
				break;
			}
		}
		sum.push_back(make_pair(l,r));
	}
	maxn=0;
	for(auto i:sum)
		if(i.first==i.second) maxn=max(maxn,i.first);
	if(maxn==0||maxn==1){
		printf("0");
		return;
	}
	for(int i=0;i<sum.size();i++){
		if(sum[i].first==sum[i].second&&sum[i].first==maxn){
				sum.erase(sum.begin()+i);
				break;
		}
	}
	int ss=0;
	int t=1;
	a[n+1]=0;
	for(int i=1;i<=n;i++){
		if(a[i]<a[i+1]);
		else{
			b.push_back(i-t);
			t=i+1;
		}
	}
	t=1;a[n+1]=1e9+7;
	for(int i=1;i<=n;i++){
		if(a[i]>a[i+1]);
		else{
			b.push_back(i-t);
			t=i+1;
		}
	}
	sort(b.begin(),b.end());
	if(b[b.size()-1]>maxn){
		printf("0");
		return;
	}
	else ss=b[b.size()-3];
	if(ss<maxn&&maxn%2==0) ans++;
	printf("%d",ans);
}
int main(){
//	scanf("%d",&_);
	_=1;
	while(_--){
		work();
	}
	return 0;
}

E. Garden of the Sun

贪心，构造
题目大意为给定一个矩阵，其中有若干个’X’，每个’X’周围8个格子中不会有其他’X’相邻，要求将矩阵中的若干个’.‘变成’X’，使得所有的’X’相互连接且矩阵中没有由’X’构成的环。
题面翻译即为构造一棵树连接所有的’X’，若将矩阵中的其中一行全部变为’X’，则这行与这行相邻的上下两行之间的’X’全部相互连接，因为任意两个’X’之间不相邻，所以不必担心将一行全部变为’X’后会出现形如
. X X .
XXXX
的情况 。
若考虑每隔两行将一行全部变为’X’，如下
XXXXXXXXXX
. . . . . . . . . . . .
. . . . . . . . . . . .
XXXXXXXXXX
. . . . . . . . . . . .
. . . . . . . . . . . .
XXXXXXXXXX
. . . . . . . . . . . .
. . . . . . . . . . . .
XXXXXXXXXX
则所有的’X’都被任意一行所连接,接下来只需将所有全部为’X’的行连接起来。
遍历一遍每一行，若存在形如
XXX
. X .
. . .
. X .
的情况，则将顶部的’X’延伸出来，若不存在这种情况，则任取一个位置构造上下两个’X’连接上下两行。
注意特判只有一行或一列的情况，与最底部没有一行全部为’X’的情况。

#include<bits/stdc++.H>
#define ll long long
#define next next_
#define y1 yy
#define pii pair<int,int>
using namespace std;
int _,n,m;
char a[510][510];
void work(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
	if(n==1||m==1){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++) a[i][j]='X';
			for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) printf("%c",a[i][j]);
			printf("\n");
		}
		return;
	}
	for(int i=1;i<=n;i+=3)
		for(int j=1;j<=m;j++) a[i][j]='X';
	if(n%3==0){
		for(int i=1;i<n;i+=3){
			if(i+3>=n){
				for(int j=1;j<=m;j++)
					if(a[i+2][j]=='X') a[i+1][j]='X';
				break;
			}
			bool ok=false;
			for(int j=1;j<=m;j++){
				if(a[i+1][j]=='X'||a[i+2][j]=='X'){
					a[i+1][j]=a[i+2][j]='X';
					ok=true;
					break;
				}
			}
			if(!ok) a[i+1][1]=a[i+2][1]='X';
		}
	}
	else{
		for(int i=1;i<n;i+=3){
			if(i+3>n) break;
			bool ok=false;
			for(int j=1;j<=m;j++){
				if(a[i+1][j]=='X'&&a[i+2][j]=='X'){
					ok=true;
					break;
				}
			}
			if(ok) continue;
			else{
				ok=false;
				for(int j=1;j<=m;j++){
					if(a[i+1][j]=='X'||a[i+2][j]=='X'){
						a[i+1][j]=a[i+2][j]='X';
						ok=true;
						break;
					}
				}
				if(!ok) a[i+1][1]=a[i+2][1]='X';
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) printf("%c",a[i][j]);
		printf("\n");
	}
}
int main(){
	scanf("%d",&_);
	while(_--){
		work();
	}
	return 0;
}

F. BFS Trees

最短路，数学
题目大意为给定一个无向图，定义一颗基于节点x的BFS树为：树上所有节点与节点x之间的距离等于原图中该节点与节点x的最短距离。现要求求出对于给定的图，同时基于图上任意两点x，y的BFS树的个数。
对于给定两点x，y，因为BFS树中所有节点到节点x，y的距离等于图上的最短距离，所以对于任意在节点x与y之间的节点z，其一定满足dis[x][z]+dis[z][y]=dis[x][y]，并且该节点的数目应恰好等于dis[x][y]+1，若不满足，则不存在基于节点x，y的BFS树。
若满足上述条件，因为树可以根据其所有节点到根节点的距离分成若干个层次，我们可以将节点x，y与节点x，y之间的所有节点看作为第0层，向外的任意相邻两层节点i，j（i比j小一层）应满足关系dis[x][j]=dix[x][i]+1与dis[y][j]=dix[y][i]+1，对于该条件中的每一个j，其必定有一条且只能有一条边连向它的上一层，这条边可能的种类数为j连向它的上一层的边的数目，我们可以遍历所有不在x，y之间的节点，记录每个节点所连出的边中指向它的上一层的边的数目，根据乘法计数原理，将每个节点指向它的上一层的边的数目相乘即可。

#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
ll n,m,u[1210],v[1210],next[1210],first[1210],dis[410][410],f[410][410];
ll head,tail,h[410];
const ll mod=998244353;
void bfs(ll t){
    head=0;
    tail=1;
    h[tail]=t;
    dis[t][t]=0;
    while(head<tail){
        head++;
        ll k=first[h[head]];
        while(k!=-1){
            if(dis[t][h[head]]+1<dis[t][v[k]]){
                dis[t][v[k]]=dis[t][h[head]]+1;
                h[++tail]=v[k];
            }
            k=next[k];
        }
    }
}
int main(){
    memset(first,-1,sizeof(first));
    memset(dis,0x7f,sizeof(dis));
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++){
        scanf("%lld%lld",&u[2*i-1],&v[2*i-1]);
        u[2*i]=v[2*i-1];v[2*i]=u[2*i-1];
        next[2*i-1]=first[u[2*i-1]];
        first[u[2*i-1]]=2*i-1;
        next[2*i]=first[u[2*i]];
        first[u[2*i]]=2*i;
    }
    for(ll i=1;i<=n;i++) bfs(i);
    for(ll x=1;x<=n;x++){
        for(ll y=x;y<=n;y++){
            ll cnt=0,ans=1;
            for(ll i=1;i<=n;i++) if(dis[x][i]+dis[i][y]==dis[x][y]) cnt++;
            if(cnt!=dis[x][y]+1) continue;
            for(ll i=1;i<=n;i++){
                if(dis[x][i]+dis[i][y]!=dis[x][y]){
                    ll k=first[i],sum=0;
                    while(k!=-1){
                        if(dis[x][i]==dis[x][v[k]]+1&&dis[y][i]==dis[y][v[k]]+1) sum++;
                        k=next[k];
                    }
                    ans=ans*sum%mod;
                }
            }
            f[x][y]=f[y][x]=ans;
        }
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++) printf("%lld ",f[i][j]);
        printf("\n");
    }
    return 0;
}
上一篇：二、描述统计(descriptive statistics)


下一篇：AI：2020年6月22日北京智源大会演讲分享之09:50-10:40 Anil教授《Pattern Recognition: Statistics to Pattern Recognition》