【CF补题】【ABC】Educational Codeforces Round 125

——————————————————————————————————————————

【题目】a[0]=0

要满足a[i]<=B,求a[0~n]的最大值

【解答】模拟贪心，当且仅当采用+ *** 作过大时才使用- *** 作

#include
using namespace std;
long long a, ans;
int n,b,x,y;
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n >> b >> x >> y;
		a = 0;
		ans = 0;
		int mx=b-x;
		for (int i = 1; i <= n; i++)
		{
			if (a <= mx)a = a + x; else a = a - y;
			ans += a;
		}
		cout << ans << '\n';
	}
	return 0;
}

 ——————————————————————————————————————————

【题目】

 【解答】首先排除暴力。

在判断回文时要注意（）不是回文！  ））才是！

然后观察发现，（）是符合常规的，((,))这两个都是回文串，那么只有在出现)(时需要判断。

然后，当开头是)(时，只要后面再出现一个），形成1000...0001，又是一个回文串，可以全部删除。

那么这题就很明朗了。

如果开头是（那么前缀全部删除，开头是）就压栈等到下一个）后全部清除，用vector

ps:题中说了“最短前缀”所以不用考虑出现100010001这种情况

#include
using namespace std;
long long a, ans;
int n,b,x,y;
string s;

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		vectorv;
		ans = 0;
		cin >> n >> s;
		for (int i = 0; i < n; i++)
		{
			v.push_back(s[i]);
			if (v.size() > 1)
			{
				if (*(v.begin()) == '(' || *(v.begin()) == v.back())
				{
					v.clear();
					ans++;
				}
			}
		}
		cout << ans << ' ' << v.size() << '\n';
	}
	return 0;
}