BzhH

###什么是基环树### 简而言之就是一个环上连了几棵树，如图 模板城市环路 结合这道题，既然是基环树，那么首先肯定要先把环找出来，直接搜索就行了 void dfs1(int u, int from){ st[u] = ins[u] = true; for (int i = head[u]; ~i; i = net[i]) { if (i == (from ^ 1)) continue; int v = ver[i]; fu[v] = u; if (!st[v]) dfs1(v, i); else if (ins[v]) { for (int j = u; j != v; j = fu[j])//记录环上的结点 cir[++tot] = j; cir[++tot] = v; } } ins[u ...

P3574 [POI2014]FAR-FarmCraft 贪心+DP 随便猜了一个贪心策略居然就A了,那我就来简单证明一下这个贪心策略 令 fif_ifi​ 表示以 iii 为根的子树内,从 iii 出发开始安装电脑所需的最长时间, tit_iti​ 表示遍历完整棵子树所需的时间 按照 fi−tif_i-t_ifi​−ti​ 从大到小排序然后转移,答案即为最优的 证明 对于当前子树 uuu, 以及它的三个儿子 v1,v2v_1,v_2v1​,v2​ 假设 fv1−tv1>fv2−tv2⇒fv1+tv2>fv2+tv1f_{v_1}-t_{v_1} > f_{v_2}-t_{v_2} \Rightarrow f_{v_1}+t_{v_2}>f_{v_2}+t{v_1}fv1​​−tv1​​>fv2​​−tv2​​⇒fv1​​+tv2​​>fv2​​+tv1​,遍历完之前的儿子结点所用的时间为 sumsumsum 若先遍历 v1v_1v1​,那么两次遍历的答案为 sum+fv1,sum+t1+fv2sum+f_{v_1},sum+t_1+f_{v_2}s ...

P6563 [SBCOI2020] 一直在你身旁 一道非常值得做的单调队列优化DP，刚开始看到这道题目一直想着二分，愣是没有看出是个DP，后来仔细想了下，可以轻易的写出 O(n3)O(n^3)O(n3) 的暴力. 定义 fi,jf_{i,j}fi,j​ 表示确定区间 [i,j][i,j][i,j] 内的数字所需的最小花费,得出转移方程 fi,j=min⁡(max⁡l≤k<r(fl,k,fk+1,r)+ak)f_{i,j}=\min(\max_{l\le k < r}(f_{l,k},f_{k+1,r})+a_k) fi,j​=min(l≤k<rmax​(fl,k​,fk+1,r​)+ak​) 显然是个区间DP 通过标签观察式子有点类似 fk+akf_k+a_kfk​+ak​ 的形式,似乎可以优化,首先不好直接对这个式子下手,可以分类讨论一下,把其中的 max⁡\maxmax 去掉 仔细思考一下,可以发现 fi,j≤fi,j+1,fi,j≥fi+1,jf_{i,j}\le f_{i,j+1}, f_{i,j} \ge f_{i+1,j}fi,j​≤fi,j+1​,fi, ...

一道毒瘤树型DP,主要是因为要用高精. 首先定义状态 fi,jf_{i,j}fi,j​ 表示以 iii 为根的子树,连通块大小为 jjj,那么这个状态记录的是什么? 它表示除去 iii 所在的连通块的贡献答案的最大值,只需要在最后统计答案的时候再加回去. 那么可以得到状态转移方程 fu,j=max⁡v∈u,1≤k≤j1≤j≤size(u)(fu,k+fv,j−k)f_{u,j}=\max_{v \in u,1 \le k \le j}^{1\le j\le size(u)}(f_{u,k}+f_{v,j-k}) fu,j​=v∈u,1≤k≤jmax1≤j≤size(u)​(fu,k​+fv,j−k​) fu,0=max⁡1≤j≤size(u)fu,j×jf_{u,0}=\max_{1 \le j \le size(u)}f_{u,j}\times j fu,0​=1≤j≤size(u)max​fu,j​×j 然后再加上一个高精就行了 部分代码 void dfs(int u, int fa){ siz[u] = 1, f[u][0] = f[u][1] = 1; f ...

一道比较难想的DP 可以想到，每个面额的钞票之间是可以独立计算的 那么就可以对于每一种面额的钞票单独考虑，接下来就是状态的定义了 有一种比较好想的状态就是定义 fi,x,y,zf_{i,x,y,z}fi,x,y,z​ 表示前 iii 种钞票, 每个人分别有多少钱,但很明显会超空间. 仔细观察可以发现,钞票的总面额是不变的,那么状态就可以优化掉一维,只需要表示出两个人所有的面额就可以计算出第三个人 然后状态的转移就比较简单了,直接枚举钞票的数量就行了 代码 #include<iostream>#include<cstring>#include<cstdio>#define INF 0x3f3f3f3fusing namespace std;int f[7][1005][1005];int x1, x2, x3, sum;int n[4][7], s[4], cnt[7];int val[7] = {0, 100, 50, 20, 10, 5, 1};int main(){ scanf("%d%d%d&quo ...

###反演 首先讲一下什么是反演，定义两个序列 ∣F(n)∣,∣f(n)∣|F(n)|,|f(n)|∣F(n)∣,∣f(n)∣,Fi=α(i)f(i)F_i=\alpha(i)f(i)Fi​=α(i)f(i),表示|F(n)|与|f(n)|之间满足某种关系, 我们需要求得 ∣f(n)∣|f(n)|∣f(n)∣,那么就可以通过反演公式求得 f(i)=β(i)F(i)f(i)=\beta(i)F(i)f(i)=β(i)F(i). ###莫比乌斯反演 首先引入个函数, 莫比乌斯函数,记作 μ(x)\mu(x)μ(x),令 x=p1a1p2a2...pkakx=p_1^{a_1}p_2^{a_2}...p_k^{a_k}x=p1a1​​p2a2​​...pkak​​,该函数有三种取值 μ={0,ai≥21,kmod  2=0−1,kmod  2≠0\mu=\begin{cases}0,a_i \ge 2\\1,k \mod 2 = 0\\-1,k \mod 2 \ne 0\end{cases} μ=⎩⎨⎧​0,ai​≥21,kmod2=0−1,kmod2=0​ 令 S(x)=∑i∣xxμ(i ...

P2664 树上游戏 一道很好的点分治练手题，虽然对于初学者可能难了点。题解里的神仙解法看得我一脸懵逼 乍一看题目，似乎是跟树上路径有关，可以用点分治，其实我是学了点分治然后来做的这道题。 对于每一个分治中心，有两种情况 子树中的点对当前的这个点的影响 经过该点的路径对其他子树中的点的影响 对于第一种情况，很好求， 我们用 cnticnt_icnti​ 表示路径中包含颜色 iii 的路径数量, SumSumSum 表示所有颜色的路径数量和, cic_ici​ 表示每个点的数量, sizisiz_isizi​ 表示以 iii 为根的子树大小 那么对当前这个点 iii 答案的贡献就是 Sum−cntci+siziSum-cnt_{c_i}+siz_{i}Sum−cntci​​+sizi​, 减去一个 cntcicnt_{c_i}cntci​​ 是为了去掉重复计算的. 对于第二种情况就比较麻烦了 我们在计算的时候不考虑子树内部对答案的贡献,之考虑其他子树对当前子树内的点的答案贡献,所以在我们求出来的 cnt,Sumcnt, Sumcnt,Sum 中把当前子树的贡献先删掉 然后 dfsdfsd ...

P3714 [BJOI2017]树的难题 首先吐槽一下自己刚开始理解错题意了，以为题目中的按顺序可以按任意顺序. 这道题是一道关于树上路径的问题，很明显可以想到点分治，考虑当前的分治中心为 xxx. 那么答案可以分为下面四种情况 1.序列一端为 xxx, 另一端在子树内. 2.序列两端在两个不同的子树内,且两个子树到分治中心的颜色相同 3.序列两端在两个不同的子树内,且两个子树到分治中心的颜色不同 4.序列两端在一个子树内 对于第4种情况,很好解决,直接递归就行,第1种情况也是,重点是第2种和第3种. 因为我们需要将所有可能的情况都存起来,所以考虑用线段树, xxx 的所有儿子按边的颜色排序,然后再来枚举, 那么就只需要开两棵线段树了,一棵存了之前的有儿子,一棵只存了当前颜色的儿子,在 dfsdfsdfs 的时候分别查询一下就是了, 只需要在查询存的是当前颜色的儿子时需要减去一个 valvalval. 代码 #include<iostream>#include<cstdio>#include<queue>#define INF (0x3f3f3f3f ...

###欧拉定理 ∀ a,m∈Z+\forall~a,m \in Z^+∀ a,m∈Z+,若gcd⁡(a,m)=1\gcd(a,m)=1gcd(a,m)=1,则aϕ(m)≡1(mod m)a^{\phi(m)} \equiv 1(mod~m)aϕ(m)≡1(mod m) 假设这ϕ(m)\phi(m)ϕ(m)个数为X1,X2,...,Xϕ(m)X_1,X_2,...,X_{\phi(m)}X1​,X2​,...,Xϕ(m)​ 引理1 XiX_iXi​两两模mmm不同余 证明 ∀1≤i,j≤ϕ(m)\forall 1\le i,j \le \phi(m)∀1≤i,j≤ϕ(m)且i≠ji \ne ji=j,那么 Xi mod m=Xi≠Xj=Xj mod mX_i~mod~m = X_i \ne X_j = X_j~mod~m Xi​ mod m=Xi​=Xj​=Xj​ mod m Xi≢Xj(mod m)X_i \not\equiv X_j (mod~m) Xi​≡Xj​(mod m) 证毕 设 pi=a×Xip_i=a\times X_ipi​=a×Xi​ 引理2 pip_ipi​ ...

一道比较裸的扩欧模板题 扩展欧拉定理 ac={ac mod‘ϕ(p),gcd(a,p)=1ac,gcd(a,p)≠1,c<ϕ(p)ac mod ϕ(p)+ϕ(p),gcd(a,p)=1,c≥ϕ(p)a^c=\begin{cases}a^{c~mod`\phi(p)},gcd(a,p)=1\\a^c,gcd(a,p) \ne1,c < \phi(p)\\a^{c~mod~\phi(p)+\phi(p)},gcd(a,p)=1,c\ge \phi(p)\end{cases} ac=⎩⎨⎧​ac mod‘ϕ(p),gcd(a,p)=1ac,gcd(a,p)=1,c<ϕ(p)ac mod ϕ(p)+ϕ(p),gcd(a,p)=1,c≥ϕ(p)​ 具体证明就不再这里讲解了主要是不会 很明显,可以直接用欧拉定理递归降幂,那么怎么保证时间复杂度是对的呢 我们将m分解为 ∏i=1kpiqi\prod\limits_{i=1}^k p_i^{q_i}i=1∏k​piqi​​ 那么 ϕ(m)=ϕ(∏i=1kpiqi)=∏i=1k(pi−1)piqi−1\phi(m)=\phi(\pro ...