【8.6】代码源 - 【前缀集】【矩阵游戏】【谁才是最终赢家？】【放置多米诺骨牌】

#930. 前缀集

题意：给定两个长为 $n(1\le n\le 5\times 10^5)$ 的序列 $a_i,b_i$ ，有 $m(1\le m\le 5\times 10^5)$ 次询问，每次询问给定 $i,j$ ，问 { a 1 , a 2 , ⋯   , a i } \{a_1,a_2,\cdots,a_i\} {a1​,a2​,⋯,ai​} 和 { b 1 , b 2 , ⋯   , b j } \{b_1,b_2,\cdots,b_j\} {b1​,b2​,⋯,bj​}两个集合是否相等。

题解：(哈希/前缀最大值)代码源每日一题 Div1 前缀集

思路：可以用哈希做。哈希有两种，一种是和前后顺序有关的有序哈希，公式是 $h(i)={\sum }_{j=1}^i{a}_j\times bas{e}^{i-j}$ ，完全相等取决于每个位置上的元素都相等；另一种是和前后顺序无关的无序哈希，公式是 $h(i)={\sum }_{j=1}^{i}f(a_j),f(x)$ 为多项式，完全相等只取决于和下标内的元素多项式值之和。

这道题我们只关注每个数第一次出现的位置。这里用的是无序哈希，使用 ULL 自然溢出。

ULL sa[N], sb[N];

ULL f(ULL x){
    return 10 + 17 * x * x + 29 * x * x * x * x * x;
}
1
2
3
4
5

AC代码：http://oj.daimayuan.top/submission/322987

---

#956. 矩阵游戏

题意：

题解：(二分图)代码源每日一题 Div1 矩阵游戏

思路：这种三个格子确定矩形上第四个格子的模型容易想到学过的二分图，然后就是抄题解的结论了（ 。二分图的生成树计数。

AC代码：http://oj.daimayuan.top/submission/323132

---

#931. 谁才是最终赢家？

题意：小明和小红经常玩一个博弈游戏。给定一个 $n\times n$ 的棋盘，一个石头被放指定位置。他们轮流移动石头。每一回合，选手只能把石头向上，下，左，右四个方向移动一格，并且要求移动到的格子之前不能被访问过。谁不能移动石头了就算输。

假如小明先移动石头，而且两个选手都以最优策略走步，问最后谁能赢？

题解：(黑白染色) 代码源每日一题 Div1 谁才是最终赢家？

思路：打表找规律。题解有证明。

AC代码：http://oj.daimayuan.top/submission/323459

---

#964. 放置多米诺骨牌

题意：给一个图表，图表是一个直方图，n列的高度分别为$a_1,a_2,\dots ,a_n(a_1\ge a_2\ge a_3....\ge a_n)$，你有许多大小为 $1\times 2$ 的多米诺骨牌(可以旋转)，不重叠最多可以放置多少个呢

题解：(黑白染色)代码源每日一题 Div1 放置多米诺骨牌

思路：黑白染色，答案就是黑白数量的最小值。

AC代码：http://oj.daimayuan.top/submission/323676