Codeforces Round #801 (Div. 2)

A Subrectangle Guess

代码

#include <bits/stdc++.h>

#define endl "\n"

using namespace std;

typedef long long ll;

const int N = 1e6;

void solve()

{

    ll mis = -1e10;

    int a, b, n, m;

    cin >> n >> m;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= m; j++)

        {

            ll sa;

            cin >> sa;

            if (sa > mis)

            {

                mis = sa;

                a = i;

                b = j;

            }

        }

    int x = max(a, n - a + 1);

    int y = max(b, m - b + 1);

    cout << x * y << endl;

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0), cout.tie(0);

    int t;

    cin >> t;

    while (t--)

    {

        solve();

    }

    return 0;

}

B Circle Game

题意

有若干堆石子围成一个圆,第一个选手从第一堆开始取走任意个,然后第二个选手从前一个选手取的后一堆取走任意个,先不能取的输,谁会赢?

分析

如果石子有奇数堆那么先手必胜,因为先手可以一直全部取完,这样后手取到第一堆的时候就没有石子可取了.

如果石子有偶数堆,那么先手只能取奇数堆的石子,后手只能取偶数堆的石子,所以最优策略是每次少取,也就是每次取一个.所以如果只需比较奇数堆和偶数堆的最小值即可,如果最小值相等,最小值在前的必败.

代码

#include <bits/stdc++.h>

#define endl "\n"

using namespace std;

typedef long long ll;

const int N = 1e6;

void solve()

{

    int n;

    cin >> n;

    int s[n + 1];

    for (int i = 1; i <= n; i++)

        cin >> s[i];

    if (n % 2 == 1)

    {

        cout << "Mike\n";

        return;

    }

    int s1 = 100, s2 = 100;

    int m1 = 1e9 + 23, m2 = 1e9 + 23;

    for (int i = 1; i <= n; i = i + 2)

        if (m1 > s[i])

        {

            m1 = s[i];

            s1 = i;

        }

        else if (m1 == s[i] && s1 > i)

            s1 = i;

    for (int i = 2; i <= n; i = i + 2)

        if (m2 > s[i])

        {

            m2 = s[i];

            s2 = i;

        }

        else if (m2 == s[i] && s2 > i)

            s2 = i;

    if (m2 > m1)

        cout << "Joe\n";

    else if (m2 == m1 && s2 > s1)

        cout << "Joe\n";

    else

        cout << "Mike\n";

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0), cout.tie(0);

    int t;

    cin >> t;

    while (t--)

    {

        solve();

    }

    return 0;

}

C Zero Path

题意

给出一个权值只有 +1 和 -1 的矩阵,只能往下或者往右走,问是否能从左上走到右下使得路径之和为 0.

分析

首先如果 n+m 为偶数,那么路径和一定是奇数,所以一定走不到.

否则我们可以用两次 dp 分别求出左上走到右下路径的最大值和最小值,如果0在最大值和最小值之间说明存在这样的路径.

简易证明，因为 n+m 为奇数那么最后得到的值一定为偶数，每次微调会导致结果差2，因次只要0在最大值和最小值之间就可以通过微调得到.

比赛时证明不必要非常严谨，需要一点直觉猜测，有时候可以蒙一下.

代码

#include <bits/stdc++.h>

#define endl "\n"

using namespace std;

typedef long long ll;

const int N = 1e3 + 233;

int dp1[N][N]; //最大

int dp2[N][N]; //最小

void solve()

{

    int n, m;

    cin >> n >> m;

    int s[n + 1][m + 1];

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= m; j++)

            cin >> s[i][j];

    if ((n + m) % 2 == 0)

    {

        cout << "NO\n";

        return;

    }

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= m; j++)

        {

            if (i == 1)

            {

                dp1[i][j] = s[i][j] + dp1[i][j - 1];

                dp2[i][j] = s[i][j] + dp2[i][j - 1];

            }

            if (j == 1)

            {

                dp1[i][j] = s[i][j] + dp1[i - 1][j];

                dp2[i][j] = s[i][j] + dp2[i - 1][j];

            }

            if (i != 1 && j != 1)

            {

                dp1[i][j] = s[i][j] + max(dp1[i][j - 1], dp1[i - 1][j]);

                dp2[i][j] = s[i][j] + min(dp2[i][j - 1], dp2[i - 1][j]);

            }

        }

    if (dp1[n][m] >= 0 && dp2[n][m] <= 0)

        cout << "YES\n";

    else

        cout << "NO\n";

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0), cout.tie(0);

    int t;

    cin >> t;

    while (t--)

    {

        solve();

    }

    return 0;

}

巴特西

Codeforces Round #801 (Div. 2)

A Subrectangle Guess

代码

B Circle Game

题意

分析

代码

C Zero Path

题意

分析

代码

最新文章

热门文章