DAY 2 下午

拼搏现实的明天。 2021-11-02 01:10 262阅读 0赞

bzoj3209

设 sum(i) 表示 i 的二进制表示中 1 的个数。给出一个正整数 N ，花神要问你Π(Sum(i)),也就是 sum(1)—sum(N) 的乘积。答案对一个质数取模。

对于 100% 的数据，N≤10^15

虽然输入的10进制数，但是本质有影响的是二进制形态

怎么来转换一下，求1~n中每个数的一的个数总相乘之积，首先感觉到，**每个数都会有唯一对应的1的个数**，且一的个数的取值不到60，因为n最大 10^15, 那么我就想，如果**枚举1的个数k，计算有多少个数含有k个1**，（因为数位dp就是来做，有多少满足的数，且不关注数的大小）这样就转化为数位dp的模型了。另外，发现含有k个1的数个数可能非常多，快速幂搞一搞啦。

这题的关键就是发现一的个数的情况比较少可以枚举再转化为另一种情况计算其实，这题本质就是转化一下，注意在模型难以建立的情况下，通过转化，可以将题目简化，

f\[i\]\[j\]表示前i个填了j个1的方案

dfs(0,j,limit)

bzoj4521: \[Cqoi2016\]手机号码 ◦数字L到R中有多少个数字满足以下两个条件。

1：要出现至少3个相邻的相同数字

2：号码中不能同时出现8和4。

10^10 < = L < = R < 10^11

f\[i\]\[j\]\[0/1\]\[0/1\]\[0/1\]\[0/1\]表示第i位，上一位是j，是否有三个连续的，上一个是否和上上个相同，是否有4，是否有8

10进制数位dp的基本最简单的形式。

记忆化搜索处理数位dp的代码实现，数位dp一般都用记忆化搜索来做。

考察思维的数位dp往往会和其他如枚举算法结合，或作为原问题的子问题。

除了十进制，二进制的数位dp也是常见的，此外K进制的也是可以的。

1：与树或图的生成树相关的动态规划。

2：以每棵子树为子结构，在父亲节点合并，注意树具有天然的子结构。 这是很优美的很利于dp的。

3：巧妙利用Bfs或Dfs序，可以优化问题，或得到好的解决方法。

4：可以与树上的数据结构相结合。

5：树形Dp的时间复杂度要认真计算，部分问题可以均摊复杂度分析。

6：一般设f\[u\]表示u子树的最优价值或者是说方案数。

或者f\[u\]\[k\]表示u子树附加信息为k的最优值，往往是通过考虑子树根节点 的情况进行转移。

7：树形dp，在树结构上，求最优值，求方案等dp问题，就可以考虑是树 形dp。

当然也有可能是点分治或者是分析性质的贪心题。但是树形dp绝对是一个很好的思考方向。

树形DP

树上最大独立集

给你一棵大小为n的树，求这棵树的最大独立集是多少。

最大独立集指的是一个最大的点集使得其中的点两两没有边相连。

N<=100000

dp\[i\]\[0/1\]表示做完了i的子树，i点是否选的最大独立集，即可直接转移。

![1605984-20190807190312607-652612520.png][]

int dfs(int u,int f)
    {
        dp[u][1]=1;
        for(int i=head[u];i;i=edg[i].nxt)
        {
            if(edg[i].to!=f)
            {
                dfs(edg[i].to,u);
                dp[u][1]+=dp[edg[i].to][0];
                dp[u][0]+=max(dp[edg[i].to][0],dp[edg[i].to][1]);
            }
        }
    }

树的直径

给你一颗点数为n的树，让你求这棵树的直径是多少，也就是求最长的两个点之间的距离。

N<=100000

Bfs做法：随便找一个点bfs求它的最远点，设为x，再从x跑一遍bfs，求x最远点y，则(x,y)就是一个直径了。

树形dp做法：设f\[i\]表示i这个点到子树里面的最远点是多远的，然后对于每一个点u 求出以这个点为根的最远路径距离，直接找\{f\[son\_i\]+edge\_i\}的前两大值加起来即可。然后再在每一个点构成的答案里面取最大值就是全局的最优值了。

void dfs(int u,int f)
    {
        fa[u]=f;
        int mx=0;
        for(int v,i=head[u];i;i=edg[i].nxt)
        {
            if((v=edg[i].to)!=fa[u])
            {
                dfs(v,u);
                ans=max(ans,mx+edg[i].dis+f[v]);
                f[u]=max(f[u],f[v]+edg[i].dis);
                mx=max(mx,f[v]+edg[i].dis);
            }
        }
    }

1：一棵无向树，结点为n(<=10,000)，删除哪些结点可以使得新图中每一棵树结点数小于等于n/2。也就是求重心。

2：树的覆盖集，求最少选几个点能覆盖所有边，也就是不存在一条边两边点都没被选。（本质？）

3：最大权独立集？

其实是一样的

给定一棵有n 个点的树，以及m 条树链，其中第i 条树链的价值为wi，请选择一些没有公共点的树链，使得价值和最大。

n,m<=1000

f\[u\]表示以u为根的子树内选取不相交树链的价值和的最大值

如果u不在树链上，f\[u\]就是所有子节点的f之和

否则可以枚举所在的树链，再对这条链上挂着的其他点的f求和

BZOJ1864 三色二叉树

给出了一棵二叉树，点数为n，然后要求每个点和其左儿子和其右儿子三者两两之间颜色互不相同，求最多能有多少点被染成绿色。

N<=10^5

f\[i\]\[0\] ，f\[i\]\[1\]，f\[i\]\[2\]分别表示根是绿红蓝三种颜色时的最多/最少绿色的数量，转移的时候只要保证上面的约束就行，并不难。

void dfsmx(int u)
    {
        if(u==0) return ;
        int l=ch[u][0],r=ch[u][1];
        dfsmx(l);
        dfsmx(r);
        f[u][0]=max(f[l][1]+f[r][2],f[l][2]+f[r][1])+1;
        f[u][1]=max(f[l][0]+f[r][2],f[l][2]+f[r][0]);
        f[u][2]=max(f[l][0]+f[r][1],f[l][1]+f[r][0]);
    }

bzoj2466

图论中的树为一个无环的无向图。给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的）。并且该节点的直接邻居也发生同样的变化。

开始的时候，所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。

◦对于100%的数据，满足1 <= n <=100。

设f\[i\]\[0/1\]\[0/1\]表示在点i，i按不按，i亮不亮时，i的子树都被点亮的最少次数

1.如果摁x，那么x的儿子都不亮；如果不摁x，那么x的儿子都要亮  
2.如果x发亮，那么它和它的儿子中一定有奇数个点摁了；如果x不亮，那么它和它的儿子中一定有偶数个点摁了。

我们可以设置一个辅助数组gx\[i\]=0/1表示当前已经选取的是否是偶数

或者这样也可以

int dp[N][2][2];
    void dfs(int u,int f)
    {
        dp[u][0][0]=0,dp[u][1][1]=1,dp[u][1][0]=dp[u][0][1]=n+1;
        for(int j=hed[u];j;j=e[j].nxt)
        {
            int to = e[j].to;
            if(to==f)continue;
            dfs(to,u);
            int d00 = dp[u][0][0],d01 = dp[u][0][1],d10 = dp[u][1][0],d11 = dp[u][1][1];
            dp[u][0][0] = min(d00+dp[to][0][1],d01+dp[to][1][1]);
            dp[u][0][1] = min(d00+dp[to][1][1],d01+dp[to][0][1]);
            dp[u][1][0] = min(d10+dp[to][0][0],d11+dp[to][1][0]);
            dp[u][1][1] = min(d10+dp[to][1][0],d11+dp[to][0][0]);
        }
    }

树上背包简化版

给出一棵n个点的有根树，每个节点都是一个物品，具有价值Vi，如果一个物品要被选择，那么它的父亲必须被选择。

求选择至多m个物品的最大价值和。

n<=1000。

f\[i\]\[j\]表示在以i为根子树中选择，i强制选择，选择j个点的最大价值，转移时每次将一个孩子暴力合并到父亲上，合并就枚举这个孩子内部选择了多少点即可。

F\[i\]\[j\]=max\{f\[i\]\[j-k\]+f\[son\]\[k\] |k=0…(j-1)\}，就是枚举son内选了多少点。

我们按照一般的分析复杂度的方式的话是：状态数N^2\*转移复杂度N，总复杂度是O(N^3)。

◦实际上我们考虑每次合并的时候相当于是一组点对数量的复杂度，总的来看的话就是n个点点对的数量，均摊复杂度O(N^2)

合并背包的代码：

for(int i=0;i<=size(f);i++)
    {
        for(int j=0;j<=size(g);j++)
        {
            h[i]=max(h[i],f[j]+g[i-j]);
            //h[i]表示合并之后的背包 
        }
    }

bzoj4033: 树上染色

有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。 问收益最大值是多少。

◦N<=1000

考虑每条边的贡献

f\[u\]\[j\]：u子树选了j个黑点u子树边最大收益是多少

贡献j\*(k-j)

把j个黑点分配给子树

考虑边的贡献：两端黑点数量的乘积+两端白点数量的乘积。

定义状态f\[i\]\[j\]表示i号节点为根节点的子树里面有j个黑色节点时最大的贡献值。

然后我们要知道的就是i到其父亲这条边会计算次数就是：子树中白色节点数∗子树外白色节点数+子树中黑色节点数∗子树外黑色节点数。

这条边的贡献 和i的各个孩子的子树内各有多少黑点是无关的，所以我们可以做背包求出来每个点子树内有j个黑点时贡献和是多少。

代码如下 红线部分必须按图示这个写法，保证N^2的均摊复杂度分析

![1605984-20190807203854111-729595786.png][]

树上背包

给出一棵n个点的有根树，每个节点都是一个物品，具有价值Vi和重量Wi，如果一个物品要被选择，那么它的父亲必须被选择。

求限制重量m内的最大价值和。

n<=1000,m<=1000。

这里不是选点的数量而是重量，所以这里的朴素做法是O(n^3)

f\[i\]\[j\]表示在以i为根子树中选择，i强制选择，重量为j的最大价值，转移时每次将一个孩子暴力合并到父亲上，合并就枚举这个孩子内部选择了多少的重量即可。

F\[i\]\[j\]=max\{f\[i\]\[j-k\]+f\[son\]\[k\] |k=0…(j-1)\}，就是枚举son内用了多少重量。

注意我们这里两个一维数组的背包合并是n^2的，所以慢。

但一个一维数组和一个单独的物品合并是线性的。

在dfs序上Dp，如果不选一个点，则跳过代表他的子树的dfs上连续一段。

设f\[i\]\[j\]表示dfs序上第i个点到第n个点，选了j的重量得到的最大的价值是多少。i可以选也可以不选。不选的话就要跳过整个子树。

设T\[i\]表示dfs序为i的点标号。

不选：f\[i + size\[ T\[i\] \] \]\[j\]

选：f\[i+1\]\[ j- w\[ T\[i\] \]\]+v\[ T\[i\] \]

两种情况取最大值即可。

bzoj5123

◦求一棵 \[1,n\] 的线段树的最大匹配数目与方案数。 ◦N<=10^18

对于等长的线段，树的形态是一样的。同样长的线段dp数组是一样的。最多log10^18种不一样的

记忆化搜索，区间长度

设 f\[l\]\[r\] 表示根节点为 \[l,r\] 的线段树，匹配选择根节点的最大匹配&方案数，g\[l\]\[r\] 表示根节点为 \[l,r\] 的线段树，匹配不选择根节点的最大匹配&方案数。那么这是一个很普通的树形dp。

注意到区间长度相等的线段树的结果是一样的，且每层至多有两种区间长度不同的区间(打表或者推推式子都行)，因此直接以区间长度为状态进行记忆化搜索即可

基环树

基环树，也是环套树，简单地讲就是树上再加一条边。

如果把那个环视为中心，可看成：有一个环，环上每个点都有一棵子树的形式。

因此，对基环树的处理两部分分别为对树处理和对环处理。

![1605984-20190807204959897-989070011.png][]

void dfs(int u,int f)
    {
        fa[u]=f;
        vis[u]=true;
        for(int i=head[u];i;i=edg[i].nxt)
        {
            if(edg[i].to==f)
            {
                f=-1;
                continue;
            }
            if(!vis[to[i]]) dfs(edg[i].to,u);
            else
            {
                int tmp=u;circle[cnt=1]=u;
                do
                {
                    tmp=fa[tmp];
                    circle[++cnt]=tmp;
                }while(v!=tmp);
                found=true;return;
            }
            if(found) return;
        }
    }

主函数调用时，要枚举每一个点。

for(int i=1;i<=n;i++)
    if(!vis[u]) dfs(i,0);
    //不要忘了还有可能是个基环森林

因为有可能是个基环树森林。

这是很容易犯的一个坑：n个点n条边不一定是个基环树，准确来讲是基环树森林！！

![1605984-20190807210037310-102958446.png][]

基环树内向

首先它是一个有向图，它构成类似基环树的结构，有一个特点是每个点都有且只有一个出度，并且环外的节点方向指向环内。

如果题目说满足每一个点都有一个唯一出度，则本质上就是给了我们一个基环内向树森林（不只是一个基环内向树！！！！）

任何一个点沿着唯一出边走都会走到环上

利用这个性质可以随便选一个点再通过一个简单循环找到基环树的环。

![1605984-20190809175133530-741620089.png][]

基环外向树

与基环内向树相反，它有且只有一个入度（基环内向树是出度），并且并且由环指向环外。

可以把所有边反向后，变成基环内向树找 快速找环。

![1605984-20190809175156377-1782822568.png][]

bzoj1040

N个人，每个人都有一个战斗力和一个讨厌的人（不是他本身），要求一个总战斗力最大的人的集合，满足集合内部两两不互相讨厌

N<=10^5

把这个讨厌关系的图画出来，就是个基环内向树森林，然后我们要求最大权独立集。

求最大独立集内向和外向和无向图毫无区别，都是相邻的不能选。

这里的基环树上有且仅有一个环，就是从任意环上一条边(u,v)断开环，分两种情况，一种是选u，不选v，一种是选v，不选u，（注意是强制一个点不选然后跑最大独立集，也就是说另一个点也有可能不选）两种情况取最大值。

转化成树的话，就是那个简单的树形dp。

找环dfs找就好，或者从一个点顺着父亲一直走直到走到一个曾经走到过的点就找到一个环了。

dfs函数：就是求一个最大权独立集，与树上的并无大的区别。

![1605984-20190809175447964-208012879.png][]

![1605984-20190809175500859-1108059440.png][]

work函数：枚举断开的这条边，哪一端点强制不选，取最优值。

BZOJ1791

求无向基环森林中的每棵基环树的直径之和。

点数n<=10^6

先找出环，很明显答案有两种情况。

1：在以一个环上节点为根的向外的树的直径。

2：以两个环上节点分别为根的最大深度再加上两个节点在环上距离。

第一种情况就是之前讲的树形dp。

第二种情况要处理出以环上每个节点为根的最大深度d\[i\]，环上的点重标 号，选环上1号点作为基准点，求出s\[i\]表示i号点到1号点的距离，sum为 总的环长。设我们找的两个环上节点是i,j

则max( min\{s\[i\]-s\[j\],sum-(s\[i\]-s\[j\]\} +d\[i\]+d\[j\])即为所求，但如果暴力求是 n^2的。并没有比最开始直接枚举快多少。

考虑优化。

我们考虑把内部的一个min去掉，式子能看起来更清晰一些。

max( min\{s\[i\]-s\[j\],sum-(s\[i\]-s\[j\])\} +d\[i\]+d\[j\])

Max( 1: s\[i\]-s\[j\] +d\[i\]+d\[j\] | s\[j\]>=s\[i\]-sum/2,

2: sum-s\[i\]+s\[j\] +d\[i\]+d\[j\] | s\[j\]< s\[i\]-sum/2 )

考虑枚举选的两个点的后一个点i，然后求对于i，离i最远的j距离是多少，然后 对于每一个i的答案求最大值就是整个基环树的直径了。

第一种情况s\[j\]>=s\[i\]-sum/2 ：求d\[j\]-s\[j\]的最大值即可，注意可选的j区间会移动， 所以这里需要单调队列。

第二种情况s\[j\]< s\[i\]-sum/2：这个可行区间只会变大，不会缩小，所以直接记录 s\[j\]+d\[j\]的最大值即可。

学的内容

一般模式的树形背包dp，求直径求最大独立集等，以及几道经典题目强 化理解。

树上背包问题，一种经典且常用的均摊复杂度分析的方式，很多时候一 道看似复杂度超的题目就因此复杂度正确了。

dfs序上树上背包或者传数组做树上背包的两个O(n\*m)的做法。

有关基环树/基环内向/基环外向树的理解。

基环树两个处理方法，断环为树，或处理树上信息后转化成环形的序列 问题。

转载于:https://www.cnblogs.com/lcezych/p/11317809.html

[1605984-20190807190312607-652612520.png]: /images/20211101/854534bc87bb40479ca261487137160f.png
[1605984-20190807203854111-729595786.png]: /images/20211101/7bf9a659473b40fcaebea4c10d00683e.png
[1605984-20190807204959897-989070011.png]: /images/20211101/6783a0408b67434ba842c78c6f660938.png
[1605984-20190807210037310-102958446.png]: /images/20211101/4c436cda3ff5466f95be892d0ac7b382.png
[1605984-20190809175133530-741620089.png]: /images/20211101/832fe9d048b648dabf2b98f6564ec29f.png
[1605984-20190809175156377-1782822568.png]: /images/20211101/0a0e2ddc603c42b3940a993709ca19c9.png
[1605984-20190809175447964-208012879.png]: /images/20211101/923951e38bc845449b0ad36048026558.png
[1605984-20190809175500859-1108059440.png]: /images/20211101/3fb62226ea9348c19796d025df1f57ba.png