首页 > 其他分享 >洛谷 P5658 [CSP-S2019] 括号树

洛谷 P5658 [CSP-S2019] 括号树

时间:2024-09-06 19:47:31浏览次数:12  
标签:洛谷 fa int top stk 括号 S2019 CSP flg

洛谷 P5658 [CSP-S2019] 括号树

题意

给定一棵树,每个点有一个括号 ()

定义 \(s_i\) 表示 根节点到 \(i\) 每个点的括号组成的序列。

求每个 \(s_i\) 中合法括号子串的个数 \(f_i\)。

思路

定义 \(g_i\) 表示 \(s_i\) 中以 \(i\) 结尾的合法括号子串的个数。

有 \(f_i=f_{fa_i}+g_i\),求出 \(g_i\) 即可。

若 \(i\) 为左括号,\(g_i=0\)。

若 \(i\) 为右括号,

若没有左括号和它匹配,\(g_i=0\),

若有左括号和它匹配,设为第 \(j\) 个,\(g_i=g_{fa_j}+1\)。

即这一段匹配的括号接在上一段后面,又多出来了一个。

如图,黑色表示上一段的 \(g\),红色表示这一段匹配的括号,绿色表示这一段的 \(g\)。

由于两个合法子串拼接后仍为合法子串,所以 \([8,9]\) 可以单独,也可以和 \([6,4],[6,1]\) 拼接,这样就是 \(g_6+1\)。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 5;
int n, fa[N], stk[N], top; 
char s[N];
ll ans, g[N], f[N];
vector <int> E[N];
void dfs(int x) {
	int flg = 0;
	if (s[x] == '(') stk[++ top] = x;
	else if (top) g[x] = g[fa[stk[top]]] + 1, flg = stk[top --]; 
	f[x] = f[fa[x]] + g[x];
	for (auto y : E[x]) dfs(y);
	if (s[x] == '(') top --;
	else if (flg) stk[++ top] = flg;
}
int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	for (int i = 2; i <= n; i ++) 
		scanf("%d", &fa[i]), 
		E[fa[i]].push_back(i);
	dfs(1);
	for (int i = 1; i <= n; i ++) 
		ans ^= 1ll * i * f[i];
	printf("%lld\n", ans);
	return 0;
}

标签:洛谷,fa,int,top,stk,括号,S2019,CSP,flg
From: https://www.cnblogs.com/maniubi/p/18400884

相关文章

  • 『模拟赛』CSP-S模拟1
    Rank1BADA.喜剧的迷人之处在于签。正好早上还在改一个要分解质因数的题,所以一眼就出思路了。首先将\(a\)的平方因子全部除去,剩下的就是\(b\)必须的因数,即若设将平方因子全部除去后的\(a\)为\(a'\),则\(b\)应表示为\(a'\timesx^2\),从\(L\)这个下界开始只用找......
  • 洛谷题单指南-常见优化技巧-P3467 [POI2008] PLA-Postering
    原题链接:https://www.luogu.com.cn/problem/P3467题意解读:用长方形的海报覆盖建筑的侧面,最少需要的海报数如上图,左边最少需要3张,右边最少需要4张解题思路:可以看出,需要海报数与建筑宽度无关,只与高度有关。当建筑高度与之前不同时,肯定需要增加一张海报;当建筑高度与之前有相同......
  • CSP-S 历年真题
    [CSP-S2023]密码锁[CSP-S2022]策略游戏[CSP-S2020]儒略日P7913[CSP-S2021]廊桥分配P7915[CSP-S2021]回文P7914[CSP-S2021]括号序列P5687[CSP-S2019江西]网格图P5689[CSP-S2019江西]多叉堆P9755[CSP-S2023]种树P8819[CSP-S2022]星战......
  • 【洛谷 P1449】后缀表达式 题解(栈+分支)
    后缀表达式题目描述所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。如:对应的后缀表达式为:。在该式中,@为表达式的结束符号。.为操作数的结束符号。输入格式输入一行......
  • 洛谷P1032 [NOIP2002 提高组] 字串变换
    ac代码:#include<bits/stdc++.h>usingnamespacestd;constintN=15;structnode{ stringstr; intstep;};stringa,b;stringorginal[N];stringtranslated[N];intn,ans;map<string,int>ma;stringtrans(conststring&str,inti,i......
  • 洛谷 P1516 青蛙的约会 题解
    一道简单的数学题~首先分析题意。精简得出:假设跳了\(t\)次,那么青蛙A的坐标是\((x+mt)\modL\),青蛙B的坐标是\((y+nt)\modL\),列出方程:\[x+mt\equivy+nt\pmodL\]由于余数具有可减性,所以把\(y+nt\)移到左边,得出:\[x-y+mt-nt\equiv0\pmodL\]写成人话:\[(x-y+mt-nt)\mod......
  • 3292. 称检测点查询 来源:第二十次CCF-CSP计算机软件能力认证 枚举 排序
    #include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=210;pair<int,int>p[N];intn,X,Y;intmain(){cin>>n>>X>>Y;for(inti=1;i<=n;i++){......
  • 3293. 风险人群筛查 来源:第二十次CCF-CSP计算机软件能力认证 模拟枚举
    #include<iostream>#include<cstring>#include<algorithm>#definexfirst#defineysecondusingnamespacestd;intn,k,t,x1,y1,x2,y2;intmain(){cin>>n>>k>>t>>x1>>y1>>x2......
  • 洛谷 P2860 Redundant Paths G
    洛谷P2860RedundantPathsG题意给定一张图,求最少添加几条边使得原图变为边双连通图。思路先将原图进行边双连通分量缩点,因为已经边双连通的子图我们不用考虑。缩点后会得到一棵树,每一条边都是桥。假定有\(k\)个叶子节点。我们可以把叶子节点两个两个配对连边形成环,这样......
  • 洛谷 P3469 BLO-Blockade
    洛谷P3469BLO-Blockade题意给定一张无向图,求每个点被封锁之后有多少个有序点对\((x,y)(x\ney,1<=x,y<=n)\)满足\(x\)无法到达\(y\)。思路使用Tarjan求出割点,有以下几种情况。当前点不是割点,答案为\(2\times(n-1)\),即该点与其他所有点不连通。当前点是割点,答案......