鸽巢原理引论

# Primary

引理1$(\text{Pigeon Nest Principle})$ 如果将$n+1$个物体放入$n$个盒子,那么至少有一个盒子包含两个或更多物体.

证明 假设每个盒子中都只有一个物体,那么总数为$n$,与$n+1$个物体的题设不符.证毕.

非常初等,非常好懂.但是我们只要来看几道小题目就会发现这个原理的强大之处.


例$1$ 给定$m$个整数$a_1,a_2,\cdots,a_m$.求证:$\exists\,l,r\in[1,m]:m|\sum_{i=l}^r a_i$.

证明 这个例子就没有引理那么显然了.考虑$a_i$的前缀和$S_i$,则我们要证:

那么考虑$q_i=S_i \bmod m$,显然有$m$种结果,如果$\exists\,q_i=0$,那么$l=1,r=i$即可使原命题成立;

除开$q_i=0$,$q_i$还有$m-1$种结果,而$q_i$有$m$个,根据引理1,必有两个$q_i$相等,那么原命题成立.


例$2$ 一位国际象棋大师有$11$周时间准备一场锦标赛,他决定每天至少下$1$盘棋,且每周下不超过$12$盘棋.求证:一定存在一个时期他刚好下了$21$盘棋.

证明 考虑他前$i$天里下棋的总盘数$S_i$,由每天都至少下一盘,我们知道$77$个元素的有穷数列$\{S_i\}$严格递增,再由于每周最多$12$盘,那么$11$周满足:$S_{77}\le11\times12=132$,更进一步有

考虑新数列$\{S_i+21\}$,它也是严格递增的,也有$77$个元素,并同样有

我们把两个数列放在一起,总共有$2\times77=154$个整数,而这些整数最小可能为$1$,最大可能为$153$,这意味着至少有两个数相等.再分别考察两个数列,由严格递增易得相等的两个数必定分居两个数列中,那么$\exists\,i,j:S_i=S_j+21\implies S_i-S_j=21$,原命题成立.


例$3$ 证明:一个有理数$p/q$必定可以写成十进制循环小数.

证明 考虑我们做除法的过程,首先我们只考虑$p>q>0$的情况,因为符号并不影响数码,而且我们总能给该有理数乘上$10^k$以使$p$足够大而不改变它的数码本身,所以除法的每一步就可以表述为寻找无符号整数$n_{\max},r_{\min}:p=nq+r$,如果$r=0$,那么返回$n$,如果$r\neq0$,就对$10^{k_{\min}}\cdot r>q>0$递归地执行该过程并把结果的$\dfrac1{10}$累加到自己的结果中再返回.

$$$$

看不懂我表述的除法过程可以不用理它……只要你发现$r$只有$[0,q-1]$这$q$种可能值就行——找到$q+1$个$r$之后,必然会与前面的有重复.不用担心$r=0$的情形,有限小数实际上也可以被认为是循环小数,只是循环节是$\overline0$罢了.

拓展 看到这里你应该对证明$\sqrt2$是无理数的方法有了更深刻的理解了,因为这个除法过程是用到了$p=nq+r$这一过程的,实际上本质是还整数的运算,所以才可以用数论方法推出矛盾.

# Enhanced

呃,窝待会(ming nian)就回来写

评论和共享

在以前的文章扫描线 · 二维数点问题及其应用中,我们提到了二维数点问题的离线做法,可以做到$\mathcal O(n\lg n)$.但是如果要求边查边加入强制在线呢?如果不强制在线可以CDQ分治,但是强制在线大概复杂度对的法子就两种了——KDTree或树套树,这里介绍线段树套线段树以及线段树套平衡树的做法.

# 线段树套线段树

思路很简单,用外层的线段树每个节点维护一个内层线段树即可,也就是说存一个内层树的根.不过我们发现空间会炸,所以要让内层线段树动态开点.

外层树对应横坐标,内层树对应纵坐标,最终确定了一个点,我们按区间求和的套路写就行.

值得注意的是,在外层树的修改操作中我们不需要再用回溯pushup的写法了,直接在访问到一个节点时立刻修改它对应的内层树.其实思想很好理解,直接上代码吧.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <cstdio>
#include <iostream>

using namespace std;

const int MAXN = 100005;

int a[MAXN], minV[MAXN], maxV[MAXN], dp[MAXN];

namespace DS {
struct inNode {
int val;
inNode *ls, *rs;
inNode(): val(0), ls(NULL), rs(NULL) { }
}inPool[MAXN<<7];

struct outNode {
inNode *root;
outNode *ls, *rs;
outNode(): root(NULL), ls(NULL), rs(NULL) { }
}outPool[MAXN<<1], *root;

inNode *newInNode() {
static int cnt = 0;
return &inPool[cnt++];
}

outNode *newOutNode() {
static int cnt = 0;
return &outPool[cnt++];
}

outNode *build(int l, int r) {
outNode *cur = newOutNode();
if(l < r) {
int mid = (l + r) / 2;
cur->ls = build(l, mid);
cur->rs = build(mid + 1, r);
}
return cur;
}

void insertY(inNode *&cur, int l, int r, int y, int v) {
if(!cur) cur = newInNode();
cur->val = max(cur->val, v);
if(l < r) {
int mid = (l + r) / 2;
if(y <= mid) insertY(cur->ls, l, mid, y, v);
else insertY(cur->rs, mid + 1, r, y, v);
}
}

void insertX(outNode *cur, int l, int r, int x, int y, int v) {
insertY(cur->root, 1, 100000, y, v);
if(l < r) {
int mid = (l + r) / 2;
if(x <= mid) insertX(cur->ls, l, mid, x, y, v);
else insertX(cur->rs, mid + 1, r, x, y, v);
}
}

int queryY(inNode *cur, int l, int r, int y1, int y2) {
if(!cur) return 0;
if(y1 <= l && y2 >= r) return cur->val;
int mid = (l + r) / 2;
int res = 0;
if(y1 <= mid) res = max(res, queryY(cur->ls, l, mid, y1, y2));
if(y2 > mid) res = max(res, queryY(cur->rs, mid + 1, r, y1, y2));
return res;
}

int queryX(outNode *cur, int l, int r, int x1, int x2, int y1, int y2) {
if(x1 <= l && x2 >= r) return queryY(cur->root, 1, 100000, y1, y2);
int mid = (l + r) / 2;
int res = 0;
if(x1 <= mid) res = max(res, queryX(cur->ls, l, mid, x1, x2, y1, y2));
if(x2 > mid) res = max(res, queryX(cur->rs, mid + 1, r, x1, x2, y1, y2));
return res;
}

void init() {
root = build(1, 100000);
}

void insert(int x, int y, int z) {
insertX(root, 1, 100000, x, y, z);
}

int queryMax(int x1, int y1, int x2, int y2) {
return queryX(root, 1, 100000, x1, x2, y1, y2);
}
}

int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
minV[i] = maxV[i] = a[i];
}
while(m--) {
int x, y;
scanf("%d %d", &x, &y);
minV[x] = min(minV[x], y);
maxV[x] = max(maxV[x], y);
}
int ans = 0;
DS::init();
for(int i = 1; i <= n; i++) {
dp[i] = DS::queryMax(1, 1, a[i], minV[i]) + 1;
DS::insert(maxV[i], a[i], dp[i]);
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
return 0;
}

# 线段树套平衡树

线段树套平衡树做法就是内层树加入该横坐标下的所有点的纵坐标,如果矩形的纵坐标跨度是$[y_1,y_2]$,我们数点只需要返回$rk(y_2)-rk(y_1-1)$即可.知道了这个思想,写法和上面几乎相同.

1
// 呃……我待会儿(xiazhou)再写吧

评论和共享

# Trie的应用进阶

# Problem0

# Description

给定$n$个非负整数$A_i$,你要求出$\displaystyle\max_{1\le i,j\le n}(A_i \mathop{xor}A_j)$.

# Analysis

这题大家肯定都会,把所有$A_i$由首自尾加入到一棵01Trie树上,如果位数不到所有数中的最大位数的就高位补零再加入.然后暴力枚举$A_i$,用以下策略求出$\max_{1\le j\le n}(A_i \mathop{xor}A_j)$:

到一个节点时,贪心地选择与$A_i$对应的位不同的儿子,也就是说如果$A_i$对应位为$1$,那么递归调用儿子$0$,反之则调用儿子$1$,如果这个儿子不存在,那么再递归调用另一个儿子,到叶子节点就得到了$A_j$.

这么做为什么是对的?因为我们进行了高位补零,所以我们从根往下找就是从高位到低位,如果当前节点的儿子中我们选择了与$A_i$对应位相同的儿子,那么以后是绝对无法做到比选择不同的儿子更优的,就像两个数比大小,$100$和$099$,就算第$1,2$位有$9>0$,但是由于高位第三位$1>0$,导致$100>99$,低位再大、高位更小的话整体的值也较小.

# Problem1

# Description

维护长度为$n$的集合$S$:

  • 把其中所有数同$x$异或
  • 查询$\text{mex}\{S\}=\min\{\complement_\mathbb NS\}$

# Analysis

这题算是上面那题的简单变式,首先我们考虑离线,注意到异或的结合律,我们可以把所有操作1的$x$累计异或起来,这样问题只剩下一个查询了,我们重新表述问题:

查询一个数列在异或$x$意义下的$\text{mex}$.

我们再次考虑更简单的问题,如果没有修改我们会怎么做?

我们照例把高位补齐、将所有数加到一个01Trie上,考虑到要求最小的不存在的数,我们只要每次贪心地选0子树就行.不过也要考虑到,如果0子树存在,但是是满的,那么显然不存在解,我们就只能递归1子树了.满怎么判断?很简单,dfs统计一下size就行了.

在异或$x$意义下呢?

我们发现只用考虑$x$的当前位的值$k$,如果$k=1$,其实异或的效果就是把当前节点的左右儿子反一下,这就好做了.

对于这个策略还有个更贴近Problem0策略的解释,既然是在异或$x$的意义下取更小,我们只需要每个节点贪心地选择同$x$当前位相同的子树即可,这个策略和上面的策略其实是本质相同的.

# Problem2

# Description

待更…

# 平衡树的一点点东西

为了让二叉查找树不退化为链、保证$\mathcal O(\lg n)$的复杂度,我们需要采取一些策略来保证其平衡,也即树高在$\mathcal O(\lg n)$级别,这样的二叉查找树称为平衡二叉查找树.

treap和splay之类的网上教程一大堆,在此不再赘述,我写点有意思的东西——宗法树.

(为啥叫这个名字呢?因为其删除过程可以形象地描述为“父死兄继”、“嫡长子继承制”,旋转也很像“过继”233333333)

我们考虑用一种类似线段树的东西来实现平衡查找树的功能,它是一棵完全二叉树.用叶节点记录值,非叶节点存两个儿子的最大值.

还没写完,这部分文字包括代码都还有待改进.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define gor(var,start,end) for(int var=start;var<=end;++var)
#define dbg(x) cout << #x << " = " << x << endl
#define prt(x) cout << x << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 3;
#define islv(x) (!c[0][x])
#define xpos(x) (x==c[1][fa[x]])
#define root (c[0][0])
int c[2][2*N], v[2*N], fa[2*N], sz[2*N], tot = 0;

// 主要是维护极值和size
void pushup(int x) {
v[x] = max(v[c[0][x]], v[c[1][x]]);
sz[x] = sz[c[0][x]] + sz[c[1][x]];
}

int newnode(int nf, int nd, int nv, int ns) {
int x = ++tot;
fa[x] = nf, c[nd][nf] = x, v[x] = nv, sz[x] = ns;
return x;
}

// 插入值为k的一个新节点
void insert(int k, int x = root) {
if (v[x] == k) return;
if (!tot) {
newnode(0, 0, k, 1);
return;
}
if (islv(x)) {
int v1 = x ? min(k, v[x]) : k, v2 = x ? max(k, v[x]) : k;
newnode(x, 0, v1, 1), newnode(x, 1, v2, 1);
return;
}
insert(k, (v[c[0][x]] >= k) ? c[0][x] : c[1][x]);
pushup(x);
}

// 删除值为k的数
void remove(int k, int x = root) {
if (v[x] == k) {
int ff = fa[fa[x]];
c[xpos(fa[x])][ff] = c[xpos(x) ^ 1][fa[x]];
fa[c[xpos(fa[x])][ff]] = ff;
return;
}
remove(k, (v[c[0][x]] >= k) ? c[0][x] : c[1][x]);
pushup(x);
}

// 查询值为k的数的排名
int rk(int k) {
int p = 1, cnt = 0;
while (p)
if(v[c[0][p]] < k) cnt += sz[c[0][p]], p = c[1][p];
else p = c[0][p];
return cnt + 1;
}

// 查询排名为k的数的值
int kth(int k) {
int p = 1, cnt = 0;
while (!islv(p))
if(cnt + sz[c[0][p]] < k) cnt += sz[c[0][p]], p = c[1][p];
else p = c[0][p];
return v[p];
}

int main() {
insert(5);
insert(4);
insert(1);
insert(3);
insert(89);
insert(52);
prt(rk(3)), prt(rk(52));
remove(3);
prt(rk(89)), prt(kth(rk(6)));
return 0;
}

评论和共享

# Description

考虑平面上的一般性静态二维数点问题:给出$n$个点$P_i(x_i,y_i)$,有$Q$次询问,每次查询$(a,b,c,d)$查询$(a,b),(c,d)$确定的矩形中有多少给定点.

$a,b,c,d\le10^5$,$n\le10^3$

# Analysis

如果矩形位置小一点,$10^3$级别,那么我们当然考虑二维前缀和做,可以做到$\mathcal O(n^2)$预处理,$\mathcal O(1)$查询。但是$(10^5)^2$级别的数组我们是开不下的.

但是我们仍然可以借鉴二维前缀和的思想,首先我们对一个查询$(a,b,c,d)$,可以转化成$(0,0,a,d)+(0,0,c,b)-(0,0,a,b)$,也就是实际上我们只用考虑左端点在原点的情况,这时我们就可以用离线扫描线算法,开一个序列$\{p_i\}$,首先对所有点和询问按$x$或$a$排序,从左到右考虑这些点或查询,对于点,给$p_y+1$;对于查询,返回前缀和$S_a$即可.序列最好用树状数组维护,当然你很闲的话也可以用线段树qwq.

# Application

# Problem1

维护一个长度为$n$的整数序列.

  • 查询$[l,r]$内有多少种数

即HH的项链那题,我们这样做:用$\mathcal O(n)$预处理一个数组$pre_x$,表示$a_x$上次出现的位置,未出现则钦定为$0$.我们发现,对于一个询问$[l,r]$就是找到所有的满足$l\le x\le r,pre_x<l\implies pre_x\le l-1$的$x$,我们将$x$看作横坐标,$pre_x$看作纵坐标,问题转变为一个矩形查询$(l,0,r,pre_x)$,就是一个二维数点模型,$BIT$求即可.

# Problem2

二维平面上顺时针排列了$n$个点,给出$m$条线段,每条线段连接两个不同的点,问这些线段会形成多少交点,可以认为不会出现三线共点的情况.

首先我们规定线段的表示,$\{(u,v)|1\le u<v\le n,\:u,v\in\Bbb Z\}$是所有合法线段的集合.

mspaint.exe感知一下,比如有$7$个点,$(2,6)$之间有条线段,那么谁会和它有交点呢?比如$(1,3),(5,7),(1,4)\cdots$我们容易发现需要一个端点在区间$(2,6)$内,另一个在外就会有交点.抽象一下,对于一条线段$(u,v)$,与它有交点的线段$(x,y),x<y$满足

  • $u<x<v$且$v<y\le n$
  • $1\le x<u$且$u<y<v$

其一即可.

写到这里,正解已经很明显了吧,二维数点模型.

评论和共享

# Description

简而言之,$N$节点$M$边的有向图中边有两个权值$V_i,P_i$,要求找到一个环使得$\dfrac{\sum V_i}{\sum P_i}$取得最大值,无环输出$-1$.

# Analysis

很容易看出有单调性,我们考虑二分到了一个答案$x$时如何check()

满足要求时应该要有$x\ge\dfrac{\sum V_i}{\sum P_i}$,化简得

这就太显然了,最后一个式子的意思不就是以$xP_i-V_i​$为边权的图不存在负环嘛,spfa判负环即可,时间复杂度最坏最坏$\mathcal O(NM\lg ans_{\max})​$,题目告诉我们$ans_{\max}\le200​$,复杂度还是比较优越的,判负环写得好可以接近0ms,如果你的负环判断超时可以考虑用栈代替队列或者改写dfs-spfa,跑得飞快.我用队列$2700ms​$,改写栈后$200ms​$.


提一下一道很水的HNOI题:[HNOI2009]最小圈,跟这题基本一样,不过换成了平均值,你可以用对付平均值的套路来,也可以和上面一样地推导一遍.

# Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#define dbg(x) cout << #x << " = " << x << endl;
#define gor(var, start, end) for(int var=start;var<=end;++var)
#define prt in.print
using namespace std;
typedef long long ll;
template<class T>
struct IOFactory{
char p[40000000],*s,e[40000000],*t;T a[24];
IOFactory():s(p),t(e){fread(s,1,sizeof p,stdin);}
~IOFactory(){fwrite(e,1,t-e,stdout);}
operator T(){static T v,j;v=0,j=1;
while(*s<48)j=*s++^45;
do v=v*10+*s++-48;while(*s>32);
return j?v:-v;}
void print(T v,char endch='\n'){
static T *q=a;if(!v)*t++=48;
else{if(v<0)*t++=45,v*=-1;
while(v)*q++=v%10+48,v/=10;
while(q!=a)*t++=*--q;}
*t++=endch;}};
IOFactory<int> in;
const int N = 1e5; const double eps = 3e-3;
int n, m, head[N], cnt[N], tot=0; bool inq[N];
double d[N];
struct Edge {
int v, p, w, to;
}G[2*N];
inline void addEdge(int u, int v, int p, int w){
G[++tot].v = v, G[tot].p = p, G[tot].w = w, G[tot].to = head[u], head[u] = tot;
}
inline bool chk(double x){
int Q[N], top = 0;
memset(cnt, 0, sizeof cnt),
cnt[0] = -1,
memset(inq, 0, sizeof inq);
for (int i = 0; i <= n; ++i) d[i] = 1e4;
Q[++top]=0, inq[0] = 1, d[0] = 0;
while(top){
int u = Q[top];top--;
inq[u] = 0;
for (int i=head[u]; i; i=G[i].to) {
int v = G[i].v; double w = (!i)?0:(1.0*x*G[i].p-1.0*G[i].w);
if(d[v]>d[u]+w){
d[v] = d[u]+w, cnt[v]=cnt[u]+1;
if(!inq[v]) Q[++top]=v,inq[v]=1;
if(cnt[v]>=n) return true;
}
}
}
return false;
}

int main() {
n = in, m = in;
gor(i, 1, m){
int u=in, v=in, w=in, p=in;
addEdge(u,v,p,w);
}
gor(i, 1, n) addEdge(0,i,0,0);
double L=0,R=200,M;
while(fabs(R-L)>eps){
M = (L+R)/2;
if(chk(M)) L=M;
else R=M;
}
fabs(L)<eps?puts("-1"):printf("%.1lf", L);
}

评论和共享

# Description

# 题目描述

早苗是个有信仰的孩子。这一天, 早苗发现自己的御币不够用了,于是就去人之里批发了$n$根御币回神社。每个御币都有两个值 $a_i$ 和 $b_i$,表示两条纸带的长度。 早苗的御币有一个特殊的要求,就是所有备用御币中如果存在$k(k>=1)$个御币,使得这$k$个御币的纸带长度种类恰好为$k$的话,就会被认为是对神奈子不敬。而早苗作为风祝当然不会让这种事发生,所以她会从买来的御币中选一些扔掉。现在早苗开始依次检查这些御币,如果可以加入这根御币,那么早苗就会将这根御币加入备选御币中,否则扔掉。 这时早苗突然想知道她一共会扔掉多少根御币。

# 输入格式

第一行一个整数 $n$

接下来 $n$ 行每行两个正整数 $a_i$, $b_i$。

阅读全文

我目前的代码模板,支持泛型快速读写整数、读写字符与字符串(包括CStyle与std::string)、循环简记法、调试宏、强制内联宏、一般性功能宏等,缺点是很长……

阅读全文

UVa11021 Tribles

# Description

一开始有$K$种生物,这种生物只能活$1$天,死的时候有$p_i$的概率产生$i$只这种生物(也只能活一天),$T$组询问,要求输出$m$天内所有生物都死的概率(包括$m$天前死亡的情况)

阅读全文

概率DP · KPGAME

# Description

Alice和Bob在玩一个游戏。

有n个石子在这里,Alice和Bob轮流投掷硬币,如果正面朝上,则从$n$个石子中取出一个石子,否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有$p$的概率投掷出他想投的一面,Bob有$q$的概率投掷出他相投的一面。

现在Alice先手投掷硬币,假设他们都想赢得游戏,问你Alice胜利的概率为多少。

有多组数据
$1 \le N \le 99999999,\qquad 0.5 \le P, Q \le 0.99999999$

阅读全文
作者的图片

HigHwind

私は風です、それだけ。


Student


China