系列链接

Spectral Graph Theory学习笔记（1）
Spectral Graph Theory学习笔记（2）

第二章

这一章感觉没什么重点

2.3节

就是之前说的那个画图的方法

2.4节

定义了一个boundary的概念，如果$S$是图$G$的一个点子集，那么定义$S$的boundary为：
$$\partial (S) = \{(u, v)\in E:u\in S,v\notin S\}$$
然后定义了一个比值：isoperimetric ratio：
$$\theta(S)=\frac{|\partial(S)|}{|S|}$$
接下来是定义了一个图的isoperimetric，取所有点子集的最小$\theta(S)$:
$$\theta_G=\underset{|S|\le n/2}{min}\theta(S)$$

系列链接

Spectral Graph Theory学习笔记（1）
Spectral Graph Theory学习笔记（2）

概述

这是个啥课

这是门用各种奇怪的数学姿势，研究图论问题的课，这个系列的博客，只是做做笔记

前驱知识

大概只需要：

线性代数基础
图论基础
复杂度分析

AC的代码或者暴力

保存为AC.cpp，并且编译

1
2
3
4
5
6
7
8
9
10
11

#include <cstdio>
int n, ans = 0;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        ans += i;
    printf("%d\n", ans); 
    return 0;
}

WA的代码

保存为WA.cpp，并且编译

1
2
3
4
5
6
7
8
9
10

#include <cstdio>
int n, ans = 0;
int main() {
    scanf("%d", &n);
    ans = (1 + n) * n / 2;
    printf("%d\n", ans);
    return 0;
}

数据生成器

保存为Data.cpp，并且编译

1
2
3
4
5
6
7
8
9
10
11
12

#include <cstdio>
#include <cstdlib>
#include <ctime>
int n;
int main() {
	srand(time(0));
	n = rand() % 100 + 1;
	printf("%d\n", n);
	return 0;
}

对拍器

保存为check.cpp，并且编译
在前面的程序都准备妥当之后，运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <windows.h>
#include <fstream>
using namespace std;
int main() {	
	int i = 0;
    while(1) {
    	i++;
        system("Data > input.in");
        system("AC < input.in > AC.out");
        system("WA < input.in > WA.out");
        if(system("fc AC.out WA.out"))   break;
        printf("%d\n", i);
    }
    system("pause");
    return 0;
}

之后会生成input.in为输入文件，WA.out为WA的代码的输出，AC.out为AC的代码的输出

接下来会讲些什么？

一些建立在集合上的反演
这是我在B站发的讲解

从错排开始

什么是错排？

比如一天有$n$只咸鱼要坐座位，第$i$号咸鱼并不想做第$i$号位置，问有多少种方案？

咸鱼怎么想？

• 全部咸鱼随便排的方案数是$n!$
• 排除有一只咸鱼坐在自己的位置$n!-\binom{n}{1}(n - 1)!$
• 加回来两只咸鱼坐对的情况$n! - \binom{n}{1}(n - 1)! + \binom{n}{2}(n - 2)!$
• …

感谢傅里叶同学做出的杰出贡献

什么是傅里叶变换？

请看这里

一些先修的概念

复数

就是$\sqrt{-1}$啦，我们写作$i$

单位根

这是整个变换的核心，也就是满足$z^n=1$的所有复数
我们定义$\omega_n=e^{\frac{2\pi i}{n}}$
那么所有的n次单位根就是
$$\omega_n=e^{\frac{2\pi i k}{n}},k=0,1,2\cdots n-1$$
这些单位根为啥长这样呢？
仔细想想发现这些单位根构成复平面上的单位圆的内接正$n$边形

欧拉公式

计算机没法计算复数，我们需要用到欧拉公式：
$$e^{i\theta}=cos(\theta)+isin(\theta)$$

代码位置：

https://github.com/HarryGuo2012/ACMCode/tree/worldLine/CDOJ/14thPr

A Graph Problem

题意

给个$n$个点的无向图，再给出$k$个要求，问最多能删除多少条边，使得每个要求的点对联通。

题解

注意到点的规模只有15，我们可以枚举集合来解决。
维护一个并查集，我们能够知道哪些点是必须在同一个连通块内的，这样要求的规模就从$n^2$降到了$n$。
令$dp[s]$表示对于要求的子集$s$，满足$s$中的每个要求需要的最少的边。这样一来，我们能够得到转移是：
$$dp[s] = \underset{u,v}{min} (dp[u] + dp[v]),u\cup v = s$$
由上面的转移，我们就只需要预处理出把每个要求子集中的点全部联通的最小解了。
祥见代码。

Bank

题意

有个神奇的售货机，有无限的纸币，并且有无限的商品，任何价格的商品都能买到。
现在要去换零钱，由于售货机的找钱机制是随机的，所以人品不好的时候是得不到我们想要的零钱的。
比如现在有40元售货机待找，我们想要一张10元的零钱，但是售货机却给了两张20的纸币。

题解

结合生活实际，这道题是非常简单的。
首先我们将这些钱分类，一个单位下的分一类，换句话说分是一类，角是一类，1元是一类，10元是一类。。
我们首先考虑类和类之间的关系，由于售货机不会将10元的钱来当1元或者2元用，所以类向上是没啥关系的，由于脸很差，所以售货机总是尝试用价值高的类来还钱，比如售货机不会用10个1块来当10块用，所以类向下是没啥关系的。
所以我们得出一个结论，类之间是独立的，那么问题就简单了，由于每个类是一样的，我们就只需要知道类里面的三个数字之间的关系就好了，这时候脑补一下就能得出结论。
接下来我们就可以枚举用多少块，然后check剩下的钱是否能够得到我们想要的零钱就好。
详见代码

球盒问题

将小球放在盒子中的问题，一共有八种情况。
我们假定一共有$n$个球，$m$个盒子。

一、球可区分，盒可区分，盒子可以为空

这个是最简单的情况，每个球有$m$种不同的选择方式，所以方案数是：
$$m^n$$

二、球可区分，盒可区分，盒子不可以为空

我们可以用生成函数来解决这个问题。
这个问题等价于，我们有$m$种不同的气球，每种气球有无限个，然后选择n个气球出来排列，每个气球至少选一个。
所以指数生成函数是：
$$G(z)=(\sum_{i=1}^{\infty}\frac{z^i}{i!})^m=(e^z-1)^m$$
二项式展开后：
$$G(z)=\sum_{i=0}^m\binom{m}{i}e^{z(m-i)}(-1)^{i}$$
那么$\frac{x^n}{n!}$的系数就是：
$$\sum_{i=0}^m\binom{m}{i}(m-i)^n(-1)^i$$

一个典型的路径统计问题

简单版的问题

从坐标系的$(0,0)$点出发到坐标系的$(n,n)$，每步只能向上或向右走一格，有多少种不同的方案数。
如下图是一个解：

这个问题是十分简单的，很容易发现无论如何都要走$2n$步，并且其中$n$步是向上走的，其中$n$步是向左走的，那么总的方案数就是$\binom{2n}{n}$，即从$2n$个东西里面拿出来$n$个。

二分法

如果序列可以被分成两个不同性质的部分，而我们想找到分界线的时候，我们就能使用二分法。
很简单的例子就是当我们去猜一个数字的时候，如果返回的是大了还是小了，我们总会使用二分的办法去寻找。
另外一种二分是浮点数的二分，两种二分写法上有很大的不同，所以分开讲。