题目
A题意：给出一个n*m的棋盘，初始每个格子为0或1.现在Ashish（先手）和Vivek玩一个游戏，都采取最优策略，判断谁赢
规则：双方轮流在方格为0且该方格的行列上都没1，才可放1.最终不能放1的一方失败。
解法：分别统计行和列上没有1的数量，因为每放一个1都会消耗1行和1个列。所以只需判断满足条件的行列的最小值的奇偶性就可得到答案，奇数先手赢。
const int maxn = 59;
int a[maxn][maxn] ;
bool visx[maxn] , visy[maxn] ;
void solve(){
ME(visx , false);
ME(visy , false);
int n , m ;
cin >> n >> m ;
rep(i , 1 , n){
rep(j , 1 , m){
cin >> a[i][j];
if(a[i][j]){
visx[i] = 1;//标记被1占用行
visy[j] = 1;
}
}
}
int x = 0 , y = 0 ;
rep(i , 1 , n){
if(!visx[i]) x++;//计数满足条件行
}
rep(i , 1 , m){
if(!visy[i]) y++;
}
if(min(x,y)%2){//判断最小值奇偶
cout << "Ashish" << endl;
}else{
cout << "Vivek" << endl;
}
}
signed main()
{
int _ ;cin>>_;while(_--)
solve();
}
B题意：n个元素，每个元素有(a_i)价值,和类型(b_i)（0或1）.不同类型之间的元素可以交换。
问是否可以使元素以价值不减的顺序排列。
解法：如果给出序列已经有序，则满足条件。如果两种类型的元素都有，也满足条件。
分析后一种情况：对于任意一对需要交换的元素a和b,并假设其类型相同，选一个与其类型不同的元素c。
通过c，可以达到a与b交换的目的，所以可满足条件。
const int maxn = 2e5+9;
int a[maxn] , b[maxn];
void solve(){
int n ;
cin >> n ;
rep(i , 1 , n){
cin >> a[i];
}
int flag = 1 ;
rep(i , 1, n-1){
if(a[i] > a[i+1]){
flag = 0 ;
break;
}
}
int x = 0 , y = 0;
rep(i , 1, n){
cin >> b[i];
if(!b[i])x++;
else y++;
}
if((x&&y) || flag){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
signed main()
{
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
int _ ;cin>>_;while(_--)
solve();
}
C题意：给出两组排列a和b，可对排列进行左右移动（首尾相连）,比如n位置元素右移变到1位置。
问：最多a排列与b排列，下标相同且值相同的最大个数。
解法：固定a数组，且记录a数组中各个元素的位置。遍历b数组，记录元素(b_i)在b数组与(b_i)在a数组之间需要移动次数。可以知道相同移动次数最多即是答案。
int a[maxn] , b[maxn];
int pos[maxn];
int cnt[maxn];//记录需i次的数量
void solve(){
int n ;
cin >> n ;
rep(i , 1 , n){
cin >> a[i] ;
pos[a[i]] = i ;
}
rep(i , 1 , n){
cin >> b[i];
}
rep(i , 1 , n){
int c = i - pos[b[i]];
if(c<0) c+=n;
cnt[c]++;
}
int ans = 0 ;
rep(i , 0 , n-1){
ans = max(cnt[i] , ans);
}
cout << ans << endl;
}
D题意：n*m大小迷宫，.代表路，G代表好人，B代表坏人，#代表墙。
可以将路(.)变成墙(#)，问是否可以使所有好人可以到达(n,m)，所有坏人不能到达(n,m)处。
解法：将所有坏人相邻的路变墙，然后判断是否所有的好人都可达(n,m)。
有种情况需要注意：当坏人与好人相邻时，则一定是不可行的，因为此时他们能不能到达(n,m)是一致的。
优化：正向对每一个好人dfs判断能否到达(n,m)时间上是不可行的，所以需要反向dfs出口能达到所有的点，然后判断是否好人所在的点能否达到。
#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
typedef long long ll ;
#define int ll
#define mod 1000000007
#define gcd __gcd
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//ll lcm(ll a , ll b){return a*b/gcd(a,b);}
ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define SC scanf
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
using namespace std;
const int N = 1e6+7;
const int maxn = 59;
char s[maxn][maxn];
int n , m ;
bool vis[maxn][maxn];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int vi[maxn][maxn];
void dfs(int x , int y){
vis[x][y] = 1 ;
for(int i = 0 ; i < 4 ; i++){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(s[xx][yy] == '#' || xx <= 0 || xx > n || yy <= 0 || yy > m || vis[xx][yy]) continue ;
dfs(xx , yy);
}
}
void solve(){
int flag = 0 ;
ME(vi , false);
ME(vis , false);
cin >> n >> m;
rep(i , 1 , n){
rep(j , 1 , m){
cin >> s[i][j];
if(s[i][j] == 'G'){
vi[i][j] = 1 ;
}
}
}
rep(i , 1 , n){
rep(j , 1 , m){
if(s[i][j] == 'B'){
rep(k , 0 , 3){
int xx = i+dir[k][0];
int yy = j+dir[k][1];
if(xx <= 0 || xx > n || yy <= 0 || yy > m) continue;
if(s[xx][yy] == '.')s[xx][yy] = '#';//给坏人周围变墙
if(s[xx][yy] == 'G'){//如果坏人周围有好人，则不符合条件
cout << "NO" << endl;
return;
}
}
}
}
}
if(s[n][m] == '.')//从出口dfs
dfs(n , m);
rep(i , 1 , n){
rep(j , 1 , m){
if(vi[i][j]){//好人所在的点
if(!vis[i][j]){//能否从出口可达
cout << "NO" << endl;
return ;
}
}
}
}
cout << "YES" << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _ ;cin>>_;while(_--)
solve();
}
E题意：给出一组n个序列，子序列长度k的值为子序列满足条件的二进制位之和，要至少有max（k-2，1）个元素具有该二进制位算满足条件。
问子序列最大值位多少。
解法：如果当k大于3时新增的数的二进制位一定在前三个数中出现的位数的集合中，所以最大有效个数为三个.(巢鸽原理)
所以只需暴力枚举任意三个数
const int maxn = 5e2+9;
int a[maxn];
void solve(){
int n ;
cin >> n ;
rep(i , 1 , n){
cin >> a[i];
}
if(n == 1){
cout << a[1] << endl;
return ;
}
if(n == 2){
cout << (a[1]|a[2]) << endl;
return;
}
int ans = 0 ;
rep(i ,1 , n){
rep(j , i+1 , n){
rep(k , j+1 , n){
ans = max(ans , a[i]|a[j]|a[k]);
}
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//int _ ;cin>>_;while(_--)
solve();
}
F题意：给出n个数ai ， n个数bi，问通过操作a数组是否可以变为b。
操作：对于长度k（1<=k<=[(frac{n}{2})]）,前缀k个元素与后缀k个元素进行交换,比如a:[1,4,2,3] 操作k=2,a:[2,3,1,4];
解法：1、可以知道当n为奇数时，a中心数与b中心数一定要相等。
2、因为交换都是中心交换，所以a的所有((a_i,a_{n-i+1})) 与b所有((b_i,b_{n-i+1})),应该完全相同。
int a[maxn] , b[maxn];
void solve(){
int n ;
cin >> n ;
rep(i , 1 , n){
cin >> a[i];
}
rep(i , 1 , n){
cin >> b[i];
}
if(n % 2 == 1){
if(a[n/2+1] != b[n/2+1]){
cout << "NO" << endl;
return ;
}
}
map<pii , int>m;
pii p ;
rep(i , 1 , n){
if(a[i] > a[n-i+1]) swap(a[i] , a[n-i+1]);//记录a的配对
p = {a[i] , a[n-i+1]};
m[p]++;
}
rep(i , 1 , n){
if(b[i] > b[n-i+1]) swap(b[i] , b[n-i+1]);
p = {b[i] , b[n-i+1]};
m[p]--;
if(m[p] < 0){//如果b的配对与a的配对不一致
cout << "NO" << endl;
return ;
}
}
cout << "YES" << endl;
}