CodeforcesRound#648(Div.2)ABCDEF题解一只酷酷光儿的博客-

首先

Cue一下队友链接：

核心选手：https://me.csdn.net/qq_43559193

核心选手：https://me.csdn.net/weixin_43916298

比赛链接:https://codeforces.ml/contest/1362

目录

A. Matrix Game

题目大意:

题目思路：

Code:

B. Trouble Sort

题目大意：

题目思路：

Code:

C. Rotation Matching

题目大意：

题目思路：

D. Solve The Maze

题目大意:

题目思路：

Code:

E. Maximum Subsequence Value

题目大意：

题目思路：

Code:

F. Swaps Again

题目大意：

题目思路：

Code:

A. Matrix Game

题目大意:

两个人玩游戏，每个人可以放石子，放石子的要求是当且仅当 该行或者该列没有石子，不能放石子的人失败。

给出初始棋盘布局

双方都采取最优策略，问谁会赢？

题目思路：

博弈论嘛。

再结合这个题是A题，肯定不是太难的博弈。

必输态很容易，就是没有行与列可以，所以看一下行与列的最小值

判断一下奇偶性就可以了

Code:

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=1e9+7; const double eps=1e-15; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p; ll mp[105][105]; int main(){     int T;scanf("%d",&T);     while(T--){         read(n);read(m);         for(int i=1;i<=n;i++){             for(int k=1;k<=m;k++)                 read(mp[i][k]);         }         ll ans = 0,ans1 = 0;         for(int i=1;i<=n;i++){             ll p = 0;             for(int k=1;k<=m;k++){                 if(mp[i][k]) break;                 if(k == m) ans++;             }         }         for(int k=1;k<=m;k++){             for(int i=1;i<=n;i++){                 if(mp[i][k]) break;                 if(i == n) ans1++;             }         }         ll temp = min(ans,ans1);         if(temp&1) printf("Ashishn");         else printf("Vivekn");     }     return 0; } /** 1[2[a]3[b]4[1[b]2[c]]] aabbb[bccb **/ 

B. Trouble Sort

题目大意：

给出一个a数组与b数组，ai与aj可以交换当且仅当bi!=bj 

b数组只包含0、1

问能否通过若干次交换后使得a数组单调不下降

题目思路：

首先明白一个结论：01同时存在一定可以(老结论了，不信可以证明一下：所有交换的元素都可以通过一个元素进行交换，实现两者的交换)

没有01同时存在的话，只能看原数组是否有序了

Code:

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=1e9+7; const double eps=1e-15; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p; ll a[maxn],b[maxn]; struct node{     ll w;     int id; }save[maxn]; int main(){     int T;scanf("%d",&T);     while(T--){         read(n);         int f = 0;         a[0] = -1;         for(int i=1;i<=n;i++){             read(a[i]);             if(a[i]<a[i-1]) f = 1;         }         ll f1 = 0,f2 = 0;         for(int i=1;i<=n;i++){             read(b[i]);             if(b[i]) f1++;             else f2++;         }        // debug(f1);        // debug(f2);         if(!f1||!f2){             if(f) printf("Non");             else printf("Yesn");         }         else printf("Yesn");     }     return 0; } /** 1[2[a]3[b]4[1[b]2[c]]] aabbb[bccb **/ 

C. Rotation Matching

题目大意：

给出a，b两个数组，每次使得a向左或者向右移动k位(k取任意值)，问最大能有多少个ai = bi

题目思路：

首先，由于没有规定移动位数的限制，所以向右移动可以代替向左移动

所以控制b不变，使得a向右移动，此时最多移动n-1位，超过n-1位就为一个循环节了

所以看一下每个数字可以移动多少位才能与b中的数字对应

最后求移动位数贡献的最大值，就是数字个数了

一个经验:做过很多全排列的题、基本都跟位置有关系，因为全排列 位置 -> 值 是一个一一映射

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=1e9+7; const double eps=1e-15; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p; ll a[maxn],b[maxn]; int pos[maxn]; int val[maxn]; int main(){     read(n);     for(int i=1;i<=n;i++) read(a[i]);     for(int i=1;i<=n;i++){         read(b[i]);         pos[b[i]] = i;     }     for(int i=1;i<=n;i++){         int temp = pos[a[i]];         if(temp>=i) val[temp-i]++;         else val[n-i+temp]++;     }     int maxl = 0;     for(int i=0;i<=n-1;i++){         maxl = max(maxl,val[i]);     }     printf("%dn",maxl);     return 0; } /** 1[2[a]3[b]4[1[b]2[c]]] aabbb[bccb **/

D. Solve The Maze

题目大意:

给出一张地图，G是好人，B是坏人，.是空地，#是墙，终点是n,m

问能否让一些点变为墙，从而使得所有的好人都能到达终点，而所有的坏人都到达不了终点。

题目思路：

考虑把坏人封锁起来，然后看所有好人能否到达终点即可

如何封锁是个问题、这里也是莽了一下，首先贪心的去想，如果要对好人的影响最小，那么封锁的范围应该最小。

所以首先考虑 B 能否到达终点，如若不到达终点不需要封锁

到达终点的话，莽了一下，封锁相邻的四个点。

然而过了，有没有大佬可以证明一下这是正确的，评论区可以讨论(我感觉有一种方案，封锁下出口，而不封锁上出口，因为上出口到达不了，然而此时封锁上出口会使得有一个好人不过，就这种情况，不知道我想复杂了还是怎么)

封锁之后，再看一下所有好人是否都可以到就可以了

Code:

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=1e9+7; const double eps=1e-15; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p; char mp[105][105]; int visp[55][55]; int vis[55][55]; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int judge(int x,int y){     if(x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]!='#') return 1;     return 0; } int bfs(int sx,int sy){     queue<pair<int,int>>q;     for(int i=1;i<=n;i++){         for(int k=1;k<=m;k++){             vis[i][k] = 0;         }     }     if(mp[sx][sy] == '#') return 0;     q.push({sx,sy});     vis[sx][sy] = 1;     while(!q.empty()){         auto u = q.front();q.pop();         int x = u.first,y = u.second;         for(int i=0;i<4;i++){             int mx = x+dx[i],my = y+dy[i];             if(judge(mx,my)&&!vis[mx][my]){                 q.push({mx,my});                 vis[mx][my] = 1;             }         }     }     return vis[n][m]; } int main(){     int T;scanf("%d",&T);     while(T--){         read(n);read(m);         memset(visp,0,sizeof(visp));         for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);         bfs(n,m);         for(int i=1;i<=n;i++){             for(int k=1;k<=m;k++){                 if(mp[i][k] == 'B'&&vis[i][k]) visp[i][k] = 1;             }         }         int f = 0;         for(int i=1;i<=n;i++){             for(int k=1;k<=m;k++){                 if(visp[i][k]){                     for(int j=0;j<4;j++){                         int mx = i +dx[j],my = k+dy[j];                         if(judge(mx,my)){                             if(mp[mx][my] == 'G') f = 1;                             mp[mx][my] = '#';                         }                     }                 }             }         }         bfs(n,m);         for(int i=1;i<=n;i++){             for(int k=1;k<=m;k++){                 if(mp[i][k]=='G'&&!vis[i][k]) f = 1;             }         }         if(f) printf("Non");         else printf("Yesn");     }     return 0; } /** 3 011 100 111 **/ 

E. Maximum Subsequence Value

题目大意：

要求你选出一段子序列，假设长度为k，将这个子序列的个元素二进制拆分。

如果第i位上的1的个数 >= max(k-2,1) 那么该位就会贡献 2^i

问子序列的最大贡献是多少？

题目思路：

k只可以取1、2、3

这里证明一下：

其实1 2 3显然成立，所以只需要证明大于3的不会产生比1 2 3大的贡献即可

如果一段序列 在第i位上不满足，那么如果扩充元素的个数，新增元素在该位只能是0或者1

如果是0，序列长度增加1，限制条件max(k-2,1)也增加1，但是该位没有增加，所以不会产生贡献

如果是1，序列长度增加1，限制条件max(k-2,1)也增加1，该位增加+1，因为之前不满足，所以现在也不满足

所以，对于长度为3的子序列来说，如果想要在其上面扩充元素，满足的一定还满足，不满足的一定还是不满足，所以扩充是没有用的。

所以只需要考虑1、2、3的情况

Code:

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=1e9+7; const double eps=1e-15; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p; ll num[maxn]; ll c[65]; vector<int>v; int main(){     read(n);      ll maxl = 0;     for(int i=1;i<=n;i++){         read(num[i]);         maxl = max(maxl,num[i]);         for(int k=0;k<=62;k++) c[k] += ((num[i]>>k&1)?1:0);     }     for(int i=1;i<=n;i++){         for(int k=i+1;k<=n;k++){             maxl = max(maxl,num[i]|num[k]);         }     }     for(int i=1;i<=n;i++){         for(int k=i+1;k<=n;k++){             for(int j=k+1;j<=n;j++){                 maxl =max(maxl,((num[i]|num[k])|num[j]));             }         }     }     printf("%lldn",maxl);     return 0; } /** 3 011 100 111 **/

F. Swaps Again

题目大意：

给出a数组和b数组，每次可以对a数组进行操作，将前k个与后k个交换(k<n/2)。

问若干次交换后能否得到数组b

题目思路：

这个应该是规律或者结论题？

首先要发现一个性质：如果x和y对称，那么无论怎么交换依然对称。

1 2 5 6 :1对应6 ，2对应5

交换后：

5 6 1 2：1依然对应6，2依然对应5

所以我们就只需要看一下b数组的对应关系，如果a数组可以满足这所有的对应关系，那么每组对应关系无论怎么交换都是可以得到的

所以只需要考虑一下对称性判断就好了，怎么判断对称性呢？

a_i太大了，但是n确很小，所以考虑把a_i离散化，用一个二维数组来标记一下

a[x][y]标记一下x对应y的关系有多少个

看a中的关系能否全部满足即可：此时注意关系是双向的，需要双向判断

Code:

 /*** keep hungry and calm CoolGuang!***/ #pragma GCC optimize(2) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include <bits/stdc++.h> #include<stdio.h> #include<queue> #include<algorithm> #include<string.h> #include<iostream> #define debug(x) cout<<#x<<":"<<x<<endl; using namespace std; typedef long long ll; typedef unsigned long long ull; const ll INF=1e18; const int maxn=1e6+6; const int mod=1e9+7; const double eps=1e-15; inline bool read(ll &num) {char in;bool IsN=false;     in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;} ll n,m,p; ll num[maxn]; ll judge[505][505]; vector<int>v; int getid(ll x){     return lower_bound(v.begin(),v.end(),x)-v.begin() +1; } ll a[maxn],b[maxn],c[maxn],d[maxn]; int main(){     int T;scanf("%d",&T);     while(T--){         read(n);         for(int i=0;i<=n;i++){             for(int k=0;k<=n;k++){                 judge[i][k] = 0;             }         }         v.clear();         for(int i=1;i<=n;i++){             read(a[i]);             c[i] = a[i];             v.push_back(a[i]);         }         for(int i=1;i<=n;i++){             read(b[i]);             d[i] = b[i];         }         sort(a+1,a+1+n);         sort(b+1,b+1+n);         int f = 0;         for(int i=1;i<=n;i++){             if(a[i] != b[i]) f = 1;         }         if(f){             printf("Non");             continue;         }         sort(v.begin(),v.end());//排序         v.erase(unique(v.begin(),v.end()),v.end());         for(int i=1;i<=n;i++){             int id1 = getid(c[i]);             int id2 = getid(c[n-i+1]);             judge[id1][id2]++;             judge[id2][id1]++;         }         for(int i=1;i<=n;i++){             int id1 = getid(d[i]);             int id2 = getid(d[n-i+1]);             if(judge[id1][id2]>0&&judge[id2][id1]>0){                 judge[id1][id2] --;                 judge[id2][id1] --;             }             else{                 f = 1;                 break;             }         }         if(f) printf("Non");         else printf("Yesn");     }     return 0; } /** 3 011 100 111 **/