[关闭]
@P2Oileen 2017-07-21T03:35:51.000000Z 字数 54887 阅读 8688

清北学堂集训笔记

巨弱 代码 笔记


模拟只会猜题意,贪心只能过样例。
数学上来先打表,DP一般看规律。
组合数学靠运气,计算几何瞎暴力。
图论一顿套模板,数论只会GCD。


QAQ在场的各位都比我强……如有谬误欢迎指正!
前排广告:欢迎访问我的博客!
近水-life and code.
六个月以后所有的图都会掉ummmmm……
赶紧去买图床orz


目录


day1


倍增

以下文章中的倍增代码中的^全都是乘方的意思……不是异或qwq不能直接复制啊orz

定义:以F[i][j]表示,以i位置出发2^j个位置的状态
【为什么只乘2?】如果按照k来查的话,实际上为(k-1)logk的复杂度,可证明k=2的时候复杂度最小2333333

应用1 ST表

应用:ST表(用来解决RMQ问题:从i到i+2^j-1这2^j个位置的最大值)//其实可以用线段树的……但是ST表好写qwq
初始化:f[i][0]=z[i];
转移:f[i][j]=max[f[i][j-1],f[i+2^(j-1)][j-1]);(相当准确的二分)
限制:不能算区间和:中间有重复的部分
不支持修改。
询问:两种情况:
n个数,m个询问,询问l->r最大值
1)若区间长度正好是2^k,那么就直接访问f[l][k];
2)若区间长度是2^k+p(p<2^k),则当前最大值=max(f[l][k],f[r-2^k+1][k]);

  1. //build
  2. for(int a=1;a<=n;a++) f[a][0]=z[a];
  3. for(int j=1;j<=logn;j++)
  4. {
  5. for(int i=1;i+z^j-1<=n;i++)
  6. f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]);、
  7. //乘方是伪代码!
  8. }
  9. //solve
  10. ans=max(f[l][k],f[r-2^k+1][k]);
  11. */

应用2 LCA

树上倍增LCA:

有一种叫做动态树的结构(LCT)可以解决这个问题,树链剖分,于是能够动态修改,noip用不着,但是还是要好好学学……

求最近公共祖先。
f[i][j]表示从树上编号为i的点向上走2^j步会走到哪个点
j大概20-30就行0 0 2^j>点数差不多就行……
初始化:f[i][0]=father[i];
转移:f[i][j]=f[f[i][j-1]][j-1];
从i往上走2^(j-1)到的那个点再往上走2^(j-1)步到的点即为从i往上走2^j到的点
tarjan是线性的。。。为什么不用tarjan呢……
询问:得到两个点p1,p2;
首先建树的时候要记录一下深度。
两种情况:
1)depth[p1]==depth[p2],则具有性质:往上走同样的距离,深度仍然相同,如果走到了最近公共祖先,那么再往上走,就一定有p1==p2;

  1. for(int x=19;x>=0;x--)
  2. if(f[p1][x]!=f[p2][x])
  3. p1=f[p1][x];
  4. p2=f[p2][x];
  5. //如果没有走到公共祖先处,就使劲往上跳
  6. //因为x的值是逆序的,所以会尽可能地上跳,接下来的长度一定不大于2^(x-1)

2)depth[p1]!=depth[p2]
若P1深度比较深,就让P1上跳,跳到深度一样的地方。
如何利用f数组在倍增上跳呢?
step=depth[p1]-depth[p2];
举例:step=13,二进制中:1101:先走八步,再走四步,再走一步就可以了

  1. int get_lca(int p1,int p2)
  2. {
  3. if(dpeth[p1]<depth[p2]) swap(p1,p2);
  4. for(int x=19;x>=0;x--)
  5. {
  6. if((2^x)<=depth[p1]-depth[p2]) p1=f[p1][x];
  7. }
  8. }

应用3 快速幂(kissme) 【也有分治】

求A^x;[O(logx)]
如果每次把a*a*a*a*a*……真的好麻烦qwq还费时间
所以如果我们要求x(x=2*k)个a的乘积,就可以分解为x/2个a的乘积的平方。就省去了一半的计算量~
x如果是奇数,就在原先的基础上再乘一次a就行了。递归代码可以改循环~

  1. int ksm(int a,int x,int mod)
  2. {
  3. ans=1;
  4. while(x)
  5. {
  6. if (x&1) ans=(ans*a) % mod;//位运算:x&1==1则x为奇数
  7. A=(a*a) % mod;
  8. x>>1;//位运算,右移一位,即将X除以2
  9. }
  10. }

引申:快速乘法
求a*x=a+a+a+a+……
把ksm里面所有的乘号都变成加号就行了- =


分治

应用1 二分查找

给定一个排序后的数组,查询某个数是否在数组中

  1. bool find(int x)
  2. {
  3. l=0,r=n;
  4. while(l+1!=r)
  5. {
  6. m=(l+r)>>1;
  7. if(z[m]>=x) r=m;
  8. else l=m;
  9. }
  10. }

可以用lowerbound或者upperbound

应用2 归并排序(nlogn)

先砍成两半再说!
把这边归并排序 那边归并排序 搞俩指针转悠转悠- = 把小值排到上面区间的下一个就行了……

应用3 快速排序(nlogn)

sort【快排】(c艹的特性:不会退化成n*n,有奇怪的优化,而且比下面三个快……)
qsort(最坏会退化成n*n,最好n,期望nlogn)
merge_sort【归并排序】(无论何时都是nlogn,稳定)
heap_sort【堆排】(同上)


贪心

以某种方式将所有物品排序
排序后按照从小到大进行选择
给你n个数,要求选出K个数使他们的和最大

[noip2012] 国王游戏
Description
恰逢 H 国国庆,国王邀请n位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序, 使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
Input
第一行包含一个整数 n,表示大臣的人数。
第二行包含两个整数a和b,之间用一个空格隔开,分别表示国王左手和右手上的整数。 接下来n行,每行包含两个整数a和b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。
Output
输出只有一行,包含一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
Sample Input
3
1 1
2 3
7 4
4 6
Sample Output
2
Hint
【输入输出样例说明】
按1、2、3号大臣这样排列队伍,获得奖赏最多的大臣所获得金币数为2;
按1、3、2这样排列队伍,获得奖赏最多的大臣所获得金币数为2;
按2、1、3这样排列队伍,获得奖赏最多的大臣所获得金币数为2;
按2、3、1这样排列队伍,获得奖赏最多的大臣所获得金币数为9;
按3、1、2这样排列队伍,获得奖赏最多的大臣所获得金币数为2;
按3、2、1这样排列队伍,获得奖赏最多的大臣所获得金币数为9。
因此,奖赏最多的大臣最少获得 2 个金币,答案输出 2。
对于 20%的数据,有 1≤ n≤ 10,0 < a、b < 8;
对于 40%的数据,有 1≤ n≤20,0 < a、b < 8;
对于 60%的数据,有 1≤ n≤100; 对于 60%的数据,保证答案不超过 10^9;
对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000。

只考虑两个人
第i个人左右手数字:l[i],r[i];第二个人:l[i+1],r[i+1];两人金币数为w[i],w[i+1];
记P[i]=l[1]*l[2]l[3]...*l[i]
可得:
w[i]=P[i-1]/r[i];
w[i+1]=P[i]/r[i+1];
又P[i]=P[i-1]*l[i];
那么 w[i+1]=P[i-1]*l[i]/r[i+1]=w[i]*l[i]*r[i]/r[i+1];
于是乎 按a[i]*b[i]为关键字从小到大排序就好啦。
乘除法都要写高精度,且答案有10000多位。//国王真有钱

所有的贪心题都可以用拟证来证明


搜索

两种不同的搜索问题
1.最优性
2.计数

两种不同的搜索方法
1.DFS
2.BFS

剪枝
卡时:(一般不用在树上)(OJ上不建议这么做)看到快超时的时候就退出程序,从只能得零分变成了至少得零分了……

  1. include <ctime>//去官网看能不能用,否则就会变成至多零分了……
  2. void dfs()
  3. {
  4. if(clock()-t>=1998)//以毫秒为单位
  5. {
  6. shuchujie();exit(0);
  7. }
  8. }
  9. int main()
  10. {
  11. t=clock();
  12. }

数据结构维护(一般不会出到这么难)

搜索的优化技巧
1.剪枝
2.BFS:双向搜索meet in the middle(前提条件:必须知道你最终需要的状态长什么样)
从初始状态扩展出来n个状态后,不再扩展出n*n个状态,而是从最后一个在扩展出来n个。再从原来的方向搜索。从原来的O(X)变成O(sqrt(X))
3.计数问题:重复结构利用
4.最优化问题:卡时
5.数据结构优化

搜索
N皇后问题[状压DP优化]
数独问题[卡时] 启发式搜索:从个数最少的开始搜索(跳舞链dancing links是啥?)
noip 2012 mayann

奇怪的东西
读入优化:(读int超快!)
int getint()
C=' ';
while(c<'0' || c>'9') c=getchar();
X=0;
while(c>='0' && c<='9') X=X*10+c-'0',c=getchar()

模拟

今天模拟三道题,我真是太菜了……
第一题
枚举换哪几个格子,真的就是无脑枚举模拟,我也不知道为什么我居然错了,就这样吧ovo
(这种题能够快速提高代码能力,建议闲的没事多做做)
第二题
二分答案+暴力
比如知道当前二分出来的答案是m,要求出是否存在这样一个矩阵,使其四个点都大于等于m。往右延伸一定的距离,再往下延伸,就能确定整个矩形,算出来最小值,和答案进行对比就可以了- =
可以这么操作:把大于等于r的值都变成0,小于r的变成0,可以等价为是否存在矩阵是四个点都是1。可以提前预处理出来哪些位置是1,就不需要枚举其它位置了。

还有另外一个方法:
将所有的点权值从大到小一个一个加到矩形中,如果出现了新的矩形就输出
第三题
杨辉三角…………………………生气

杨辉三角的补充:

组合数:从n个物体中选m个的方案数
Cnm=n!/(m!(n-m)!)
Cnm=C(n-1)(m-1)+C(n-i)(m)//可以不断拆开
Cnm=sigma(j=0->i) C(n-2)(m-i+j)*cij;
cnm=cn(n-m)
如果把它们都列出来,就是一个杨辉三角,是右上方和左上方两个数的和

lucas:
cnm%p 可以逆元,或者把n,m变成p进制的数,则cnm%p=cn1m1*cn2m2*cn3m3%p

ummmm我觉得我现在做题还比较稚嫩……就像我都想到正解或者接近正解,就是不敢写……要么就写挂,果然要锻炼代码能力啊……


day 2


素数的判定

1)弱智才会用的办法

  1. bool prime(int x)
  2. {
  3. if (x<2) return 0;
  4. for*int a=2;a*a<x;a++) if(x % a==0) return 0;
  5. return 1;
  6. }

2)费马小定理

p为一个素数且p不是a的倍数,则a^(p-1)=1(mod p);[不能反推]
多次选取a,检验p是否满足费马小定理。
O(klogp)
卡迈尔数

3)miller-rabin(MR定理【听不懂】)

如果n为素数,取a < n,设n-1=d*2^r,则要么a^d≡1(mod n),要么30<=i < r,s.t.a ^(d*s^t)≡-1(mod n)

  1. int prime=[3,7,11,23,37];
  2. bool miller_rabin(int x)
  3. {
  4. n-1=d*2^r;
  5. for(int a=1;a<=5;a++)
  6. {
  7. if(ksm(a,d) %n !=1)
  8. {
  9. for(int i=0;i<r;i++)
  10. {
  11. if(ksm(a,d*2^i)%n==-1) return 1;
  12. }
  13. return 0;
  14. }
  15. }
  16. }

钟神:“背结论吧。”

4)筛法

用来处理连续区间内有哪些质数。
a.非线性筛法(nlogn=1/1+1/2+1/3+···+1/n)
质数的倍数一定是合数。

  1. bool not_prime[1000005];
  2. not_prime[1]=true;
  3. for(int a=2;a<=n;a++)
  4. {
  5. if(!not_prime[a]) for(int b=a+a;b<=n;b+=a) not_prime[b]=true;//如果有那个if优化的话,就是nloglogn
  6. }

b.线性筛法(欧拉筛法)
每个合数都由它最小的质因数筛掉。一个数会被拆成几个质数相乘,最小的质数就直接筛了,就避免了重复筛的过程。接近于O(n)

  1. memset(notprime,0,sizeof(notprime)),notprime[1]=true;
  2. for(int i=2;i<=n;i++)
  3. {
  4. if(!notprime[i]) prime[++ prime_count]=i;
  5. for(int j=1;j<=prime_count;++j)
  6. {
  7. if(prime[j]*i>n) break;
  8. not_prime[prime[j]*i]=true;//用来筛质数的倍数的数
  9. if(i%prime[j]==0) break;//保证了只会找到最小的质因子来筛掉它
  10. }
  11. }

欧几里得定理:

求n个不超过m的正整数复杂度:O(n+logm);
通过辗转相除法求最大公因数。

  1. int gcd(int a,int b)
  2. {
  3. return b?gcd(b,a%b):a;//一行代码就是爽
  4. }

扩展欧几里得定理

欢迎访问我的博客,讲的和钟神一样清晰233
扩展欧几里得算法

求解同余方程

题目描述求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
输入数据输入只有一行,包含两个正整数 a, b,用一个空格隔开。
输出数据输出只有一行,包含一个正整数 x0,即最小正整数解。输入数据保证一定有解。
输入样例3 10
输出样例7
数据范围
对于 40%的数据,2 ≤b≤ 1,000;
对于 60%的数据,2 ≤b≤ 50,000,000;
对于 100%的数据,2 ≤a, b≤ 2,000,000,000。

ax%b=1 <=> ax-by=1;
可由此求出一组x,y的解,转移得到正整数最小解就行啦

求解一次同余式组:中国剩余定理

有一个数 x≡a1(b1 mod p1),x≡a2(mod p2),x≡a3(mod p3)……,x≡ak(mod pk);
求解最小x。
x=k1p1+a1,x=k2p2+a2……
k1p1+a1=k2p2+a2 -> k1p1-k2p2=a2-a1;
将好多好多的这样的方程加在一起。

大数翻倍法

x=a1(mod p1);
x=a2(mod p2);
假设P1 < P2;
复杂度O(min(p1,p2));

  1. int fanbei(int a1,int p1,int a2,int p2)//p1<p2
  2. {
  3. ans=a2;
  4. while(ans % p1 != a1) ans+=p2;
  5. return ans;
  6. }

大体的意思就是,找到一个最大的P,然后不断翻倍,使它能够整除其它所有的P

逆元

在模的意义下通过逆元也能做除法。
如果gcd(a,m)=1,且存在唯一的b,使得a*b≡1(mod m)且1<=b < m,则b为a在模m意义下的逆元
当m为质数的时候,直接使用费马小定理 a^(p-1)≡1
m非质数时,使用欧拉定理 a^φ(m)≡1
φ(m):欧拉函数,表示小于等于m的质数的个数

积性函数

如果对于(n,m)=1,有f(nm)=f(n)f(m),则称f为积性函数
σ(n)=Σd|n d 从1到n的加和
τ(n)=Σd|n 1 n的因子个数
φ(n) 欧拉函数 1-n当中与n互质的数的个数 ϕ(n)=n∗∏(pi−1)/pi(∏:乘积)
μ(n) 莫比乌斯函数 n=p1^k1*p2^k2*p3^k3……

当n=1时,μ(n)=1
当k1=k2=k3=……=kr=1时,μ(n)=(-1)^r;
否则μ(n)=0;

在数论的容斥原理中多有使用。
求积性函数只需要在线性筛中加上函数就行。
举例子:欧拉函数

  1. memset(notprime,0,sizeof(notprime)),notprime[1]=true;
  2. for(int i=2;i<=n;i++)
  3. {
  4. if(!notprime[i])
  5. {
  6. prime[++ prime_count]=i;
  7. phi[i]=i-1;
  8. }
  9. for(int j=1;j<=prime_count;++j)
  10. {
  11. if(prime[j]*i>n) break;
  12. not_prime[prime[j]*i]=true;
  13. if(i%prime[j]!=0)//积性必须满足gcd(n,m)=1
  14. {
  15. phi[prime[j]*i]=phi[prime[j]]*phi[i];//a与b互质的话,a+b与b也互质
  16. }
  17. else phi[i*prime[j]]=phi[i]*prime[j];
  18. if(i%prime[j]==0) break;
  19. }
  20. }

留着看:欧拉函数
如果你看到这行文字……代表我的图挂了QAQ

例题:求a^x≡b(mod m)的最小正整数解。
BSGS(北上广深)算法:
a^φ(m)≡1(mod m),所以解一定在a^1,a^2,a^3……a^m之间
可以每次两个两个枚举,如果没有答案就乘上a^2,再继续枚举下去。
最高效的方式:k=sqrt(m),写成一个k*k的矩阵形式

a^1 a^2 a^k
a^(k+1) a^(k+2) a^(k+3)
a^(2k+1) a^(2k+2) a^(2k+3)

每行询问klogk,第一行排序klongk,O(sqrt(m)log(m)).
在每一行是否出现,可以直接通过除以a^nk(乘法逆元),转移到第一行

作业:给一个n,m,for(int i=1,i<=n;i++) for(int j=1;j<=m;j++) 求Σgcd(i,j);


概率


基本知识

Pr[i]表示事件i发生的概率 Σi=1->N Pr[i]=1; xi表示事件i的权重 E[x]=Σi=1->N Pr[i]*xi 有x个人没有人生日相同的概率:366/366+365/366+364/366……+366-x+1/366
对于独立事件i和j,Pr[i^j]=pr[i]*pr[j] 事件i和事件j的期望是可加的。
条件概率: 当事件j已经发生时,事件i发生的几率 pr[i|j]=pr[i^j]/pr[j] 一个有趣的结论: 当太阳已经从东边升起n天后,第n+1天从东边升起的概率:(n+1)/(n+2)

题目

1)problem 1
甲乙面前三瓶药,两瓶毒药,每人喝一瓶。
甲喝了一瓶,挂掉了
为了活下去,乙应该喝手上的这瓶,还是另外剩下的一瓶呢?
喝哪个都一样,因为乙不知道哪个有毒。

2)problem 2

小胡站在原点,手里拿着两枚硬币。抛第一枚硬币正面向上的概率为𝑝,第二枚正面向上的概率为𝑞。
小胡开始抛第一枚硬币,每次抛到反面小胡就向𝑥轴正方向走一步,直到抛到正面。
接下来小胡继续抛第一枚硬币,每次抛到反面小胡就向𝑦轴正方向走一步,直到抛到正面。
现在小胡想回来了,于是他开始抛第二枚硬币,如果小胡抛到正面小胡就向𝑥轴的负方向走一步,否则小胡就向𝑦轴的负方向走一步。
现在小胡想知道他在往回走的时候经过原点的概率是多少呢?

假设小胡走到(x,y)又回到原点。首先往x正方向走x步又抛到正面的概率是p*(1-p)^x,在往y轴正方向走y步的又抛到正面的概率是(1-p)^y*p。往回走的时候:往X负方向走x步的概率是q^x,往Y负方向走y步的概率是(1-q)^y。总的概率是:
p*(1-p)^x*(1-p)^y*p*q^x*(1-q)^y=p^2*(1-p)^(x+y)q^x(1-q)^y;
一共走x+y步,其中不知道x有几步,于是我们要枚举x+y和x。每对x+y,x都有c(x+y)x种方式。在原来的概率上加上组合数就行啦。
最后的概率:
图挂了qwq
化简以后:
图跪了qwq
注意这个公式的运用:
图炸了qwq

2.3) problem 2.3

小葱想要过河,过河有两条路
一条路有100个石头,每个石头有1/100的概率会挂掉
一条路有1000个石头,每个石头有1/1000的概率会挂掉
小葱应该走哪边呢?
请勿使用计算器

显然:
Markdown

3) problem 3
这道题被抛弃了……

4) problem 4

小泽在数轴上的0点处
小泽每次有𝑟的概率向右走,有1−𝑟的概率向左走
问小泽走到−1处的概率

试着枚举步数www

步数 概率
一步 1-r
两步 0
三步 r*(1-r)^2
四步 0
五步 r^2*(1-r)^3*卡特兰数(保证前缀和>=0)

PS:刚刚翻到一个超棒的浅谈卡特兰数

如果按照上面那种一步步加上来的办法,特别麻烦……
所以换个思路,设概率试试。
设从x出发到达x-1的概率为p,第一步向左的概率是1-r,第一步向右到x,再从x到x-1的概率是rp^2。则有p=(1-r)+rp^2。
解得:
p=1 (r<=1/2),
p=(1-r)/r (r>1/2);

5) problem 5

小胡有一棵一个点的树,小胡会给这个点浇水,于是这个点会有𝑝的概率长出两个儿子节点。
每次长出新的节点之后,小胡又会给新的节点浇水,它们也都有𝑝的概率长出两个新的儿子节点。
小胡不希望自己被累死,所以小胡希望知道这棵树的大小是有限的的概率。

这道题和problem4是一样的……

6) problem 6
老师又弃题啦QAQ

给一堆点的坐标。在平面内画个圆,把所有的点都包含进去,问最小半径

第一种方法:
三点可以确定一个圆,所以暴力方法:枚举三个点,再把剩下的点一个一个扔进去,看看在不在圆里面
O(n^4)
如何优化?
举个例子,通过a,b,c三个点你确定了一个圆,圆