当前位置：首页 > news >正文

cf1750E Bracket Cost

news 2025/6/28 10:52:07

前言：

好久没训练了,来做道计数题找找感觉。**期末毁我青春

大意：

定义对于一个括号串 s的值，为通过最小次数以下操作使 s 实现括号匹配的操作次数。

选择一个子串，循环右移一位。
在任意一个位置插入一个任意括号。

求一个括号串的所有非空子串的值的和。

思路：
显然先分析对于一个串的情况

不难发现，操作1其实就是把子串的末尾提到前面，对于其它的字符不会有任何影响

我们令L表示串内左括号的数量，R表示右括号的数量，x表示串内已经匹配的括号对的数量

然后这里就有一个比较显然的操作思路：

假定L>=R,对于每一个没有匹配的左括号，如果我们能找到一个尚未匹配的右括号，则它一定在该左括号的前面，所以我们直接取以它们为端点的字串，执行操作1，这就实现了一个匹配。由于操作一只会对字串的端点产生影响，所以这不会破坏任何已有结构。如果这个左括号找不到尚未匹配的右括号，我们就直接执行操作2即可。

注意到每次操作都不会浪费，都达到了对应操作所能消去的最多的括号数，所以该操作是最优的，此时总操作次数是L-x

同理，R>=L时，总操作次数就是R-x

总结一下，对于一个字符串，其操作此时就是max{L,R}-1

所以我们得到答案就是 $\sum max(L,R)-\sum x$

先求x

很套路地考虑每一个匹配的贡献，有多少个字串可以包含它。取左端点l，右端点r，则贡献就是l*(n-r+1)，整体用一个栈就能实现匹配+求和的过程了

考虑max(L,R),可以做如下转化： $max(L,R)=\frac{L+R-|L-R|}{2}$ ,L+R的求和是比较简单的，就是类似于上一个的求法，考虑每一个位置的贡献。|L-R|,其实就是区间和的绝对值

取sum表示字符串的前缀和（左括号取1，右括号取-1）,对sum排序之后（注意要把sum0也加进去）

不难发现这个的求和可以转化为 $\sum_{i=0}^{n-1}\sum_{j=1}^{n} sum_j-sum_i$

也就是 $\sum_{i=1}^{n}i*sum_i-(n-i)sum_i$

两部分求完之后除以2即可

整体时间复杂度nlogn

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define endl '\n'
const ll N=2e5+10;
ll n;
string s;
ll sum[N];
void solve()
{cin>>n;for(int i=0;i<=n+5;++i) sum[i]=0;cin>>s;s=" "+s;for(int i=1;i<=n;++i){if(s[i]=='(') sum[i]=sum[i-1]+1;else sum[i]=sum[i-1]-1;}sort(sum,sum+1+n);ll tot=0;for(int i=1;i<=n;++i) tot+=i*(n-i+1);for(int i=1;i<=n;++i) tot+=i*sum[i];for(int i=0;i<=n-1;++i) tot-=(n-i)*sum[i];tot/=2;//cout<<tot<<' ';stack<ll> st;for(int i=1;i<=n;++i){if(s[i]=='(') st.push(i);else{if(st.empty()) continue;int id=st.top();tot-=id*(n-i+1);st.pop();}}cout<<tot<<endl;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t;cin>>t;while(t--)solve();return 0;
}

查看全文

http://www.lryc.cn/news/90453.html