Regular Bracket Sequences

队列模拟

#include<bits/stdc++.h>
using namespace std;

int main(){
   
    ios::sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--){
   
        int n;
        cin >> n;
        
        queue<char> a;
        queue<char> b;
        
        for (int i = 1; i <= n;i++){
   
            for (int j = 0; j < n;j++){
   
                        a.push('(');
                        b.push(')');
                    }
            queue<char> q;
            int na = 1;
            q.push(a.front());
            a.pop();
            for (int j = 1; j < 2 * n; j++){
   
                if(a.empty()){
   
                    q.push(b.front());
                    b.pop();
                    continue;
                }
                if(i==na){
   
                    q.push(b.front());
                    b.pop();
                    na--;
                }else{
   
                    na++;
                    q.push(a.front());
                    a.pop();
                }
            }
            for (int i = 0; i < 2 * n;i++){
   
                char c = q.front();
                cout << c;
                q.pop();
            }
            cout << "\n";
        }
    }
    return 0;
}

Combinatorics Homework

理解题意很关键
up和down 考虑最特殊的情况成立就好
题中关键：

大意为：AAA也成立，记为m=2;(坑了我半个小时)

#include<bits/stdc++.h>
using namespace std;
int t;
int main()
{
   
	cin >> t;
	while (t--)
	{
   
		int x[3];
		int m;
        cin >> x[0] >> x[1] >> x[2] >> m;
        int up = x[0] + x[1] + x[2] - 3;
        sort(x + 0, x + 3);
        int down = x[2] - x[1] - x[0] - 1;
        if (m <= up && m >= down)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
	return 0;
}

Slay the Dragon

使用lower_bound（）找位置
注意两种情况分类返回最小值：

• check(sum, pos)//满足攻击值的士兵，剩余士兵防御，总金币数
• check(sum, pos-1)//不满足攻击值的士兵，用金币补齐，剩余士兵防御，总金币数

注意:

• 数据范围，用 long long
• 与数据流读入数据的时间是否会超时，关闭数据流同步

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 5;
ll n, m, a[N], sum, def, att;
const ll inf = 7e18;
 
ll check(ll tem,int pos)
{
   
	if (pos == 0) return inf;
	ll ans = 0;
	if (a[pos] < def)
        ans += (def - a[pos]);
    tem -= a[pos];
	if (tem < att) {
   
		ans += (att - tem);
	}
	return ans;
}
 
int main()
{
   
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
   
		cin >> a[i];
		sum += a[i];
		if (sum >= inf || sum < 0) sum = inf;
	}
	cin >> m;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= m; i++)
	{
   
		ll ans = 0;
		cin >> def >> att;
		int pos = lower_bound(a + 1, a + n + 1, def) - a;
		if (a[pos] == 0) {
   
			ans += (def - a[n]);
			if (att > sum - a[n]) {
   
				ans += (att - sum + a[n]);
			}
		}
		else {
   
			ans = min(check(sum, pos), check(sum, pos - 1));
		}
		cout << ans << endl;
	}
	return 0;
}