Summer training daily record 7.19~7.22

2023-07-20

技术 / 算法类

概率与期望

https://notes.sshwy.name/Math/Expectation/Classic/

哈夫曼树

费马点

Dilworth定理反链定理

https://blog.csdn.net/shulianghan/article/details/109070679

牛顿迭代法优化 sqrt

组合数取模的各种方法

http://acm.hdu.edu.cn/contest/problem?cid=1098&pid=1012

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#define INF 0x3f3f3f3f
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 100, mod = 1e9 + 7;
int sum[N];
ll jie[N], res[N];
void init() {
jie[1] = 1;
jie[0] = 1;
for (int i = 2; i <= 1e6; i++) {
jie[i] = i * jie[i - 1], jie[i] %= mod;
}
}
ll qpow(ll a, ll b, ll m = mod) {
ll s = 1;
while (b) {
if (b & 1)s = (s * a) % m;
b >>= 1;
a = (a * a) % m;
}
return s % m;
}
ll inv(ll x,ll m=mod) {
x %= m;
return qpow(x, m - 2, m);
}
ll C(int n, int m) {
if (m == n)
return 1;
return (jie[m] * inv(jie[m - n] * jie[n])) % mod;
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
sum[i] = 0, res[i] = 0;
while (m--) {
int u, v;
cin >> u >> v;
sum[u]++, sum[v]++;
}
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= sum[i]; j++) {
res[j] += C(j, sum[i]), res[j] %= mod;
}
}
ll ans = res[2];
for (int i = 3; i <= n - 1; i++) {
ans ^= res[i];
}


cout << ans <<'\n';
}
int main() {

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int t;
cin >> t;
while (t--)
solve();
return 0;
}

各种树

https://www.cnblogs.com/maybe2030/p/4732377.html

卡spfa

https://www.cnblogs.com/luckyblock/p/14317096.html

bellmon-ford
迭代n次，
for n（不超过n条边的路径）
for 所有边//松弛操作
dist[b]=min(dist[b],dist[a]+w)

spfa就是队列优化的bellman_ford算法
使用spfa判断图中是否存在负环的话，有两种方法

判断一个点是不是已经进入队列了n次，由bellman_ford算法可以知道，如果不存在负环最多经过n次迭代就可以得到1到任何一个点的最短距离，一个点最多被更新n-1次

判断到当前点的最短路径长度是不是大于等于n了！如果是的话，就说明存在一条路径有n的长度，那么该路径有n+1个点，必有两个点相同，所以一定存在负环
需要注意的是判断整个图存不存在负环，并不是判断从1开始存不存在负环，所以一开始要把所有点加入到队列中
数组模拟单链表

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()
{
    queue<int> q;

    for (int i = 1; i <= n; i ++ )
    {
        st[i] = true;
        q.push(i);
    }

    while (q.size())
    {
        int t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if (cnt[j] >= n) return true;
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    if (spfa()) puts("Yes");
    else puts("No");
    return 0;
}

vector存图

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector> 
#include<queue>
using namespace std;
const int N = 2010;
const int INF = 0x3f3f3f3f;
int n, m;
bool st[N];
int dist[N];
int cnt[N];
struct VER
{
	int to;
	int w;
};
vector<VER> h[N];

void add(int a, int b, int w)
{
	VER ver;
	ver.to = b;
	ver.w  = w;
	h[a].push_back(ver);
}

bool spfa()
{
// 	memset(dist, 0x3f, sizeof dist);
// 	dist[1] = 0;
	
	queue<int> q;
	// 所有点都入队 
	for(int i = 1; i <= n; i++)
	{
		st[i] = true;
		q.push(i);
	}
	
	while(q.size())
	{
		int t = q.front();
		q.pop();
		st[t] = false;
		if(cnt[t] >= n) return true;
		for(int i = 0; i < h[t].size(); i++)
		{
			int j = h[t][i].to, w = h[t][i].w;
			if(dist[j] > dist[t] + w)
			{
				dist[j] = dist[t] + w;
				cnt[j] = cnt[t] + 1; // t->j路径长度+1 
				if(!st[j]) // j不在队列中 
				{
					q.push(j);
					st[j] = true;
				}	
			}	
		} 
	}
	return false;
}	

int main()
{
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		add(a, b, w);
	}
	bool t = spfa();
	if(t) puts("Yes");
	else  puts("No");
	return 0;
}

图和树的概念整理

https://blog.csdn.net/weixin_45697774/article/details/104495126
https://blog.csdn.net/weixin_45697774/article/details/105352366

链式向前星存图

https://blog.csdn.net/lookqaq/article/details/81304637

向前星：边集数组
所有边首先按照起点从小到大第一次序排列，然后按照终点从小到大第二次序排列
并记录以i为起点的边的数量(len[i])，和所有符合条件的边的在数组中的起始位置(head[i])
主要用于优化spfa,dfs,bfs;
因为需要排序操作，使用快排时间至少为O（nlogn）

链式向前星：优化了排序的向前星

struct Edge
{
     int next;
     int to;
     int w;
};
其中edge[i].to表示第i条边的终点,edge[i].next表示与第i条边同起点的下一条边的存储位置,edge[i].w为边权值.
另外还有一个数组head[i],存储所有符合起点为i的边的在数组中的起始位置
head[]数组一般初始化为-1,对于加边的add函数是这样的:
void add(int u,int v,int w)//起点u，终点v，边权重w
{
    edge[cnt].w = w;
    edge[cnt].to = v;
    edge[cnt].next = head[u]//与第cnt条边同起点(u)的下一条边的存储位置
    head[u] = cnt++;
}

模拟输入输出
1 2
2 3
3 4
1 3
4 1
1 5
4 5
得到（cnt=0）
edge[0].to = 2; edge[0].next = -1; head[1] = 0;//
edge[1].to = 3; edge[1].next = -1; head[2] = 1;
edge[2].to = 4; edge[2],next = -1; head[3] = 2;
edge[3].to = 3; edge[3].next = 0; head[1] = 3;//
edge[4].to = 1; edge[4].next = -1; head[4] = 4;
edge[5].to = 5; edge[5].next = 3; head[1] = 5;//
edge[6].to = 5; edge[6].next = 4; head[4] = 6;
例如起点为1的边，读取head[1]=5,从5——>3——>0链式逆序回溯


struct node
{
    ll v,nex,val,u;
}e[N];

ll head[N],cnt;

inline void add(ll u,ll v,ll val)//从u到v，从父节点到子节点
{
    e[++cnt].nex=head[u];
    e[cnt].val=val;//可有可无
    e[cnt].v=v;
    e[cnt].u=u;//可有可无
    head[u]=cnt;
}
for(ll i=head[u];i;i=e[i].nex)
    {
        ll v=e[i].v;
        ---------------
    }

//这样我们就可以遍历全部的点了！！！：）

二分图/二部图

01背包朴素优化

只需要用到上一层或者下一层状态时，在两个状态（0·1）之间轮流转化
利用滚动数组或者代码的等价变形优化

https://www.acwing.com/solution/content/52491/

各种使用时新晋语法函数

2023-07-12

技术 / 算法类

new int[m]

例：p[n]为struct,有*time，p[n].time=new int[m],time变成int 数组，有m项

auto

for(auto t:res)cout<<t<<’ ‘;
auto res=get_di(X);【vector get_di(int n)】

for（int i=n-1;~i;i–）

在for循环中，~~i的作用是判断i是否为-1。因为-1的二进制表示是全1，所以~~(-1)就是全0，也就是0。所以当i等于-1时，~i就为0，循环就会终止。这样可以避免使用==或!=运算符来比较i和-1。

const double eps=1e-6;

判断浮点数是否为零或者小于零时由于浮点数特性需要判断它是否小于一个很小的数

struct结构体内比较格式

struct node{
    int l,r;
    bool operator<(const node &w)const{
        return r<w.r;
    }
}

* &的传递区别

vector传递高精度计算

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    return 0;
}

*lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i]

它返回一个指向范围 [first, last) 中第一个不小于 val 的元素的迭代器
可以替代二分查找

priority_queue<int,vector,greater> heap;

优先队列是一种特殊的队列，它的元素被赋予优先级，当访问元素时，具有最高级优先级的元素先被访问12。在C++中，priority_queue是一个容器适配器，它提供了常数时间查找默认情况下最大（或最小）元素的功能，但以对数时间为代价进行插入和提取。
empty() 如果队列为空返回真

    pop()       删除队顶元素

    push()     入队一个元素

    size()      返回优先队列中拥有的元素个数

    top()        返回优先队列队顶元素

默认情况下，priority_queue是一个大根堆，这意味着根节点的值大于或等于子节点的值,
如果想要使用小根堆，可以将priority_queue的第三个参数设置为greater。

大根堆是一种完全二叉树，其中所有父节点的值都比左右孩子的值大。小根堆与大根堆相反，其中所有父节点的值都比左右孩子的值小。
大根堆例如：
10
/
8 7
/ \ /
6 4 3

是默认的大根堆实现，top()是当前优先队列的最大值

#include <iostream>
#include <queue>
using namespace std;
int my_array[10] = {3,5,6,2,1,-8,10,4,-7,-6};
int main()
{
    priority_queue<int> q;
    
    for (int i=0;i<10;i++)
    {
        q.push(my_array[i]);
    }
 
    for (int i = 0; i < 10; i++)
    {
        cout << "order: " << q.top() << endl;
        q.pop();
    }

小根堆例如
1
/
2 3
/ \ /
4 5 6

cout<<fixed<<setprecison(15)<<dp[a]

精确输出小数点后几位

while (cin >> a >> b >> c, a || b || c)w[a][b] = c;

用于输入多组数据且全为0时表示结束的输入

lower_bound()、upper_bound()、equal_range() 以及 binary_search()

lower_bound()

/*
在 [first, last) 区域内查找不小于 val 的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//在 [first, last) 区域内查找第一个不符合 comp 规则的元素
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);
*/

#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i,int j) { return i>j; }

//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i>j;
    }
};

int main() {
    int a[5] = { 1,2,3,4,5 };
    //从 a 数组中找到第一个不小于 3 的元素
    int *p = lower_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;

    vector<int> myvector{ 4,5,3,1,2 };
    //根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
    vector<int>::iterator iter = lower_bound(myvector.begin(), myvector.end(),3,mycomp2());
    cout << "*iter = " << *iter;
    return 0;
}

upper_bound()

/*
//查找[first, last)区域中第一个大于 val 的元素。
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val);
//查找[first, last)区域中第一个不符合 comp 规则的元素
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
                             const T& val, Compare comp);
*/

#include <iostream>     // std::cout
#include <algorithm>    // std::upper_bound
#include <vector>       // std::vector
using namespace std;
//以普通函数的方式定义查找规则
bool mycomp(int i, int j) { return i > j; }
//以函数对象的形式定义查找规则
class mycomp2 {
public:
    bool operator()(const int& i, const int& j) {
        return i > j;
    }
};
int main() {
    int a[5] = { 1,2,3,4,5 };
    //从 a 数组中找到第一个大于 3 的元素
    int *p = upper_bound(a, a + 5, 3);
    cout << "*p = " << *p << endl;
    vector<int> myvector{ 4,5,3,1,2 };
    //根据 mycomp2 规则，从 myvector 容器中找到第一个违背 mycomp2 规则的元素
    vector<int>::iterator iter = upper_bound(myvector.begin(), myvector.end(), 3, mycomp2());
    cout << "*iter = " << *iter;
    return 0;
}

equal_range()

http://c.biancheng.net/view/7531.html

1
2
3

/*

*/

binary_search()

http://c.biancheng.net/view/7537.html

1
2
3

/*

*/

增加堆栈空间

int main() {
int size(512<<20); // 512M
asm ( “movq %0, %%rsp\n”::”r”((char*)malloc(size)+size)); // YOUR CODE

exit(0);

}

c++引用

引用的本质：

引用是一个变量的别名。可以把它想象成对一个已存在变量的另一个称呼。

引用不是一个独立的变量，它不占用额外的内存空间来存储自身的值。它是直接指向原始变量的内存地址。

对引用的操作等同于对原始变量的操作。

引用的声明和初始化：

语法：类型 &引用名 = 变量名;

类型: 引用所引用的变量的类型。

&: 引用声明符。它是区分引用和普通变量声明的关键。

引用名: 你为引用选择的名称。

变量名: 引用所引用的已存在的变量的名字。

必须初始化：引用在声明时必须立即初始化，即必须指定它所引用的变量。这是因为引用一旦创建，就永远绑定到那个变量，不能再改变。尝试不初始化引用会导致编译错误。

1
2
3

int num = 10;
int &refNum = num; // 正确： refNum 是 num 的引用，并且初始化了
// int &ref;        // 错误： 引用 ref 没有被初始化

引用的使用：

使用引用就像使用原始变量一样。你可以读取引用的值，修改引用的值，将引用传递给函数等等。所有这些操作都会直接影响原始变量。


int num = 10;
int &refNum = num;

cout << refNum;   // 输出 10 (读取引用 refNum 的值)
refNum = 20;     // 修改引用 refNum 的值（同时修改了 num 的值）
cout << num;      // 输出 20 (num 的值已经被 refNum 修改)
IGNORE_WHEN_COPYING_START
content_copy
download
Use code with caution.
C++
IGNORE_WHEN_COPYING_END

引用的特性：

不能重新绑定：引用一旦绑定到一个变量，就不能再绑定到另一个变量。

不存在空引用：引用必须始终引用一个有效的对象。不允许有空引用（即引用不指向任何东西）。

不能引用字面常量：通常情况下，你不能直接引用字面常量（例如数字、字符串）。如果你想引用字面常量，需要先将字面常量赋值给一个变量，然后引用这个变量。但是，使用 const 关键字可以引用常量。

//int &ref = 10; //错误
const int &ref = 10; //正确，相当于创建了一个临时变量 const int temp = 10; int &ref = temp;
IGNORE_WHEN_COPYING_START
content_copy
download
Use code with caution.
C++
IGNORE_WHEN_COPYING_END

引用与指针的区别：

引用必须初始化，指针可以不初始化。

引用不能重新绑定，指针可以重新指向。

引用不存在空引用，指针可以为空指针 (nullptr)。

引用更安全：由于引用必须初始化且不能重新绑定，因此使用引用可以避免一些空指针和野指针的问题。

引用更容易使用：使用引用时不需要像指针那样使用 * 解引用操作符。

引用的应用场景：

函数参数传递：通过引用传递参数可以避免复制实参，提高效率，并且允许函数修改实参的值。

void increment(int &x) {
    x++; // 修改了实参的值
}

int main() {
    int num = 5;
    increment(num); // 通过引用传递 num
    cout << num;   // 输出 6 (num 的值被 increment 函数修改)
    return 0;
}
IGNORE_WHEN_COPYING_START
content_copy
download
Use code with caution.
C++
IGNORE_WHEN_COPYING_END

函数返回值： 函数可以返回引用，允许调用者直接修改函数内部的变量。

int& getElement(int arr[], int index) {
    return arr[index]; // 返回数组元素的引用
}

int main() {
    int numbers[] = {1, 2, 3};
    getElement(numbers, 1) = 10; // 修改了 numbers[1] 的值
    cout << numbers[1];           // 输出 10
    return 0;
}
IGNORE_WHEN_COPYING_START
content_copy
download
Use code with caution.
C++
IGNORE_WHEN_COPYING_END

运算符重载：在运算符重载中，可以使用引用来提高效率并允许修改对象的状态。

示例总结：

#include

int main() {
int x = 5;
int &y = x; // y 是 x 的引用

std::cout << "x: " << x << std::endl;  // 输出：x: 5
std::cout << "y: " << y << std::endl;  // 输出：y: 5

y = 10; // 修改 y 的值

std::cout << "x: " << x << std::endl;  // 输出：x: 10  (x 的值也被修改了，因为 y 是 x 的引用)
std::cout << "y: " << y << std::endl;  // 输出：y: 10

return 0;

}
IGNORE_WHEN_COPYING_START
content_copy
download
Use code with caution.
C++
IGNORE_WHEN_COPYING_END

希望这个详细的解释能够帮助你理解 C++ 中引用的相关语法和用法。记住，理解引用就是理解它是原始变量的另一个名字，并且对它的操作会直接影响原始变量。

Summer training daily record 7.12~7.18

2023-07-12

技术 / 算法类

图论构造 Tenzing and His Animal Friends

https://codeforces.com/problemset/problem/1842/D
看不懂的题面部分：u,v,y的意义。
理解为u或者v分开单独玩的时间不超过y。一共m组.

思路总结：
求最长时间的情况下，由于n一定不参加聚会，所以和n关联的m最大可以参加v(m->n)的时间，类推每个点最长参加时长为它到n的最短路。当1,n不相连则无上限（样例如果没有2 5 1 那么2 3可以无限参加派对）。

接着构造聚会的方案。di为1->i的最短路，仅在di->dn时间选择i,使得（u,v）满足du-dv<=y。即每次选出最短路的点，之后加入

另一个是dijkstra构造，即每次取最短点。设存在两个集合S,T，集合S 中为还能参加聚会的点，集合 T 中为不能再参加聚会的点。最初 T 中仅n 一个元素。联系到上述每个点最大参会总时长的得出方式，我们每次从 S 中选择一个参会时间上限最短的点 x，让S 中的所有点都参加一次聚会，时长为 x 的参会时间上限。一直这样进行下去，直到点 1不在 S 当中。

CF876(div2)-C-Insert Zero and Invert Prefix(偏移量+贪心)

https://codeforces.com/problemset/problem/1839/C

考察的部分：特殊情况贪心+偏移量
具体解答https://zhuanlan.zhihu.com/p/634514907
偏移量cost解释：当做逆操作时候，数组前面的书均取逆，cost记录奇偶次，并且与原数组的数操作得出数现在的状态

该评论区有提及从左向右扫的逆向思路：形如1111……0的串，删去最后的0并反转所有的1
不断重复
例如
1 0 0 1 1 0
x
0 0 1 1 0
x
1 1 0 0
x
0 0 0

但是怎么变成代码呢emmmm
拆解操作思路
https://zhuanlan.zhihu.com/p/636927276

CF 884 vp

acwing 数学部分补充

卡特兰数
https://leetcode.cn/circle/article/lWYCzv/

一、引言

卡特兰数（Catalan number）是组合数学中一个常出现在各种计数问题中的数列。

数列的前几项为：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862，...

本文将会选取几个经典的卡特兰问题，难度先易后难，带领读者逐个击破解决，最后给出相关的解题模板。

二、经典问题

2.1 进出栈序列

这是一道最经典的入门级卡特兰数题目，如果能把这题看懂，相信后面的题目也能迎刃而解。

题目描述

n 个元素进栈序列为：1，2，3，4，...，n，则有多少种出栈序列

思路

我们将进栈表示为 +1，出栈表示为 -1，则 1 3 2 的出栈序列可以表示为：+1 -1 +1 +1 -1 -1。

根据栈本身的特点，每次出栈的时候，必定之前有元素入栈，即对于每个 -1 前面都有一个 +1 相对应。因此，出栈序列的所有前缀和必然大于等于 0，并且 +1 的数量等于 -1 的数量。

接下来让我们观察一下 n = 3 的一种出栈序列：+1 -1 -1 +1 -1 +1。序列前三项和小于 0，显然这是个非法的序列。

如果将第一个前缀和小于 0 的前缀，即前三项元素都进行取反，就会得到：-1 +1 +1 +1 -1 +1。此时有 3 + 1 个 +1 以及 3 - 1 个 -1。

因为这个小于 0 的前缀和必然是 -1，且 -1 比 +1 多一个，取反后，-1 比 +1 少一个，则 +1 变为 n + 1 个，且 -1 变为 n - 1 个。进一步推广，对于 n 元素的每种非法出栈序列，都会对应一个含有 n + 1 个 +1 以及 n - 1 个 -1 的序列。

如何证明这两种序列是一一对应的？

假设非法序列为 A，对应的序列为 B。每个 A 只有一个”第一个前缀和小于 0 的前缀“，所以每个 A 只能产生一个 B。而每个 B 想要还原到 A，就需要找到”第一个前缀和大于 0 的前缀“，显然 B 也只能产生一个 A。

每个 B 都有 n + 1 个 +1 以及 n - 1 个 -1，因此 B 的数量为 C2nn+1C_{2n}^{n+1}，相当于在长度为 2n 的序列中找到 n + 1 个位置存放 +1。相应的，非法序列的数量也就等于 C2nn+1C_{2n}^{n+1}。

出栈序列的总数量共有 C2nnC_{2n}^{n}，因此，合法的出栈序列的数量为 C2nn−C2nn+1=C2nnn+1C_{2n}^{n} - C_{2n}^{n+1} = \frac{C_{2n}^n}{n + 1}。

此时我们就得到了卡特兰数的通项 C2nnn+1\frac{C_{2n}^n}{n + 1}，至于具体如何计算结果将会在后面进行介绍。

2.2 括号序列

题目描述

n 对括号，则有多少种 “括号匹配” 的括号序列

思路

左括号看成 +1，右括号看成 -1，那么就和上题的进出栈一样，共有 C2nnn+1\frac{C_{2n}^n}{n + 1} 种序列。

2.3 二叉树

题目描述

n + 1 个叶子节点能够构成多少种形状不同的（国际）满二叉树

（国际）满二叉树定义：如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。

思路

使用深度优先搜索这个满二叉树，向左扩展时标记为 +1，向右扩展时标记为 -1。

由于每个非叶子节点都有两个左右子节点，所有它必然会先向左扩展，再向右扩展。总体下来，左右扩展将会形成匹配，即变成进出栈的题型。n + 1 个叶子结点会有 2n 次扩展，构成 C2nnn+1\frac{C_{2n}^n}{n + 1} 种形状不同的满二叉树。

2.4 电影购票

题目描述

电影票一张 50 coin，且售票厅没有 coin。m 个人各自持有 50 coin，n 个人各自持有 100 coin。

则有多少种排队方式，可以让每个人都买到电影票。

思路

持有 50 coin 的人每次购票时不需要找零，并且可以帮助后面持有 100 coin 的人找零；而对于持有 100 coin 的人每次购票时需要找零，但 100 coin 对后面的找零没有任何作用。

因此，相当于每个持有 100 coin 的人都需要和一个持有 50 coin 的人进行匹配。我们将持有 50 coin 的标记为 +1，持有 100 coin 的标记为 -1，此时又回到了进出栈问题。

不同的是，m 并一定等于 n，且排队序列是一种排列，需要考虑先后顺序，例如各自持有 50 coin 的甲和乙的前后关系会造成两种不同的排队序列。所以，将会有 (Cm+nm−Cm+nm+1)∗m!∗n!(C_{m+n}^{m}-C_{m+n}^{m+1})*m!*n!

第二项为什么是 Cm+nm+1C_{m+n}^{m+1}，其实很简单，我们每次把第一个前缀小于0 的前缀取反后，会造成 +1 多了一个而 -1 少了一个。这里 +1 有 m 个，-1 有 n 个，取反后 +1 变成 m + 1 个，-1 变成 n - 1 个，总和不变。

三、解题模板

最后我们需要来计算一下卡特兰数的通项 Cn=C2nnn+1C_{n} = \frac{C_{2n}^n}{n + 1}

卡特兰数满足以下递推式：

C1=1C_{1}=1，Cn=Cn−14∗n−2n+1C_{n} = C_{n-1}\frac{4*n-2}{n+1}（证明从略）

因此，我们可以通过递推来得到第 n 个卡特兰数。

代码

import java.math.BigInteger;
// 打印前 n 个卡特兰数
int n = 20;
BigInteger ans = BigInteger.valueOf(1);
System.out.println("1:" + ans.toString());
BigInteger four = BigInteger.valueOf(4); 
BigInteger one = BigInteger.valueOf(1);
BigInteger two = BigInteger.valueOf(2);
for (int i = 2; i <= n; i++) {
    BigInteger bi = BigInteger.valueOf(i);
    ans = ans.multiply(four.multiply(bi).subtract(two)).divide(bi.add(one));
    System.out.println(i + ":" + ans.toString());
}

# 打印前 n 个卡特兰数
ans, n = 1, 20
print("1:" + str(ans))
for i in range(2, n + 1):
    ans = ans * (4 * i - 2) // (i + 1)
    print(str(i) + ":" + str(ans))

需要注意的是，由于卡特兰数增长速度较快，当 n 等于 17 时，卡特兰数将会超过 int 最大值，造成溢出（Python 除外）。对于 Java 语言来说，可以使用 BigInteger 来计算大整数。

那如果 +1 的数量不等于 -1 的数量呢，如前面提到的电影购票问题。此时 Cn=Cm+nm−Cm+nm+1C_{n}=C_{m+n}^{m}-C_{m+n}^{m+1}，不是卡特兰数的通项，也就不能够继续使用原有的递推性质。

那就直接推呗。

Cn=Cm+nm−Cm+nm+1=(m+n)!m!∗n!−(m+n)!(m+1)!∗(n−1)!=(m+n)!m!∗n!−(m+n)!∗1m+1∗nm!∗n!=(m+n)!m!∗n!∗(1−1m+1∗n)=(m+n)!m!∗n!∗m+1−nm+1\begin{aligned}C_{n}&=C_{m+n}^{m}-C_{m+n}^{m+1}\\ &=\frac{(m+n)!}{m!*n!}-\frac{(m+n)!}{(m+1)!*(n-1)!}\\ &=\frac{(m+n)!}{m!*n!}-\frac{(m+n)!*\frac{1}{m+1}*n}{m!*n!}\\ &=\frac{(m+n)!}{m!*n!}*(1-\frac{1}{m+1}*n)\\ &=\frac{(m+n)!}{m!*n!}*\frac{m+1-n}{m+1}\\ \end{aligned}

一般而言，为了降低难度，题目会要求我们计算排列数量，所以 An=Cn∗m!∗n!=(m+n)!∗m+1−nm+1A_{n}=C_{n}*m!*n!=(m+n)!*\frac{m+1-n}{m+1}

四、总结

基本上所有的卡特兰数问题经过一定的转换都可以还原成进出栈问题。因此，只要我们能够学会进出栈问题的解法，无论问题再怎么变化，本质还是不变的。

卡特兰数问题中都会存在一种匹配关系，如进出栈匹配，括号匹配等，一旦计数问题中存在这种关系，那我们就需要去考虑这是否是卡特兰数问题。此外，我们还可以记住序列前四项：1, 1, 2, 5，这些将有利于我们联想到卡特兰数。

目前，LeetCode 已经出现一道卡特兰数问题 1259. 不相交的握手，这也是这篇文章编写的原因之一。同时，近年某巴巴，某讯的笔试题中也有出现过这类题目，无非将背景换成买烧饼，借书排队等，相信这些都难不倒读者。

五、扩展

最后留一道比较有意思的卡特兰数问题，欢迎读者留言，提出自己的看法。

8 个高矮不同的人需要排成两队，每队 4 个人。其中，每排都是从低到高排列，且第二排的第 i 个人比第一排中第 i 个人高，则有多少种排队方式。

以 1 2 3 4 5 6 7 8 表示8个人升高，陆续为这8个人排队，排到第一队记为0，排到第二队记为1.
观察两个界，即 00001111 和 01010101分别对应排队：
观察紧迫界，01 01 01 01 ，拥有特征（1）任意前缀 0 的个树大于1的个数，特征（2）每两个作为一对，有左0右1的特征。具备卡特兰数特征。1可以和后面的0交换位置，1不可以和前面的0交换位置。解即卡特兰数

01背包一维优化倒序更新问题

一维01背包为什么倒序：

我们每次计算dp[j] (即dp[i][j]) 的时候都会需要dp[j-w[i]] (即dp[i-1][j-w[i]])的值。因为j-w[i]比j小，所以如果我们正序计算，那么dp[j-w[i]]就已经更新了 (即dp[i][j-w[i]])，与状态转移方程不符。

如果重量是负数，怎么处理？：

如果重量是负数，那么上述状态转移方程中j-w[i]就会比j大，为避免先更新dp[j-w[i]]我们只能正序更新数组。
example:[http://poj.org/problem?id=2184]
题意：给你n头奶牛，每头奶牛都有一个智商和情商，在选出的x头奶牛智商和与情商和都大于等于0的情况下求智商总和与情商总和的最大值。

思路：以智商或者情商为价值，另一个为重量，就是典型的01背包问题，首先重量为正数时就是正常的01背包，但重量为负数时由于下标不能为负，我们需要增加数组长度。也就是把坐标0向正方向移动：-100000…0…100000 –> 0…100000…200000。dp[100000]设为0，最后扫一遍正数区间[100000, 200001]更新一个最大值即可。
N, H = 200000, 100000
dp = [-float(“inf”)] * (N+1)
dp[H] = 0
w = [-5, 8, 6, 2, -8]
v = [7, -6, -3, 1, -5]
n = 5


for i in range(n):
    if w[i] > 0://把第二层循环遍历展开分类讨论
        for j in range(N, w[i]-1, -1):
            dp[j] = max(dp[j], dp[j-w[i]] + v[i])
    else:
        for j in range(0, N+w[i]+1):
            dp[j] = max(dp[j], dp[j-w[i]] + v[i])

res = 0
for j in range(H, N+1)://在正情况中遍历最大
    if dp[j] >= 0:
        res = max(res, dp[j]+j-H)//情商+智商和-前移的1000
print(res)

win11 搭建hexo+github以ayer为主题的个人博客

2023-06-26

技术 / web类

本教程针对的主题是Ayer,主播建议是选好自己喜欢的主题后再进入看教程。
博客和主题安装部分通用
ayer调教部分以及遇到的bug可供参考

参考的教程

hexo官方文档必看官方文档
知乎教程大部分步骤来自这里，~~一部分懒得打字会照抄，~~主播会省略诸如github注册操作、使用英文名等等程序员基本素养问题，只提及主要步骤做记录,有疑问可以具体查看这里
Ayer主页说明主页个性化设置
*B站教程github打包式建站github比较流畅的小伙伴可以试试这个

碎碎念：主播wsl2和codespace都试过了，能成功搭建博客但是部署theme都有大大小小的问题，最终win11本地成功搭建模板化的主题，目前商在个性化修改中。

正文

1.环境准备

hexo的安装前提是

Node.js nodejs.org/zh-cn(安装时自带npm平台)
Git https://git-scm.com/downloads
（当然以上都可以使用镜像站点下载）
说明：
如果你细心的看了官方文档那么你会发现它会提及Node.js 版本需不低于 10.13，建议使用 Node.js 12.0 及以上版本,以及后面附带了一张hexo与Node.js版本一一对应的表格。本人的经验是可以先一律无脑最新版，大部分旧版都兼容。若主题有特殊版本要求建议按照主题的要求来。~~虽然我没有那么做~~

下载 Node.js 和 Git 程序并安装，一路点 “下一步” 按默认配置完成安装。

安装完成后，Win+R 输入 cmd 并打开，依次输入 node -v、npm -v 和 git –version 并回车，如下图出现程序版本号即可。

2.安装hexo

首先你需要准备一个完全空白的文件夹（本文假设为blog）来存放hexo的程序文件。新建好后在该文件夹空白处右键选择Git Bash Here,这个选项可能藏在win11的显示更多选项。

npm一键安装hexo程序指令：

npm install -g hexo-cli

如果你是mac用户需要sudo（管理员权限）来操作，例如：

sudo npm install -g hexo-cli

安装时长视网络环境而定，可以考虑挂加速器，请耐心等待

3.link（链接）github

首先你已经有了一个github的免费账户并且完成了一系列验证。

然后回到你的blog文件夹，依旧是右键Git Bash Here进入到terminal，设置用户名和邮箱；

git config --global user.name "你的gitHub 用户名"
git config --global user.email "你的gitHub 邮箱"
（替换双引号内容）

说明：
如果你遇到了error: key does not contain a section: xxx的报错，你可以尝试自己手写命令并输入，或者输入git config --global --edit手动编辑配置文件并保存。

然后创建SSH密匙，无脑回车到程序结束：

ssh-keygen -t rsa -C "你的gitHub 邮箱"

完成后，登录github——>选择右侧边栏的总setting——>选择左侧边栏的SSH and GPG keys——>选择New SSH keys——>title取名并且附上——>

My New Post

2023-06-25

Hello World

2023-06-25

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment

Wild Puffer Fish Breeding Base

概率与期望

哈夫曼树

费马点

Dilworth定理 反链定理

牛顿迭代法优化 sqrt

组合数取模的各种方法

各种树

卡spfa

图和树的概念整理

链式向前星 存图

二分图/二部图

01背包朴素优化

new int[m]

auto

for（int i=n-1;~i;i–）

const double eps=1e-6;

struct结构体内比较格式

* &的传递区别

vector传递 高精度计算

*lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i]

priority_queue<int,vector,greater> heap;

cout<<fixed<<setprecison(15)<<dp[a]

while (cin >> a >> b >> c, a || b || c)w[a][b] = c;

lower_bound()、upper_bound()、equal_range() 以及 binary_search()

lower_bound()

upper_bound()

equal_range()

binary_search()

增加堆栈空间

c++引用

图论构造 Tenzing and His Animal Friends

CF876(div2)-C-Insert Zero and Invert Prefix(偏移量+贪心)

CF 884 vp

acwing 数学部分补充

一、引言

二、经典问题

2.1 进出栈序列

2.2 括号序列

2.3 二叉树

2.4 电影购票

三、解题模板

四、总结

五、扩展

01背包一维优化倒序更新问题

参考的教程

正文

1.环境准备

2.安装hexo

3.link（链接）github

Quick Start

Create a new post

Run server

Generate static files

Deploy to remote sites

Dilworth定理反链定理

链式向前星存图

vector传递高精度计算