♐ CSP_J 组真题
2010年
4. 三国游戏

线上OJ:

一本通:http://ybt.ssoier.cn:8088/problem_show.php?pid=1952 (opens in a new tab)
AcWing:https://www.acwing.com/problem/content/description/446/ (opens in a new tab)
洛谷:https://www.luogu.com.cn/problem/P1199 (opens in a new tab)

核心思想:

这道题先用 瞪眼法 找规律(不能硬写模拟)。
因为电脑采用的是 防守策略(不会主动进攻),所以如果我们想选每一行的最大值,一定选不到(会 被电脑破坏掉)。但同样的,每行的极大值 人选不到,电脑也选不到)。所以,每行的 次极大值 就是 胜败的关键,因为次极大值是可以选到的。
所以我们只要先拿到次极大值中最大的,然后依次和电脑一起把所有极大值都破坏,人类就赢了。

由于本题的“武将默契值均不相同”,所以次极大值只有一个,所以人类一定赢。
由于本题不需要输出每次的选择,所以直接输出最大的那个次极大值即可。

注意:在寻找每行的次极大值时,要先把完整的矩阵构建出来,因为题目输入的只有一半。

题解代码:

瞪眼法找规律
#include <bits/stdc++.h>
using namespace std;
 
const int N = 505;
int n, x, a[N][N] = {0};
int ans = -1;
 
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
        {
            scanf("%d", &x); // 读入数据
            a[i][j] = a[j][i] = x; // 构建完整的矩阵,不能只用一半,因为缺前向的关系
        }
 
    for(int i = 1; i <= n; i++) // 找出每一行中的次极大值
    {
        sort(a[i] + 1, a[i] + 1 + n);
        ans = max(ans, a[i][n-1]);  // a[i][n-1]时第i行的次极大值。所有的次极大值中最大的一个,即为能保证获胜的数值
    }
 
    printf("1\n%d", ans);
    return 0;
}