建网站多少钱?,wordpress登录页面空白页,网站如何在百度搜索,萝岗区营销型网站建设cf1556Compressed Bracket Sequencex
题意#xff1a;
给你n个数#xff0c;奇数位置上的数表示左括号的数量#xff0c;偶数位置上的数表示右括号的数量。问有多少个[l,r]是满足括号匹配的
题解#xff1a;
括号匹配也算是经典问题了 直接统计不好计算#xff0c;我们…cf1556Compressed Bracket Sequencex
题意
给你n个数奇数位置上的数表示左括号的数量偶数位置上的数表示右括号的数量。问有多少个[l,r]是满足括号匹配的
题解
括号匹配也算是经典问题了 直接统计不好计算我们听过左括号来进行统计 对于每组左括号(即奇数位置上的数算一组)我们向右找遇到左括号就累加遇到右括号就去抵消累加的左括号。这样统计的括号序列不会重复 比如 2 2 1 1 1 1 对应的是
( ( ) ) ( ) ( )
对于第一组位置的左括号统计的括号序列有三种( )
( ( ) )
( ( ) ) ( )
( ( ) ) ( ) ( )
对于第二组( )( ) ( )
对于第三组( )复杂度是O(n2)
代码
// Problem: C. Compressed Bracket Sequence
// Contest: Codeforces - Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 Div. 2)
// URL: https://codeforces.com/contest/1556/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Data:2021-09-01 10:09:04
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
int vec[300000];
int main()
{//rd_test();int n;read(n);for (int i 1; i n; i) {// int x;read(vec[i]);// vec.push_back(x);}ll ans 0;int len n;if (len % 2 1)len--;for (int i 1; i len; i 2) {ll sum vec[i]; //左括号的数量ll L 0;for (int j i 1; j len; j) {if (j % 2 1)L vec[j]; //左括号累加else //处理遇到右括号的情况{ll R vec[j];ll k min(L, R);if (k) {R- k;L- k;if (L 0)ans;}if (R 0) {ll k min(R, sum);R- k;sum- k;ans k;}if (R 0)//如果有多的右括号break;}}printf(%d%lld\n,i, ans);}printf(%lld\n, ans);//Time_test();
}
