令\(\text{nxt}_i\)为\(i\)之后的第一个质数。考虑最后\(a_i\)会变成什么。首先第一种就是直接变为\(\maxa_i\)。其次还发现可能变为\(\operatorname{nxt}_{\maxa_i}\)。对于其他的，可以证明一定不优于这两种，因为其他的情况无非就是在这基础上继续跳\(\operatorname

题目链接：Atcoder或者洛谷先考虑暴力，显然是枚举整棵树的路径，这个枚举复杂度显示是\(O(n^2)\)，还不考虑计算\(f(i,j)\)，考虑使用点分治优化枚举复杂度：\(O(n\log{n})\)。接下来考虑如何计算每条路径的\(f(i,j)\)，注意到\(f(i,j)\)：当且仅当\(a[i]=a[j]\)时，答案加上\(dis(i,j

题目链接:https://www.luogu.com.cn/problem/P4824kmp+栈栈处理字符串问题有一道入门题:https://www.luogu.com.cn/problem/AT_abc328_d实际上处理方式就是用数组模拟栈.在遍历字符串的过程中我们时刻监测,对未达到条件的字符我们进行压栈操作,然后如果说遇到了符合条件的字符

A.绿豆蛙的归宿\(f[x]\)表示从x走到终点经过的路径的期望长度。从\(x\)出发经过\(k\)条边，则有：\[f[x]=\frac{1}{k}\sum_{i=1}^{k}(f[y_i]+z_i)\]由于\(f[N]=0\)，所以从终点出发在反图上跑拓扑排序。点击查看代码#include<bits/stdc++.h>#definekw0usingnamespac

涉及知识点：树、倍增、单调栈题意给你一颗有\(n\(\leq7\times10^5)\)个节点的树，再给你一个长为\(m\(\leq7\times10^5)\)的序列，序列中的值代表树上点的编号，有\(q\)次询问，每次询问取原序列的\(k\(\sumk\leq7\times10^5)\)个子区间并连起来成为一段新的序列，问新的序列

链接：https://www.luogu.com.cn/problem/P1057思路：左手倒右手，建立递推方程建立初始参数：定义dp[j][k]是第k次，以j结尾的方法，就是传k次最后传到j的方法。那么状态转移方程：dp[j][k]=dp[next][k-1]+dp[before][k-1]。其中before是j的前一个元素（j-1）；next是j的后一个元素j+1。同时要注

ABC354E-RemovePairs做题笔记题目链接对于这种带有博弈论的dp，考虑这样设计状态：令\(f_s\in\{1,0\}\)表示“游戏局面”为\(s\)时，先手必胜还是必败。本题中，“游戏局面”可以表示为剩余卡牌的编号集合。又因为本题中\(N\)​很小，通过状压，可以直接用一个int表示游戏

每个点拆成入点和出点。发现每个点、每条边都只能经过一次，所以所有边的容量都是\(1\)。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=405,M=1e5+5;intn,m,s,t,k=1,h[N],vis[N];intto[M],nxt[M],w[M],f[M];intlst[N],flw[N],dis[N];v

@目录题目题意题解思路详解注意事项代码AC记录尾声题目CF527EDataCenterDrama·戳这里题意给定一张$n$个点$m$条边的连通无向图。你需要加尽可能少的边，然后给所有边定向，使得每一个点的出入度都是偶数。边可以是自环，也可以有重边。$n\le10^5$，$m\le2\times1

关于二分图判断是否为二分图左部和右部的点之间不存在连边，即不存在奇环；codes点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+10;intn,m,tot;intto[maxn*2],nxt[maxn*2],w[maxn*2],h[maxn];intcol[maxn],x[maxn],y[maxn],z[maxn];

https://atcoder.jp/contests/abc353/tasks/abc353_e其实就是字典树板子题。似乎遇到最长公共前缀，就该想到字典树。依次加入每个字符串：维护一个数组siz来统计在当前串之前的串在对应点的出现次数。手模一下字典树的建树过程，显然如果当前串\(S_i\)能跑到一个曾经串\(S_

假如将所有激光武器放在一边，所有机器人放在一边，激光武器向它可以伤害的机器人连边，再加超级源/汇点，这就是一个网络流问题。考虑激光武器向机器人连的边容量无限，而机器人向超级汇点连的边容量为机器人的装甲值，而超级源点连向激光武器的边则是用时\(\times\)激光武器伤害。发现假

522-D题目大意给定一个长为\(n\)的序列\(a\)，现有\(q\)个查询，每个查询\(q_i\)给定\(l_i,r_i(1\lel_i,r_i\len)\)，要你找出所有相等元素对\(a_x\)和\(a_y(l_i\lex,y\ler_i)\)中，绝对值\(|x-y|\)的最小值。Solution考虑三个相等的元素\(a_x,a_y,a_z(x<y<z)\)，对于一个

发现实际上就是在求有多少只蜥蜴能逃出来。发现可以将柱子拆成入点和出点两部分，自己的出点向别人的入点连边，自己的入点向自己的出点连边。最后再加一个超级源点\(S\)，连接所有有蜥蜴的柱子入点；再加一个超级汇点\(T\)，连接所有能够跳出地图的柱子。我们猛然发现：这个问题不就是求

2024.4.12【“相遇总是猝不及防、爱意总是野蛮生长”】Sunday三月初四<theme=oi-"search">P1092NOIP2004提高组虫食算//2024.4.12//bywhite_ice#include<bits/stdc++.h>usingnamespacestd;#defineitnintconstintoo=30;chars1[oo],s2[oo],s3[oo];i

邻接表感觉写的很好啊！转载自：数组模拟邻接表-AcWing首先假设我们有n个点(n<=N)，m条边(m<=M)。我们可以想一下对于任意一个结点u,需要记录邻边的哪些信息。这些信息应该包括这条邻边的终点，权重，以及下一条邻边的编号。注意这里不需要记录邻边的起点，因为我们使用的时候都

很容易想到树形dp。考虑在有根树内，每个点都有两种状态：不选自己和父亲的边；要选自己和父亲的边。那么单独对于子树内部而言，就要分两种情况：最多可以向\(d_i\)个孩子连边，对应上述第一种情况，我们称之为\(f_i\)；最多可以向\(d_i-1\)个孩子连边，对应上述第二种情况，我们称之

abc343GCompressStrings思路一眼状压（n只有20）分类讨论如果\(s[i]\)包含了\(s[j]\)，就没有\(s[j]\)什么事了否则考虑\(i\)加到\(j\)后面和反过来的代价就是求\(i+j\)的border上述两个过程都可以KMP解决代码#include<bits/stdc++.h>#

题面核心思想树形DPdp[1]表示以当前节点为根节点所包含的子树且当前节点能染色的最大染色数量dp[0]表示以当前节点为根节点所包含的子树且当前节点不染色的最大染色数量详情看注释~代码importjava.util.*;publicclassMain{publicstaticvoidmain(String[

核心思想Dijkstra+堆优化模板题，每次查询做一次最短路查询即可。classGraph{privateList<int[]>[]nxt;publicGraph(intn,int[][]edges){nxt=newList[n];for(inti=0;i<n;i++){nxt[i]=newArrayList<>();

\(\texttt{ProblemLink}\)简要题意在一个字符串\(s\)中，对于每个后缀，任意删掉一些相邻的相同的字符，使得字符串字典序最小。注意：删掉之后拼起来再出现的相邻相同字符不能够删除。思路倍增好题。发现存在局部最优解（最优子结构），并且可以转移到其它结点，可以考虑使用dp。那就

G-PermutationQuestion找到一个排列\(p\)，使得\(\prod_{i=1}^nlcm(p_i,p_{(imodn)+1})\)最大Solution考虑到\(x\)和\(x-1\)必然是互质的所以顺序排列即可Code#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;for(inti

介绍二叉堆是一种基础数据结构，主要应用于求出一组数据中的最大最小值。C++的STL中的优先队列就是使用二叉堆。堆的性质: 1.堆是一颗完全二叉树;2.堆分为大根堆和小根堆(这里不讨论那些更高级的如:二叉堆，二叉堆，左偏树等等)3.大根堆满足每个节点的键值都小于等

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongstructiid{   intpre,nxt,id,hi;}j[100018];boolcmp(idda,iddb){   returna.hi<b.hi;}intn,t;intpos[100005],ga[100005],gb[100005];intf[25][100005][2];intda[25][100005][2],db[

P4690[Ynoi2016]镜中的昆虫本质就是区间修改，区间数颜色弱化一下，先考虑不带修的情况，也就是P1972[SDOI2009]HH的项链其难点在于区间颜色的去重，需要想一个办法让区间内一个颜色只被数一次我们可以去维护一个\(Nxt\)数组，表示下一个与当前位置颜色相同的位置若当前位