Codeforces Round #801 — EPIC Institute of Technology Round (Div. 2)题解

• A. Subrectangle Guess
• B. Circle Game
• C. Zero Path

题意：
迈克尔和乔正在玩一个游戏。这个游戏是在一个有n行m列的网格上进行的，网格中充满了不同的整数。我们用（i,j）表示第i（1≤i≤n）行和第j（1≤j≤m）列的方格，用aij表示那里的数字。

迈克尔先说两个数字h（1≤h≤n）和w（1≤w≤m）。然后乔在棋盘上任意选取一个h×w的子矩形（迈克尔看不到）。

从形式上看，一个h×w的子矩形从某个方格（a,b）开始，其中1≤a≤n-h+1，1≤b≤m-w+1。它包含所有a≤i≤a+h-1和b≤j≤b+w-1的方格（i,j）。

如果迈克尔说是3×2（最大为15），那么乔可能会走这一步。
最后，迈克尔必须猜出子矩形中的最大数字。如果他猜对了，他就赢了。

因为迈克尔不喜欢大数字，他希望所选的子矩形的面积（即h⋅w）尽可能小，同时仍能确保他获胜，而不是取决于乔的选择。请帮助迈克尔找到这个可能的最小面积。

可以证明，迈克尔总是可以选择h,w，对其而言，他可以确保自己获胜。

注意：保证输入的数字不会重复

思路：
先找到矩阵中最大的那个数字，然后分别从上下，左右算出每部分所需要的最大矩阵边长，然后乘一起就是答案。

#include

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair PII;
const ll mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn =50;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second


int read () {
    int k=0,f=1;
    char c=getchar ();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
    while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
    return k*f;
}
int a[maxn][maxn];

void solve() {
    int n,m;
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j ++)
            cin>>a[i][j];

    int mx = 0,my = 0;
    int maxx = -INF;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            if(maxx < a[i][j])
            {
                mx = i;
                my = j;
                maxx = a[i][j];
            }
        }
    }

    int ansx = 0,ansy = 0;

    ansx = max(mx,n - mx + 1);
    ansy = max(my,m - my + 1);
    ll ans = ansx * ansy;

    //cout<
    cout<
    ios;
    int t; cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

题目：


题意:

迈克和乔正在用一些石头做游戏。具体来说，他们有n堆大小为a1,a2,…,an的石头。这些石堆被安排在一个圆圈里。

游戏过程如下。玩家从第1堆开始，按顺时针顺序轮流从一堆中取出一些正数的石头。从形式上看，如果一个玩家在某一回合从i堆中移走了石头，那么另一个玩家在下一回合就会从（（imodn）+1）堆中移走石头。

如果一个玩家在自己的回合中不能取出任何石头（因为这堆石头是空的），他们就输了。迈克先走。

如果迈克和乔以最佳方式下棋，谁会赢？

思路：
分类讨论：
(1).若n为奇数，则Mike一定赢。
证明：由于每一步都是最优的，并且n为奇数，所以第二轮M走过的位置就是J要走的位置，石头初始时一定大于0，所以Mike只需要在第一堆把所有石头拿走，第二轮开始时，J一定会走到这个位置，故若n为奇数，则先手必胜（即Mike赢）
(2).若n为偶数，再次分类
证明:(首先需要确定一点，n为偶数，则无论多少轮，M和J取的堆一直都是自己的，假设有四堆，则无论多少回合，M一定取的是第一堆和第三堆，而J取的一定是第二堆和第四堆)
1.若全部相等，Joe只需要严格按照Mike的取法来取，最后一定是Mike输
2.，若不相等，则所有的石头堆中石头数目最少的位置谁取谁就输

#include

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair PII;
const ll mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn = 60;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second


int read () {
    int k=0,f=1;
    char c=getchar ();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
    while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
    return k*f;
}

int a[maxn];
map num;

void solve() {
    num.clear();
    int n;
    cin >> n;
    int temp = INF;
    int idx = -1;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        num[a[i]] = i;
        if (temp > a[i]) {
            idx = i;
            temp = a[i];
        }
    }
        if (n % 2 == 0) {
            if (num.size() == 1) cout << "Joe" << endl;
            else {
                if (idx % 2 == 0) cout << "Mike" << endl;
                else cout << "Joe" << endl;
            }
        } else {
            cout << "Mike" << endl;
        }
    }


int main()
{
    ios;
    int t; cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

题意：
给你一个有n行和m列的网格。我们用(i,j)表示第i(1≤i≤n)行和第j(1≤j≤m)列的方格，用aij表示那里的数字。所有的数字都等于1或等于-1。

你从方格（1,1）开始，每次可以向下或向右移动一个方格。最后，你想在(n,m)方格处结束。

有没有可能以这样的方式移动，使所有访问过的单元格（包括a11和anm）中的数值之和为0？

思路：
1.如果n+m是偶数，那么从左上角到右下角的任何路径的总和将是奇数，因此是非零。所以在这种情况下，没有解决方案。
2.否则，从左上角到右下角的每条路径的和都是偶数。对于网格中的每个位置(i,j)，我们定义mx[i][j]为从左上角开始到(i,j)结束的路径的最大可能和。同样，mn[i][j]被定义为从左上角开始到(i,j)结束的最小可能和。
如果0

#include

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair PII;
const ll mod=1e9+7;
const int INF=0x3f3f3f3f;
const int maxn = 1010;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define x first
#define y second


int read () {
    int k=0,f=1;
    char c=getchar ();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar ();}
    while (c>='0'&&c<='9') {k=k*10+c-'0';c=getchar ();}
    return k*f;
}

int a[maxn][maxn];
int mx[maxn][maxn];
int mn[maxn][maxn];

void solve()
{
    int n,m; cin>>n>>m;
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            cin>>a[i][j];

    mx[1][1] = mn[1][1] = a[1][1];

    for(int i = 2; i <= n; i++)
        mx[i][1] = mn[i][1] = mx[i - 1][1] + a[i][1];

    for(int j = 2; j <= m; j++)
        mx[1][j] = mn[1][j] = mx[1][j - 1] + a[1][j];

    for(int i = 2;i<=n;i++)
        for(int j = 2;j<=m;j++)
        {
            mx[i][j] = max(mx[i-1][j],mx[i][j-1])+a[i][j];
            mn[i][j] = min(mn[i-1][j],mn[i][j-1])+a[i][j];
        }

    if(mx[n][m] % 2 || mx[n][m] < 0 || mn[n][m] > 0) cout<<"NO"<
    ios;
    int t; cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}