A.Matrix Game

题意：

两人博弈，给定一个 $01$ 矩阵，对于某一个点，如果此时的行和列均没有 $1$ 存在的话，可以将这个点设置成 $1$ ，两人依次进行操作，询问谁最终会获胜

题解：

计算出全为 $0$ 的行数和列数，取较小者判断奇偶性即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;

void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int x[n] = {0};
    int y[m] = {0};
    for (int i = 0; i < n; i++)
        for (int j = 0, t; j < m; j++)
        {
            scanf("%d", &t);
            if (t == 1)
                x[i] = 1, y[j] = 1;
        }
    int sx = 0, sy = 0;
    for (int i = 0; i < n; i++)
        sx += x[i];
    for (int j = 0; j < m; j++)
        sy += y[j];
    puts(min(n - sx, m - sy) % 2 ? "Ashish" : "Vivek");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

B.Trouble Sort

题意：

数组中所有数字由 $0,1$ 两种类型，每次可以交换数组中两个类型不同的数字，问若干次操作后是否可以使得数组从小到大排序。

题解：

注意到只要不是所有类型都相同，我们一定可以通过多次交换使得数组最终完成排序。所以只要判断是不是所有数字的类型都相同且初始状态下并非排序完成的结果即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int INF = 0x3f3f3f3f;
int a[maxn],b[maxn];
void solve()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    for(int i=0; i<n; i++)
        scanf("%d",&b[i]);
    sort(b,b+n);
    if(b[0]==b[n-1]&&!is_sorted(a,a+n))
        puts("No");
    else
        puts("Yes");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

C.Rotation Matching

题意：

给定两个 $1$ 到 $n$ 排列数组 $a,b$ 。问怎么循环位移可以使得匹配的数量尽可能的多。求最大匹配数量。

题解：

记录 $b$ 中每个数字位移到$a4中对应匹配位置所需的位移量。对所有的位移量所被记录的次数求一个最大值即可。

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

D.Solve The Maze

题意：

地图上有空地，墙，好人，坏人四种类型。规定右下角为出口。问能否再安排一些墙使得好人都能到出口，且坏人都不能到达出口。

题解：

我们只要将坏人的四周围起来。具体实现的时候，只要坏人的四周不是坏人，那么就在这个位置安排一个墙。最后从出口开始反向深搜检查每一个好人能否到达出口。注意坏人的四周如果是好人，我们将其直接覆盖为墙。由于坏人四周存在好人，那么坏人一定能够到达出口。这不会影响我们最后得到的结果。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 55;
const int INF = 0x3f3f3f3f;
char mp[maxn][maxn];
int dir[4][2]= {0,1,0,-1,1,0,-1,0};
bool vis[maxn][maxn];
int n,m;
int dfs(int x,int y)
{
    int res=0;
    if(x<0||x>=n||y<0||y>=m)
        return 0;
    if(vis[x][y]||mp[x][y]=='#')
        return 0;
    vis[x][y]=1;
    if(mp[x][y]=='G')
        res++;
    for(int i=0; i<4; i++)
        res+=dfs(x+dir[i][0],y+dir[i][1]);
    return res;
}
void solve()
{
    memset(vis,0,sizeof(vis));
    scanf("%d%d",&n,&m);
    int sum = 0;
    for(int i=0; i<n; i++)
    {
        scanf("%s",mp[i]);
        for(int j=0; j<m; j++)
            if(mp[i][j]=='G')
                sum++;
    }
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
        {
            if(mp[i][j]=='B')
            {
                if(i-1>=0&&mp[i-1][j]!='B')
                    mp[i-1][j]='#';
                if(i+1<n&&mp[i+1][j]!='B')
                    mp[i+1][j]='#';
                if(j-1>=0&&mp[i][j-1]!='B')
                    mp[i][j-1]='#';
                if(j+1<m&&mp[i][j+1]!='B')
                    mp[i][j+1]='#';
            }
        }
    if(sum==dfs(n-1,m-1))
        puts("Yes");
    else
        puts("No");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
    return 0;
}

E.Maximum Subsequence Value

题意：

从 $n$ 个数字中选取 $k$ 个，要求最大化这 $k$ 个数字构成集合的价值。定义集合的价值为在二进制下，若第 $i$ 位至少存在 $max(1,k−2)$ 个 $1$ ，那么对价值产生 $2^i$ 的贡献。

题解：

分析可得 $k=3$ 时最优。首先，若 $k=1,2$ 每一位同样需要存在 $1$ 个 $1$ ，那么相同情况下增加一个数字只会使得值更大。若 $k \geq 4$ ，在 $k=3$ 时恰好满足的条件下多出来的数字的每一位必须要满足一定的条件，否则值只会更小。所以我们可以暴力枚举每三项的或值取最大值即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll a[505];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    ll res = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            for (int k = j; k < n; k++)
                res = max(res, a[i] | a[j] | a[k]);
    printf("%lld\n", res);
    return 0;
}

F.Swaps Again

题意：

问数组 $a$ 是否可以通过若干次任意相等长的前缀和后缀的交换变为数组 $b$ 。

题解：

分析可以发现，对于每一对 $(i,n-i-1),i \in [0,n-1]$ ,无论怎么交换其下标之和总是 $n-1$ ，也就意味着每对 $(i,n-i-1)$ 只有 $(a_{i},a_{n-i-1})$ 和 $(a_{n-i-1},a_{i})$ 两种情况，对 $b$ 同理。因此只需要对每对 $(a_{i},a_{n-i-1})$ 和 $(b_{i},b_{n-i-1})$ 判断能否相等即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[505], b[505];
void solve()
{
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
        scanf("%d",&a[i]);
    for (int i = 0; i < n; i++)
        scanf("%d",&b[i]);
    vector<pii> pa(n), pb(n);
    if ((n & 1) && a[n / 2] != b[n / 2])
    {
        puts("No");
        return;
    }
    for (int i = 0; i * 2 < n; i++)
    {
        if ((n & 1) && i == n / 2)
            break;
        if (a[i] > a[n - i - 1])
            swap(a[i], a[n - i - 1]);
        if (b[i] > b[n - i - 1])
            swap(b[i], b[n - i - 1]);
        pa.emplace_back(a[i], a[n - i - 1]);
        pb.emplace_back(b[i], b[n - i - 1]);
    }
    sort(pa.begin(), pa.end());
    sort(pb.begin(), pb.end());
    if (pa == pb)
        puts("Yes");
    else
        puts("No");
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

Codeforces Round #648 (Div. 2)