526互联

AtCoder Regular Contest 166 AB题题解

发布时间 2023-10-09 00:11:38作者: 尹昱钦

A - Replace C or Swap AB

个人感觉挺有意思的一道思维题（好久没做思维题了，竟然卡了一个小时）。

除去C不看，我们发现X序列中的A只能向后移动，B只能向前移动，且可以移动任意次数。

所以假如没有C的话，做法是这样的：

从前往后分别统计X和Y序列中的A的数目，若某一时刻发现X中A的数量小于Y了，那么就直接No，因为A只能向后移动。

同理，从后往前统计判断B的数量也是等价的。

现在加上C，考虑这两种情况：

  • 若Y中某一位是C，而X中该位置不是C：直接No，因为不存在一个操作让X的某一位变成C。
  • 若X和Y中的某一位都是C：则该位置可以理解为一个断点，该位置左右两部分的判断互不干涉。（在代码中会看到每一部分都分别去判断）
  • 若X中的一位是C，而Y中该位置不为C：那么C肯定要变成A或者B，根据没有C时候的结论（A只能向后移动，B只能向前移动），最优策略即为将靠前的C变成A，靠后的变成B即可。

具体操作起来可以不去真的变，直接把C全部变成A/B，然后分别从前/后统计判断A/B数量即可。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<unordered_set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
string a,b;
bool check(int l,int r){
	if(r<l) return 1;
	int cnta=0,cntb=0;
	for(int i=r;i>=l;i--){
		if(a[i]=='B'||a[i]=='C') cnta++;
		if(b[i]=='B') cntb++;
		if(cnta<cntb) return 0;
	}
	cnta=0,cntb=0;
	for(int i=l;i<=r;i++){
		if(a[i]=='A'||a[i]=='C') cnta++;
		if(b[i]=='A') cntb++;
		if(cnta<cntb) return 0;
	}
	return 1;
}
int main()
{
    ios::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--){
		int ok=1,n,lst=0;
		cin>>n>>a>>b;
		for(int i=0;i<n;i++){
			if(b[i]=='C'){
				if(a[i]!='C'){
					ok=0;
					break;
				}else{
					if(!check(lst,i-1)){
						ok=0;
						break;
					}else{
						lst=i+1;
					}
				}
			}
		}
		if(!check(lst,n-1))  ok=0;
		if(ok) cout<<"Yes\n";
		else cout<<"No\n";
	} 

    return 0;
}

B - Make Multiples

我们观察到只有 \(abc\) 三个数，所以情况数非常少：

  1. 把一个数变成 \(abc\) 的最小公倍数的倍数
  2. 把两个数分别变成一个数的倍数、另外两个数的最小公倍数的倍数
  3. 把三个数分别变成三个数的倍数

对于第 \(1\) 种情况，把每一个 \(A_i\) 修改的代价算出来，最小值就是答案。

对于第 \(2\) 种情况，把每一个 \(A_i\) 修改的代价分别算出来，答案取各自最小的两个代价中的一个（因为有可能两个最小代价都是修改同一个位置）。

对于第 \(3\) 种情况，同理，计算后排序，答案肯定取各自三个最小代价中的一个。

复杂度 \(O(n)\)

因为 \(n\) 不是很大，所以我们可以直接省事用 \(sort\) 解决问题 （\(O(nlogn)\) 也可以接受）。

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<unordered_set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
const int maxn=200005;
struct node{
	long long va;
	int id;
}m1[maxn],m2[maxn],m3[maxn];
int n;
long long d[maxn];
bool cmp(node a,node b){
	return a.va<b.va;
}
long long gcd(long long a,long long b){
	if(b==0) return a;
	return gcd(b,a%b);
}
long long work1(long long x){
	long long res=1e18+5;
	for(int i=1;i<=n;i++){
		res=min(res,x-((d[i]-1)%x+1));
	}
	return res;
}
long long work2(long long x,long long y){
	for(int i=1;i<=n;i++){
		m1[i].va=x-((d[i]-1)%x+1),m1[i].id=i;
		m2[i].va=y-((d[i]-1)%y+1),m2[i].id=i;
	}
	sort(m1+1,m1+n+1,cmp);
	sort(m2+1,m2+n+1,cmp);
	if(m1[1].id!=m2[1].id) return m1[1].va+m2[1].va;
	return min(m1[1].va+m2[2].va,m1[2].va+m2[1].va);
}
long long work3(long long x,long long y,long long z){
	for(int i=1;i<=n;i++){
		m1[i].va=x-((d[i]-1)%x+1),m1[i].id=i;
		m2[i].va=y-((d[i]-1)%y+1),m2[i].id=i;
		m3[i].va=z-((d[i]-1)%z+1),m3[i].id=i;
	}
	sort(m1+1,m1+n+1,cmp);
	sort(m2+1,m2+n+1,cmp);
	sort(m3+1,m3+n+1,cmp);
	long long res=1e18+5;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(m1[i].id==m2[j].id) continue;
			for(int k=1;k<=3;k++){
				if(m1[i].id==m3[k].id) continue;
				if(m2[j].id==m3[k].id) continue;
				res=min(res,m1[i].va+m2[j].va+m3[k].va);
			}
		}
	}
	return res;
}
int main()
{
    ios::sync_with_stdio(false);
    long long a,b,c;
	cin>>n>>a>>b>>c;
	for(int i=1;i<=n;i++) cin>>d[i];
	long long x1=a/gcd(a,b)*b,x2=b*c/gcd(b,c),x3=a*c/gcd(a,c),x4=x1*c/gcd(x1,c);
	long long ans=work1(x4);
	if(n>2) ans=min(work3(a,b,c),ans);
	if(n>1) ans=min(ans,min(min(work2(x2,a),work2(x3,b)),work2(x1,c)));
	cout<<ans;
    return 0;
}

比赛总结

明显思维能力下降了，A题竟然卡了一个多小时。以后要多打比赛。

ksun48 在119:57（比赛结束前3秒）的时候交了一发最后一题且A掉了，拿下rank2，估计手速慢了submit都点不上吧，燃起来了。