[NOIP2010-普及] 三国游戏

GitHub跳转原题关系图返回列表

小涵最多只能拿到每个武将的次大默契值：先抢次大值最大的武将，电脑必抢其最强搭档，小涵再抢次强搭档即必胜，答案就是全体次大值的最大者。

OJ: roj

题目 ID: 3579

难度:普及

标签:博弈思维最大次大值python

创建: 2026-10-02 09:08

更新: 2026-10-06 14:26

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

小涵和电脑轮流从 NN（偶数，4⩽N⩽5004 \leqslant N \leqslant 500）位自由武将中选将，小涵先手；轮到电脑时，它抢走"小涵军队与自由武将配对中默契值最高"的那名自由武将，直到武将均分。终局双方各取自己军队中默契值最大的一对比较。给定两两默契值（互不相同，0⩽0 \leqslant 值 ⩽109\leqslant 10^9）：第 11 行是 NN，第 i+1i+1 行给出 ii 号与 i+1…Ni+1 \dots N 号武将的默契值；若小涵有必胜策略，输出 1 再输出所有胜利结局中其组合的最大默契值，否则输出 0。

样例 1 输入：6 / 5 28 16 29 27 / 23 3 20 1 / 8 32 26 / 33 11 / 12，输出：1 / 32。

思路

电脑每手都抢走小涵当前最强组合里的自由武将，所以小涵任何武将的"最强搭档"都保不住，能稳拿的上限是每个武将的次大默契值。取次大值 VV 最大的武将先手，电脑必抢其最强搭档，小涵再抢其次强搭档即拿到 VV，且此后电脑每组组合都 <V< V。故答案恒为全体次大值的最大值。

参考代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 09:09
# update_at: 2026-10-02 09:09

import sys


def keep_top2(cell: list[int], w: int) -> None:
    """用边权 w 刷新某个武将的 (最大, 次大) 默契值。"""
    if w > cell[0]:
        cell[1], cell[0] = cell[0], w  # 原最大降级为次大
    elif w > cell[1]:
        cell[1] = w


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 武将个数：偶数且不小于 4

    # 每个武将维护 (最大, 次大) 两条边：电脑只破坏"最强组合"，次大稳拿
    top: list[list[int]] = [[0, 0] for _ in range(n)]
    for i in range(n - 1):  # 第 i+1 行给出 i 号与 i+1..n-1 号的默契值
        for j in range(i + 1, n):
            w = next(data)
            keep_top2(top[i], w)  # 边 (i, j) 对两端各自刷新
            keep_top2(top[j], w)

    # 必胜：先抢次大值最大的武将 i，电脑抢走 i 的最强搭档，再抢 i 的次强搭档；
    # 电脑任一组合都小于该次大值，故输出 1 和所有次大值中的最大者
    print(1, max(cell[1] for cell in top), sep="\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:26
 * update_at: 2026-10-06 14:26
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 505;
ll top1[MAXN]; // top1[i]：i 号武将关联的最大默契值
ll top2[MAXN]; // top2[i]：i 号武将关联的次大默契值

// 用边权 w 刷新武将 v 的最大、次大默契值
void keep_top2(int v, ll w) {
    if (w > top1[v]) {
        top2[v] = top1[v]; // 原最大降级为次大
        top1[v] = w;
    } else if (w > top2[v]) {
        top2[v] = w;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    // 第 i+1 行给出 i 号与 i+1..n 号武将的默契值
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            ll w;
            scanf("%lld", &w);
            keep_top2(i, w); // 边 (i, j) 对两端各自刷新
            keep_top2(j, w);
        }
    }

    // 电脑每手只破坏"最强组合"，小涵能稳拿的只有次大值；
    // 取次大值最大的武将先手，电脑必抢其最强搭档，小涵再抢次强搭档即可必胜。
    ll ans = 0;
    for (int v = 1; v <= n; v++) {
        ans = max(ans, top2[v]);
    }
    printf("1\n%lld\n", ans);
    return 0;
}