首页 CF题解

# Codeforces Round 913 (Div. 3)A~F

比赛链接

# A. Rook

# 题目大意

给出国际棋盘中车的位置，求该车一步能走到的位置（车可以横向或纵向移动任意步数）

# 思路

模拟

# 代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
	int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=9;
int awa[maxn][maxn];
signed main()
{
	int t=read();
	while(t-->0)
	{
		string awa;cin>>awa;
		for(int i=1;i<=8;i++)
		{
			if(awa[1]-'0'!=i) cout<<awa[0]<<i<<endl;
		}
		for(char i='a';i<='h';i++)
		{
			if(awa[0]!=i) cout<<i<<awa[1]<<endl;
		}
	}
	return _123hh2;
}

# B. YetnotherrokenKeoard

# 题目大意

给出一个字符串，模拟输入操作，当遇到 BB 时删除先前最后输入的大写字母，遇到 bb 时删除先前最后输入的小写字母，若没有则视为不操作，求最后的字符串

# 思路

模拟，先将这个字符串的每个位置状态记为 11 ，对于需要删除的大小写字母，我们可以用两个数组分别记录，碰到 B,bB,b 时将最后进入数组的大小写字母状态置为 00 ，最后再扫描一下这个字符串即可

# 代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
	int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e6+11;
int x[maxn],d[maxn];
bool judge[maxn];
void init(int q)
{
	for(int i=0;i<=q;i++) x[i]=0,d[i]=0,judge[i]=1;
}
signed main()
{
	int t=read();
	while(t-->0)
	{
		string awa;cin>>awa;
		init(awa.length());
		int cntx=0,cntd=0;
		for(int i=0;i<awa.length();i++)
		{
			if(awa[i]>='a'&&awa[i]<='z'&&awa[i]!='b') x[++cntx]=i;
			if(awa[i]>='A'&&awa[i]<='Z'&&awa[i]!='B') d[++cntd]=i;
			if(awa[i]=='B'&&cntd) judge[d[cntd]]=0,cntd--;
			if(awa[i]=='b'&&cntx) judge[x[cntx]]=0,cntx--;
		}
		for(int i=0;i<awa.length();i++)
		{
			if(judge[i]&&awa[i]!='B'&&awa[i]!='b') cout<<awa[i];
		}
		cout<<endl;
	}
	return _123hh2;
}

# C. Removal of Unattractive Pairs

# 题目大意

给你一个长度为 nn 的字符串，你可以将这个字符串任意两个不相同的字母从这个字符串中删除，求这个字符串可能的最小长度

# 思路

贪心

字符串最后不能删除的情况有三种

  • 字符串为空
  • 字符串只剩一个字母
  • 字符串剩余的字母都是相同的

所以我们可以找出该字符串中出现次数最多的那个字母，尽可能将这个字母先删除完即可

# 代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
	int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=27;
int tong[maxn];
void init() {for(int i=0;i<26;i++) tong[i]=0;}
signed main()
{
	int t=read();
	while(t-->0)
	{
		int n=read();init();string awa;cin>>awa;
		for(int i=0;i<awa.length();i++) tong[awa[i]-'a']++;
		int maxx=0;
		for(int i=0;i<26;i++) maxx=max(maxx,tong[i]);
		if(n%2==0)
		{
			if(n-maxx>=maxx) puts("0");
			else write(2*maxx-n),puts("");
		}
		else
		{
			if(n-maxx>=maxx) puts("1");
			else write(2*maxx-n),puts("");
		}
	}
	return _123hh2;
}

# D. Jumping Through Segments

# 题目大意

给出 nn 条线段，每个线段都在数轴上，左右端点为 li,ril_i,r_i ，现有一玩家从坐标 00 出发，每次都能移动不超过 kk 的距离，且第 ii 次移动过后必须落在第 ii 个线段上，求 kk 可能的最小值

# 思路

二分

不难发现 kk 的取值满足二分答案的性质，所以我们可以对 kk 进行二分

如何判断一个 kk 是否合法？

我们可以维护两个值 nowl,nowrnowl,nowr 表示当前所能到达的最左和左右位置，再模拟每次移动更新两个值即可

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
	int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=2e5+1;
struct A {int l,r;}awa[maxn];
bool judge(int k,int n)
{
	int nowl=0,nowr=0;
	for(int i=1;i<=n;i++)
	{
		if(awa[i].l>nowr+k||awa[i].r<nowl-k) return 0;
		if(awa[i].l>=nowl-k&&awa[i].r<=nowr+k) {nowl=awa[i].l,nowr=awa[i].r;continue;}
		if(awa[i].l<=nowl-k&&awa[i].r>=nowr+k) {nowl-=k,nowr+=k;continue;}
		if(awa[i].r>=nowl-k&&awa[i].r<=nowr+k) {nowl-=k,nowr=awa[i].r;continue;}
		if(awa[i].l>=nowl-k&&awa[i].l<=nowr+k) {nowl=awa[i].l,nowr+=k;continue;}
	}
	return 1;
}
signed main()
{
	int t=read();
	while(t-->0)
	{
		int n=read();
		for(int i=1;i<=n;i++) awa[i].l=read(),awa[i].r=read();
		int l=0,r=1e9;
		while(l!=r)
		{
			int mid=(l+r)/2;
			if(judge(mid,n)) r=mid;
			else l=mid+1;
		}
		write(l),puts("");
	}
	return _123hh2;
}

# E. Good Triples

# 题目大意

给出一个数 nn ，求有多少个 (a,b,c)(a,b,c) 满足

  • a+b+c=na+b+c=n
  • digsum(a)+digsum(b)+digsum(c)=digsum(n)digsum(a)+digsum(b)+digsum(c)=digsum(n)

其中 digsum(x)digsum(x) 的值为数 xx 每位的数之和

# 思路

将 nn 按位进行拆分，令 a,b,ca,b,c 的对应位之和等于 nn 的对应位

这样可以保证上述两条规则成立，不难发现每位都是互相独立的，所以最终答案就是每位的方案数之乘

对于每位数的方案数，相当于 nn 个球放入三个编号不同的盒子，允许盒子为空的方案数

# 代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
	int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
int num[10]={1,3,6,10,15,21,28,36,45,55};
int div(int x)
{
	int sum=1;
	while(x)
	{
		sum*=num[x%10];x/=10;
	}
	return sum;
}
signed main()
{
	int t=read();
	while(t-->0)
	{
		int n=read();
		write(div(n)),puts("");
	}
	return _123hh2;
}

# F. Shift and Reverse

# 题目大意

给出一个长度为 nn 的数组，现有两种操作

  • 移位：将数组的最后一个元素移到首位，并将所有其他元素向右移动
  • 反转：将整个数组反转

求将该数组变成非递减排序的最小操作次数，否则输出 −1-1

# 思路

贪心 + 模拟

我们发现，将数组看成首尾衔接的环，对于两个操作来说是不会改变环上每个元素的位置的

所以判断是否有解可以看从某个位置出发顺序访问的值是否递增 / 递减即可

# 代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
	int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e5+1;
int awa[maxn<<1];
signed main()
{
	int t=read();
	while(t-->0)
	{
		int n=read(),ans=1e9;
		for(int i=1;i<=n;i++) awa[i]=read(),awa[i+n]=awa[i];
		for(int i=1;i<=n;i++)
		{
			int now=i,cnt=1;
			while(awa[i]>=awa[i+1]&&i<2*n) i++,cnt++;
			if(cnt>=n) ans=min(now,n-now+2);
		}
		for(int i=1;i<=n;i++)
		{
			int now=i,cnt=1;
			while(awa[i]<=awa[i+1]&&i<2*n) i++,cnt++;
			if(cnt>=n) ans=min(min(ans,now+1),n-now+1);
			if(cnt>=n&&now==1) ans=0;
		}
		if(ans!=1e9) write(ans),puts("");
		else puts("-1");
	}
	return _123hh2;
}
更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

123hh2 微信支付

微信支付

123hh2 支付宝

支付宝

123hh2 贝宝

贝宝