HLAIA-光子

算法竞赛中涉及博弈论的知识并不多 公平组合游戏 Nim游戏 Nim游戏是一个很经典的博弈论模型，这类题有个通法通解：求Nim和。以下面的题目为例 题目 给定 nnn 堆石子，每堆有 a[i]a[i]a[i] 个石子 ，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。 问如果两人都采用最优策略，先手是否必胜。 分析 类似于这种题，问是否有必胜策略，计算异或和(Nim和)。 定义异或和(Nim和)为： Nim=a1⊕a2⊕a3⊕⋯⊕anNim = a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n Nim=a1​⊕a2​⊕a3​⊕⋯⊕an​ 异或和 != 0 先手玩家有必胜策略，后手玩家输 异或和 == 0 先手玩家输，后手玩家有必胜策略 原因： 异或和 ≠ 0：意味着至少有一个堆的某些位是“不平衡”的，当前玩家可以通过调整某个堆的石子数，使异或和变为0，迫使对手进入必输局面。 异或和 = 0：任何移动都会破坏平衡，使得对手可以采取策略让异或和再次归零，...

回溯与剪枝 当递归所衍生出的子节点不符合条件时，就该“看到不对劲就撤退”——中途停止并返回。这个思路就是回溯。在回溯中用于减少子节点的拓展函数就是剪枝函数。 其难度主要在于拓展子节点的时候如何构造停止递归并返回的条件。 以HDU 2553 N皇后为例 题目 不同行: old_x≠new_xold\_ x \not= new\_ xold_x=new_x 不同列: old_y≠new_yold\_ y \not= new\_ yold_y=new_y 不同对角线: abs(old_x−new_x)≠abs(old_y−new_y)abs(old\_ x - new\_ x) \not= abs(old\_ y - new\_ y)abs(old_x−new_x)=abs(old_y−new_y) 代码 12345678910111213141516171819202122232425262728293031323334353637383940#include <bits/stdc++.h>using namespace std;int n,lie[11]...

容斥原理 集合 SSS 的子集 A1A_1A1​ 有性质 p1p_1p1​ ，A2A_2A2​ 有性质 P2P_2P2​ ， …\dots… ， AnA_nAn​ 有性质 PnP_nPn​ 。 那么，集合 SSS 中具有性质 P1,P2,…,PnP_1,P_2,\dots,P_nP1​,P2​,…,Pn​ 的集合个数为 ∣⋂i=1nAi∣=∑i=1n∣Ai∣−∑1≤i≤j≤n∣Ai∩Aj∣+∑1≤i≤j≤k≤n∣Ai∩Aj∩Ak∣−⋯+(−1)n+1∣∩i=1nAi∣\Big|\bigcap_{i=1}^nA_i \Big| = \sum_{i=1}^n\left| A_i\right| - \sum_{1 \leq i \leq j \leq n} \left| A_i \cap A_j \right| + \sum_{1 \leq i \leq j \leq k \leq n} \left| A_i \cap A_j \cap A_k \right| - \dots + (-1)^{n+1} \left| \cap_{i=1}^n A_i \right| ​i=1⋂n​Ai...

ITA练习赛2 B 这道签到题我交了7发… 最初把题目看成了任意两个元素互素，结果怎么提交都不对，就发现看错题了… 1234567891011121314151617181920212223#include <bits/stdc++.h>using namespace std;const int maxn = 1e5+5;int n,a[maxn];map <int,int> ma;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n; a[0] = -1; bool pd; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=2;i<=n;i++){ if(__gcd(a[i],a[i-1]) != 1){ cout << "-1\n"; ...

基环树 基环树不是树，而是只有一个连通环的图，它有$ n 个点和个点和个点和 n $条边。 无向图上的基环树。在一颗基于无向图的无根树加上一条边，就形成了基环树。去掉环上任意一条边，基环树就变成了一颗真正的树 有向图上的基环树。一个有向无环图，如果能在图中加一条边形成一个自连通的环，则形成一颗基环树。把环看成一个整体，根据它与环外点的关系，把基环树分为两种：内向树，环外的点只能进入环内，所有边都指向环；外向树，环外的点无法进入环内，所有边都背离环。 （图是丑了一点，意思到位就行…） 基环树的找环问题，就是“图的连通性”的一个简化问题。 无向图，用拓扑排序的BFS找出环，操作结束后，度数大于$ 1 的点就是环上的点。具体做法：①计算所有点的度数；②把所有度数为的点就是环上的点。具体做法：①计算所有点的度数；②把所有度数为的点就是环上的点。具体做法：①计算所有点的度数；②把所有度数为 1 的点入队；③队列弹出度数为1的点，把它连的所有边都去掉，并将边所连的邻居点的度数减的点入队；③队列弹出度数为1的点，把它连的所有边都去掉，并将边所连的邻居点的...

拓扑排序 拓扑排序不是对数字进行大小排序的那种排序，而是对一系列事物的顺序关系和依赖关系进行排序，属于图论。拓扑排序的排序结果通常不是唯一的。 一个图能进行拓扑排序的充要条件是它是一个**有向无环图(DAG) **。 拓扑排序需要用到点的入度(Indegree)和出度 (Outdegree) 入度：以点$ v 为终点的边的数量，称为为终点的边的数量，称为为终点的边的数量，称为 v $的入度。 出度：以点$ u 为起点的边的数量，称为为起点的边的数量，称为为起点的边的数量，称为 u $的出度。 一个点的入度为0，说明它是起点，是排在最前面的；一个点的出度为0，说明它是终点，排在最后面。 拓扑排序的简单的图遍历，用BFS和DFS都能实现。 基于BFS的拓扑排序 (1)无前驱的顶点优先 先输出入度为0的点(无前驱，优先级最高)，以下是具体步骤： 找所有入度为0的点，放入队列作为起点，这些点谁先谁后没有关系。如果找不到入度为0的点，说明这个图不是DAG，不存在拓扑排序。 弹出队首元素a，将a的所有邻居点入度-1，入度减为0的邻居点入队。没有减为0的不入队。 继续上述操作，直到队列...

逆序对 最简单的求逆序对的方法：冒泡排序，时间复杂度$ O(n^2) $ 直接给无优化的代码，不解释了： 123456789101112131415161718#include <bits/stdc++.h>using namespace std;int a[10] = {3,5,7,9,2,1,4,6,8,10};int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n = 10, cnt = 0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(a[j] < a[i]){ swap(a[i],a[j]); cnt++; } cout << cnt << '\n'; ...

区间DP 以一道模板题目为例----石子合并 不能用贪心，会陷入局部最优解。用DP求解 定义dp[i][j]为合并第i堆到第j堆的最小花费 状态转移方程为： dp[i][j] = min(dp[i][k] + dp[k+1][j] + w[i][j])，i <= k < j，w[i][j]表示第i堆到第j堆的石子总数，可以用前缀和计算。dp[1][n]就是答案 复杂度O(n3)，可以用四边形不等式优化到O(n2) 自顶向下的思路： 计算大区间[i,j]的最优值时，合并它的两个子区间[i][k]和[k+1][j]，对所有可能的合并(i <= k < j)采取最优合并。子区间再分解为更小的区间，最小区间[i,i+1]只包含两堆石子 自底向上的编程： 先在小区间进行DP得到最优解，再逐步合并小区间为大区间。以下是code： 123456789101112const int INF = 0x3f3f3f3f;int dp[n][n] {}; //C++11特性，集成初始化为0for(int len = 2; len <= n; ...

蓝桥杯15届国赛B 题目可以在官网https://www.lanqiao.cn/上查到 填空A 暴力找每个长度为8~16的子区间，然后判断是否满足条件即可 12345678910111213141516171819#include <bits/stdc++.h>using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); string s = " kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th"; int si = s.size()-1, sum = 0; for(int i=1;i<=si;i++){ bool num = 0, fu = 0; for(int j=i;j<=i+15 &am...

CF1013 div3 给个题目链接，就不一题一题截图了：https://codeforces.com/contest/2091 F 比较好的思路：dp+前缀和 用u[i][j]表示从i-1排满足距离条件的点到点(i,j)的所有走法之和，状态转移方程为： u[i][j] = (prep[i-1][r2] - prep[i-1][l2]); 用p[i][j]表示在第i排满足距离条件的点横着走到点(i,j)的所有走法之和，状态转移方程为： p[1][j] = (preu[1][r1] - preu[1][l1]); 用preu[i][j]表示第i排的u的前缀和 用prep[i][j]表示第i排的p的前缀和 先特殊处理第1排（起始排），再从2排到n排逐排处理 比较我硬着头皮写的思路和官解的思路，我发现两个本质上差不多，就是实现方法不同 来看看我写的屎： （dp+BFS） 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585...