CSP-S 2021 补题

P7913 [CSP-S 2021] 廊桥分配

考虑对于国际航班和国内航班单独进行分配

对于国际航班 处理 \(res1[i]\) 数组作为给国际航班分配 \(i\) 个廊桥的最大飞机停靠数量 \(res2[i]\) 同理

对于每一种类的航班 我们维护一个 \(in\) 优先队列和一个 \(left\) 优先队列

\(in\) 队列中放所有现在停靠在廊桥里的飞机(记录离港时间和使用廊桥编号) \(left\) 是剩余的廊桥编号

那么显然我们可以将

最后对于 \(res\) 数组分别做前缀和即可

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define inl inline
#define eb emplace_back
#define endl '\n'
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define print(x) cerr<<#x<<'='<<x<<endl
#define getchar() cin.get()
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

int read()
{
	int x = 0 , f = 1;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

int n , m1 , m2 , res1[N] , res2[N] , ans;

struct node { int l , r; friend bool operator < ( const node &a , const node &b ) { return a.l < b.l; } } a[N] , b[N];

void solve ( node * a , int m , int * res )
{
    priority_queue < pii , vector<pii> , greater<pii> > in;
    priority_queue < int , vector<int> , greater<int> > left;
    for ( int i = 1 ; i <= n ; i ++ ) left.push(i);
    for ( int i = 1 ; i <= m ; i ++ )
    {
        while ( !in.empty() && a[i].l >= in.top().fi ) left.push ( in.top().se ) , in.pop();
        if ( left.empty() ) continue;
        ++ res[left.top()];
        in.push ( { a[i].r , left.top() } );
        left.pop();
    }
    for ( int i = 1 ; i <= n ; i ++ ) res[i] += res[i-1];
}

signed main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
    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 + m1 + 1 ) , sort ( b + 1 , b + m2 + 1 );
    solve ( a , m1 , res1 ) , solve ( b , m2 , res2 );
    for ( int i = 0 ; i <= n ; i ++ ) ans = max ( ans , res1[i] + res2[n-i] );
    cout << ans << endl;
    return 0;
}

P7915 [CSP-S 2021] 回文

我们首先找到唯一的点使得 \(a[1]=a[pos1]\) \(a[pos2]=a[2*n]\)

相当于是枚举第一个点到底应该是左还是右 并确定最后一个点的位置 下面以第一个操作为左操作为例 右操作是一样的

那么我们对于 \([1,pos1-1]\) 和 \([pos1+1,2*n-1]\) 来进行处理

将第一个栈的栈顶或第二个栈的栈顶 和第一个栈的栈底或第二个栈的栈底来进行匹配

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define inl inline
#define eb emplace_back
#define endl '\n'
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
#define print(x) cerr<<#x<<'='<<x<<endl
#define getchar() cin.get()
const int N = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;

int read()
{
	int x = 0 , f = 1;
	char ch = getchar();
	while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
	while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
	return x * f;
}

int n , a[N] , cnt , vis[N] , pos1 , pos2;

char res[N];
int check ( int l1 , int r1 , int l2 , int r2 )
{
    for ( int i = 1 ; i <= n - 1 ; i ++ )
    {
        if ( l1 <= r1 && ( ( l2 <= r2 && a[l1] == a[l2] ) || ( l1 < r1 && a[l1] == a[r1] ) ) )
        {
            if ( l1 < r1 && a[l1] == a[r1] ) res[i] = 'L' , res[2*n-2-i+1] = 'L' , ++ l1 , -- r1;
            else res[i] = 'L' , res[2*n-2-i+1] = 'R' , ++ l1 , ++ l2;
        }
        else if ( l2 <= r2 && ( ( l1 <= r1 && a[r1] == a[r2] ) || ( l2 < r2 && a[l2] == a[r2] ) ) )
        {
            if ( l1 <= r1 && a[r1] == a[r2] ) res[i] = 'R' , res[2*n-2-i+1] = 'L' , -- r1 , -- r2;
            else res[i] = 'R' , res[2*n-2-i+1] = 'R' , ++ l2 , -- r2;
        }
        else return 0;   
    }
    return 1;
}
/*
2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3
*/

signed main ()
{
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
    int T = read();
    while ( T -- )
    {
        memset ( res , 0 , sizeof res );
        n = read();
        for ( int i = 1 ; i <= 2 * n ; i ++ ) a[i] = read();
        for ( int i = 2 ; i <= 2 * n ; i ++ ) if ( a[i] == a[1] ) { pos1 = i; break; }
        for ( int i = 1 ; i < 2 * n ; i ++ ) if ( a[i] == a[2*n] ) { pos2 = i; break; }
        if ( check ( 2 , pos1 - 1 , pos1 + 1 , 2 * n ) ) cout << "L" << res + 1 << "L" << endl;
        else if ( check ( 1 , pos2 - 1 , pos2 + 1 , 2 * n - 1 ) ) cout << "R" << res + 1 << "L" << endl;
        else cout << -1 << endl;
    }
    return 0;
}