博弈例题练习 luogu P5765 Problem 题目 $ nnn $ 堆石头,从中选择若干堆,进行Nim游戏,并规定先手取的第一堆。问先手必败的方案数量。 Solution 枚举第一步取第 kkk 堆,对于剩下的 n−1n-1n−1 堆dp, fif_{i}fi 表示这 n−1n-1n−1 堆中异或和为 iii 的方案数。 这部分的答案为 ∑i≥akfi\sum\limits_{i \ge a_k}f_ 2021-08-18 数学 #博弈论
博弈论和SG函数基础 公平组合游戏 公平组合游戏^gpzh的定义如下: 游戏有两个人参与,二者轮流做出决策,双方均知道游戏的完整信息; 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关,而与游戏者无关; 游戏中的同一个状态不可能多次抵达,游戏以玩家无法行动为结束,且游戏一定会在有限步后以非平局结束。 策梅洛定理 策梅洛定理[^cml]说明了,在公平组合游戏中,任意状态一定是胜态(先手必胜,N), 2021-08-17 数学 #博弈论
C++lambda表达式的简单应用 https://www.cnblogs.com/DswCnblog/p/5629165.html // 规定返回值类型 sort(a + 1, a + 1 + n, [](int x, int y) -> bool { return x > y; }); // 自动推断返回值类型 sort(a + 1, a + 1 + n, 2021-08-16
自适应辛普森法 一般求解定积分,采用自适应辛普森法。 二次函数积分公式(辛普森公式)^simpson $ ∫lrf(x)dx=(r−l)(f(l)+f(r)+4f(l+r2))6\int_l^r f(x) {\mathrm d}x = \frac{(r-l)(f(l)+f(r)+4 f(\frac{l+r}{2}))}{6}∫lrf(x)dx=6(r−l)(f(l)+f(r)+4f(2l+r)) $ 普通辛 2021-08-16 计算几何 #自适应辛普森法
模板:凸包周长 https://www.luogu.com.cn/record/55936318 使用单调栈, O(n logn)O(n \, \log n)O(nlogn) #include <bits/stdc++.h> #define rep(i, a, b) for (int i = (a); i <= (b); i++) #define per(i, a 2021-08-14 计算几何 #计算几何 #模板 #凸包
非旋转式Treap Treap分为旋转式和非旋转式,编写复杂度都不高。非旋转式的基本操作是分裂、合并,因此支持可持久化。 这里采用了记录权值出现次数的操作,由 cntcntcnt 这一字段记录,树的大小由 sizsizsiz 记录。 以下是基本操作: 分裂 split 把树分别分裂成 ≤val\le val≤val 和 >val> val>val 的两部分。 递归分裂左或右子树。 合并 merge 2021-08-14 平衡树 #treap #数据结构 #平衡树
后缀数组简述 模板题 #include <bits/stdc++.h> #define rep(i, a, b) for (int i = (a); i <= (b); i++) #define per(i, a, b) for (int i = (a); i >= (b); i--) using namespace std; const 2021-08-09 #SA
莫比乌斯反演例题 关于莫比乌斯反演,这篇说得非常清楚了。 记录以下做过的莫比乌斯反演例题。 P2257 YY的GCD ∑i=1N∑j=1M∑p∈P, p∣i, p∣j[gcd(ip,jp)=1]=∑p∈P∑i=1⌊Np⌋∑j=1⌊Mp⌋ε(gcd(i,j))=∑p∈P∑i=1⌊Np⌋∑j=1⌊Mp⌋∑d∣gcd(i,j)μ(d)=∑p∈P∑d=1∑i=1⌊Npd⌋∑j=1⌊Mpd⌋μ(d)\begin{ali 2021-07-30
简述CDQ分治 luogu随机到了一道题,看了题解才知道是CDQ。。 三维偏序 求满足 $ i<j,ai<aj,bi<bji<j,a_{i}<a_{j},b_{i}<b_{j}i<j,ai<aj,bi<bj $ 的 (i,j)(i,j)(i,j) 对数。 用 solve(l,r)solve(l,r)solve(l,r) 表示求解区间 [l,r][l,r 2021-07-26
Codeforces 729 Codeforces Round #729 (Div. 2) A #include <cstdio> #include <cstring> #include <algorithm> int T, n; int main() { scanf("%d", &T); while (T--) { 2021-07-17