简要思路 & 短篇题解 集锦

P4178 Tree/252. 树

给定一棵带边权的树((napprox10^4)),求长度不超过 (k)路径有多少条。

点分治模板题

定根 (rt),树上的路径只有两种情况:

  • 经过或端点是 (rt)

  • 只在 (rt) 的子树内。

对于第一类,DFS 整棵树,求出每一个点到根的距离,容斥即可,(O(nlog n))瓶颈在排序

处理完第一类路径后可以在子树里递归求解

那不铁定超时吗?不然。

我们每次选择重心定根即可,由于这样子问题规模都减半,总时间 (O(nlog^2n))

P4381 [IOI2008] Island/358. 岛屿

题意转化:给定带边权的基环树森林(nleqslant10^6)),求每一棵基环树的最长链的长度之和。

考虑单个基环树,最长链只有如下两种情况:

  • 在去掉基环的边后的森林中,(O(n)) 树形 DP 求直径取最大值即可。

  • 经过基环。

对于第二种情况,记录每一个基环 (C) 上的点 (x),存所在子树中离她最远的点的距离 (f_x),则答案为(设基环上的点顺时针编号依次为 (1,2,dots,|C|)):

[ans=maxlimits_{i<j}(f_i+f_j+dis_i-dis_j+len,f_i+f_j+dis_j-dis_i) ]

其中 (dis_x) 表示环上 (1to 2todotsto x) 的距离,(len) 表示环长。

(g_x=f_x+dis_x,h_x=f_x-dis_x),则:

[ans=maxlimits_{i<j}(g_i+h_j+len,h_i+g_j) ]

(O(V(C))) 即可,最终 (O(n))

377. 泥泞的区域

将每一个行极大泥泞块和列泥泞块看作点,单个泥泞 block 看作所在两个极大泥泞块之间的边,题目要求的最小木板数就是这个二分图的最小覆盖,即最大匹配(O(N^4))匈牙利算法 (O(Vtimes E))),以下为二分图最大匹配模板代码

点击查看模板代码
//...head bool vis[MAXN];//visited int ma[MAXN];//女生匹配的男生,无对象则为 0  vector<int> e[MAXN];//graph  bool dfs(int rt){//帅哥 rt 找对象  	for(int i:e[rt]){ 		if(vis[i]) continue;//试过了  		vis[i]=1;//约会  		if(ma[i]==0 || dfs(ma[i])){//女生小 i 本来就没有对象或者把对象绿了  			ma[i]=rt; return true;//match  		} 	} 	return false;//男生 rt 为单身狗  } signed main(){ 	//...input 	//...init 	int ans=0; 	memset(ma,0,sizeof ma); 	For(i,1,men){//遍历男生 		memset(vis,0,sizeof vis);//清除约会记忆  		if(dfs(i)) ans++;//世上又多了一对  	} 	cout<<ans<<endl;     return 0; } 

348. 沙漠之王

最优比率生成树模板。

用 0/1 规划,假设答案为 (x),设所有边 ((i,j)) 的边权为 (cost(i,j)-xtimes dis(i,j)),用 Prim 判断最小生成树总长是否小于 (0) 二分即可。

注意这里为实数二分,我用的固定二分次数

arc132_d

转化好题。

给定两个 (01)(s,t),两串 (0) 的个数都为 (n)(1) 的个数都为 (m)。两个等长的 (01) 串之间的距离 (d(a,b)) 定义为最小的邻项交换次数使得 (s,t) 可以互相变换。一个 (01) 串的价值 (v(a)) 为相邻两项值相同的个数((e.g. s=mathtt{00111},v(s)=3,t=mathtt{01010},v(t)=0))。求:

[minlimits_{d(s,x)+d(x,t)=d(s,t)}v(x) ]

发现 (0,1) 分别的个数不随操作而改变,联想到(我考场上没想到)(binom{n+m}{n}) 和平面中从 ((0,0)) 走到 ((n,m)) 的方案。

是的,我们(01) 串转化成一条 ((0,0)to(n,m)) 的折线

结论:(d(s,x)+d(x,t)=d(s,t)iff) 表示成路径后 (x) (被夹)在 (s,t) 的路径之间。

证明看官方题解,不再赘述。

于是有了贪心策略:

  1. 枚举 (x) 的起始方向(上或右)(即字符串的第一位 (0/1))。

  2. 贪心地直走,“碰壁”转弯。

  3. 更新答案。

我们可以通过证明有不“碰壁”转弯的 (x) 路径,一定有转弯次数不比她少的 (x') 不“碰壁”转弯出现在其之后,来证明贪心是对的(证明看官方题解 qwq)。

官方题解

P4180 [BJWC2010]严格次小生成树

结论:必有一个严格次小生成树与最小生成树的对称差的边数为 (2)

先用 Kruscal 求出最小生成树,再枚举每一条非树边,加入树边,再在树边中删掉一条使得仍然是树,计算答案

然而这样是 TLE 的,我们考虑维护枚举的非树边两端在树上的路径中边权的最大值、严格次大值(因为题目要求严格次小生成树,所以要存严格次大),在之中断掉一条边使得新的树严格次于最小生成树,再在这些答案中取 (min) 即可

路径中边权的最大值、严格次大值可以用树上倍增 (O(log n)) 实现,总时间 (O(nlog n))

202. 最幸运的数字

题意:求最小的正整数 (N) 使得 (L | dfrac{8}{9}(10^N-1)),不存在则输出 (0)

变形:

[dfrac{9L}{gcd(8,L)} | 10^N-1 ]

(M=dfrac{9L}{gcd(8,L)}),则:

[10^Nequiv 1pmod{M} ]

如果 (gcd(10,M)>1),则必然无解,输出 (N=0)

否则,由欧拉定理得到:

[10^{k}equiv 1pmod{M}implies k|varphi(N) ]

我们用 (O(sqrt{n})) 计算 (varphi(N))(O(sqrt{varphi(N)})) 枚举其因数(O(log varphi(N))) 快速幂判断是否合法,总时间 (O(sqrt{n}+sqrt{varphi(N)}log varphi(N)))

由于快速幂中模数最大 (10^{10}) 级别,所以不要忘了龟速乘!不要忘了龟速乘!不要忘了龟速乘!

CF1606F Tree Queries

根号算法万岁!

答案一定非负,那么对于一个 (k)(m) 上界是 (dfrac{n}{k}) 的,于是我们考虑根号分治。

考虑当 (k<sqrt{n}) 时,我们直接进行树上 DP,设 (f_{i,j}) 表示 (i) 的子树里当 (k=j) 时的答案,那么转移的时候我们直接考虑当前子节点删不删,这样这部分复杂度就是 (O(nsqrt{n})) 的。

然后考虑当 (kgeqslantsqrt{n}) 的时候,一定有 (mleqslant sqrt{n}),这样的话考虑树形背包,记 (g_{i, j}) 表示 (i) 子树里删 (j) 个点的最大儿子数,这样进行树形背包,考虑每个儿子删不删,由于树形背包的复杂度是 (O(nm)) 的,所以这部分复杂度就是 (O(nsqrt{n}))

不过如果直接这么做空间会萎,于是你把询问离线下来,分成两部分做就不会 MLE 了。

219. 剪纸游戏

模板博弈 SG 函数

对于一个状态:

  • 若分情况(即一场游戏走一条路),则为 (operatorname{mex})

  • 若分子游戏(即所有路一起走),则为 (operatorname{xor})

int f[N][N];//记忆化 int sg(int x,int y){ 	if(f[x][y]!=-1) return f[x][y]; 	unordered_set<int> S; 	For(i,2,x-2) S.insert(sg(i,y)^sg(x-i,y)); 	For(i,2,y-2) S.insert(sg(x,i)^sg(x,y-i)); 	int pos=0; 	while(S.find(pos)!=S.end()) pos++; 	return f[x][y]=f[y][x]=pos; } 

CF1280D Miss Punyverse

显然先将 (w-b) 作为点权,题意即为将这棵树划分为 (m) 个连通块,最大化点权和为正数的连通块个数

想到树形背包,状态 (f_{i,j}) 表示以 (i) 为根的子树分成了 (j+1) 块,点权和为正数的连通块个数的最大值

但是这样转移不了,再定义一个 (g_{i,j}) 表示 (i) 为根的子树中分成了 (j+1) 块,点 (i) 所在的连通块的点权和的最大值

特殊地,(g_{i,j}=0) 可以表示不将根节点 (i) 的连通块与祖先连通,即闭关锁国,此时一共分成 (j) 块而不是 (j+1)

转移见代码

转移后再更新一下:是否从开放至闭关能获得更大结果,即可。

P1600 [NOIP2016 提高组] 天天爱跑步

小小紫题,耗我两天 qwq。

“LCA+桶+树上差分”

发现我们要处理树上的路径,必定要求 LCA,用倍增即可

如果一个观察员 (P) 能够准时看到 (sto t) 路线上的人在跑步,则满足任一

  1. (W(P)+deep(P)=deep(s)land Pin anc(s)land Pnotin anc(lca(s,t)))

  2. (W(P)-deep(P)=dis(s,t)-deep(t)land Pin anc(t)land Pnotin anc(lca(s,t)))

发现两部分的处理方式类似,我们着重讲第 (1) 种。

可以做树上差分。

将树建 DFS 序(每个点只有第一次才到 DFS 序里),将路径拆成底端加,顶端的 (fa) 减的差分形式,这样可以用桶扫一遍 DFS 序,每到一个点就相应的修改,用前缀和相减的方式即可求出 (P) 为根的子树内的操作的集合,(P) 的答案即为桶中下标为 (W(P)+deep(P)) 的值。

Code

P1054 [NOIP2005 提高组] 等价表达式

我写了两天 qwq。

题目就是求与给出的代数式恒等的有哪些(变量只有 (a))。

想到评测机对提交者代码的做法,想到:

我们可以多代入一些 (a) 的值来 check 两个代数式的值是否相同。

接下来就是计算一个无变量的式子了,但在实操中发现对于负号 "-" 的特判极其难弄:

  • 不能以负号分裂求解 (e.g. 1-2+3not=1-(2+3))

  • 要将负号提出幂次不至于正负颠倒 (e.g. -3^4not=(-3)^4)

  • (dots)

我突发奇想:是否将 string 中的所有 "-" 替换成 "+b*"(如果在最左端改成 "b*")即可算出同样的效果?((b=-1)

答案是肯定的。

原因是负号的优先级与乘号相同……

这样做即可,细节看代码。

Code

P5110 块速递推

先计算得到通项公式

[f_n=a(b^n-c^n)% mod ]

其中

[a=233230706,b=94153035,c=905847205,mod=10^9+7 ]

发现 (O(Tlog N))(T=5times 10^7,N=1.8times 10^{19}) 的数据下根本过不了。

优化:

由于 (x^yequiv x^{y%(mod-1)}pmod{mod}),将 (N) 降到 (10^9) 级别。

于是瞟一眼题目“块速递推”,想到分块加速幂运算

(n=xB+yquad(B=65536land x,y<B)),以 (b) 为例,预处理出 (b^{kB})(b^kquad(0<k<B)) 即可 (O(1))(b^n=b^{xB}times b^{y})

时间 (O(T))

P1471 方差

建线段树,每个节点存区间的和及平方和。

[avg=dfrac{sum}{len},s^2=dfrac{lentimes sos-sum^2}{len^2} ]

区间修改,区间询问 打懒标记即可。

arc131_d

我可能永远不会猜结论 qwq

结论零

标枪的位置只取整数即可。

结论一

相邻的两个标枪一定相距正好 (D)

结论二

(x=leftlceildfrac{n+1}{2}rightrceil) 个标枪一定在 ([0,D]) 位置范围内。

于是有了想法:

(a_iquad (0leqslant ileqslant D)) 表示 (x-1) 个标枪分别插在 (i,i+D,i+2D,dots,i+(x-2)D) 的位置时的分数。

(b_iquad (0leqslant ileqslant D)) 表示 (n-x+1) 个标枪分别插在 (i,i+D,i+2D,dots,i+(n-x)D) 的位置时的分数。

最终答案即为 (maxlimits_{i=0}^D(a_i+b_{D-i}))

问题就在于如何求 ({a},{b})

以下以 ({a}) 为例。

考虑每一段相同分值的区间,计算每一个 (i),这段对于 (a_i) 的贡献,发现这些贡献只有可能为 (y)(y+1)(即相差不过 (1),这算结论三吧 qwq),而且贡献为 (y+1) 的只是连续的一段(特别地,当同余类里包含了 (0),要分成前后两段),用差分数组维护即可。

时间复杂度:(O(m+D))

P2375 [NOI2014] 动物园

对于字符串 (S)(长度为 (nleqslant 10^6))的前 (i) 个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作 (num_i),求 ({num})

KMP 求 (nxt) 数组,倍增跳即可。

时间 (O(Tnlog n),Tleqslant 5),极其卡常,过不了。

但是,将倍增数组的两维交换(即代表 (2^k) 那一维放前面),这样数组指针只会单次增减 (O(1)),实测能基本快一倍,能过。

P2486 [SDOI2011]染色

树剖,线段树维护区间连续颜色块数量和两端颜色。

P7950 [✗✓OI R1] 后方之水

通过生成函数计算得答案为:

[binom{S+1}{n+1}binom{n}{2} ]

(O(n)) 计算即可。

P1450 [HAOI2008]硬币购物

先作完全背包,再用容斥原理减掉多算的。

P7883 平面最近点对(加强加强版)

期望 (O(n)) 的算法:

先将点 (rand_shuffle) 一下,保证随机,维护前缀点集的答案。

记前 (i) 个点的答案为 (d_i)

我们将全平面划分为边长为 (d_i) 的正方形网格。将前 (i) 个点丢到网格里,可以发现每个正方形中最多只有 (3) 个点。

对于新加入的第 (i+1) 个点,只需检查它所属的正方形周围 (9) 个正方形中的所有备选点。

如果 (d_{i+1}ne d_i),则需要 (O(i)) 重构整个网格。但由于第 (i) 个点只有 (frac{1}{i}) 的概率更新答案,故总复杂度仍为 (O(n))

需要使用哈希表存储每个方格中的点。

AcWing326

将二进制的每一位分开考虑期望。

(f_x) 表示 (xto n) 随机路径边权异或和的当前二进制位的期望(即为 (1) 的概率)。

[f_x=dfrac{1}{deg_x}sum_{yin N(x)}(f_y[val(x,y)=0]+(1-f_y)[val(x,y)=1]) ]

其中 (N(x))(x) 的开领域,(val(x,y))((x,y)) 这条边当前二进制位的权值。

由于该式子有后效性,用高斯消元即可。

总共 (O(32n^3))

P4054

注意到值域只有 (100),可以作 (100) 个数据结构来二维单点修改,矩阵查询。

而且 (ntimes m) 很小(否则就要用树套树或 CDQ 分治了 qwq),直接二维树状数组(本蒟蒻初学)维护每一种值即可。

时间 (O(100nmlog(nm)))

P4396

经典莫队的变形。

sol 1:

莫队区间移动时实时维护一个数组表示某个值在区间内出现的次数和是否出现。

再用树状数组维护它。

最终复杂度 (O(nsqrt{m}log n+mlog n))

跑得慢,不知道能不能过。

sol 2:

在 sol 1 的基础上将树状数组换成分块维护,实现 (O(1)) 修改,(O(sqrt{n})) 查询。

最终复杂度 (O(nsqrt{m}+msqrt{n})),能过。

P3863

将区间修改和单点查询离线下来。

扫描线按序列 (1to n) 顺序扫描。

如果碰到修改的左端点,则扫描线上该时刻及以后的时刻加上对应的值。

如果碰到修改的右端点,则扫描线上该时刻及以后的时刻减去对应的值。

如果碰到一个询问,则求扫描线上该时刻以前的时刻中询问值的 rank。

扫描线上用分块即可。

P2163

二维静态数点模板题

先对 (y) 坐标进行离散化。

对于每一个矩形询问,拆分成四个二维前缀和询问。

从左往右扫,维护一个树状数组存目前扫过的各个 (y) 上的点的个数。

当扫到一个二维前缀和询问 ((x,y))(x) 时求树状数组中 (pre(y)) 的值即为该询问的答案。

(x,y) 两维都离散化了的屑程序

CF1582G

维护一个序列 (L_i) 表示第 (i) 位为右端点的子串的最大左端点下标,可对每个素数用 vector 存当前还有哪些位置上的数是该素数的倍数且没有被抵消,一边更新一边扫当前 (a_i) 的素因数求出 (L_i)

再对 (L_i) 开线段树,每次将 (query(i,i)quad(1leqslant ileqslant n)) 累加得到答案。

(query(x,y)) 表示 (L_xto L_n) 中最长前缀使得所有该前缀中的 (L_i) 均不小于 (y),该前缀的长度。

P2633

比 P3302 少了 Link 操作,稍加修改 P3302 的代码即可。

P3302

对每个点存该点到根节点的所有点权的可持久化值域线段树(点权离散化后)。

Link 时启发式合并。

Query 时四个值域线段树相加减搜索第 (k) 小即可。

P1972

对每个位置 (x) 存前一个颜色相同的位置 (pre_x)

顺序遍历数组,当前为 (a_x),维护树状数组,每次 (add(x,1)) 并且 (add(pre_x,-1))

当遍历到了某一个询问 ([l_i,r_i]) 的右端点 (r_i)(ans)(sum(r_i)-sum(l_i-1))

CF1446D2

猜结论:子串长度取最大值时其中一个众数必为全局众数。

根号分治即可,其中之一用尺取法。

巨佬的题解

P4592

对于 1 操作,用 DFS 序+可持久化 01trie 维护。

对于 2 操作,可持久化 01trie 维护到根节点的所有值。

P3834

离散化后维护数组的前缀值域可持久化线段树,每次按照对应的子树大小之差二分查找。

[O((n+q)log n) ]

P7447

值域倍增分块。

奆佬的题解

CF438D

考虑 (x%p) 的情况:

[begin{cases}x%p=x ,x<p\x%pleqslantdfrac{x}{2} ,xgeqslant pend{cases} ]

所以一个数的有意义取模((x%pne x))最多进行 (log x) 次。

线段树暴力(无懒标记)解决即可。

P4198

斜率预处理+线段树 (O(mlog^2n)) 维护(单点修改后每层 (push_up)(O(log n)) 递归求解)。

CF1583E

先按度的奇偶来判断,奇点个数 (cnt>2) 则 NO 并输出 (frac{cnt}{2})

否则建原图的任意生成树,求 (q) 组两点间路径记录途径点即可。

P2709

莫队模板

CF1598E

二维数组斜着开 set 记录位置,每次 upd 计算差值

推荐这些技术文章:

简要思路 & 短篇题解 集锦

AT3955 [AGC023D] Go Home/agc023_d
小粉兔的 Sol
P2150 [NOI2015] 寿司晚宴
给定 \(\sum=\{2,3,\dots,n\}(n\le 500)\),求有几种方案取两个子集 \(S,T\),使得 \(\forall x\in S,y\in T,\gcd(x,y)=1\)。
发现 \(n\le 30\) 时可以用状压 DP,其实 \(n\le...

CF587F&CF547E口胡

这两道题好像啊
贡献一种使用SAM和ACAM草两道题的方法
下面假装有 \(O(\sum |S|=m)=O(n)\)。
你看看,这CF换过多少个出题人啦?换汤不换药啦!其实这两道题是同一个人出的
CF587F
根号分治。把长度大于 \(B\) 的串全部拿出来,有 \(\frac{m}{B}\) 个串。
然后对于这些串,每个串建一个 SAM,然后把 \(n\) 个串全部丢进来匹配。只需要对 SAM...

走迷宫 简要题解

走迷宫 简要题解
题面
走迷宫,带起点终点 .
有传送门,传送门个数不超过 \(26\) 个 .
做法
BFS
不会 .
显式建图
我们可以考虑把每个点能到的点连边 .
二维压到一维,常见 Trick .
于是我们有一个很显然的想法:点到传送门连 \(0\) 权值的边 .
但是这样是错的,因为我们经过传送门必须得进去 .
e.g.

红色是边,蓝色是最短路 .
于是如果一个点能到传送门,我们就直...

ABC245 简要题解

A
由题意模拟。
int a,b,c,d;
signed main(){
a=read(),b=read(),c=read(),d=read();
if(a<c||(a==c&&b<=d)) puts("Takahashi");
else puts("Aoki");
return 0;
}

B
由题意模拟。
int n,a[2005];
signed ma...

ARC135 简要题解

链接
D
首先,能操作的位置有 \((n - 1)(m - 1)\) 个,同时我们知道左上角 \((n - 1)(m - 1)\) 个格子可以取到任意值,因此这个问题的解域就是一个 \((n - 1)(m - 1)\) 个变元的线性空间,理论上可以找到 \(n + m - 1\) 条线性无关的恒等式。
仔细观察可以发现,每次操作同一行或同一列要么没有一个格子被操作,否则被操作的两个格子必定相邻也...

GDOI2021简要题解

GDOI2021游记
\(Day\ 1\)
\(T1\)
考虑修改一定是前缀和后缀,枚举修改的前缀,后缀指针移动取最优即可。
需要预处理一下前缀\(min,max\)和后缀\(min,max\)。
\(T2\)
差分约束,爬了。
发现限制不等式每个都有四个变量,考虑是否可以分成行和列。
我们考虑是否对于每个位置\(a[i][j]\)用行和列来差分约束得到答案。
考虑只修改第一行第一列上的数,考虑...

NOIP 2016 简要题解

D1T1
直接根据题意模拟即可。
代码
D1T2
咕咕咕。
D1T3
记 \(dp_{i,j,0/1}\) 表示前 \(i\) 个课,选了 \(j\) 个课,第 \(i\) 个课换不换的最小期望。
floyd 预处理两点之间的最短路,转移显然。
代码
D2T1
数据范围很小,考虑 \(\mathcal O(n^2)\) 求出组合数。
求个二维前缀和就做完了。
代码
D2T2
发现切完之后其他蚯蚓...

CQOI 2018 简要题解

\(\text{}\)
  冬眠营自闭了,于是划水更一个比较水的省选题解。
Luogu4454 [CQOI2018]破解D-H协议

点此看题:P4454 [CQOI2018]破解D-H协议 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  BSGS 裸题。
Luogu4455 [CQOI2018]社交网络

点此看题:P4455 [CQOI2018]社交网络 - 洛谷 |...

洛谷P6754题解

本文同步更新于洛谷博客
题目描述
给定 \(a,b\),求区间 \([a,b]\) 中有多少个不含长度大于一的回文子串的数字串。
题解
还是比较套路的数位 dp。我们传五个参数 \(k,x,y,p,q\) 进入 dfs,分别表示枚举到第 \(k\) 位,前两位为 \(x\),前一位为 \(y\),是否为前导 \(0\),以及这一位填的数有没有限制,用 \(f\) 数组记忆化即可。
下面来简要说明...

前缀和(简单)

前缀和

#include<iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],s[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;...

文章标题:简要思路 & 短篇题解 集锦
文章链接:https://www.dianjilingqu.com/3640.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>