Luogu P1199 – 贪心/博弈论

PROBLEM

https://www.luogu.org/problemnew/show/P1199

ANALYSIS

题意就不描述了。

此题中，人是必胜的，只需要做到 每次取所有行中第二大元素最大的那个行。

证明：

1. 计算机和人都永远都拿不到第一大的元素。
2. 计算机永远都拿不到第二大的元素，但是人可以。

SOLUTION

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

constexpr int N = 550;

int d[N][N], n;
bool v[N];


void go(int n) {
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            scanf("%d", d[i] + j);
            d[j][i] = d[i][j];
        }
    }
    int u = 0, v, z = 0;
    for (int i = 1; i <= n; i++) {
        u = 0;
        for (int j = 1; j <= n; j++) {
            if (u < d[i][j]) {
                v = u;
                u = d[i][j];
            }else if(v<d[i][j]){
                v = d[i][j];
            }
        }
        z = max(v, z);
    }
    cout << 1 << endl;
    cout << z << endl;
    return 0;
}

REFERENCE

这篇题解写的太好了

1. https://peerless.blog.luogu.org/solution-p1199

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.