创业论坛网站有哪些,订餐网站开发流程,专门做焦点图的网站,百度做网站的电话传送门 文章目录解析代码解析
没有做出来。。。 一开始看到了一个#xff08;自以为#xff09;很好的性质#xff0c;再加上之前做一些括号相关题的刻板印象#xff0c;导致这题没掉了… 我的角度和正解完全背道而驰了 放下乱七八糟的前缀和与st’表#xff0c;回归朴素…传送门
文章目录解析代码解析
没有做出来。。。 一开始看到了一个自以为很好的性质再加上之前做一些括号相关题的刻板印象导致这题没掉了… 我的角度和正解完全背道而驰了 放下乱七八糟的前缀和与st’表回归朴素的括号匹配的栈的做法
如果对于一个括号串如何统计其合法字串的个数 我们考虑统计新增一个括号的贡献 显然增加左括号是不会产生贡献的 关键在于右括号与之前栈中的某个左括号匹配时的贡献 设与这个右括号匹配的左括号位置在 pl 显然它自己有一的贡献 其次如果它能和之前的串连接每连一个就会多1的贡献 不难发现递归来说能与之前连接的括号的个数其实就是pl-1的位置的贡献! 到了这里本题就迎刃而解了 注意为了处理树需要再回溯时逆处理一下对栈的出入元素操作 本题得以解决
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N5e5100;
const int mod1e8;
int n,m;
int fi[N],cnt-1;
struct node{int to,nxt;
}p[N1];
void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}
char s[N];
ll val[N],ans[N],tot;
int fa[N];
int zhan[N],top;
void dfs(int x){int pl0;//printf(x%d\n,x);ans[x]ans[fa[x]];if(s[x]() zhan[top]x;else if(top){plzhan[top--];val[x]val[fa[pl]]1;ans[x]val[x];//printf(x%d ans%lld\n,x,ans[x]);}tot^1ll*x*ans[x];for(int ifi[x];~i;ip[i].nxt){int top[i].to;dfs(to);}if(s[x]() top--;else if(pl) zhan[top]pl;
}
int main(){memset(fi,-1,sizeof(fi));scanf(%d %s,n,s1);for(int i2;in;i){scanf(%d,fa[i]);addline(fa[i],i);}dfs(1);printf(%lld,tot);
}
/*
5
()()(
1 2 3 4
*/
