Press "Enter" to skip to content

CodeForces #648 Div.2

发表于 2020年6月27日 作者 EricXia

A. Matrix Game

题目大意

给定一个n行m列由01构成的矩阵，每次可以在一个格子，那个格子所在的行和列上都没有1，将0变为1，Ashish先手，求谁先获胜

解题思路

统计没有1的行数和列数取最小的那个，然后判断其奇偶性

源码

#include <bits/stdc++.h>

#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)

typedef long long ll;
using namespace std;

const int MAXN=(int)100+5;

int mp[MAXN][MAXN];
int r[MAXN],c[MAXN];
int main()
{
    int T,n,m;
    cin>>T;
    while (T--)
    {
        cin>>n>>m;
        MEM(r,0);
        MEM(c,0);
        rep(i,0,n)rep(j,0,m)cin>>mp[i][j];
        rep(i,0,n)rep(j,0,m)r[i]|=mp[i][j],c[j]|=mp[i][j];
        int nc,nr;
        nc=nr=0;
        rep(i,0,n)nr+=(r[i]==0);
        rep(i,0,m)nc+=(c[i]==0);
        if(min(nc,nr)%2)cout<<"Ashish"<<endl;else cout<<"Vivek"<<endl;
    }

    return 0;
}

B. Trouble Sort

题目大意

只能交换不同类的数值的位置，判断是否能形成不单调递减数列

解题思路

如果数列中有多类，那么一定是可以形成的。
如果只有一个类，那么就判断一下输入就好了。

源码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int a[MAXN],b[MAXN],n;
bool solve()
{
    bool flag=true;
    for (int i = 0; i+1 < n; i++)
    {
        if(b[i]!=b[i+1]){flag=false;break;}
    }
    if(!flag)return true;
    for (int i = 0; i+1 < n; i++)
    {
        if(a[i]>a[i+1])return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while (T--)
    {
        cin>>n;
        rep(i,0,n)cin>>a[i];
        rep(i,0,n)cin>>b[i];
        if(solve())cout<<"Yes"<<endl;else cout<<"No"<<endl;
    }

    return 0;
}

C. Rotation Matching

解题思路

统计相同数字所在位置的差值，统计相同差值的数量，输出最大的数量

源码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)2e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int a[MAXN],b[MAXN],c[MAXN];
int main()
{
    int n;
    cin>>n;
    map<int,int>mp;
    rep(i,0,n)cin>>a[i];
    rep(i,0,n)c[b[i]]=i;
    rep(i,0,n)mp[(i-c[a[i]]+n)%n]++;
    int ans=0;
    for (auto &&i : mp)ans=max(ans,i.second);
    cout<<ans<<endl;
    return 0;
}

D. Solve The Maze

解题思路

初始化的时候，根据贪心，在坏人的四周堵上墙，如果有好人直接与坏人相邻那么是不存在的
然后从终点DFS统计能和终点相连的好人的数量，判断是否与总数相等

源码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e2+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
char mp[MAXN][MAXN];
int n,m,g;
bool init()
{
    g=0;
    rep(i,0,n)rep(j,0,m)
    {
        if(mp[i][j]=='B')
        {
            for (int k = 0; k < 4; k++)
            {
                int tx=dx[k]+i,ty=dy[k]+j;
                if(tx>=0&&tx<n&&ty>=0&&ty<m&&mp[tx][ty]!='B'&&mp[tx][ty]!='#')
                {
                    if(mp[tx][ty]=='G')return false;
                    else mp[tx][ty]='#';
                }
            }
        }else if(mp[i][j]=='G')g++;
    }
    return true;
}
bool vis[MAXN][MAXN];
int dfs(int x,int y)
{
    vis[x][y]=true;
    int res=0;
    if(mp[x][y]=='G')res++;
    for (int k = 0; k < 4; k++)
    {
        int tx=dx[k]+x,ty=dy[k]+y;
        if(tx>=0&&tx<n&&ty>=0&&ty<m&&mp[tx][ty]!='#'&&!vis[tx][ty])
        {
            res+=dfs(tx,ty);
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;

    cin>>T;
    while (T--)
    {
        cin>>n>>m;
        rep(i,0,n)cin>>mp[i];
        if(!init()||mp[n-1][m-1]=='#'&&g||mp[n-1][m-1]=='B'){cout<<"No"<<endl;continue;}
        MEM(vis,0);
        if(dfs(n-1,m-1)==g)cout<<"Yes"<<endl;else cout<<"No"<<endl;
    }

    return 0;
}

E. Maximum Subsequence Value

解题思路

根据贪心我们取得数不会超过3个
然后枚举答案
时间复杂度$O(n^2)$

源码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
ll a[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    rep(i,0,n)cin>>a[i];
    sort(a,a+n,greater<ll>());
    if(n<=3)
    {
        ll ans=0;
        rep(i,0,n)ans|=a[i];
        cout<<ans<<endl;
    }else
    {
        ll ans=0;
        for (int i = 0; i < n; i++)
        {
            ll tmp=a[i],res=a[i];
            for (int j = i+1; j < n; j++)res=max(res,tmp|a[j]);
            tmp=res;
            for (int j = i+1; j < n; j++)res=max(res,tmp|a[j]);
            ans=max(ans,res);
        }
        cout<<ans<<endl;
    }

    return 0;
}

发表于 CodeForces

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点，欢迎评论。x
()
x