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;
}

本栏目推荐文章
• NSSCTF Round#16 Basic WriteUp
• AT_arc125_c [ARC125C] LIS to Original Sequence 题解
• P5321 [BJOI2019] 送别 题解--zhengjun
• P9007 [入门赛 #9] 最澄澈的空与海 (Hard Version) 题解
• P2198 杀蚂蚁 题解
• P3243 [HNOI2015] 菜肴制作 题解
• AT_abc243_g [ABC243G] Sqrt题解
• AT_abc243_g [ABC243G] Sqrt题解
• P9754 题解
• AT_arc167_e 题解

题解 Codeforces Round 859 Divcodeforces round 859 div 题解codeforces round 859 题解codeforces div round 题解codeforces round div2 codeforces queries round 859 题解codeforces round div3 codeforces round 911 div codeforces round 864 div codeforces round 887 div codeforces round 863 div