比赛链接: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,距离定义为 .求能否通过,且最少步数。
这个题做的有点拉了,更像是蒙对了。我们很容易得出,如果能够走到一定是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;
}
}