首页 > 其他分享 >P10536 [Opoi 2024] 二十六点 题解

P10536 [Opoi 2024] 二十六点 题解

时间:2024-06-03 22:33:05浏览次数:26  
标签:ch int 题解 void son 2024 fst ans 二十六点

比较直接的做法。

当 \(P_x = 1\) 时显然可以暴力 DP,设 \(f_{x,c}\) 表示 \(x\) 的子树中以 \(c\) 开头的最长不下降子序列的长度。直接转移即可。

\(P_x \neq 1\) 的时候呢?我们发现,所谓“忽略掉这些路径中的第 \(2\) 到第 \(P_x\) 个的点”,代表的就是按照深度转移,大概就是这样:

只和深度有关,很难不想到长链剖分,套板子即可。

转移方程(其中 \(mxdep\) 代表其最大深度)

\[ans = \begin{cases} 1 \quad P_x \ge mxdep_x\\ max_{f_{dfn_x+P_x,c}} \quad c<c_x\\max_{f_{dfn_x+P_x,c}}+1 \quad c \ge c_x\end{cases} \]

一定要在回溯时就统计答案,要不然答案就会被祖先覆盖然后就会和我一样寄掉

时间复杂度 \(O(n\left|\Sigma\right|)\)。

代码

#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
	char ch=getchar();
	T f=1;x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x*=f;rd(args...);
}
const int N=1e5+5;
char ch[N];
int n,p[N],fst[N],nxt[N<<1],v[N<<1],idx;
void Add(int a,int b){
	v[idx]=b,nxt[idx]=fst[a];
	fst[a]=idx++;
}
int mxdep[N],son[N],dfn[N],cnt;
int ans[N];
void DFS(int x,int f){
	mxdep[x]=1;
	for(int i=fst[x];~i;i=nxt[i]){
		int y=v[i];
		if(y==f)continue;
		DFS(y,x);
		mxdep[x]=max(mxdep[x],mxdep[y]+1);
		if(mxdep[y]>mxdep[son[x]])son[x]=y;
	}
}
void DFS2(int x,int f){
	dfn[x]=++cnt;
	if(son[x])DFS2(son[x],x);
	for(int i=fst[x];~i;i=nxt[i]){
		int y=v[i];
		if(y==f||y==son[x])continue;
		DFS2(y,x);
	}
}
int f[N][30],c[N];
void Solve(int x,int fa){
	if(son[x])Solve(son[x],x);
	for(int i=fst[x];~i;i=nxt[i]){
		int y=v[i];
		if(y==fa||y==son[x])continue;
		Solve(y,x);
		for(int j=1;j<=mxdep[y];j++){
			for(int k=1;k<=26;k++){
				f[dfn[x]+j][k]=max(f[dfn[x]+j][k],f[dfn[y]+j-1][k]);
			}
		}
	}
	if(son[x])for(int i=1;i<=26;i++)f[dfn[x]][i]=max(f[dfn[x]][i],f[dfn[x]+1][i]);
	for(int i=c[x];i<=26;i++)f[dfn[x]][c[x]]=max(f[dfn[x]][c[x]],f[dfn[x]][i]+1);
	int pls=0;
	if(p[x]==1){
		for(int j=1;j<=26;j++){
			ans[x]=max(ans[x],f[dfn[x]][j]);
		}
	}else{
		if(p[x]>=mxdep[x])ans[x]=1;
		else{
			for(int j=1;j<=26;j++){
				if(j>=c[x])pls=1;
				ans[x]=max(ans[x],f[dfn[x]+p[x]][j]+pls);
			}
		}
	}
}
signed main(){
	memset(fst,-1,sizeof fst);
	rd(n);
	for(int i=1;i<=n;i++)rd(p[i]);
	scanf("%s",ch+1);
	for(int i=1;i<=n;i++)c[i]=ch[i]-'a'+1;
	for(int i=1;i<n;i++){
		int x,y;rd(x,y);
		Add(x,y);Add(y,x);
	}
	DFS(1,1);DFS2(1,1);
	Solve(1,1);
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
	return 0;
}

标签:ch,int,题解,void,son,2024,fst,ans,二十六点
From: https://www.cnblogs.com/11-twentythree/p/18229831

相关文章

  • 2024.6.3 时光机会是最没用的发明
    正如标题,时光机会是最无用的发明。如果问昨天的我,时光机有用吗,我会毫不犹豫地回答有用。我希望回到5月,乞求自己好好改初赛;我希望回到1月,乞求自己不要虚度光阴;我希望回到去年9月,乞求自己不要头铁T2,乞求自己检查T1;我希望回到去年6月,乞求自己不要玩florr,这个万恶之源;我希望回到......
  • CF960G Bandit Blues 题解
    我不会斯特林数。CF960GBanditBlues给你三个正整数\(n\),\(a\),\(b\),定义\(A\)为一个排列中是前缀最大值的数的个数,定义\(B\)为一个排列中是后缀最大值的数的个数,求长度为\(n\)的排列中满足\(A=a\)且\(B=b\)的排列个数。\(n\le10^5\),答案对\(998244353\)取......
  • 2024-6-3 石群电路-22
    2024-6-3,星期一,20:45,天气:晴,心情:阴转晴。今天没有发生了一些令人不开心事情,心情有些差,不过还是调整过来了,活好自己,就是对你讨厌的人最大的惩罚。因为准备毕业论文答辩的材料所以更新的晚了一点。今日观看了石群老师电路课程的第38个视频,开始了第九章的学习,主要学习内容为:阻抗的......
  • 20240531/01模拟赛
    地盘划分想说暴力思路对于任意两个\(a\)和\(b\),当\(a<b\)时,可以发现最大的正方形应该是\(a\timesa\)。既然题目要让每一个正方形最大,那么就可以直接用刚刚的方法来解决这一题直到最短的一条边为\(0\)。这个思路的的时间复杂度时\(O(n)\)可以获得\(50\)分。这个思路的问题是......
  • 2024年人文艺术与媒体传播国际学术会议(ICHAMC 2024)
    2024年人文艺术与媒体传播国际学术会议(ICHAMC2024)会议简介随着全球化的深入,人文、艺术与传媒交流的交汇与融合成为推动社会进步和文化发展的重要力量。本次会议将聚焦人文、艺术与传媒之间的紧密联系,探讨如何更好地通过传媒的力量传承和发展人文艺术。会议将涵盖多个议题,......
  • 2024年新能源科学技术与储能研究国际会议(ICNESTESR 2024)
    2024年新能源科学技术与储能研究国际会议(ICNESTESR2024)会议简介随着全球能源结构的转变和可持续发展理念的日益普及,新能源技术和储能研究引起了广泛关注。国际新能源科学与技术及储能研究大会将汇聚世界各地的顶尖专家,共同探讨该领域的最新成果、技术趋势和市场应用。参会者......
  • 2024年计算机视觉、设计与算法国际会议( ICCVDA 2024)
    2024年计算机视觉、设计与算法国际会议( ICCVDA2024)会议简介本次大会旨在建立一个国际性的学术交流和合作平台,重点关注计算机视觉领域的最新进展、设计与算法的创新应用,分享前沿研究成果,并探索未来发展趋势。我们诚挚邀请全球各地的学者、专家、企业代表及感兴趣的个人积......
  • P10550 [THUPC2024] 贸易 题解
    正式场上拿了这题的首\(A\),让队伍不至于无奖而返。思路容易发现题目的买入卖出过程形似一个括号匹配。那么我们可以对每一种类型的物品做括号匹配。若是一个匹配的括号在询问区间内则可以记入答案。就变成了一个二维数点问题。离线树状树组即可。Code#include<bits/stdc......
  • 关于vue关闭页面时去除定时器失效问题解决
    1.先去除页面缓存,这个在路由部分 2.    ......
  • 2024年项目任务管理软件大盘点:12款值得一试的主流工具
    12款优秀的项目任务管理软件:PingCode、Worktile、AIrTable、ClickUp、Teambition、Asana、Todoist、TAPD、Monday.com、Notion、MicrosoftProject、Trello。任务管理软件对于生活繁忙的人来说极为重要。它帮助用户有效跟踪他们需要完成的各项任务,包括任务的截止日期、相关的......