首页 > 其他分享 >luogu-P3262题解

luogu-P3262题解

时间:2024-11-11 08:50:03浏览次数:4  
标签:状态 P3262 int 题解 贡献 枚举 luogu 节点

简要题意

有一棵不超过十层的满二叉树,需要对每个节点进行染色。每个叶子节点会对其颜色相同的祖先节点产生贡献且黑白贡献不同。求最大贡献。

题解

首先我会暴力!我如果直接暴力枚举每个节点的颜色,复杂度就是 \(O(2^{2^n})\)。然后还要算贡献,所以还有一个 \(O(2^{n-1}(n-1))\)。然后肯定爆了。

不用说都知道是因为我们在枚举的时候重复枚举了很多相同的状态,这时我们应该单独考虑贡献。对于一个点,它的贡献应该只与其祖先节点有关,而我们暴力是去枚举了其他无关的节点。所以我们就可以设计一个 \(f_{u,S}\) 表示当前考虑到 \(u\) 节点,\(u\) 的祖先状态为 \(S\) 时子树最大贡献。然后题目中还有对黑点的个数限制,所以我们还需要加一维表示子树内黑点个数。所以最终状态是 \(f_{u,S,cnt}\) 表示 \(u\) 的子树内,其祖先染色状态为 \(S\) 且子树内有 \(cnt\) 个黑点时最大贡献。然后对于任意节点,假设它在第 \(x\) 层,则它的祖先结点状态数为 \(2^{x-1}\),子树大小为 \(2^{n-x+1}-1\),所以时间复杂度为 \(O(n\times2^n)\)。但是空间是 \(O(n\times2^{2n})\),所以我们就在搜索状态的过程中记录一个状态 \(S\),数组就只用开二维。

转移其实就是合并两个子树的信息,所以直接预处理出叶子节点的答案,然后跑一遍 \(dfs\) 然后类似合并背包一样做即可。

代码

inline void upd(int &x, int y){x = x > y ? x : y;}

void dfs(int u, int sta, int dep){
	if(dep == n)return(void)(f[u][0] = c[u - lim][sta][0], f[u][1] = c[u - lim][sta][1]);
	for(int i = 0; i <= qp[dep]; ++i)f[ls][i] = f[rs][i] = 0;
	dfs(ls, sta, dep + 1); dfs(rs, sta, dep + 1);
	for(int i = 0; i <= qp[dep]; ++i)for(int j = 0; j <= qp[dep]; ++j)upd(f[u][i + j], f[ls][i] + f[rs][j]);
	for(int i = 0; i <= qp[dep]; ++i)f[ls][i] = f[rs][i] = 0;
	dfs(ls, sta + qp[dep], dep + 1), dfs(rs, sta + qp[dep], dep + 1);
	for(int i = 0; i <= qp[dep]; ++i)for(int j = 0; j <= qp[dep]; ++j)upd(f[u][i + j], f[ls][i] + f[rs][j]);
}
signed main(){
	n = rd(), m = rd(); lim = 1 << n - 1;
	for(int i = 0; i < lim; ++i)for(int j = 0; j < n - 1; ++j)v[i][j][1] = rd();
	for(int i = 0; i < lim; ++i)for(int j = 0; j < n - 1; ++j)v[i][j][0] = rd();
	qp[n - 1] = 1; for(int i = n - 2; ~ i; --i)qp[i] = qp[i + 1] << 1;
	for(int i = 0; i < lim; ++i)for(int j = 0; j < lim; ++j)
		for(int k = 0, bit = i; k < n - 1; ++k, bit >>= 1)c[j][i][bit & 1] += v[j][k][bit & 1];
	dfs(1, 0, 1); int ans = 0;
	for(int i = 0; i <= m; ++i)upd(ans, f[1][i]);
	wt(ans);
}

标签:状态,P3262,int,题解,贡献,枚举,luogu,节点
From: https://www.cnblogs.com/Nekopedia/p/18538989

相关文章

  • CF 1365 题解
    CF1365题解APrimeSubtraction任何数的因数中都会有质数,除非他是\(1\).因此原题不合法当且仅当\(b-a=1\).BKill'EmAll首先,答案有明确的下界:最右面的怪兽一定要处理.不断模拟去杀掉当前最靠右的怪兽,得到的答案就是答案的下界.是否能取到下界呢?答案是肯定......
  • CF622E Ants in leaves 题解
    传送门给定一棵\(n\)个节点的树,根节点是\(1\)。这棵树的每一个叶节点都有一只小蚂蚁。每过\(1\)秒钟,可以选择让一些蚂蚁向父节点走一步。注意,两只蚂蚁不能同时在一个除去根节点的节点上。问这些蚂蚁最少用多少秒的时间,使得所有蚂蚁都走到根节点。根结点的各个子树独立,因......
  • ABC372D ABC379F 题解 单调栈二分
    ABC372DABC379F题解单调栈二分一直觉得AT上面学到的东西比CF要多一些,无意捧一踩一,但可能是我太菜的原因,毕竟ABC的题目普遍要比Div.2简单一些。好多次碰到这个单调栈里面二分的trick了,所以写一篇来总结一下。ABC372D形象地给定一系列Buildings的高度\(h\),保证每个......
  • P2123 皇后游戏 / [USACO12JAN] Mountain Climbing S / P1248 加工生产调度 题解
    P2123皇后游戏/[USACO12JAN]MountainClimbingS/P1248加工生产调度先来看P2123。我们把这个特别重要的公式打出来:\[c_{i}=\begin{cases}a_{1}+b_{1}&,i=1\\\displaystyle\max\left\{c_{i-1},\sum_{j=1}^{i}a_{j}\right\}+b_{i}&,2\leqi\leqn\end{......
  • 历年CSP-J初赛真题解析 | 2019年CSP-J初赛完善程序(34-43)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客矩阵变幻有一个奇幻的矩阵,在不停的变幻,其变幻方式为:数字0变成矩阵[......
  • [NOIP2012 提高组] 国王游戏 题解
    [NOIP2012提高组]国王游戏典贪心。设当前点为\(i\),\(\prod_{k=0}^{i-1}a_k\)为\(x\),则对于\(i,j\)两点的答案:(为了方便,记\(i+1=j\))\[\mathit{res}_1=\max\bigg(\dfracx{b_i},\dfrac{xa_i}{b_j}\bigg)~;\]若交换,则:\[\mathit{res}_2=\max\bigg(\dfracx{b_j},\dfrac{......
  • [luogu1248] 加工生产调度 题解
    考虑\(i\)排在\(j\)前的条件是\(a_i+\max(a_j,b_i)+b_j\lea_j+\max(a_i,b_j)+b_i\),然后发现这一坨东西是皇后游戏中的倒数第三个式子,直接转化为\(\min(a_j,b_i)\ge\min(a_i,b_j)\),然后就按皇后游戏中的排序方法就可以了……#include<bits/stdc++.h>#defineintlonglong......
  • [luogu1248] 加工生产调度 题解
    考虑\(i\)排在\(j\)前的条件是\(a_i+\max(a_j,b_i)+b_j\lea_j+\max(a_i,b_j)+b_i\),然后发现这一坨东西是皇后游戏中的倒数第三个式子,直接转化为\(\min(a_j,b_i)\ge\min(a_i,b_j)\),然后就按皇后游戏中的排序方法就可以了……#include<bits/stdc++.h>#defineintlonglong......
  • [luogu1248] 加工生产调度 题解
    考虑\(i\)排在\(j\)前的条件是\(a_i+\max(a_j,b_i)+b_j\lea_j+\max(a_i,b_j)+b_i\),然后发现这一坨东西是皇后游戏中的倒数第三个式子,直接转化为\(\min(a_j,b_i)\ge\min(a_i,b_j)\),然后就按皇后游戏中的排序方法就可以了……#include<bits/stdc++.h>#defineintlonglong......
  • CCPC 网络赛题解(D/I/J)
    D根据题目给出的构造方式,\(S_n'\)的长度会达到\(2^n\)数量级,没法求出\(S_n'\),所以考虑递推。设\(dp_{i,l,r}\)为\(S_i'\)里\(T\)的\([l,r]\)区间以子序列的方式出现了多少次,可以写出转移方程:\(dp_{i,l,r}=\sumdp_{i-1,l,k}\cdotdp_{i-1,k+1,r}+[a_i=T_k]\cdot......