技巧总结

知识体系

这一篇博客可能会是一个大坑

放一些好的东西 戳我

学长的 戳我

---

没错，最重要的当然是

卡常&优化

1.bitset

bitset存储二进制数位(作为高斯消元你不可多得的选择)
bitset就像一个bool类型的数组一样，但是有空间优化——bitset中的一个元素一般只占1 bit，相当于一个char元素所占空间的八分之一
bitset中的每个元素都能单独被访问，例如对于一个叫做foo的bitset，表达式foo[3]访问了它的第4个元素，就像数组一样
bitset有一个特性：整数类型和布尔数组都能转化成bitset
bitset的大小在编译时就需要确定。如果你想要不确定长度的bitset，请使用（奇葩的）vector<bool>
它支持与(&)、或(|)、异或(^)、左移(<<)、右移(>>)等操作
bitset的相关函数

对于一个叫做foo的bitset：
foo.size() 返回大小（位数）
foo.count() 返回1的个数
foo.any() 返回是否有1
foo.none() 返回是否没有1
foo.set() 全都变成1
foo.set(p) 将第p + 1位变成1
foo.set(p,x) 将第p + 1位变成x
foo.reset() 全都变成0
foo.reset(p) 将第p + 1位变成0
foo.flip() 全都取反
foo.flip(p) 将第p + 1位取反
foo.to_ulong() 返回它转换为unsigned long的结果，如果超出范围则报错
foo.to_ullong() 返回它转换为unsigned long long的结果，如果超出范围则报错
foo.to_string() 返回它转换为string的结果

具体参见 大佬博客

2.long long不够换double

你如果不想打高精的话
知识点来源:Robert 的军队

3.离散化与去重&不想手写的二分

是“去掉”容器中相邻元素的重复元素，这里去掉要加一个引号，为什么呢，是因为它实质上是一个伪去除，它会把重复的元素添加到容器末尾，而返回值是去重之后的尾地址

lower_bound(a+1,a+1+n,x)-a;
返回第一个不小于的x的位置
upper_bound(a+1,a+1+n,x)-a;
返回第一个大于x的位置

还有就是
len=unique(a+1,a+1+n)-a-1

4.SPFA与Dijstra

被坑惨了，来源于NOI2018Day1T1
"SPFA它死了"，出题人把SPFA成功卡成O(n^2*m)
所以下次一定要注意边的数量！是否稠密！
SPFA:O(k*E)最坏情况下O(N*E)
Dijstra(堆优化):O((E+N)*logN)

5.矩阵不具有交换律！一定注意乘法顺序

数据结构优化

1.知识点来源 2018.6.8考试T3
若考虑对于整个区间向后平移时，会想到Splay
但可以根据题目性质易知并不需要真的将区间往后移，只要知道位置在不断变小，是与要调换位置之差即可，并不需要还原当前位置是什么，所以就是单点修改和区间查询，考虑树状数组
再根据需要查询区间最小值，根据数据范围，可知O(26)的常数很优秀，类似挂链

数论

欧拉函数

1.知识点来源[SDOI2008]仪仗队

由于要求在同一条直线上的点看不到，于是我们得知对于某两点恭献来说
若有 $k$=$\frac{x1}{y1}$=$\frac{x2}{y2}$;
则将$\frac{x1}{y1}$化简后，得到最简分数比$k$=$\frac{x3}{y3}$，此时在这条直线上我们只能看到(x3,y3)，即gcd(x3,y3)=1。因此我们能看到的所有点是

$$\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==1]$$
经过一系列简单的化简为
$$2*\sum_{i=3}^{n}\phi[i-1]+3$$
至于证明过程以后再补

2.知识点来源[HAOI2007]反素数

这其实是一个比较裸的数论题

区间问题

1.区间连续k个元素之和的最大值
知识点来源 切蛋糕

考虑以p[i]表示以i为结尾的区间最大值，则不难得到
$p[i]=max{sum[i]-sum[j-1]}(i-j+1>=m)$
又由于sum[i]是固定的，则
$p[i]=sum[i]-min{sum[j-1]}$
因而我们只需维护 $i-j\le m$ 的一个单调队列即可

实现代码如下

N=read();M=read();
for(int i=1;i<=N;i++)a[i]=read(),sum[i]+=sum[i-1]+a[i];
int head=1,tail=0;
dui[head]=(hand){1,sum[1]};
for(int i=2;i<=N;i++)
{
    while(head<=tail&&dui[tail].s>sum[i])tail--;
    dui[++tail]=(hand){i,sum[i]};
    while(head<=tail&&dui[head].p+M<i)head++;
    ans=max(ans,sum[i]-dui[head].s);
}
cout<<ans<<endl;

2.求区间最大子段和
知识点来源:[2017杭二联考]Black Rock Shooter,[NOI2005]维护数列
相信不带修改的大家都会做吧，O(n)的
但是带修改的O(n)就不适用了,可以使用线段树或者平衡树来解决
记录以左端点的lx,右端点的rx，整个区间的mx(都是必须选当前点的)

lx[now]=max(lx[lson],sum[lson]+lx[rson]+v[now]);
rx[now]=max(rx[rson],sum[rson]+rx[lson]+v[now]);
mx[now]=max(max(mx[lson],mx[rson]),v[now]+rx[lson]+lx[rson]);

另外就是$Update$的时候注意一下就好了，然后注意区分一下定义
看看子段是否强制选一个，还是可以都不选

3.求区间的并
知识点来源:10.20T3考试40分
正常线段树是左闭右闭的开，但是求区间的并我们需要左闭右开的开，否则无法统计到[mid,mid+1]这条线段的贡献，具体修改是
注意一下不要死循环即可(r-l==1)return

if(L<mid)upd(lson,l,mid,L,R);
if(R>mid)upd(rson,mid,r,L,R)

4.维护类似最长上升子序列
知识点来源:楼房重建

有关多组同余方程求公解

知识点来源 Biorhythms
资料借鉴 MashiroSky,中国剩余定理【数论】 ,证明

求长方形的对角线所经过的矩形个数

公式(长为N,宽为M的长方形)

$$N+M-gcd(N,M)$$
可是证明过程并不会的我

知识点来源 付公主的矩形

值得注意的扩展

若要求所有满足经过矩形个数为$k$的长方形方案(长宽互换算重复)
显然$N\leq k$且$M\leq k$，然后有

$$N+M-gcd(N,M)==k$$
则有
$$\frac{N}{d}+\frac{M}{d}==\frac{k}{d}+1$$
又有$\frac{N}{d}$与$\frac{M}{d}$是互质的,即
$$gcd(\frac{N}{d},\frac{M}{d})==1$$
$$gcd(\frac{N}{d},\frac{M}{d}+\frac{N}{d})==1$$
所以有
$$gcd(\frac{N}{d},\frac{k}{d}+1)==1$$
这不就是求$\phi[\frac{k}{d}+1]$吗？枚举所有可能的因子d
$$Ans=\sum_{d=1}^{n}\phi[\frac{k}{d}+1]$$
然后由于长宽交换是不能重复计算的，所以先Ans+1再左移一位
至于为什么Ans要先+1，我暂时还没弄明白

斐波那契数列

$$f[m]=f[m-n-1]*f[n]+f[m-n]*f[n+1]$$
$$\sum_{i=1}^n f[i]*i=n*f[n+2]-f[n+3]+2$$

树的联通块方案数

将一棵$n$个节点的树划分为$m$个联通块的方案数为

$$C(n-1,m-1)$$
然后如果要随机选择联通块进行游走的话，方案数为
$$C(n-1,m-1)*m!$$

图论

一笔画问题

知识点来源 游历校园

由于图中存在若干个联通块，因此需要多遍dfs(bfs)，传送器使用次数是为了让某些边连起来，从而使得图中奇点互相达到(具体请看“信息学奥赛一本通”)
x笔画次数=图中奇数点个数/2,
传送器使用次数=x笔画次数-1
还有两个细节就是：
1.联通块与联通块之间也需要互相转移也需要转换器
2.若一个联通块内只有一个点的话不予考虑

void dfs(int u,int fa)
{
    dfn[u]=1;
    if(du[u]&1)tot++;
    for(int i=head[u];i;i=a[i].next)
    {
        int v=a[i].to;
        if(v==fa||dfn[v])continue;
        dfs(v,u);
    }
}
for(int i=1;i<=n;i++)
{
    if(!dfn[i]&&du[i]>=1)
    {
        ans++;
        tot=0;
        dfs(i,i);
        if(tot)ans+=tot/2-1;
    }
}

最小生成树类变形题

1.知识点来源[SCOI2012]滑雪与时间胶囊
考虑到时间胶囊是具有回溯功能的，所以易知第一问答案就是以“1”为根的一个强联通分量图，第二问就是求这个有向图的最小生成树，考虑到同一高度的海拔间就是普通的最小生成树，而且不同高度海拔层的路径相当于是自动取最好的地方，反正就这样吧，我暂时还没扯清
拓展最小树形图：戳我有知识讲解

2.知识点来源 2018.6.9考试T2
如何确定给定的一个邻接矩阵是一棵树？
考虑构造MST,对于三点x,y,z，考虑反证法
已知y是离x最近的，若y与x之间未直接连边，而是x->z->y
则存在dis[x][z]+dis[z][y]<=dis[x][y]
又因为dis[x][y] 所以对于每一个点离它最近的点之间一定会直接连边
然后考虑Floyed，易知MST正确
然后O(n^2)check，即MST+DFS构造邻接矩阵，与原矩阵比较
若有一处不同，则不可能构成一棵树
反之则行

3.知识点来源 2018.6.17考试T3(超级好的一道题)
给你n个点m条边的无向图。有q个询问，给出两个点u,v，要从u到v找两条没有相同边的路径，使得两条路径上所有边权最大值最小。如果不足两条路径则输出”No”

首先观察要求有两条路径，则是要求我们有边双，找边双的话dfs就可以了
（也就是做个并查集）
然后观察部分分是每条边只存在于一个简单环里，则是仙人掌的性质
我们考虑构造mst，然后依次从小到大加边，每找到一个环时，则将这个环在另外一张新构的图上缩为一个点，也就是环中所有点只想出现最早的点（也就是dep）
然后再在新图上跑倍增就可以了
然后推广至全部
由于边从小到大加入，即某个点可能已被并入了某个环内了，再引入新点时，则直接连接之前该点所处在的环内就ojbk了，正确性显然
eg.
1-2,2-3,3-4 为mst
然后引入 2-4 则此时2,3,4缩为一个环，环顶为2
然后引入 1-3 则在新图中将1连向2即可

总结一下

首先判断是否存在两条路径：显然如果两个点不在一个边双联通分量里则无解，否则一定有解。
这道题看起来不太好做，但是可以考虑下面的方法：
1. 先求出原图的mst
2. 继续按权值加非树边，然后维护双联通分量。
3. 询问时判断两个点最早什么时候在同一个双联通分量里。
这样做显然正确，问题是怎样维护答案。
首先考虑第二步。如果我在mst上加入一条非树边(u,v)，考虑哪些点会被缩成双联通分量，显然是u到v的简单路径上的所有点。那么我们可以把它们缩成一个点。这样我们得到的还是一棵树，继续这样的过程即可。
然后是询问了。考虑到我们是按权值从小到大加边，那么询问u,v第一次缩在一起时，也就是u,v路径上所有点第一次缩在一起的时候。
那么缩点的时候，给路径上所有边取个min，然后询问就是路径上所有边的max值了。
由于从小到大加边，缩点可以打个并查集。询问时打个倍增即可。

4.对于每一条边具有两种边权的题
先让一条边有序
再按题目要求考虑正着或倒着做最小生成树

弱联通分量

给一张图，若对于两点(x,y)中，x可以到达y或者y可以到达x，则称(x,y)为弱联通，求图上所有点对是否满足弱连通。
Solve:先Tarjan缩环，然后对环上跑遍最长链是否等于点数，或者跑遍拓扑序，要求每次拓扑完后入度为0的点不超过1个。

来回遍历问题

知识点来源 航空路线问题
近日网络流是高频考点啊所以补个坑
对于要求来回路径上点不重复的问题，我们考虑进行拆点，

二分图

二分图撞上欧拉回路

知识点来源:CF547D
对于行和列的限制的题目，我们可以考虑将每个点的行向列连边
然后大部分可以转换成二分图的问题
如本题限制要求两色差<=1
我们可以将相邻的行和列连边，做二分图染色就好了
至于存在孤立点不影响答案，顶多让差变为1

点分治

1.知识点来源[国家集训队]聪聪可可
这虽然是一道点分治的经典裸题，但是这并不属于我今天要讲的技巧
一棵树$N$个点，求两人随机选择树上所有点的方案数(可选择相同点)
若考虑有序的话

$$Ans=N*N$$
若要求路径长度关于x的倍数的呢？
巧妙利用模数的性质，点分治最基础的即是与桶套用
例如$x=3$，那么tong[0,1,2]则记录模数后的路径个数
则总方案数为(仍然考虑有序)
$$Ans=2*tong[1]*tong[2]+tong[0]*tong[0]$$

dp大坑

方案计数型问题

1.LIS型问题
知识点来源:5.19 考试
问题为:将一个序列转换成用最少的修改次数使这个整数序列严格单调递增。
于是很自然的想到了LIS,但单纯用LIS是有一些问题的,
比如这种情况:2 3 1 4, LIS 为 2 3 4,答案求出来为 1,
但由于整数的限制,应该要修改2次。即直接LIS求出的答案是在非严格递增的情况下的答案
于是我们有了
将严格递增整数序列映射成非严格递增整数序列的技巧
a1, a2, a3, a4 ... an
映射成:
a1 - 1, a2 - 2, a3 - 3, a4 - 4 ... an - n.
这样映射后求最长不下降子序列的长度就没问题了。

2.最短路型问题
给你一个很大的标准时间T
对于路径s->t，是否有路径能满足恰好时间T，允许经过同一条道路多次
对于小数据易知，vis[u][t]表示到结点u时间t是否存在，爆搜即可
后来发现状态许多重复，假设对于一个我们必走的环(环长为2*d)来说
vis[u][t]存在，则vis[u][t+d],vis[u][t+2*d]...都可以
所以只要t%2d存在即可
设f[u][t]表示到达结点u所花时间为t+k*2d的最小代价
跑最短路，由于最短路是会更新环中状态的，所以不需要考虑有环没算到的情况，同时也不需要考虑所选初始环不会走的情况(那么就是k==0)
f[v][(t+e[i].w)%2d]=min(f[u][t]+e[i].w) 这是转移
考虑最后 f[n][T%2d]<=T
至于环长可以选择与s相连的最小边长*2

Update 8.15
题目来源[国家集训队]墨墨的等式
又是一道巧妙利用剩余系缩小数据范围的好题
设$f[i]$表示在$mod i$意义下的最短路(也就是代价)，其实和上面的题目差不多了
由于最小的数一定是从0开始增长，所以就从0开始跑遍最短路就好了

3.交换dp下标与内容

4.前缀和优化dp
题目来源:8.27考试T3

5.关于状压的超集前缀和
一定要先枚举位数再枚举值！！！否则会WA！
因为这样修改个数才是$2^m$
否则就是$m+1$

6.关于合并石子如何优化至O(n^2)
将O(n^3)优化至O(n^2)的方法就是观察到(或打表发现)每次转移只会在端点进行转移
所以只需考虑端点了，这样还能滚掉长度那一维
题目来源:8.29考试T2

整数拆分数

Noi.ac MST和[JLOI2012]时间流逝
都是整数拆分数加上期望的好题

多项式

1.题目来源:10.18考试T3
考虑生成函数，表示选或不选每个子节点的$sz[v]$

$$\sum (1+kx)$$
来自师傅的思考:其实上式可以写出带权组合数的形式
$$f[i][j]=f[i-1][j-1]*k+f[i-1][j]$$
如果不用组合数思考，并且你不会分治FFT的话
$f[u][i]$表示第$u$个节点的生成函数的第$i$项的系数
因为此题是单点插入和单点删除
所以考虑$O(项数)$的修改，初值第0项为1
插入:倒着写，这个易知

++d;
for(int i=d;i;--i)(s[i]+=1ll*s[i-1]*x%mod)%=mod;

删除:正着写，这个不知道为什么，但是手玩了一下是对的

for(int i=1;i<=d;++i)s[i]=(s[i]-1ll*s[i-1]*x%mod+mod)%mod;
d--;

然后至于什么时候我会了$FWT$再回来吧