白色L号谢谢

题解

/ 注册

全部文章 / 题解（共22篇）

Matrix

很显然的一个二维矩阵哈希，就是有点卡内存。离线处理即可。 #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef ...

2020-12-04

3 796

[TJOI2017]DNA

三个不同，三个叶子，分治解决。时间复杂度O(n*log m) #include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; typedef unsign...

2020-12-03

1 538

Neat Tree

可以分开计算，先计算所有区间内的最大值之和，再减去所有区间的最小值之和。 #include <iostream> #include <stdio.h> #include <string.h> #include <time.h> #include &l...

2020-07-13

0 609

chess

一道博弈题，可以先用SG函数打表，看看什么时候先手会输。发现(1,2),(3,5),(4,7)...其实就是个威佐夫博弈。实际上向左边移动等价于取第一堆石子，向下移动等价于取第二堆石子，向左下移动等价于两堆同时取相同数目的石子。 #include <stdio.h> #include &...

2020-07-12

1 519

游戏

SG定理：n个有向图游戏组成的组合游戏当且仅当SG值异或和等于0时先手必输，否则先手必胜。直接求出每个状态的SG值，最后遍历每堆石头第一次取的情况，如果能满足异或和等于0即留给对手一个必败状态，则方案数加1。 #include <bits/stdc++.h> #include <u...

2020-07-07

0 735

取石子

设d[i][j]表示先手面临两堆石子分别为i，j时的取胜状态。直接求SG函数即可。实际上可以通过值看出来两堆石子和为奇数时候先手必胜，否则后手胜。因为每次取的都为奇数并不会对总的石子数奇偶性造成改变。所以奇数时即会有奇数轮，先手必胜。 #include <bits/stdc++.h> #...

2020-07-07

3 466

是是非非

nim博弈的基础上增加了修改，a ^ a = 0。所以每次修改的时候我们先异或上a[x]再异或上y,最后把a[x]变成y。判断异或和是不是0即可。 #include <bits/stdc++.h> #include <unordered_map> using namespac...

2020-07-07

1 807

黑黑白白

比较明显的SG函数。设d[x]表示先手轮到x点时的取胜情况。当子状态有必败状态时，该状态为必胜状态。当子状态全部为必胜状态，该状态为必败状态。 #include <bits/stdc++.h> #include <unordered_map> using namespace ...

2020-07-07

2 501

Disport with Jelly

数字x左边有x - L个数字，右边有R - x个数字。可以看成有两堆石子，分别有x - L个、R - x个。玩家每次可以取多个或者取完，但至少取一个。至此就是一个nim博弈。考虑异或和等于0即可。或者考虑对称博弈，每次先手取多少，对手跟着在另一边取多少，因为两边的数目一样，所以当x - L = R ...

2020-07-07

2 588

捡石头

经典Bash博弈。结论：n % (m + 1) = 0时先手必输，否则后手必赢。当n % (m + 1) = 0时，先手如果出k，后手跟着出一个(m + 1 - k)即可。最终会进行(n / (m + 1)) * 2轮，后手胜。当n % (m + 1) != 0可知n % (m + 1) <=...

2020-07-07

1 617