首页 > 其他分享 >Codeforces Round 859 (Div. 4) 题解集

Codeforces Round 859 (Div. 4) 题解集

时间：2023-03-25 14:57:28浏览次数：58  
标签：ch int 题解 ll Codeforces long while Div getchar

目录
比赛链接

CF1807A Plus or Minus

题目链接

Description

给定 \(a,b,c\) 三个整数。

  • 若 \(a+b=c\)，输出 +。
  • 若 \(a-b=c\)，输出 -。

保证三个数的关系仅有上述两种。

Solution

判断两种情况即可。

分支结构题单

循环结构题单

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int a,b,c;
int main(){
	cin>>t;
	while(t--){ //循环结构
		cin>>a>>b>>c;
		if(a+b==c) cout<<"+"<<endl; //分支结构
		else cout<<"-"<<endl;
	}
	return 0;
}

CF1807B Grab the Candies

题目链接

Description

有 \(n\) 包糖果，每包有 \(a_i\) 糖果，如果该包糖果数是偶数，Mihai会拿走，否则 Bianca会拿走。

两人会按照顺序依次拿走 \(a_1,a_2\dots a_n\)，现在可以对数列重新排序，问是否存在一种情况，使得任意时刻 Mihai拿到的糖果数严格大于 Bianca拿到的。

Solution

我们可以将所有偶数排在数列前面，这样开始 \(k\)（\(k\) 为偶数的个数）包，Bianca的个数始终为零，最后 Bianca的个数为所有奇数之和（此时 Bianca的个数最大），与 Mihai的偶数之和比较即可。

即可转为奇数之和与偶数之和的大小比较。

注意，需严格大于（即两人数量相等是不行的）。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n=read();
	int cnt1=0,cnt2=0;
	for(int i=1;i<=n;i++){
		int x=read();
		if(x%2==0)cnt1+=x;
		else cnt2+=x;
	}
	if(cnt1>cnt2) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

CF1807C Find and Replace

题目链接

Description

给定一串长度为 \(n\) 的字符串 \(s\)，你可以将每种字母转为 \(0\) 或 \(1\)，将所有字母转换完后，问能否得到一串由 \(0\) 和 \(1\) 交替而成的字符串（即相邻两个字符不同）。

Solution

因为最终得到的是 01交替的字符串，说明相同字符的下标相距定为偶数，而相同字母转换后又定为同一字符，所以我们枚举每种字母，看当前字母与上次该字母出现的位置的下标是否相距偶数个即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int last[30];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	memset(last,-1,sizeof(last)); //last表示该字母上次出现的位置的下标，多测记得初始化
	int n=read();
	string s;
	cin>>s;
	for(int i=0;i<n;i++){
		int x=s[i]-'a'+1;
		if(last[x]!=-1){ //如果这不是该字母第一次出现
			if((i-last[x])%2==0){
				last[x]=i;
			}else{
				cout<<"NO"<<endl;
				return ;
			}
		}else last[x]=i;
	}
	cout<<"YES"<<endl;
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

CF1807D Odd Queries

题目链接

Description

对于长度为 \(n\) 的数列 \(a\)，有 \(q\) 次询问，每次给定 \(l,r,k\)，问将 \(a_l,a_{l+1}\dots a_r\) 全都转为 \(k\) 后，该数列的总和是否为奇数。

注意，每次操作对后续操作没有影响，即每次操作都是在原数列 \(a\) 上做操作。

Solution

我们将每次操作完后分为两部分：操作部分和未操作部分。

操作部分总和为 \((r-l+1)\times k\)，未操作部分为 \(sum_n-(sum_r-sum_{l-1})\)，其中\(sum_i\) 表示前 \(i\) 个数的总和。

前缀和在输入时即可得到。

最后将两部分加起来，看是否为奇数即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
ll sum[200200];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n=read(),q=read();
	sum[0]=0;
	for(int i=1;i<=n;i++){
		sum[i]=0;
		int x=read();
		sum[i]=sum[i-1]+x;//求得前缀和
	}
	while(q--){
		int l=read(),r=read(),k=read();
		ll i=sum[n]-(sum[r]-sum[l-1]),j=k*(r-l+1); //分为两部分
		if((i+j)%2==0){
			cout<<"NO"<<endl;
		}else{
			cout<<"YES"<<endl;
		}
	}
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

CF1807E Interview

题目链接

Description

director有 \(n\) 堆石头，其中 \(n-1\) 堆都只有重量为一克的石头，剩下一堆有则有一块有两克的石头和若干重量为一克的石头。

你的任务是在 \(30\) 次询问内推理出那一堆有重量为两克的石头是第几堆。

首先输入 \(n\)，接下来输入 \(n\) 个数 \(a_1,a_2\dots a_n\)，其中 \(a_i\) 表示第 \(i\) 堆有 \(a_i\) 块石头。

一共有 \(t\) 组数据。

每次询问你需要输出 ?这个符号，然后输出 $k $ 及 \(p_1,p_2\dots p_k\)（用空格隔开），表示询问 \(p_1,p_2\dots p_k\) 这 \(k\) 堆石头的总重量，然后你需要输入一个数 \(x\) 表示你刚刚询问得到的答案。

如果你推理出来答案，输出 !这个符号以及你得到的答案 \(m\)。

如果你的询问次数大于 \(30\) 次，或有非法的询问，将会得到 Wrong Answer评测结果。

记得每次输出后，都要输出一行代码来刷新缓冲区，否则会得到 Idleness limit exceeded评测结果或其他评测结果。

  • 对于 C++，输出 fflush(stdout)或 cout.flush()
  • 对于 Java，输出 System.out.flush()
  • 对于 Pascal，输出 flush(output)
  • 对于 Python，输出 stdout.flush()

Soluton

我们可以考虑运用二分的思想，每次选目标区间的前二分之一去询问，最多需要 \(\log_2 n\) 次，在给定范围内一定小于 \(30\)。

判断方法，若当前得到了第 \(l\) 到 \(r\) 堆的总重量，如果得到的答案等于 \(sum_r-sum_{l-1}\)，则目标堆不在这一区间内，否则反之，其中 \(sum_i=a_1+a_2+\dots+a_i\)。

具体步骤见代码。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
ll sum[200200];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n=read();
	sum[0]=0;
	for(int i=1;i<=n;i++){
		int x=read();
		sum[i]=0;
		sum[i]=sum[i-1]+x; //预处理求前缀和
	}
	int l=1,r=n;
	while(l<r){ //还没确定到具体堆的编号
		int mid=l+r>>1;
		cout<<"? "<<mid-l+1;
		for(int i=l;i<=mid;i++){ //取前二分之一
			cout<<" "<<i;
		}
		cout<<endl;
		fflush(stdout);
		int get=read();
		if(sum[mid]-sum[l-1]!=get){ //如果匹配不上说明目标堆在前半部分
			r=mid;
		}else l=mid+1; //否则在后半部分
	}
	cout<<"! "<<r<<endl;
	fflush(stdout); //记得刷新缓冲区
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

CF1807F Bouncy Ball

题目链接

Description

在一个 \(n\times m\) 的房间内有一个球，初始位置为 \((i_1,j_1)\)，目标位置为 \((i_2,j_2)\)，初始方向为字符串 \(d\)。

  • \(d=\texttt{UL}\)，向左上移动
  • \(d=\texttt{DR}\)，向右下移动
  • \(d=\texttt{DL}\)，向左下移动
  • \(d=\texttt{UR}\)，向右上移动

当小球碰到墙壁后会反弹，新的方向与旧方向以垂直与墙壁的一条线为轴对称。（见图）

当小球移到角落时会原地返回。

若小球会移到目标位置，问最少会反弹几次（碰到角落为一次），若无法移到，则输出 -1。

Solution

由于一共有 \(n\times m\) 个点，有四种移动方向，所以在移动最多 \(4\times n\times m\) 步后，每个点都会移到至少一遍。

然后模拟即可。

具体步骤见代码。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n=read(),m=read(),sx=read(),sy=read(),ex=read(),ey=read();
	int dx,dy,x=sx,y=sy,cnt=0;
	string s;
	cin>>s;
	if(s[0]=='D') dx=1;
	else dx=-1;
	if(s[1]=='L') dy=-1;
	else dy=1;
	ll lim=n*m*4;
	while(lim--){
		if(x==ex&&y==ey){ //移到目标点
			cout<<cnt<<endl;
			return ;
		}
		bool is=0;
		if(dx==1&&x==n){ //碰到下侧墙壁
			dx=-1;
			is=1;
		}
		if(dx==-1&&x==1){ //碰到上侧墙壁
			dx=1;
			is=1;
		}
		if(dy==1&&y==m){ //碰到右侧墙壁
			dy=-1;
			is=1;
		}
		if(dy==-1&&y==1){ //碰到左侧墙壁
			dy=1;
			is=1;
		}
		//碰到角落时，因为碰到两面墙壁，x和y都会取反
		if(is) cnt++; //有反弹
		x+=dx,y+=dy; //移动
	}
	cout<<-1<<endl;
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

扩展：CF724C Ray Tracing（该题也是类似于小球反弹，但做法完全不一样，我就是赛时被这题带偏的，此题难度较大，需要数论基础，有能力者可以做扩展）。

CF1807G1&G2 Subsequence Addition

easy version
hard version

Description

数列 \(a\) 最开始只有一个数 \(1\)，你可以进行若干次操作，每次操作你可以选取 \(k\) 个数（\(k\) 无限制，小于等于 \(a\) 的大小即可），将这 \(k\) 个数的和放入 \(a\) 的任意一个位置。

给定一个长度为 \(n\) 的序列 \(c\)，问 \(a\) 能否在进行若干次操作后转为 \(c\)。

有 \(t\) 组数据。

Solution

若当前进行了一次操作，则新加入的数大于当前最小的数（\(k=1\)），小于当前所有数的总和（\(k=n\)），所以我们对目标数列从小到大排序，若当前的数小于前面所有数的总和，说明这个数是可以实现的否则就不可能实现。

注意：目标序列至少要有一个 \(1\)。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t;
int a[5050];
ll read(){
    ll x=0,f=1;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void solve(){
	int n=read();
	ll sum=0;
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	sort(a+1,a+1+n);
	if(a[1]!=1){ //如果最小的不是1，说明该序列没有1（不可能有非正数）
		cout<<"NO"<<endl;
		return;
	}
	sum=1;
	for(int i=2;i<=n;i++){
		if(a[i]>sum){ //如果大于前缀和，则不可能实现
			cout<<"NO"<<endl;
			return ;
		}
		sum+=a[i];
	}
	cout<<"YES"<<endl;
}
int main(){
	t=read();
	while(t--){
		solve();
	}
	return 0;
}

标签：ch,int,题解,ll,Codeforces,long,while,Div,getchar
From： https://www.cnblogs.com/larryyu/p/17254735.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99