ACM训练日记—4月1日

时间:2022-07-04 13:51:10

        还是先整理下昨天收获最多的两道题吧,因为我太菜,直接让全队少A了两个题。QAQ

 ZOJ—3964

题意:给出两个数组a和b,a表示每一堆石子的个数,b(当b=0,Alice随便取,当b=1,Alice只能取奇数个,当b=2,Alice只能取偶数个),两个人Alice和Bob,轮流取石子,Bob随便取(至少拿1个)。Alice先取。问谁赢。

       这是道很明显的博弈题,首先因为两人取石子的规则不一样,所以这道题无法使用sg函数推规律。那么就来分析

1,Bob相对来说拥有主动权(很明显,不受限)

2,当ai=奇数,bi=2时,Alice无法拿走这堆,有这种情况Alice必败。

3,当(bi=2||bi=1)&&ai!=1超过两堆时,Alice必败。(必有一堆会被Bob改变成奇数)。

4,当只有一堆(bi=1||bi=2)&&ai!=1时,Alice必须先处理那堆,否则必败。

5,当bi=1&&ai=1时或bi=0的堆,就是正常的Nim博弈。

       其实这道题自己证明下第3条中多个bi=1必败的理论,还有第4条。手动推下就行。

 这道题难度并不难,但是在sg函数无法用的情况下确实很难受,不能过分依赖sg函数。明明并不难的题目,我有点钻牛角尖,认为在bi=2&&ai是奇数情况下可以反逼Bob取走这堆,还是我太菜了。。。必须恶补博弈的题目了

 ZOJ—3962

题意:给你十六进制下  每个数字的价值  问从m开始  显示n个十六进制数字需要的价值  定义FFFFFFFF+1=0

        这道题网上绝大多数题解都是数位dp。但我的思路不同。

因为只输入八位数,每一位数出现一次就加一次权值,所以只要模拟两个数之间每一位数的跳动此数轮回算出来就可以了。。。。。然而这个算法要求考虑的情况实在太多,还有精度控制,我调了很长时间,还是输出不对,还是因为我太菜的原因,有思路却没完成出代码来,太丢人了。

下面是我翻遍博客找到和我一模一样思路的大佬写的代码,简直把我美哭了,居然这么短。

来自:https://www.cnblogs.com/fightfordream/p/6764475.html

const LL MOD = 1LL << 32;
int w[] = { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6, 6, 5, 4, 5, 5, 4 };
LL sum[20];
LL solve(LL x)
{
    if(x < 0) return 0;
    LL pw = 1, ans = 0;
    for(int i = 1; i <= 8; i++, pw*=16)
    {
        LL a=x/(pw*16)*sum[16]; //这一位总共完整跑了几轮
        LL b=sum[x/pw%16]; //跑完a轮后还有剩余b次
        LL c=(x%pw+1)*w[x/pw%16]; //当前的这一位的这一个数要多加几次,0也算一个所以+1
        ans+=(a+b)*pw+c;//a和b每次都会停留pw秒
    }
    return ans;
}

       

      接下来一段时间博弈,组合数学,dp,计算几何基础。