T1：

洛谷

题目大意：

有 \(n\) 个廊桥，\(m_1\) 个一类飞机、\(m_2\) 个二类飞机，贪心原则分配廊桥，问做多能给多少飞机分上廊桥。

思路：

设 \(f_i\) 表示分 \(i\) 个廊桥给一类飞机的最多的飞机，\(g_i\) 表示分 \(i\) 个廊桥给二类飞机的最多的飞机。题目就转化为求最大的 \(f_i+g_{n-i}\)

考场上想的是三分，但是用脚趾都能造出一个卡三分的数据。

实际上可以发现一个飞机只要在 \(x\) 个廊桥的情况下能分配到，那么 \([x,\infty]\) 都能。先用堆求出每个飞机能分配最少需要的廊桥，然后解法显然。

代码：

const int N = 1e5 + 10;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, m1, m2;
struct node {
	int l, r;
	bool operator < (node a) const { return l < a.l; }
} a[N], b[N];
int pa[N], pb[N], ca[N], cb[N];
priority_queue<int, vector<int>, greater<int> > q;
struct pQueue {
	int val, id;
	bool operator < (const pQueue &a) const { return val > a.val; }
};
priority_queue<pQueue> qr;
int suma = 0, sumb = 0, ans;

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = Read(), m1 = Read(), m2 = Read();
	for (int i = 1; i <= m1; i++) 
		a[i].l = Read(), a[i].r = Read();
	for (int i = 1; i <= m2; i++)
		b[i].l = Read(), b[i].r = Read();
	sort (a + 1, a + 1 + m1);
	sort (b + 1, b + 1 + m2);
	
	for (int i = 1; i <= n; i++) q.push(i);
	for (int i = 1; i <= m1; i++) {
		if (!qr.empty())
			for (pQueue j = qr.top(); j.val < a[i].l && !qr.empty(); ) {
				qr.pop();
				q.push(j.id);
				if (!qr.empty()) j = qr.top();
			}
		if (!q.empty()) {
			pa[i] = q.top();
			ca[pa[i]]++;
			qr.push((pQueue){a[i].r, pa[i]});
			q.pop();
		}
	}
	for (; !q.empty(); q.pop());
	for (; !qr.empty(); qr.pop());
	for (int i = 1; i <= n; i++) q.push(i);
	for (int i = 1; i <= m2; i++) {
		if (!qr.empty())
			for (pQueue j = qr.top(); j.val < b[i].l && !qr.empty(); ) {
				qr.pop();
				q.push(j.id);
				if (!qr.empty()) j = qr.top();
			}
		if (!q.empty()) {
			pb[i] = q.top();
			cb[pb[i]]++;
			sumb++;
			qr.push((pQueue){b[i].r, pb[i]});
			q.pop();
		}
	}
	
	for (int i = 0; i <= n; i++) {
		suma += ca[i], sumb -= cb[n - i + 1];
		ans = max(ans, suma + sumb);
	}
	printf ("%d\n", ans);
	return 0;
}

T2：

洛谷

思路：

有一个很强的状态 \(f_{l,r,[0,5]}\) 表示在区间 \([l,r]\) 中字符串属于 全部是*、左右为匹配的括号、左括右*、左右不一定匹配的括号、左*右括，左右为*。

这个状态设法不用判重太强了。

转移见代码。

代码：

const int N = 510;
const ll mod = 1e9 + 7;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, m;
char s[N];
ll f[N][N][10];

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = Read(), m = Read();
	scanf ("%s", s + 1);
	for (int i = 1; i <= n; i++) f[i][i - 1][0] = 1;
	for (int len = 1; len <= n; len++) 
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len -  1;
			if (len <= m) f[l][r][0] = f[l][r - 1][0] * (s[r] == '?' || s[r] == '*');
			if (len >= 2) {
				if ((s[l] == '(' || s[l] == '?') && (s[r] == ')' || s[r] == '?'))
					f[l][r][1] = (f[l + 1][r - 1][0] + f[l + 1][r - 1][2] + f[l + 1][r - 1][3] + f[l + 1][r - 1][4]) % mod;
				for (int k = l; k < r; k++)
					(f[l][r][2] += f[l][k][3] * f[k + 1][r][0] % mod) %= mod,
					(f[l][r][3] += (f[l][k][2] + f[l][k][3]) % mod * f[k + 1][r][1] % mod) %= mod,
					(f[l][r][4] += (f[l][k][4] + f[l][k][5]) % mod * f[k + 1][r][1] % mod) %= mod,
					(f[l][r][5] += f[l][k][4] * f[k + 1][r][0] % mod) %= mod;
			}
			f[l][r][3] = (f[l][r][3] + f[l][r][1]) % mod;
			f[l][r][5] = (f[l][r][5] + f[l][r][0]) % mod;
		}
	printf ("%lld\n", f[1][n][3]);
	return 0;
}

T3：

洛谷

思路：

你看它像个栈，那就把它当栈做。没了。

代码：

const int N = 1e6 + 10;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int t, n, sm, em;
int a[N];
char b[N];
int top1, bot1, top2, bot2;

bool Work(int opt = 1) {
	int pos = 0; top1 = top2 = 0, bot1 = bot2 = 1;
	if (opt) {
		for (int i = 2; i <= 2 * n; i++)
			if (a[i] == a[1]) { pos = i; break; } 
		bot1 = 2, top1 = pos - 1, bot2 = pos + 1, top2 = 2 * n;
	} else {
		for (int i = 2 * n - 1; i; i--)
			if (a[i] == a[2 * n]) { pos = i; break; } 
		bot1 = 1, top1 = pos - 1, bot2 = pos + 1, top2 = 2 * n - 1;
	}
	bool flag = 0;
	for (int i = 1; i < n; i++) {
		if (bot1 <= top1 && (a[top1] == a[bot1] && bot1 < top1 || a[bot1] == a[bot2] && bot2 <= top2)) {
			if (bot1 < top1 && a[top1] == a[bot1]) 
				top1--, bot1++, b[++sm] = 'L', b[--em] = 'L';
			else bot1++, bot2++, b[++sm] = 'L', b[--em] = 'R';
		} else {
			if (bot2 <= top2 && (a[top2] == a[top1] && bot1 <= top1 || a[top2] == a[bot2] && bot2 < top2)) {
				if (bot2 < top2 && a[top2] == a[bot2]) 
					top2--, bot2++, b[++sm] = 'R', b[--em] = 'R';
				else top2--, top1--, b[++sm] = 'R', b[--em] = 'L';
			} else return 0;
		}
	}
	printf ("%s\n", b + 1);
	return 1;
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	for (t = Read(); t--; ) {
		n = Read();
		for (int i = 1; i <= 2 * n; i++) a[i] = Read();
		for (int i = 1; i <= 2 * n + 1; i++) b[i] = 0;
		b[sm = 1] = b[em = 2 * n] = 'L';
		if (!Work()) {
			for (int i = 1; i <= 2 * n + 1; i++) b[i] = 0;
			b[sm = 1] = 'R', b[em = 2 * n] = 'L';
			if (!Work(0)) printf ("-1\n");
		}
	}
	return 0;
}

T4：

咕咕咕。