传送门:CodeM2017 决赛 melon

题目大意:Alice 和 Bob 玩博弈玩累了于是开始吃瓜,Alice 手速永远比 Bob 快,同时刻拿瓜 Alice 先抢到,每人每次拿瓜 L 个,总共 n 个瓜,每人需要 k 个单位的时间吃掉 k 个瓜,而且 Alice 和 Bob 永远是互相知道对方是绝顶聪明的,问 Alice 最多能吃到多少瓜
这道题其实就是一个分析

情况一:$n \leq L$

这时候我们的 Alice 会凭借她的先手优势直接拿掉 n 个瓜。

情况二: $L < n \leq 2L$

容易知道Bob一定不可能比Alice吃的多(否则Alice在 $n > L$的状况下跟 Bob 取同样的就行),因此我们尝试最大化 Bob 吃掉的瓜,Alice 一定能至少先吃 $L$个瓜,因此 Bob 最多还能拿 $n-L$个瓜,显然这是可以拿到的,所以 Bob 最多吃 $n-L$个瓜,Alice 吃 $L$个

情况三 : $n > 2L$

思路依旧是最大化Bob的瓜,显然每次拿一个瓜是不亏的,就算Alice手速快,但在剩余瓜数 $>2L$的时候Bob是跟Alice保持同步的,而且若出现一种情况,当Bob吃完某一个瓜的时候猛然发现只剩下 $2L$个瓜了,然后Alice手里还有 $k>=1$个瓜在苦苦地吃,Bob就能先拿 $k-1$个瓜吃完,然后再一次拿掉 $L$个瓜,这样他就不会比Alice吃的少了,但Alice辣么聪明她不会给他这样的机会的,因此Alice也每次拿一个瓜,因此他们在 $n>2L$时永远保持同步,一旦 $n<=2L$,Alice 就会拿 L 个瓜,Bob 会拿掉剩下的瓜,因此 Alice 最多能吃 $[\frac{n+1}{2}]$个瓜
代码就不用给了吧。

传送门:2017 ACM-ICPC ECL-FINAL L 题

题目大意:给一个空序列,两人(就 Alice 先手 Bob 后手吧)轮流每回合在任意一个位置填’S’ 或者’O’,填出’SOS’ 的人胜利,给出序列长度求是否有必胜策略,若有,输出谁必胜。

个人感觉挺毒瘤的 QwQ
首先,序列长度 $n < 7$的时候,显然是没有必胜策略的。
$n=7$的时候,Alice 可以这样做,她能取得胜利:
第一步 (Alice):
$$—\;—\;—\;S\;—\;—\;—$$
第二步 (Bob)(由对称性,不妨放在左边):
$$—\;—\;S\;S\;—\;—\;—$$
第三步 (Alice):
$$—\;—\;S\;S\;—\;—\;S$$
容易发现后面的四个格子被 “封死” 了(谁下就必输),而且能下的格子只剩下两个,当前 Bob 下,所以最后下被’ 封死’ 格子的一定是 Bob。所以 Alice 获胜。
那如果 Bob 第二步这样下呢:
$$S\;—\;—\;S\;—\;—\;—$$
容易分析,还是 Alice 获胜。
我们发现,$S\;—\;—\;S$的阵型是弄出必胜策略的关键,但为什么即使对方也构造这种阵型依然是赢不了的呢?
容易知道,无论如何下,两个人一轮之后,接下来的可下位置($n-$下过位置 $-$封死位置)的奇偶性是保持不变的(不变量),因此胜负性是始终保持不变的。
因此下最后一步的,n 是奇数的话肯定是 Alice,反之是 Bob。
n 为奇数的时候,Alice 肯定有优势,可能会赢,由上面的讨论,易知 $n \geq 7$的时候是一定能赢的,因为 Alice 能构造出不可能平局的阵型 $S\;—\;—\;S$
n 为偶数的时候,则是 Bob 有优势,这个时候 Alice 会尽力阻止 Bob 形成不可能平局阵型,因此 Alice 会在正中间下一个 O,
相当于把棋盘分成了 $n/2$和 $n/2-1$两份,Bob 当然会挑大的那一份继续下,这时候相当于 Bob 先手,由上面的讨论易知需要有 7 个空位才会赢,而且 O 相邻的那个位置是不能放 S 的,因此要 $n/2\geq 8$,也就是 $n\geq 16$的时候 Bob 是必胜的。
也就是这种状况 (一轮过后):
$$—\;—\;—\;S\;—\;—\;—\;—\;O\;—\;—\;—\;—\;—\;—\;—$$
其它情况就是平局了。
代码也不给了(几个 if 真的太短了懒得找记录复制)

传送门:HNOI2007 分裂游戏

题目大意:有 n 个瓶子, 第 i 个瓶子中装有 $p[i]$颗巧克力豆,Alice 和 Bob 轮流取豆子,每一轮每人选择 3 个瓶子。标号为 i,j,k, 并要保证 i < j , j < = k 且第 i 个瓶子中至少要有 1 颗巧克力豆,随后这个人从第 i 个瓶子中拿走一颗豆 子并在 j,k 中各放入一粒豆子,无法取豆子的人输

显然这种游戏可以考虑 Nim
但是如果把每个游戏当成一个独立游戏的话,我们会发现并不好表示每个游戏的 SG 函数值,这里我们改变一下策略,我们把每一个豆子当成一个游戏,那样的话我们就可以找到准确的后继状态,设第 i 个瓶子里的豆子为 $SG(i)$,则有
$$SG(i)=mex \{SG(j)\;xor\; SG(k) | i \lt j \leq k = n \}$$

然后把所有豆子 $xor$起来就是答案了。
代码:

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
#define ll long long
#define N 105
int T, n, num[N], a, b, c, sg[N], now, fl[N], ans;
inline int mex (int x)
{
    int i = 0;
    while (fl[i] == x) ++i;
    return i;
}
int main ()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        fo (i, 1, n)
            scanf("%d", &num[i]);
        sg[n] = 0;
        fd (i, n - 1, 1)
        {
            ++now;
            fo (j, i + 1, n)
                fo (k, j, n)
                    fl[sg[j] ^ sg[k]] = now;
            sg[i] = mex(now);
//          printf("sg[%d] = %d\n", i, sg[i]);
        }
        ans = 0;
        fo (i, 1, n)
            if (num[i] & 1) ans ^= sg[i];
        if (!ans) printf("-1 -1 -1\n0\n");
        else
        {
            int cnt = 0;
            a = b = c = 0;
            fo (i, 1, n)
                if (num[i])
                {
                    fo (j, i + 1, n)
                        fo (k, j, n)
                            if ((ans ^ sg[i] ^ sg[j] ^ sg[k]) == 0)
                            {
                                if (!a)
                                {
                                    a = i; b = j; c = k;
                                }
                                ++cnt;
                            }
                }
            printf("%d %d %d\n%d\n", a - 1, b - 1, c - 1, cnt);
        }
    }
}

传送门:Daizhenyang's Coin

题目大意:桌面上有 n 个硬币,其中有一些正面朝上,而有一些背面朝上,两个人轮流游戏。当轮到一个人时,他需要选取一枚正面朝上的硬币,翻转该硬币,并且再选取它之前的 0 或 1 或 2 枚硬币(不一定正面朝上),并翻转它们。无法操作的人算输,问先手是否必胜。

其实还是类似的玩法,把每个硬币当成一个独立的游戏,然后把所有值 $xor$起来就行了,但是这次不同的是,算 $SG$函数的复杂度太大了 $a[i] <= 10^8$,因此我们需要先打个表(雾
打表代码:

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u, v) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
#define ll long long
#define N 105
int T, n, num[N], a, b, c, sg[N], now, fl[N], ans;
inline int mex (int x)
{
    int i = 0;
    while (fl[i] == x) ++i;
    return i;
}
int main ()
{
    scanf("%d", &n);
    sg[0] = 0;
    fo (i, 1, n)
    {
        ++now;
        fl[0] = now; //choose zero
        fo (j, 1, i - 1)
            fl[sg[j]] = now;
        fo (j, 1, i - 1)
            fo (k, j + 1, i - 1)
                fl[sg[j] ^ sg[k]] = now;
        sg[i] = mex(now);
    }
    fo (i, 1, n)
        printf("%d %d %d\n", i, sg[i], i * 2 - sg[i]);
}

可以发现 $ i , sg[i] , i*2-sg[i] $十分有规律

有一个十分不显然的关系:

$$SG[i]=i*2- ( count ( a [ i ] -1 ) \& 1 ) -1$$

其中 $count(a[i]-1)$表示 $a[i]$二进制中 $1$的个数
然后我们就可以很开心的 A 掉这题啦~
(注意题目中的 $a[i]$可能重复,要去重)
代码:

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define lowbit(x) (x & -x)
int n, a[1005], ans, sg;
inline int count (int x)
{
    int ret = 0;
    while (x)
    {
        x -= lowbit(x);
        ++ret;
    }
    return ret;
}
int main ()
{
    while (~scanf("%d", &n))
    {
        ans = 0;
        fo (i, 1, n)
            scanf("%d", &a[i]);
        std::sort(a + 1, a + n + 1);
        n = std::unique(a + 1, a + n + 1) - a - 1;
        fo (i, 1, n)
        {
            ++a[i];
            if (a[i] == 1) sg = 1; else
            sg = a[i] * 2 - ((count(a[i] - 1) & 1) ? 2 : 1);
            ans ^= sg;
        }
        if (ans)
            printf("No\n");
        else
            printf("Yes\n");
    }
}
分类: 文章

HomuraCat

明日は何になる? やがて君になる!

2 条评论

XZYQvQ · 2018年10月1日 4:49 下午

Orz 跪膜巨犇
很快就要 NOIP 了吧,大佬 RP++哦~

    quhengyi11 · 2018年10月1日 7:44 下午

    您太强啦 qwq,也祝您 NOIP2018rp++

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注