Educational Codeforces Round 134 (Rated for Div. 2)

比赛链接：https://codeforc.es/contest/1721

没参加比赛，之后补的题，有点难==。居然是教育周的题。做出来了两个题，第三个题有点没读明白。

A题：大意是给出四个字母，你每次可以操纵不超过两个相同颜色的字母，使得变成一个字母，求最少操作数。
直接分情况讨论，如果全部相同为0，有两种为1，三种为2，四种为3

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
set<char> se;
void solve()
{
	se.clear();
	string a,b;
	cin>>a>>b;
	for(int i=0;i<a.size();i++)
		se.insert(a[i]),se.insert(b[i]);
	if(se.size()==1) cout<<0<<endl;
	else if(se.size()==2) cout<<1<<endl;
	else if(se.size()==3) cout<<2<<endl;
	else cout<<3<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

B题：大意是在一个n*m的矩阵中，你需要从1,1 到 n，m ，存在一个障碍，且你和障碍之间的距离不能超过d，距离定义为 $| x_{1} - x_{2} | + | y_{1} - y_{2} |$ .求能否通过，且最少步数。

这个题做的有点拉了，更像是蒙对了。我们很容易得出，如果能够走到一定是n+m-2.那么问题就在于哪些情况走不到。
这里我定义方向为上下左右，如果堵死上下和左右一定走不到，因为你至少经过其中一个，如果堵死上左一定不到，因为你无法到达右下位置。
如果堵死右下那么也一定不到，因为你无法到达n，m

很难说明白，需要意会。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void solve()
{
	int n,m,a,b,d;
	cin>>n>>m>>a>>b>>d;
	if(a+d>=n&&a-d<=1||b+d>=m&&b-d<=1||a-d<=1&&b-d<=1||a+d>=n&&b+d>=m) cout<<-1<<endl;
	else cout<<n+m-2<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

C题：大意是给出一个有序数组a和一个经过排序后的数组b。你需要通过a来得到b，bi = a + di。这就意味着b是由某一个a来转变而来的。
求出每个di的最小值和最大值。

这里需要想到，最小值是离ai最近的大于等于它的bj，因为双方都有序，这里遍历一定能保证形成的b是有序的，因为j的大小是一个升序。最大值是离ai最远的一个大于等于它的bj。每遍历到一个 i ，j从 i 和 j中选一个最大的开始往后遍历，不用再管前面的数。
code：

#include<bits/stdc++.h>
using namespace std;
int t,n,a[200100],b[200100];
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)scanf("%d",&b[i]);
		int j=1;
		for(int i=1;i<=n;i++){
			while(b[j]<a[i])j++;
			cout<<b[j]-a[i]<<' ';
		}
		cout<<endl;
		j=1;
		for(int i=1;i<=n;i++){
			j=max(j,i);
			while(b[j]>=a[j+1]&&j<n)j++;
			cout<<b[j]-a[i]<<' ';
		}
		cout<<endl;
	}
}

搜索

标签

存档