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

[CSP-S2019] 括号树

时间:2024-10-07 21:24:51浏览次数:10  
标签:tmp int top 括号 lst maxn S2019 CSP define

算法

特殊性质

显然链的情况就是括号匹配

因此显然有代码

代码

#include <bits/stdc++.h>
#define int long long
const int MAXN = 5e5 + 20;

int n;
std::string Braket;
int fa[MAXN];

bool Check_Special_Quality()
{
    for (int i = 2; i <= n; i++)
    {
        if (fa[i] != i - 1)
        {
            return false;
        }
    }

    return true;
}

std::stack<int> Pre;
int k[MAXN];
int Sum[MAXN];

int calc()
{
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        // printf("%d ", k[i]);
        ans = ans ^ (i * Sum[i]);
    }

    return ans;
}

void Solve_For_Special_Quality()
{
    for (int i = 1; i <= n; i++)
    {
        if (Braket[i] == '(')
        {
            Pre.push(i);
        }
        else if (Braket[i] == ')')
        {
            if (Pre.empty())
            {
            }
            else
            {
                int Now = Pre.top();
                Pre.pop();
                k[i] = k[Now - 1] + 1;
            }
        }

        Sum[i] = Sum[i - 1] + k[i];
    }

    printf("%lld", calc());
}

signed main()
{

    scanf("%lld", &n);
    std::cin >> Braket;
    Braket = ' ' + Braket;
    for (int i = 2; i <= n; i++)
    {
        scanf("%lld", &fa[i]);
    }

    if (Check_Special_Quality())
    {
        Solve_For_Special_Quality();
        return 0;
    }

    return 0;
}

注意不能用单数组, 因为不能计算反括号对应正括号

正解

显然有树状的递推性质
那么有

\[lst_i = lst_{t - 1} + 1 \rightarrow lst_x = lst_{\text{fa of x}} + 1 \]

代码

#include<bits/stdc++.h>
#define orz 0
#define inf 0x3f3f3f3f
#define ll long long
#define maxn 500005;

using namespace std;

int n;
char c[maxn];
int head[maxn], nxt[maxn], to[maxn], cnt, fa[maxn];
ll lst[maxn], sum[maxn], ans;
int s[maxn], top;

void add_edge(int u, int v)
{
	nxt[++ cnt] = head[u];
	head[u] = cnt;
	to[cnt] = v;
}

void dfs(int x)
{
	int tmp = 0;
	if(c[x] == ')')
	{
		if(top)
		{
			tmp = s[top];
			lst[x] = lst[fa[tmp]] + 1;
			-- top; 
		}
	}
	else if(c[x] == '(') s[++ top] = x; 
	sum[x] = sum[fa[x]] + lst[x]; //如上所述 
	for(int i = head[x]; i; i = nxt[i])
		dfs(to[i]); //递归 
	//回溯复原操作
	if(tmp != 0) s[++ top] = tmp; //不为 0 代表有信息被弹出 
	else if(top) -- top; 
	//为 0 代表没有弹出,如果栈不为空说明一定压入了一个信息,需要弹出这个信息复原 
}

int main()
{
	scanf("%d", &n);
	scanf("%s", c + 1);
	for(int i = 2; i <= n; i ++)
	{
		int f;
		scanf("%d", &f);
		add_edge(f, i);
		fa[i] = f;
	}
	dfs(1);
	for(int i = 1; i <= n; i ++)
		ans ^= sum[i] * (ll)i;
	printf("%lld", ans);
	return orz;
}

ctj 是这样的

总结

特殊套路 :
dfs 时保持状态稳定

标签:tmp,int,top,括号,lst,maxn,S2019,CSP,define
From: https://www.cnblogs.com/YzaCsp/p/18450622

相关文章

  • 代码源Csp-S模拟赛Day10-11赛后总结
    代码源Csp-S模拟赛Day10-11赛后总结Day10赛时T1赛时感觉很难维护时间以及多个精灵同时到达同一格子的情况,后来想了一种做法:对于每个格子最早被遍历到的时间我们的处理是容易的,你考虑我们可以对每行每列都建一棵线段树(数据范围保证了\(rc\leq5e5\),所以总空间大致是一个\(4rc......
  • CSP2024 前集训:csp-s模拟9
    前言T1状压挂了\(10pts\),貌似做法是假的,但是一下午也没调出来哪儿假了,但是错误率很低,几百组能有一组错的。T2赛时数据锅了赛后重测了,赛时想到线段树但是没能具体实现,最后无奈写暴力。T3、T4没看。T1邻面合并\(m\le8\)所以考虑状压表示每一行哪些地方被覆盖,对与相邻两......
  • CSP 联训 3
    好吧,又倒数了,就签了个T2,100pts。T1我把相同颜色的存起来,每种颜色找出枚举选哪两个座位不合法的矩阵的左上和右下,如果找到的矩阵左下和右上也相同,则这个矩阵确实不合法,减去,但判断左下和右上的时候写的太急(最后十五分钟才开始打这个暴力)少判了和当前颜色是否相同,挂了80pts,!总......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛03
    前言T1没想到正难则反,脑瘫了没敢用bitset(复杂度擦边但卡常能过),T2空间开大了挂了\(100pts\),\(T3\)是原。T1五彩斑斓部分分\(20pts\):\(O(n^4)\)暴力。部分分\(20+?pts\):进行一些优化,极限数据下仍是\(O(n^4)\)。部分分\(60\sim100pts\):bitset优化一下,\(O(\f......
  • [CSP-S 2021] 回文
    算法暴力容易发现双指针可以找到每一个区间\([L,R]\),使得这个区间覆盖\(1\)~\(n\)的每一个数,也即区间外覆盖\(1\)~\(n\)的每一个数,这是\(O(n)\)的考虑判断对于两个数列\(A\),\(B\)显然,在\(A\)中先取出的要在\(B\)中最后取出,所以把\(A\)压入栈......
  • 信息学奥赛复赛复习14-CSP-J2021-03网络连接-字符串处理、数据类型溢出、数据结构Map
    PDF文档公众号回复关键字:202410071P7911[CSP-J2021]网络连接[题目描述]TCP/IP协议是网络通信领域的一项重要协议。今天你的任务,就是尝试利用这个协议,还原一个简化后的网络连接场景。在本问题中,计算机分为两大类:服务机(Server)和客户机(Client)。服务机负责建立连接,客户机......
  • CSP-S 模拟赛 35
    CSP-S模拟赛35rnk14,\(45+45+15+18=123\)。T1送花愚蠢题。看到区间想到线段树,预处理出每个位置的颜色上一次出现的位置,记为\(\mathit{las}_i\)。从左到右扫右端点,给\([\max(1,\mathit{las}_{\mathit{las}_i}),\mathit{las}_i]\)减去\(d(c_i)\),给\((\mathit{las}_i,i]\)......
  • CSP-S 模拟赛 34
    CSP-S模拟赛34rnk12,\(24+50+20+0=94\)。T1玩游戏有一个痿正解:从\(k\)到\(1\)扫左端点,对于每个左端点扫它最远能到达的右端点。如果在任何一时刻它的右端点位置\(<k\),则断定输出No。否则检查当左端点到\(1\)时右端点能否到\(n\)。注意这里扫右端点的方式,不要每次都......
  • CSP-S 模拟赛 33
    CSP-S模拟赛33rnk19,\(30+20+40+15=105\)。T1构造字符串10pts:输出\(-1\)。30pts:对于所有\(z_i=0\)的情况,也就是说给定的两个位置字符都不同。记录有哪些位置的字符是不同的,然后从\(1\)到\(n\)扫一遍,输出除去不同的字符之外的字典序最小的字符。70pts:暴搜。枚举每个......
  • P3215 括号修复 题解
    Statement维护一个括号序列,有以下操作:区间覆盖区间翻转区间反转(左括号变右括号,右括号变左括号)区间问最少改多少位能使括号序列合法,保证有解Solution单纯没想到答案怎么算。。。首先一段括号序,如果消除中间的所有匹配,最终一定形如))))(((,这个信息是可合并的设这时左括......