2020.6.8
最近连续两场翻车让我不得不加紧了一下训练。前几天没再划水了，昨天上午去医院看完奶奶下午回来锻炼完就坐在电脑前刷题，把二分做了做，重点练了下手动模拟，还是蛮重要的，因为前几场就是吃了手动模拟的亏，手速太慢导致明明ac/wa/tle情况一样别人涨分我掉分的情况。到了八点买了杯coco就坐在电脑前等待开始。昨天心态有点小小的波动，因为还是太曲折了。看这个结果就不难想到为什么了hhhh

A题果不其然又是开幕雷击，题目很好想，就是找到行和列同时全都为0的点的数量，若是奇数则先手必胜，偶数则必败，然后wa2，淦。窝自己看了好一会才发现我把col[]加了两遍，然而row根本没动，就这还把样例水过去了也是太惨。结果就是改了之后秒了A。一起打的大三的群友估计对我无语了吧，什么菜鸡a题都能卡。

B题很有意思，问的是数组a内的元素分为0和1两种，只有种类不同才能合法互换，问能不能通过无限次数合法的互换将数列完全排好序。思路是不可能的，这辈子都不可能的。一开始以为是独立集排序然后比较端点大小。后来窝发现好像没考虑全情况，样例都过不了，朋友wa4，这可咋办呢。然后我看着数据手动模拟了下，有一种感觉是除了一开始升序的情况直接可以判断之外，其余只要同时有0和1同时存在，那么就一定可以排好序，但窝不会证明。样例过了就交了一发，然后re了点4，后来发现是数组没开够，开大之后一发过了？？？刚才被我微信自言自语烦死的老哥都懵了。事后我发邮件问了下Piot教授，Piot说他觉得对，但是没法证明。

然后看C，C是问a和b序列都是只包含1-n中的数字，每个数字出现一次，可以把a的元素集体左移或者右移，问a通过任意移动之后和b数组同位置元素相同的最大数量是多少。窝一开始没看见1-n每个数字只出现一次，写了个假算法跟朋友说我算法fAke了，不能处理重复数字。然后朋友跟我说，喵的每个数字本来就出现一次好吧？窝：？？？看到n可以开数组，然后这样就简单了，和之前一道dp类似。那么直接预处理a的元素对应的位置，然后算和b中元素的下标差值，开个桶投票，最多的一个即为答案。窝因为没查0和比n大的元素各wa了一次。后来想想边跑边统计难道不行么？？就A了，窝太菜了。然后隔壁老哥写到C估计觉得这人好没意思，拿群友当聊天垃圾桶和工具人了么？

D有意思，问能不能在矩阵中空地(".")添加墙壁，让"B"代表的坏人不能到达（n,m），好人(“G”)可以。然后窝一开始就觉得首先要逃出去坏人不能和好人相邻，然后wa3。朋友告诉我我忘了在坏人周围筑墙，就是把坏人旁边的空地换成墙，然后在终点bfs看能不能收集齐所有的好人并且坏人不能和好人相邻。之后因为judge函数写串了差点没交上hhhh

E我觉得挺简单，但当时前面耽误时间太多了，没能开，呜呜呜呜。陪我一起打的老哥估计被我大话痨给折磨惨了。基本都是我自己自言自语一堆，然后莫名其妙就AC了。道个歉。不过也证明了训练的重要性，以前划水太厉害了，导致之前思维有所下降。还是得加强训练。po代码

A题：

#include <bits/stdc++.h>
using namespace std;
#define limit (100 + 5)//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-6
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a,b) pair<a,b>
#define rep(i, a, b) for(int i = a; i <= b ; ++i)
#define per(i, a, b) for(int i = b ; i >= a ; --i)
#define mint(a,b,c) min(min(a,b), c)
#define MOD 998244353
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\acm_01\\data.txt", "rt", stdin)
typedef long long ll;
typedef unsigned long long ull;
ll read(){ll sign = 1, x = 0;char s = getchar();while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}while(s >= '0' && s <= '9'){x = x * 10 + s - '0';s = getchar();}return x * sign;
}//快读
void write(ll x){if(x < 0) putchar('-'),x = -x;if(x / 10) write(x / 10);putchar(x % 10 + '0');
}
int n ,k,kase;
int f[limit][limit],row[limit],col[limit];
int main() {
#ifdef LOCALFOPEN;
#endifcin>>kase;while(kase--){cin>>n>>k;int tot = 0;rep(i ,1, n){rep(j ,1, k){int val;cin>>val;if(val)f[i][j] = 1;else f[i][j] = 0;}}rep(j ,1, k){int flag = 0;rep(i ,1, n){if(f[i][j])flag = 1;}col[j] = flag;}rep(i ,1, n){int flag = 0;rep(j ,1, k){if(f[i][j])flag = 1;}row[i] = flag;}int ans2 = 0;rep(i ,1, n){if(!row[i])++tot;}rep(i ,1, k){if(!col[i])++ans2;}tot = min(tot, ans2);puts(tot % 2 == 1 ? "Ashish" : "Vivek");}return 0;
}

B题：

#include <bits/stdc++.h>
using namespace std;
#define limit (100000 + 5)//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-6
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a,b) pair<a,b>
#define rep(i, a, b) for(int i = a; i <= b ; ++i)
#define per(i, a, b) for(int i = b ; i >= a ; --i)
#define mint(a,b,c) min(min(a,b), c)
#define MOD 998244353
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\acm_01\\data.txt", "rt", stdin)
typedef long long ll;
typedef unsigned long long ull;
ll read(){ll sign = 1, x = 0;char s = getchar();while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}while(s >= '0' && s <= '9'){x = x * 10 + s - '0';s = getchar();}return x * sign;
}//快读
void write(ll x){if(x < 0) putchar('-'),x = -x;if(x / 10) write(x / 10);putchar(x % 10 + '0');
}
int n ,k,kase;
struct node{int at, bt;
}a[limit];
int g[limit] , f[limit];
int main() {
#ifdef LOCALFOPEN;
#endifcin>>kase;while(kase--){cin>>n;int cnt = 0 , cnt2 = 0;int last = -INF;int flag = 0;rep(i ,1, n){cin>>a[i].bt;if(a[i].bt < last)flag = 1;last = a[i].bt;}rep(i , 1, n){cin>>a[i].bt;}if(!flag){cout<<"Yes"<<endl;continue;}rep(i ,1, n){int s = a[i].at , t = a[i].bt;if(t){f[++cnt] = s;}else{g[++cnt2] = s;}}puts(min(cnt2, cnt) ? "Yes" : "No");}return 0;
}

C题：

#include <bits/stdc++.h>
using namespace std;
#define limit (1000000 + 5)//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-6
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a,b) pair<a,b>
#define rep(i, a, b) for(int i = a; i <= b ; ++i)
#define per(i, a, b) for(int i = b ; i >= a ; --i)
#define mint(a,b,c) min(min(a,b), c)
#define MOD 998244353
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\acm_01\\data.txt", "rt", stdin)
typedef long long ll;
typedef unsigned long long ull;
ll read(){ll sign = 1, x = 0;char s = getchar();while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}while(s >= '0' && s <= '9'){x = x * 10 + s - '0';s = getchar();}return x * sign;
}//快读
void write(ll x){if(x < 0) putchar('-'),x = -x;if(x / 10) write(x / 10);putchar(x % 10 + '0');
}
int n ,k,kase;
int a[limit] , b[limit];
int posa[limit], dist[limit];
int bucket[limit];
int main() {
#ifdef LOCALFOPEN;
#endifcin>>n;rep(i ,1, n){cin>>a[i];posa[a[i]] = i;//反映射}rep(i ,1, n){cin>>b[i];if(posa[b[i]] < i){bucket[(posa[b[i]] + n - i)]++;}else{bucket[(posa[b[i]] - i)]++;}}int maxx = 0;rep(i ,0, 2 * n){maxx = max(maxx, bucket[i]);}cout<<maxx<<endl;return 0;
}

D题：

#include <bits/stdc++.h>
using namespace std;
#define limit (100 + 5)//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-6
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0);
#define ff(a) printf("%d\n",a );
#define pi(a,b) pair<a,b>
#define rep(i, a, b) for(int i = a; i <= b ; ++i)
#define per(i, a, b) for(int i = b ; i >= a ; --i)
#define mint(a,b,c) min(min(a,b), c)
#define MOD 998244353
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\acm_01\\data.txt", "rt", stdin)
typedef long long ll;
typedef unsigned long long ull;
ll read(){ll sign = 1, x = 0;char s = getchar();while(s > '9' || s < '0' ){if(s == '-')sign = -1;s = getchar();}while(s >= '0' && s <= '9'){x = x * 10 + s - '0';s = getchar();}return x * sign;
}//快读
void write(ll x){if(x < 0) putchar('-'),x = -x;if(x / 10) write(x / 10);putchar(x % 10 + '0');
}
int n ,k,kase;
char mapp[limit][limit];
int vis[limit][limit];
bool legal(int x, int y){return x >= 1 && y >= 1 && x <=n && y <= k && mapp[x][y] != 'G' && mapp[x][y] != 'B'&& !vis[x][y] ;
}
bool legal2(int x, int y){return x >= 1 && y >= 1 && x <=n && y <= k && !vis[x][y] && mapp[x][y] != '#';
}int main() {
#ifdef LOCALFOPEN;
#endifcin>>kase;while(kase--){cin>>n>>k;int flag = 0;memset(vis, 0 , sizeof(vis));rep(i ,1, n){string str;cin>>str;rep(j ,1, k){mapp[i][j] = str[j - 1];if(mapp[i][j] == 'G')flag++;}}if(!flag){puts("Yes");continue;}int status = 0;rep(i ,1, n){rep(j , 1, k){if(mapp[i][j] == 'B'){if(legal(i + 1, j)){mapp[i+1][j] = '#';}if(legal(i - 1, j)){mapp[i-1][j] = '#';}if(legal(i, j + 1)){mapp[i][j+1] = '#';}if(legal(i, j - 1)){mapp[i][j-1] = '#';}}}}queue<pi(int, int)>q;vis[n][k] = 1;q.push({n,k});int t = 0;while(q.size()){auto it = q.front();q.pop();int i = it.first, j = it.second;if(legal2(i + 1, j)){vis[i+1][j] = 1;if(mapp[i+1][j] == 'G'){++t;}if(mapp[i+1][j] == 'B'){status = 1;}q.push({i+1,j});}if(legal2(i - 1, j)){vis[i-1][j] = 1;if(mapp[i-1][j] == 'G'){++t;}if(mapp[i-1][j] == 'B'){status = 1;}q.push({i-1,j});}if(legal2(i, j + 1)){vis[i][j+1] = 1;if(mapp[i][j+1] == 'G'){++t;}if(mapp[i][j+1] == 'B'){status = 1;}q.push({i,j+1});}if(legal2(i, j - 1)){vis[i][j-1] = 1;if(mapp[i][j-1] == 'G'){++t;}if(mapp[i][j-1] == 'B'){status = 1;}q.push({i,j-1});}}if(status){puts("No");continue;}if(t == flag){puts("Yes");}else{puts("No");}}return 0;
}