原文oi wiki:博弈论

Bash 博弈

Bash 博弈是一种简单的取石子博弈，其规则如下：

• 初始只有一堆石子，数量为 $N$。

• 两个玩家轮流操作，每次可以从堆中取走不超过 $M$ （$M \le N$） 个石子（至少取走 1 个）。

• 无法进行操作的玩家判负。

1.对拍

首先，我对于oi这个赛制有着极其的厌恶感!(主要是有一场打差了QAQ)所以我愤起写了这么一个博客。 对拍是什么呢?
oi赛制是看不到提交代码是否正确的,所以怎么去判断呢?这个时候我们可以用很暴力的方式来比对。
现在我们有一道题:输入a,b,输出a+b;我们现在有一个自己的代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a%20==1)cout<<a-b<<'\n';
    else cout<<a+b<<'\n';
    return 0;
}

原文oi wiki:树状数组 离散化

数组离散化

离散化步骤

1. 创建原数组的副本，同时记录每个元素出现的位置。
2. 将副本按值从小到大排序，当值相同时，按出现顺序从小到大排序。
3. 将离散化后的数字放回原数组。

原文oi wiki:贪心

贪心策略

1. 序列定义：

   • 序列 $a: a_1, a_2, a_3, \cdots, a_n$
   • 序列 $b: b_1, b_2, b_3, \cdots, b_n$

2. 问题：求 $\sum a_i b_j$（(i, j) 不重复）的最大值

3. 表达式：

   • $max = a_{(1)}b_{(1)} + a_{(2)}b_{(2)} + \cdots + a_{(n)}b_{(n)}$
     （其中 $a_{(i)}$ 是序列 (a) 中第 (i) 大的元素，$b_{(i)}$ 是序列 (b) 中第 (i) 大的元素）

背包DP

原文oi wiki:背包dp

1. 01 背包

每个物品只能获取一次。

模版

01Knapsack

原文oi wiki:二分图 二分图，又称二部图，是一类结构特殊的图。它的顶点集可以划分为两个互不相交的子集，使得图中的每条边都连接这两个集合之间的一对点，而不会连接同一集合内部的点。

得益于这种简单的结构，二分图不仅展现出许多优雅的性质，也广泛应用于现实生活中的建模场景，例如任务分配、推荐系统、匹配市场等。许多在一般图上困难的优化问题，在二分图上都可以高效、准确地求解。

模版

组合数

原文oi wiki:组合数

方法一：数据规模较小时使用动态规划（DP）

当数据规模较小时，可以使用动态规划的方式计算组合数。其核心思路基于组合数的递推公式

$$C_i^j=C_{i-1}^j+C_{i-1}^{j-1}$$

线性、区间、树形 DP

原文oi wiki:树形 DP区间 DP

1. 线性 DP

每个状态只依赖于前一个或前几个状态，且状态转移是线性的（即没有复杂的依赖关系）。通常用于解决序列或数组上的问题。

并查集

原文oi wiki:并查集

基础

介绍

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 顾名思义，并查集支持两种操作： 合并（Union）：合并两个元素所属集合（合并对应的树） 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合 路径压缩