总结

AubRain · 2019-04-03 09:07:44 · 个人记录

总结——小题解合集

P3745 [六省联考2017]期末考试

贪心+双指针。

枚举天数，双指针即可。利用前缀和后缀和计算答案。

P3746 [六省联考2017]组合数问题

矩阵乘法。

转移方程 f_{i ,j}=f_{i-1,(j-1)mod\;k}+f_{i-1,j}

最后 f_{n*k,r} 即为答案。注意特判 k=1 的情况

P3747 [六省联考2017]相逢是问候

线段树+欧拉定理。

指数对phi(p)取模，再对phi(phi(p))取模，最多log次模数就变为1

线段树记录区间取模次数即可。

然后最毒瘤的是判断是否 \ge 模数，要在快速幂里面判断，细节不少。

要用光速幂计算c的幂

P4068 [SDOI2016]数字配对

费用流。

想办法建立二分图。配对的条件a_i 是 a_j 的倍数，且 a_i/a_j 是一个质数，所以按照质因子指数和 建图。奇数连s，偶数连t。

总价值和\ge 0 的条件增广的时候判一下就行了。

P4251 [SCOI2015]小凸玩矩阵

二分答案+网络流。

二分第k大是多少，网络流判断能否选出n-k+1个\le它的数。

P4589 [TJOI2018]智力竞赛

二分答案+网络流

先传递闭包，把所有小于mid的值建图。最小路径覆盖问题即可。

P3247 [HNOI2016]最小公倍数

分块+并查集+套路。

先把边按照a排序，分成\sqrt m 块。对于第i块，只处理a在该块之间的询问。

首先把该块以前的所有边按照b再排序，询问也按照b排序。双指针加入之前的边。

然后枚举当前块的所有合法边，加进去。这里要带撤销。

然后并查集记录连通块a,b最大值就行了。

每个询问会枚举\sqrt m 条边，加上并查集按秩合并，复杂度 O(m\sqrt m logm)

P4108 [HEOI2015]公约数数列

分块。

见前缀gcd就要想最多有log种。

每个块开一个map，记录每个前缀异或和的位置。再记录区间gcd。

修改的时候暴力重构这个块，把后面所有块都打上异或标记。

询问就枚举每个块，如果这个块里没有分界点，那么就map找一下。否则就暴力枚举每个元素判断。

复杂度 O(q\sqrt n log^2n) 。能跑过去就是奇迹。

P3245 [HNOI2016]大数

莫队。

记录前缀表示的数，然后就是 \frac{s_i}{10^i}==\frac{s_j}{10^j} 的有多少对。莫队即可。

注意p=2或5的时候10没有逆元，要特判。

P4211 [LNOI2014]LCA

树剖+离线。

相当于把[l,r]到根的路径上的点都+1,再询问z到根的权值和。

P3241 [HNOI2015]开店

树剖+主席树。

就是上一题加上强制在线。主席树+标记永久化维护就行了。

P3243 [HNOI2015]菜肴制作

贪心+堆。

反图上大根堆拓扑排序即可。

P3171 [CQOI2015]网络吞吐量

最短路+网络流。

点权化边权最短路径上最大流。

P4345 [SHOI2015]超能粒子炮·改

Lucas定理。

设答案为f(n,k)，把Lucas式子写出来，容易发现

递归计算即可。

P3705 [SDOI2017]新生舞会

分数规划+费用流。

二分答案后最大费用流判断费用是否\ge0即可。

P4071 [SDOI2016]排列计数

组合数+错排。

P3320 [SDOI2015]寻宝游戏

set+思维。

按照Dfs序递增访问肯定是最优的，用set维护Dfs序就行了。

P3242 [HNOI2015]接水果

整体二分+扫描线。

Dfs序上，每个盘子相当于二维平面一个区间。每次询问相当于求包含这个点的区间的权值k小。整体二分即可。统计的话就差分一下，扫描线。

#4472. [Jsoi2015]salesman

树形dp+贪心。

每个点贪心的选儿子dp值前几大的就行了。至于方案唯不唯一，判一下就行了。

P2585 [ZJOI2006]三色二叉树

树形dp。

没了。

P4109 [HEOI2015]定价

枚举。

边界：f[x][1]=1

条件：若x在y前，j \in [k-i+1,sz[y]]，否则j\in[1,min(sz[y],k-i)]

优化：树形背包sz优化，前缀和优化。

P3345 [ZJOI2015]幻想乡战略游戏

动态点分治。

先把点分树构建出来。这道题里点分树有两个作用：

1、可以维护每个点为根时的答案。

2、可以在点分树上爬，找到最优解。

一张图看懂动态点分治的精髓。精髓就在于加上自己的，减去父亲的。

没什么用的性质：1、点分树上一个子树是原树的一个连通块。2、点分树两点LCA一定在原树两点路径上。

注意在点分树上爬的时候比较的不是 x和儿子的值，而是 x和儿子那个连通块离x最近的点的值。如果更优就爬到儿子。

P3246 [HNOI2016]序列

rmq+思维。

预处理 f[r]=\sum_{i=1}^r min\{a[i...r]\} ， g是f的前缀和。

先找到[l,r]的最小值位置p，然后推一下式子就行了。

P4104 [HEOI2014]平衡

整数划分+dp。

状态：f[i][j]表示i划分为j个不同的[1,n]的数的方案数。

转移：f[i][j]=f[i-j][j-1]+f[i-j][j]-f[i-n-1][j-1]

前面是整数划分式子，后面是保证最大值为n。最后枚举左边放几个总和为多少统计答案就行了。

P3250 [HNOI2016]网络

整体二分+树剖。

如果所有\ge mid的路径都经过x，说明答案<mid 。

P3265 [JLOI2015]装备购买

线性基+高斯消元。

排序后逐个加入。实数意义下的线性基就是把异或变成了高斯消元。

P4655[CEOI2017]Building Bridges

斜率优化。

由于查询的斜率和x坐标都不是单调的，所以要维护动态凸包。

用set维护即可，自定义<，查询的时候把<定义成斜率小于就行，维护的时候<定义为x坐标小于。

为了保险起见，把切点附近20个点都枚举一下。

P3967 [TJOI2014]匹配

费用流。

二分图求一定在最大权匹配上的边的个数。枚举删掉每条边，如果最大权匹配变小说明这条边删不得。

CF24D Broken robot

期望dp+高斯消元。

dp方程显然，可是转移有环。考虑高斯消元。

发现个方程最多只涉及三个变量，于是就可以O(n)高斯消元了。

P3172 [CQOI2015]选数

计数+容斥。

首先l=ceil(l/k),r=floor(r/k) ，转化为gcd=1的方案数 。

枚举gcd从[1,r-l+1]，算出区间内有x个倍数，然后f[i]=x^n-x，意思就是只能选倍数，但是不能都选一样的数的方案（防止gcd超过枚举范围。

然后容斥，f[i]-=f[i*k] 。f[1]+(l==1)就是答案。

P4107 [HEOI2015]兔子与樱花

贪心。