江苏建设通网站,设计网站源代码,怎么免费咨询律师,扬州市住房和城乡建设局网站前言#xff1a;
好久没训练了,来做道计数题找找感觉。**期末毁我青春
大意#xff1a;
定义对于一个括号串 s的值#xff0c;为通过最小次数以下操作使 s 实现括号匹配的操作次数。
选择一个子串#xff0c;循环右移一位。在任意一个位置插入一个任意括号。
求一个括…前言
好久没训练了,来做道计数题找找感觉。**期末毁我青春
大意
定义对于一个括号串 s的值为通过最小次数以下操作使 s 实现括号匹配的操作次数。
选择一个子串循环右移一位。在任意一个位置插入一个任意括号。
求一个括号串的所有非空子串的值的和。
思路 显然先分析对于一个串的情况
不难发现操作1其实就是把子串的末尾提到前面对于其它的字符不会有任何影响
我们令L表示串内左括号的数量R表示右括号的数量x表示串内已经匹配的括号对的数量
然后这里就有一个比较显然的操作思路
假定LR,对于每一个没有匹配的左括号如果我们能找到一个尚未匹配的右括号则它一定在该左括号的前面所以我们直接取以它们为端点的字串执行操作1这就实现了一个匹配。由于操作一只会对字串的端点产生影响所以这不会破坏任何已有结构。如果这个左括号找不到尚未匹配的右括号我们就直接执行操作2即可。
注意到每次操作都不会浪费都达到了对应操作所能消去的最多的括号数所以该操作是最优的此时总操作次数是L-x
同理RL时总操作次数就是R-x
总结一下对于一个字符串其操作此时就是max{L,R}-1 所以我们得到答案就是
先求x
很套路地考虑每一个匹配的贡献有多少个字串可以包含它。取左端点l右端点r则贡献就是l*(n-r1)整体用一个栈就能实现匹配求和的过程了
考虑max(L,R),可以做如下转化,LR的求和是比较简单的就是类似于上一个的求法考虑每一个位置的贡献。|L-R|,其实就是区间和的绝对值
取sum表示字符串的前缀和左括号取1右括号取-1,对sum排序之后注意要把sum0也加进去
不难发现这个的求和可以转化为
也就是
两部分求完之后除以2即可
整体时间复杂度nlogn
code
#includebits/stdc.h
using namespace std;
#define int long long
#define ll long long
#define endl \n
const ll N2e510;
ll n;
string s;
ll sum[N];
void solve()
{cinn;for(int i0;in5;i) sum[i]0;cins;s s;for(int i1;in;i){if(s[i]() sum[i]sum[i-1]1;else sum[i]sum[i-1]-1;}sort(sum,sum1n);ll tot0;for(int i1;in;i) toti*(n-i1);for(int i1;in;i) toti*sum[i];for(int i0;in-1;i) tot-(n-i)*sum[i];tot/2;//couttot ;stackll st;for(int i1;in;i){if(s[i]() st.push(i);else{if(st.empty()) continue;int idst.top();tot-id*(n-i1);st.pop();}}couttotendl;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t;cint;while(t--)solve();return 0;
}
