Day 2

考试题解

T1 小路灯

~~再次签到成功。~~考试时做法是二分然后加上一点点小贪心。不过这个贪心调了一万年。一开始用半小时写出了“正解”，然后开始写暴力造数据。结果第二组数据就拍出问题了。于是开始调试。调了两个小时才终于调出来，然后开始看$T2$。

不过真的就只是二分吗？中间应该还有一些细节要注意。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
ll n,k,minn=2000000005,maxx=0,ans=2000000005;
ll a[100005];
bool check(ll x){
	ll t=a[1],sum=0;
	for(ll i=2;i<=n;i++){
		if(a[i]-t>x){
			sum++;
			t=a[i-1];
			for(ll j=i,k1=i;j<=n;j=k1){
				k1=j;
				while(a[k1]-t<=x&&k1<=n){
					k1++;
				}
				ll k2=k1;
				if(k1>j){
					while(a[k2+1]-a[k1]<=x&&k2+1<=n){
						k2++;
					}
				}
				if(k2>n) break;
				k1=k2;
				sum++;
				t=a[k2];
			}
			break;
		}
	}
	if(sum<=k) return true;
	else return false;
}
int main()
{
	scanf("%lld%lld",&n,&k);
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		minn=min(minn,a[i]);
		maxx=max(maxx,a[i]);
	}
	ll l=0,r=maxx-minn;
	while(l<=r){
		ll mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

老师做法（没有那么多细节要注意，更好写）：在这个距离内往后找，找到一个路灯然后点亮它即可。不需要像我一样考虑前后的最优选择。

类似题目：$NOIp$ 2015 D2T1 跳石头

T2 序列

~~40pts白扔，暴力分-=40。~~考试的时候真的有点急了，主要是$T1$花费了太多时间。不过这的确是值得的（因为$T1$暴力一分都没有）。暴力模拟就可以得到$40pts$。但是nc写挂了。

40分做法：

暴力模拟。

60分做法：

对每次操作用线段树或者平衡树维护。

100分做法：

发现每一次操作都是将所有的数向后移一位。然后在这种模拟下有特殊情况，每个序列都有$n/k$个数需要挪到每一段后面单独处理，这样总复杂度就是$O(n/1+n/2+n/3+...)=O(n*ln(n)）$，开一个二倍数组维护即可。

T3 路灯

~~靠着$T1$对拍用的暴力改了改，水了$60$pts。~~爆搜就是60分做法。

100做法：

~~我就知道是$dp$，但是我不会。~~f_{i,j}表示前$i$个路灯点亮了$j$个，而且第$i$个是点亮的。$f_{i,j}=min(f_{r,j-1}+h_{r,i})$。需要提前预处理$h$数组，然后总时间复杂度是$O(n^2*k)$。

类似题目：$NOIp$ 2015 子串（拓展：改成子序列）

$f_{i,j,k}=f_{i-1,j-1,k-1}$

T4 匹配

考试由于时间原因写假了且来不及改（20分做法）。

20分做法：

暴力求出两两之间距离然后$n^3$枚举。

40分做法：

暴力求出两两之间的距离（此过程复杂度？），枚举三个点的中间点，然后找到所有与中间点距离为2的点（考试时我也曾有过此思路，但是不太好写）。

100分做法：

一个点与一个子树中距离为2的所有点权和和

树形dp或边加边维护

拓展：洛谷P3565 [POI2014]HOT-Hotels

搜索专题补充

记忆化搜索

实质是$dp$。

slots

啥也没听懂？？？？？？？？？

计数

记录13种牌每一种剩多少张，同时记录上一张牌是什么。每当已经搜索过这个状态就不用再搜索了。

优化：用一个数组$a_i$来记录面值相同牌数为i的时候的方案数。

idfs

埃及分数

用$s$来记录和，用$a$来记录当前分母，$k$记录个数，然后剪枝：如果$1/a*k<s$，那么肯定不行了。而且还要让分母尽可能小。

八数码问题

k短路问题

优先队列，取出队首然后最短路。第$k$次到达就是$k$短路

骑士精神

剪枝：估价函数大于剩余搜索层数。

Lizard 。。。

先搜索出前一半三个人的收益差，然后再搜索后一半，然后比较。然后$Hash$查询（不会）。

随机算法（骗分）

用正确性换取时间复杂度。

爬山算法

$N$个点，有权值，选一个点，使其他点到他的距离乘上权值的和最小。

模拟退火

[HAOI2006]均分数据

???????????????????????????????????????????????????????????????????

例题

背包问题变搜索

$max$ $x_1+3x_2+5x_3+9x_4$//价值最大化

$2x_1+3x_2+4x_3+7x_4<=10$//体积

搜索：当前搜到了第几层，剩余体积，得到价值

剪枝：先按价值排序，如果剩余体积乘以当前物品价值仍然小于已得到的价值，那么剪去

货郎问题

剪枝：用$L_i$来记录$i$的出边的最小值，记录当前已走的路径长度，如果长度加上每一个剩余顶点向外连的最小值已经比答案大了，那么直接减去。

邮票面值设计

剪枝：确定一个可选的区间

Tales。。。

求奇最短路和偶最短路（$NOIp$ 2019 普及组$T4$ 加工零件）

建两个图（分层图思想）

NOIp 2014 寻找道路

删掉不符合条件的点然后跑最短路（画图

NOIp 2015 斗地主

按顺序搜索

数论

快速幂

越狱

求出总情况和不会越狱的情况，然后相减得到会越狱的情况。

总：$m^n$

不会越狱：$m*(m-1)^(n-1)$

用快速幂求解即可

素数

线性筛

积性函数

莫比乌斯函数：0，n>1;1,n==1

积性函数性质：如果能够求出f(p^k)，那么就可以快速地求出f(1)到f(n)。

例题：sigma那个题

看到gcd就枚举。$gcd(i,n)=d -> gcd(i/d,n.d)=1 -> 设i=kd$ -> 枚举

？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

逆元

$xy≡1(mod n)$

$x$在模$n$意义有逆元当且仅当$(x,n)=1$

$a=[n/x],b=x%a$

$ax+b=0(mod n)$

$ax=-b$

$ax*b^{-1}=-b*b^{-1}$

$ax*b^{-1}=-1$

$-ax*b^{-1}=1(mod n)$

所以$x$的逆元是$-a*b^{-1}$

线性求逆元代码

inv[1]=1;
for(i=2;i<=n-1;i++)
   inv[i]=(n-inv[n%i]*(n/i)%n)%n;

$O(1)$计算组合数(模意义下）

Lucas定理

设$P$是质数，则$C_n^m$%$P$= $C_{nmodP}^{mmodP}$ * $C_{n/P}^{m/P}$ % $P$
常用来求$n$,$m$较大，但$P$较小的组合数取模

最大公约数和最小公倍数

定理: $ab = gcd(a,b) * lcm(a,b)$

求最大公约数：利用公式$gcd(a, b)=gcd(b, a mod b)$, 时间复杂度为$O(logb)$

威尔逊定理：若$p$为素数，则$(p-1)!≡-1 (mod p)$。

费马小定理：$p$是素数且$(a,p)=1$，则$ap-1≡1 (mod p)$

线性求欧拉函数：

void eular(int n)
{for(int i=2;i<=n;i++)
     {if (!IsPrime[i])
         {	prime[++cnt]=i;  phi[i]=i-1;}
	  for(int j=1;j<=cnt;j++)
          { if (prime[j]*i>n) break;
       	 Isprime[prime[j]*i]=1;
      	 if (i%prime[j]==0)
               {phi[i*prime[j]]=phi[i]*prime[j];  break;}
      	 else
               phi[i*prime[j]]=phi[i]*(prime[j]-1);
          }
	 }
}

Euler定理: 若$gcd(a, n)=1$则$a^n = 1 (mod n)$
意义：当$b$很大时，$a^b$ = $a^{ $bmodn$ }$ $(mod n)$，让指数一直比较小

裴蜀定理：设$gcd(a,b)=d$，一定存在整数$x,y$，使得$ax+by=d$ 。拓展GCD是求特解的过程。

int ex_gcd(int a, int b, int &x, int & y)
	   {if (b==0){ x = 1; y = 0; return a; }
        else {int r =ex_gcd(b, a%b, x, y);
                 int t = x; x = y; y = t – a/b*y;
                 return r; 
                }
       }

P1516 青蛙的约会

设总共跳$T$次可以相遇，则有：$A$的坐标$X+MT$，$B$的坐标$Y+NT$相遇的充要条件：$X+MT-Y-NT=PL ( p是整数)$ ，变形为$(N-M)*T+LP=X-Y(L>0)$，利用扩展欧几里德原理，求出最小的$T$即可。

$a1_{x1}+a2_{x2}+…+an_{xn}=N$，有整数解的充分必要条件是$(a1,a2,…,an)|N$

中国剩余定理

$a≡a1 (mod n1)$
$a≡a2 (mod n2)$
……………
$a≡ak (mod nk)$

$a=(a1*c1+a2*c2+…+ak*ck) mod (n)$…中国剩余定理
其中$n= n1*n2*…*nk$ ，$ci=mi*(mi-1 mod ni)$，$mi=n/ni$

int remainder()//求同余方程组a
{int i,j,n=1,m,d,x,y;
 for (i=1;i<=k;i++) n*=n[i];
 a=0;
 for (i=1;i<=k;i++)//将同余方程组转化为对应的多项式求值
    {m=n/n[i];//求mi
      d=ex_gcd(n[i],m,x,y);//通过欧几里得扩展形式求y=mi-1
      a=(a+y*m*a[i])%n//累加a的值
    }
 if (a>0) return a;
 else return a+n;
}

炸裂

容斥原理

错排问题

有$n$个物品和$n$个盒子，编号都是从$1$到$n$。现在要把每个物品放进一个盒子，每个盒子刚好放一个物品，并且$i$号物品不能放进$i$号盒子。求方案数模1000000007。
$n<=100000$

$n!$-$C_n^1*(n-1)!+C_n^2*(n-2)!-......+...$

阶乘，组合数都可以预处理（逆元方法$O(1)$求组合数)

隔板法

有$m$个未知数$x_1,x_2,……,x_m$。满足$x_1+x_2+x_3....+x_m=k$ $0<=xi<=n$。求方程解的个数。$1<=n,m<=100000$。$0<=k<=100000$。

相当于有$k-1$个空，插进去$m-1$个板，答案即为$C_{k-1}^{m-1}$

拓展：$xi>=n$

做法：$k$减去$m*n$即可转化为原题

概率与期望

如果一个随机事件发生的概率是$p$，那么重复做这个实验，期望做多少次才能第一次发生该事件？

$1*p+2*(1-p)*p+3*(1-p)^2*p+4*(1-p)^3*p+……=1/p$

收集邮票

？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

小左的GCD

似乎可做，求$1≤x,y≤N$且$gcd(x,y)$为素数的数对$(x,y)$的个数，就相当于是在$1<=x,y<=n/i$中找互素对，用欧拉函数可以$O(n)$求解。

qbxt Day 2