[数据结构与算法]Asia Tsukuba 2016-2017 K - Black and White Boxes

Asia Tsukuba 2016-2017 K - Black and White Boxes

Black and White Boxes

参考：官方题解

国家集训队论文-浅谈如何解决不平等博弈问题

pro.：

两个人玩游戏，规则是有n列正方体，每个人可以选择他能选择的正方体然后把包括这个正方体之上的所有正方体取走，每个正方体为黑色或白色分别对应两个人的选择范围，不能操作者输；

这个游戏的输赢和初始局面以及先后手有关，存在一些初始局面下存在玩家（黑色或白色玩家）不论先后手均必胜，这些局面为不公平局面，剩余初始局面称为公平局面，给出一些待选的正方体列，可以选出一些作为初始局面，问这些初始局面中公平的、且包含正方体最多的局面下有多少个正方体。

ideas：

对于这个问题如果没有颜色，就是nim博弈，这个问题加上了颜色变成了不平等博弈

类似地，将问题拆分，即n列正方体各自单独考虑；如果存在式子能将一列正方体的局面表达，式子能合并，合并后的值为共同局面的表达，同时式子的值越正越对某一玩家有利，越负越对另一玩家有利，当值为0的时候，当前局面为公平局面

考虑引入surreal number （SN）

• def . SN : 由两个集合组成，称为“左集合”与“右集合”，将SN写作 { L ∣ R } \{L | R\} {L∣R}， 左集合和右集合中的元素也为SN，且右集合中不存在元素x使得左集合中存在元素y满足x $\le$ y。

• 构造 SN ：第一个SN： { ? ∣ ? } = { ∣ } = 0 \{\empty| \empty\} = \{ |\} = 0 {?∣?}={∣}=0

  构造出0后，尝试利用0构造新的SN，即：
  { 0 | }，{ | 0 }以及{0 | 0}

  因为0 $\le$ 0，所以{ 0 | 0 }不是一个合法的SN

  因为{ | 0 } < 0 < { 0 | }，所以令{ | 0 } = -1，{ 0 | } = 1
  因为{ 1 | } > 1，{ | -1} < -1，所以令{ 1 | } = 2，{ | -1} = -2。
  因为0 < { 0 | 1 } < 1，且{ 0 | 1 } + { 0 | 1 } = 1，因此我们令{ 0 | 1 } = 1/2。
  同理我们可以得出{ -1 | 0 } = -1/2。

  以此类推可以得出所有形如$\frac{b}{2^a}$ 的有理数的SN

达利函数：建立部分有理数与SN的关系：

δ ( x ) = { { ∣ } , x = 0 { δ ( x ? 1 ) ∣ } , x > 0 & x ∈ Z { ∣ δ ( x + 1 ) } , x < 0 & x ∈ Z { δ ( b ? 1 2 a ) ∣ δ ( b + 1 2 a ) } , x = b 2 a & a , b ∈ Z & k > 0 \delta(x) = \begin{cases} \{ |\} , x = 0 \\ \{\delta(x - 1) | \},x > 0 \&x \in Z\\\{|\delta(x+ 1)\},x < 0 \& x \in Z \\ \{\delta(\frac{b - 1}{2^a})| \delta(\frac{b + 1}{2^a})\}, x = \frac{b}{2^a} \& a, b \in Z \& k > 0 \end{cases} δ(x)=??????????{∣},x=0{δ(x?1)∣},x>0&x∈Z{∣δ(x+1)},x<0&x∈Z{δ(2ab?1?)∣δ(2ab+1?)},x=2ab?&a,b∈Z&k>0?

定理: 对于一个SN: x = { L | R }，若集合L中有最大元素$l_{max}$，那么{ $l_{max}$ | R } = x；类似地，若集合R中有最小元素$r_{min}$，那么{ L | $r_{min}$ } = x

将SN和游戏结合：对于一个游戏，如果它当前处于状态P，玩家L可以转移到的状态的集合为$P_L$，玩家R可以转移到的状态的集合为$P_R$，那么我们把这个游戏写作P = { $P_L$ | $P_R$ }。

• 当前所处的状态：P
  玩家L可以到达的状态：A B C
  玩家R可以到达的状态：D
  则：P = { A B C | D }

用字母G来表示刚才所述的局面SN对应的值：
如果G > 0，那么无论先手还是后手，玩家L都会获胜。
如果G < 0，那么无论先手还是后手，玩家R都会获胜。
如果G = 0，那么谁后手谁获胜。

回到这个问题，问题拆分后相当于对每列正方体根据SN求一个值，然后将这些值合并就是直接加起来（根据SN的加法规则）

考虑值的表示：（假设白色为左玩家

当没有正方体列的时候，为公平局面： G = { ∣ } = 0 G = \{|\} = 0 G={∣}=0

当只有一个列，列中只有一个白色正方体的时候， G = { 0 ∣ } = 1 G = \{0 |\} = 1 G={0∣}=1

当一列，列中有白色两个正方体 G = { 0 ， 1 ∣ } = 2 G = \{0， 1 |\} = 2 G={0，1∣}=2

推广到一列n个白色正方体G = n，一列n个黑色正方体 G = -n

推广到更一般，一列正方体为下方n个白色正方体，上方1个黑色正方体 G = { 0 , 1 , . . , n ? 1 ∣ n } = n ? 1 2 G = \{0,1,..,n - 1| n\} = n - \frac{1}{2} G={0,1,..,n?1∣n}=n?21?

一列正方体为下方n个白色正方体，上方m个黑色正方体 : $G=n?\frac{1}{2^{n+1}}?\frac{1}{2^{n+2}}?\dots \frac{1}{2^{n+m}}$

下方n个白色，上方m个为混色（m个中最下方为黑色），设除了最上方的正方体（黑色）剩余正方体的G值为u，总体n+m个正方体的$G=u?\frac{1}{2^m}$

这题的数据范围n = 40，每列正方体数为40，可以先对每列正方体计算G值，然后对半枚举情况，总体复杂度$O(2^{\frac{n}{2}})$

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

const ll N = 50;
ll num[N];
long double t[N];
map<long double, ll> mp;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    ll n;
    cin >> n;
    for (ll i = 0; i < n; ++i) {
        string s;
        cin >> s;
        ll siz = s.size();
        num[i] = siz;
        long double po = 1;
        bool flag = 0;
        for (ll j = 0; j < siz; ++j) {
            if (s[j] != s[0]) flag = 1;
            if (flag) po = po * 2;
            if (s[j] == 'W') t[i] += 1.0 / po;
            else t[i] -= 1.0 / po;
        }
//        cerr << t[i] << endl;
    }
    ll nn = n >> 1;
    for (ll st = 1; st < (1 << nn); ++st) {
        long double sum = 0;
        ll cnt = 0;
        for (ll i = 0; i < nn; ++i) {
            if ((st >> i) & 1) {
                sum += t[i];
                cnt += num[i];
            }
        }
        mp[sum] = cnt;
    }
    ll ans = 0;
    for (ll st = 1; st < (1 << (n - nn)); ++st) {
        long double sum = 0;
        ll cnt = 0;
        for (ll i = 0; i < (n - nn); ++i) {
            if ((st >> i) & 1) {
                sum += t[i + nn];
                cnt += num[i + nn];
            }
        }
        if (mp[-sum] > 0) ans = max(ans, mp[-sum] + cnt);
        else if(fabs(sum) == 0.0) ans = max(ans, cnt);
    }

    ans = max(ans, mp[0]);
    cout << ans << endl;

    return 0;
}