wk , 我三道题全写挂了，愤怒！所以来写总结

T1 廊桥分配

贪心 + 优先队列 + 前缀和

solution

我们设 $f_i$ 为当国内区有 $i$

code

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

const int N = 1e5 + 5;

struct node{
	int a , b , id;
	
	bool operator <(const node &lhs)const &{
		return lhs.b < b;
	}
}p1[N] , p2[N];

int n , m1 , m2 , s1[N] , s2[N] , ans;
priority_queue<node> q;
priority_queue<int , vector<int> , greater<int> > lq;

bool cmp(const node &lhs , const node &rhs){
	return lhs.a < rhs.a;
}

int main(){
	cin >> n >> m1 >> m2;
	
	for(int i = 1 ; i <= m1 ; i ++){
		cin >> p1[i].a >> p1[i].b;
	}
	for(int i = 1 ; i <= m2 ; i ++){
		cin >> p2[i].a >> p2[i].b;
	}
	sort(p1 + 1 , p1 + m1 + 1 , cmp);
	sort(p2 + 1 , p2 + m2 + 1 , cmp);
	
	for(int i = 1 ; i <= n ; i ++) lq.push(i);
	for(int i = 1 ; i <= m1 ; i ++){
		while(!q.empty() && p1[i].a > q.top().b){
			lq.push(q.top().id);
			q.pop();
		}
		if(lq.empty()) continue;
		s1[lq.top()] ++; p1[i].id = lq.top(); lq.pop();
		q.push(p1[i]);
	}
	while(!q.empty()) q.pop();
	while(!lq.empty()) lq.pop();
	
	for(int i = 1 ; i <= n ; i ++) lq.push(i);
	for(int i = 1 ; i <= m2 ; i ++){
		while(!q.empty() && p2[i].a > q.top().b){
			lq.push(q.top().id);
			q.pop();
		}
		if(lq.empty()) continue;
		s2[lq.top()] ++; p2[i].id = lq.top(); lq.pop();
		q.push(p2[i]);
	}
	
	for(int i = 1 ; i <= n ; i ++) s1[i] += s1[i - 1];
	for(int i = 1 ; i <= n ; i ++) s2[i] += s2[i - 1];
	for(int i = 0 ; i <= n ; i ++){
		ans = max(ans , s1[i] + s2[n - i]);
	}
	cout << ans;
	return 0;
}

T2 括号序列

区间 dp + dp 优化

solution

code

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

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

ll n , k;
ll dp[N][N][2] , b[N] , f[N][N];
string s;

bool check(int l , int r){
	for(int i = l + 1 ; i <= r - 1 ; i ++){
		if(s[i] != '*' && s[i] != '?') return false;
	}
	return r - l - 1 <= k;
}

int main(){
	cin >> n >> k >> s;
	
	s = " " + s;
	b[n + 1] = n;
	
	for(int i = n ; i >= 1 ; i --){
		if(s[i] == '?' || s[i] == '*'){
			b[i] = min(b[i + 1] , i + k - 1);
		}
		else b[i] = i - 1;
	}
	
	for(ll l = 2 ; l <= n ; l ++){
		for(ll i = 1 ; i <= n - l + 1 ; i ++){
			ll j = i + l - 1;
			
			if((s[i] != '(' && s[i] != '?') || (s[j] != ')' && s[j] != '?')){
				f[i][j] = f[i + 1][j];
				continue;
			}
			if(check(i , j)) dp[i][j][0] = 1;
			
			dp[i][j][0] += dp[i + 1][j - 1][0] + dp[i + 1][j - 1][1];
			
			for(int p = i + 1 ; p <= min(b[i + 1] , j - 2) ; p ++){
				dp[i][j][0] += dp[p + 1][j - 1][0] + dp[p + 1][j - 1][1];
			}
			for(int p = j - 1 ; p >= i + 2 ; p --){
				if(j - 1 > b[p]) break;
				dp[i][j][0] += dp[i + 1][p - 1][0] + dp[i + 1][p - 1][1];
			}
			for(int p = i ; p < j ; p ++){
				if(s[p] == ')' || s[p] == '?'){
					dp[i][j][1] += dp[i][p][0] * (f[p + 1][j] - f[min(b[p + 1] + 2 , j)][j] + mod) % mod;
				}
			}
			dp[i][j][0] %= mod;
			dp[i][j][1] %= mod;
			f[i][j] = (f[i + 1][j] + dp[i][j][0] + dp[i][j][1]) % mod;
		}
	}
	cout << (dp[1][n][0] + dp[1][n][1]) % mod;
	return 0;
}

T3 回文

队列 + 构造 + 贪心

solution

code

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

const int N = 1e6 + 5;

int t , n;
int a[N] , q1[N] , q2[N];

bool solve_(int x){
	vector<int> ans , s;
	
	int id = 0 , l1 = 1 , l2 = 1 , r1 = 0 , r2 = 0;
	if(x == 1){
		ans.push_back(1);
		s.push_back(1);
	}
	else{
		ans.push_back(2);
		s.push_back(1);
	}
	for(int i = 1 ; i <= 2 * n ; i ++){
		if(x == i) continue;
		if(a[x] == a[i]){
			id = i; break;
		}
	}
	for(int i = 1 ; i < id ; i ++){
		if(x == i) continue;
		q1[++ r1] = a[i];
	}
	for(int i = 2 * n ; i > id ; i --){
		if(x == i) continue;
		q2[++ r2] = a[i];
	}
	
	while(l1 <= r1 || l2 <= r2){
		if(l1 < r1 && q1[l1] == q1[r1]){
			ans.push_back(1); s.push_back(1);
			l1 ++ , r1 --;
		}
		else if(l1 <= r1 && l2 <= r2 && q1[l1] == q2[r2]){
			ans.push_back(1); s.push_back(2);
			l1 ++ , r2 --;
		}
		else if(l2 <= r2 && l1 <= r1 && q2[l2] == q1[r1]){
			ans.push_back(2); s.push_back(1);
			l2 ++ , r1 --;
		}
		else if(l2 < r2 && q2[l2] == q2[r2]){
			ans.push_back(2); s.push_back(2);
			l2 ++ , r2 --;
		}
		else return false;
	}
	reverse(s.begin() , s.end());
	for(auto u : ans){
		if(u == 1) cout << 'L';
		if(u == 2) cout << 'R';
	}
	for(auto u : s){
		if(u == 1) cout << 'L';
		if(u == 2) cout << 'R';
	}
	return true;
}

void solve(){
	cin >> n;
	
	for(int i = 1 ; i <= 2 * n ; i ++){
		cin >> a[i];
	}
	if(solve_(1)) return;
	else if(!solve_(2 * n)) cout << -1;
}

int main(){
	cin >> t;
	
	while(t --){
		solve();
		cout << '\n';
	}
	return 0;
}