题解：P11133 【MX-X5-T5】「GFOI Round 1」World Ender

· · 题解

前言

I. 时间之初的歌曲。

II.完美地，或是空洞地。

III.创造奇迹，冲破世界。

World Ender - Beyond 11

题意

光光和对立在玩游戏。

有 n 堆碎片，你可以选择一堆，扔掉不少于一片，然后随你怎么分都行。

你可以选择先手或后手，问你是否存在必胜策略。

思路

谁家好人教练赛前最后一次模拟压轴放交互啊？

这是一道交互题，仅支持 C++ 语言提交，且不支持 C++14（GCC 9）。

博弈论好题。

Get

按部就班即可，不过在保存的时候存一下原下标，后面有用。

Init

初始化，选择先后手，选择方式见下。

Play

考虑到每一次至少扔掉一片碎片，不可能出现循环。

手玩一下不难发现，真正决定结果的只有如下两种情况。

为什么说只有这两种情况是真正决定结果的呢？

当 n=3 时，不妨设先手是光光，那么光光可以直接清空数量最大的一堆，并将剩下两堆中较小的一堆补到和较大的那一堆一样多（不难证明数量最大的那一堆一定是可以把剩下两堆中较少的那一堆补到和较大的那一堆一样多的），那么就回到了对立面对两堆相等的必败情况，此时先手光光必胜。

同理，当 n 为奇数时，不妨设先手是光光，光光可以用类似的方法获胜，对立一定会输得很惨。可怜的对立。

当 n 为偶数时，继续假设光光是先手，如果堆数能两两配对，那么相当于有 \dfrac{n}{2} 组情况二中的两堆相等的情况摆在光光面前，那么光光只能含泪认输。为了让光光赢，我们得把这个难题摆在对立面前。所以,如果不能两两配对，但凡有一组是不同的，那么光光可以将其变为上面的情况，那么对立就只能输掉这场比赛。

但是！你是玩家，你的目标是打赢电脑！

虽然我是光厨，但是如果初始序列给你就是堆数能两两配对的情况，你选光光（初始先手）显然是赢不了的。

为了胜利，你只能选对立。

哎这个出题人太坏了。

编译方式

想必不少人应该是第一次见到交互题，在这里说一下交互题怎么编译。

  1. DEV-C++ 新建项目。
  2. 左上角项目管理，添加项目，导入题目给出的交互判定程序和你的程序。
  3. 编译运行即可。

Code

#include<bits/stdc++.h>
#define pr pair<int,int>
#define mp make_pair
using namespace std;
const int M=2000;
int n,cnt,vis[M+10];
vector<pr> vec;
vector<int> Play() {
    vector<int> ans(cnt,0);
    sort(vec.begin(),vec.end());
    if (cnt&1) for (int i=0;i<cnt;i++) vec[i].first=(cnt-i-1?vec[i+1-i%2].first:0);
    else for (int i=0;i<cnt;i++) vec[i].first=(cnt-i-1?vec[i+i%2].first:vec[0].first);
    for (int i=0;i<cnt;i++) ans[vec[i].second]=vec[i].first;
    return ans;
}
void Get(vector<int> a) {
    vec.clear();cnt=0;
    for (auto i:a) vec.emplace_back(mp(i,cnt++));
    return;
}
bool Init(int n,int op,vector<int> a) {
    memset(vis,0,sizeof(vis));vec.clear();cnt=0;
    for (auto i:a) vec.emplace_back(mp(i,cnt++));
    for (auto i:a) vis[i]++;
    for (int i=1;i<=M;i++) if(vis[i]&1) return false;
    return true;
}

宣传