A. Regular Bracket Sequences

题意：给出n，输出n个长度为2n的合法括号序列

分析：正常输出所有括号序列，然后统计个数，在输出n个后停止，dfs爆搜，搜的时候三个变量，当前以及存储到符号个数，当前输出到第几个左括号，第几个右括号，当左括号没达到n就可以走左括号，同时右括号允许值++，当右括号有值可以走右括号，右括号数目--

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

typedef long long ll; 
typedef pair<int, int> PII;

const int N = 3e5 + 10, mod = 1e9 + 7;

int n, m, t, k;

int cnt = 0;

int s[N], dp[N], f[N];
char g[N];

string str;

vector<int> vec;

void dfs(int a, int b, int c)
{
	if (a == 2 * n)
	{
		for (int i = 0; i < 2 * n; i++)
		{
			if (s[i] == 1) printf("(");
			else printf(")");
		}printf("\n");
		cnt++;
		return;
	}
	if (b < n)
	{
		s[a] = 1;
		dfs(a + 1, b + 1, c + 1);
		if (cnt == n) return;
	}
	if (c)
	{
		s[a] = -1;
		dfs(a + 1, b, c - 1);
		if (cnt == n) return;
	}
}

void solve()
{
	cnt = 0;
	cin >> n;
	dfs(0, 0, 0);
}

int main()
{
    t = 1;
    cin >> t;
    while(t--) 
        solve();
    return 0;
}

B. Combinatorics Homework

题意：给定a，b，c三种字符的数目和相邻数d，询问是否存在相同字符相邻的情况数为d，保证字符数存在，是输出YES，否则输出NO

分析：显然在任意排列的情况下，存在最小相邻和最大相邻数，答案在这两者间必定可以存在，最小相邻数就是把字符数少的两个交错往最长的里面差，差完还不够的话就没办法了，3个字符可以拆分4个字符，所以最小相邻数就是s[2]-(s[0]+s[1]+1),负数显然不可能，最小是0，而最大就是直接排，不交叉，答案就是三者字符数-3。

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

typedef long long ll; 
typedef pair<int, int> PII;

const int N = 3e5 + 10, mod = 1e9 + 7;

int n, m, t, k;

int cnt = 0;

int s[N], dp[N], f[N];
char g[N];

string str;

vector<int> vec;

void solve()
{
	cin >> s[0] >> s[1] >> s[2] >> n;
	sort(s, s + 3);
	int l = max(s[2] - (s[0] + s[1] + 1), 0);
	int r = s[0] + s[1] + s[2] - 3;
	if (n >= l && n <= r) puts("YES");
	else puts("NO");
}

int main()
{
    t = 1;
    cin >> t;
    while(t--) 
        solve();
    return 0;
}
 

C. Slay the Dragon

题意：n个勇者，每个勇者有自己的能力值，多次任务相对独立，每次给出一条龙的攻击力和防御力，要去出站的一个勇者的能力值>=龙的防御力，剩余勇者的能力值之和要大于龙的攻击力，可以进行任意次操作让任意勇者的能力值提升1点，询问每次完成任务，操作次数最少为多少

分析：考虑到最少，勇者之间互不影响，我们可以找到第一个能力值>=龙的防御值的勇者排他出任务，或者找一个能力值比龙的防御值小的前提下能力值最大的勇者，让他去出任务，答案只会是这两种，否则都绝对会多浪费勇者的能力值

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

typedef long long ll; 
typedef pair<int, int> PII;

const int N = 3e5 + 10, mod = 1e9 + 7;

int n, m, t, k;

int cnt = 0;

ll s[N], dp[N], f[N];
char g[N];

string str;

vector<int> vec;

void solve()
{
	cin >> n;
	ll sum = 0;
	for (int i = 0; i < n; i++) 
		scanf("%lld", &s[i]), sum += s[i];
	s[n++] = 1e18;
	sort(s, s + n);
	cin >> m;
	while (m--)
	{
		ll a, b, c;
		scanf("%lld %lld", &a, &b);
		c = lower_bound(s, s + n, a) - s;
		if (c == n - 1)
		{
			printf("%lld\n", a - s[n-2] + max(0ll, b - (sum - s[n-2])));
		}
		else
		{
			ll ans = 0;
			if (sum - s[c] > b) ans = 0;
			else ans = b - (sum - s[c]);
			if (c)
			{
				ll ans1 = a - s[c-1] + max(0ll, b - (sum - s[c-1]));
				ans = min(ans, ans1);
			}
			printf("%lld\n", ans);
		}
	}
}

int main()
{
    t = 1;
//    cin >> t;
    while(t--) 
        solve();
    return 0;
}

D. The Strongest Build

题意：有不超过10个装备栏，每个装备栏有不超过2e5件装备可以挑选，现按提升的攻击力从小到大已经排好序，给出m个不合法的情况数，每行有n个装备栏的装备位置，表示这些位置上的装备不能同时选，m<=1e5

分析：爆搜，每回最多分十次，在去重状态下，最多只有1e6种情况，用map建立vector到int的映射来直接判定合不合法，如果当前状态被禁止，那么就找下十个储存，放优先队列中，用pair第一维是sum，第二维是vector的答案，因为放优先队列中，如果合法那必定是答案的一种，输出即可，过程中容易爆内存，所以要用set存放vector，来判定当前这个vector存不存在，不存在才能往进放

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>
#include <set>

#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

typedef long long ll; 
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<int, vector<int> > PIV;

const int N = 2e5 + 10, mod = 1e9 + 7, p = 13331;

int n, m, t, k;

int cnt = 0;
int f[N];
vector<vector<int> > s;

map<vector<int>, int> ma;

vector<int> vec, ve;

priority_queue<PIV> q;

set<vector<int> > st;

void solve()
{
	int sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> m;
		vec.push_back(m);
		ve.clear();
		ve.push_back(0);
		for (int j = 1; j <= m; j++)
		{
			int a;
			scanf("%d", &a);
			ve.push_back(a);
		}
		s.push_back(ve);
		sum += s[i][m];
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		ve.clear();
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &f[j]);
			ve.push_back(f[j]);
		}
		ma[ve] = 1;
	}
	q.push({sum, vec});
	sum = 0;
	while (q.size())
	{
		int ans = q.top().first;
		ve = q.top().second;
		q.pop();
		if (ma[ve] == 1)
		{
			for(int i = 0; i < n; i++)
			{
				if (ve[i] > 1)
				{
					int a = s[i][ve[i]];
					ve[i]--;
					int b = s[i][ve[i]];
					if (!st.count(ve))
					{
						q.push({ans - a + b, ve});
						st.insert(ve);
					}
					ve[i]++;
				}
			}
			continue;
		}
		for (int i = 0; i < ve.size(); i++)
		{
			if (i) printf(" ");
			printf("%d", ve[i]);
		}printf("\n");
		break;
	}
}

int main()
{
    t = 1;
//    cin >> t;
    while(t--) 
        solve();
    return 0;
}