比赛链接 https://codeforces.com/contest/1365
比赛记录 https://blog.csdn.net/cheng__yu_/article/details/105395197

B. Trouble Sort

题意：给定 n 个元素的数组 a 。每个元素有两种类型：0和1。不同类型之间可以交换。问给定的数组能否，替换成非降形式的数列

思路：只要存在 0、1两种不同的类型，就可以交换成任何你想要的排列方式

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10,inf=2e9;int t,n;
int a[maxn];int main()
{cin>>t;while(t--){cin>>n;for(int i=1;i<=n;++i) cin>>a[i];bool f[2];f[0]=f[1]=0;for(int i=1;i<=n;++i){int x;cin>>x;f[x]=true;}if(f[0]&&f[1]){puts("Yes");}else{bool ok=1;for(int i=2;i<=n;++i){if(a[i-1]>a[i])ok=0;}puts(ok?"Yes":"No");}}return 0;
}

C. Rotation Matching

题意：给定两个长度为 n 的数组 a 和 b 。可以对 a 数组进行循环移动，问最多有多少对 a[i]=b[i]。
思路：同一个数的距离之差相等

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;int n;
int a[maxn],b[maxn];
int pos1[maxn],pos2[maxn];int main()
{cin>>n;for(int i=1;i<=n;++i){cin>>a[i];pos1[a[i]]=i;}for(int i=1;i<=n;++i){cin>>b[i];pos2[b[i]]=i;}map<int,int> mp;for(int i=1;i<=n;++i){int d=(pos1[i]-pos2[i]+n)%n;mp[d]++;}int ans=0;for(auto i : mp){ans=max(ans,i.second);}printf("%d\n",ans);return 0;
}

D. Solve The Maze

题意：给定一张 $n\times m$ 的图，图上有好人（记为G）和坏人（记为B），出口在（n，m）。现在可以将一些空白的位置’,‘改成墙’#’。问能否让所有的好人都到达出口，而坏人无法逃脱
思路：将坏人周围的空白位置改成墙，然后从（n，m）开始dfs，看能否走遍好人的位置，并且不会走到坏人的位置。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;int t,n,m;
char mp[100][100];
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int ok;
int visit[60][60];void dfs(int x,int y)
{for(int i=0;i<=3;++i){int nx=x+dx[i];int ny=y+dy[i];if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[nx][ny]!='#'&&!visit[nx][ny]){if(mp[nx][ny]=='G')mp[nx][ny]='.';if(mp[nx][ny]=='B'){ok=0;}visit[nx][ny]=1;dfs(nx,ny);}}
}int main()
{cin>>t;while(t--){cin>>n>>m;for(int i=1;i<=n;++i)scanf("%s",mp[i]+1);bool exist=0;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(mp[i][j]=='B'){if(i>1&&mp[i-1][j]=='.')mp[i-1][j]='#';if(i<n&&mp[i+1][j]=='.')mp[i+1][j]='#';if(j>1&&mp[i][j-1]=='.')mp[i][j-1]='#';if(j<m&&mp[i][j+1]=='.')mp[i][j+1]='#';}if(mp[i][j]=='G')exist=1;}}if(mp[n][m]=='#'&&!exist){puts("Yes");continue;}ok=1;memset(visit,0,sizeof(visit));dfs(n,m);if(ok){bool finds=0;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(mp[i][j]=='G')finds=1;if(finds)ok=0;}puts(ok?"Yes":"No");}return 0;
}

E. Maximum Subsequence Value

题意：给定 n 个元素的数组 a。从中选取 k 个数，如果这 k 个数的第 i 位至少有 max(1,k-2)个数为 1 ，则贡献增加 $2^i$，求最大贡献

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10,inf=2e9;
int n;
ll a[maxn];int main()
{cin>>n;for(int i=1;i<=n;++i) cin>>a[i];ll ans=0;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)for(int k=1;k<=n;++k)ans=max(ans,a[i]|a[j]|a[k]);cout<<ans<<"\n";return 0;
}

F. Swaps Again（思维）

题意：给定两个长度为 n 的数组 a 和 b。可以对 a 进行操作，将 a 的前 k 个和 a 的后 k 个进行交换，问最终能否将 a 数组变成 b 数组

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=500+10,inf=2e9;
int t,n;
int a[maxn],b[maxn];int main()
{cin>>t;while(t--){cin>>n;for(int i=1;i<=n;++i) cin>>a[i];for(int i=1;i<=n;++i) cin>>b[i];bool ok=1;if(n&1&&a[n/2+1]!=b[n/2+1])ok=0;map<pair<int,int>,int> mp;for(int i=1;i<=n/2;++i){if(a[i]>a[n-i+1]) swap(a[i],a[n-i+1]);mp[{a[i],a[n-i+1]}]++;}for(int i=1;i<=n/2;++i){if(b[i]>b[n-i+1]) swap(b[i],b[n-i+1]);pair<int,int> p={b[i],b[n-i+1]};if(mp[p]<=0)ok=0;mp[p]--;}puts(ok?"Yes":"No");}return 0;
}