传送门: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");
    }
}
分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

2 条评论

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

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

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

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

发表评论

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

你是机器人吗? =。= *