1.廊桥分配

题目链接

题目大意：

有n个廊桥，m1个国际航班和m2个国内航班。每个航班降落时，可以停靠在廊桥上。停靠方式为先到先得，若廊桥没有空余时，则当前到达的航班只能停靠到远站区。给定每个航班降落的时间和离开的时间，问如何分配国际航班和国内航班的廊桥数，使得尽量多的航班可以停靠到廊桥上。

数据范围：

$n\le 10^5,m1+m2\le 10^{5}n\; \backslash leq\; 10^5\; ,\; m1\; +\; m2\; \backslash leq\; 10^5$

思路：

题目中的停靠方式为先到先得，因此停靠的策略就是若有空余廊桥，那么当前的航班就给停靠，而不考虑该航班一共会停靠多久。

因此若不考虑廊桥的数量，对于国际航班和国内航班，一共需要多少廊桥是可以计算的。这显然可以用一个贪心来解决：

由于两种航班相互独立。我们仅考虑国内（国际同理）：

先对航班按照降落时间进行升序排序。枚举国内航班，若当前航班到达时，之前的航班可以离开，则离开。否则将其停靠到一个廊桥上。期间可以用一个变量来记录当前需要的廊桥的最大数量。

如果仅有上面的思路，是不足以解决本题。但是如果我们更进一步地思考，可以发现借助上面的贪心，我们只需多维护一下每个航班用到的廊桥编号，就可以解决本题。

在上面的贪心中，我们更进一步地将廊桥进行编号，同时记录每个航班可以停靠的廊桥编号。根据贪心思想，我们可以模拟一样样例1：

3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16

① 航班(1,5)到达，分配停靠廊桥1；

② 航班（3,8）到达，到达时间3，航班①还未离开，分配停靠廊桥2；

③ 航班（6,10）到达，到达时间6，航班① 离开，分配停靠廊桥1；

④ 航班（9,14）到达，到达时间9，航班②离开，分配停靠廊桥2；

⑤航班（13,18）到达，到达时间13，航班③离开，分配停靠廊桥1.

可以发现对该样例，只需2个廊桥，若只给1个廊桥，那么其中航班①③⑤可以停靠，②④不行。

那么我们可以开一个前缀和数组来记录，sum[i]表示分配i个廊桥的最多航班停靠数。上例中sum[0]=0,sum[1]=3,sum[2]=5

类似的我们计算国际航班，也求出一个前缀和数组。

只需要枚举给国内航班的廊桥数k，国际航班就是n-k。求两个前缀和数组的最大和就可以了。

在上述的过程中，为了快速计算当前航班到达时，有哪些航班可以离开。我们需要一个优先队列来维护航班离开时间。

总复杂度为$O(nlogn)O(nlogn)$

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,m1,m2,sum1[maxn],sum2[maxn];
struct node{
    int a,b,val;
    bool operator < (const node &B)const{
        return b > B.b;
    }
}g1[maxn],g2[maxn];
bool cmp (node A, node B){
    return A.a < B.a;
}
priority_queue< node >pri;     //维护一个离开时间越小优先级越高的优先队列
priority_queue< int ,vector<int> , greater<int> >qp;    //再开一个队列维护当前空余的廊桥的最小编号


int main()
{
    cin >> n >> m1 >> m2;
    for ( int i = 1; i <= m1; i++){
        cin >> g1[i].a >> g1[i].b;
    }
    for ( int i = 1; i <= m2; i++){
        cin >> g2[i].a >> g2[i].b;
    }
    sort ( g1 + 1 , g1 + 1 + m1, cmp);    //先按到达时间升序排序
    sort ( g2 + 1 , g2 + 1 + m2, cmp);
     
    for ( int i = 1; i <= m1 + m2; i++)qp.push(i);
    for ( int i = 1; i <= m1; i++){
        while( !pri.empty() && pri.top().b <= g1[i].a){
            qp.push(pri.top().val);
            pri.pop();
        }
        int k = qp.top();
        qp.pop();
        sum1[k]++;
        g1[i].val = k;
        pri.push(g1[i]);
    }
    for ( int i = 1; i <= n; i++) sum1[i] += sum1[i-1];    //求前缀和
    
    while(!pri.empty())pri.pop();
    while(!qp.empty())qp.pop();
    
    for ( int i = 1; i <= m1 + m2; i++)qp.push(i);
    for ( int i = 1; i <= m2; i++){
        while( !pri.empty() && pri.top().b <= g2[i].a){
            qp.push(pri.top().val);
            pri.pop();
        }
        int k = qp.top();
        qp.pop();
        sum2[k]++;
        g2[i].val = k;
        pri.push(g2[i]);
    }
    for ( int i = 1; i <= n; i++) sum2[i] += sum2[i-1];
    
    int maxi = 0;
    for ( int i = 0; i <= n; i++) maxi = max(maxi,sum1[i] + sum2[n-i]);   //暴力枚举答案
    cout << maxi <<endl;
    return 0;
}

小结：

作为第一题，重在思维的考查，只能说csp的难度在上升。

代码知识点上来看，主要涉及的是优先队列和前缀和的使用。如果理清思路，程序编写起来是不复杂的。

但是要注意优先队列的使用，对于一些结构体重载等操作，可以在考前再去复习一遍。

3.回文

题目链接

题目大意：

给定一个长度为$2\ast n2\; *\; n$的序列，里面由[1,n]的元素构成，每个元素出现2次。

现在有$2\ast n2\; *\; n$次操作，每次操作可以从序列的左端或者右端取出一个元素放到B数组中。

问能否将B数组中的元素放置成回文的序列。

数据范围：

$n\le 5\ast 10^{5}n\; \backslash leq\; 5\; *\; 10^5$

思路：

作为T3，难度虽然不算低，但是应该是比T2要低。

首先可以发现，第一个元素只有2种选择，L或者R。

假设选择了L，即选择了a1，那么我们可以确定好a1的另一个出现的位置ax，这里满足$a_1==a_{x}a\_1\; ==\; a\_x$

显然$a_{x}a\_x$是最后被取的，拿走a1和$a_{x}a\_x$以后，我们把剩下的元素分成两部分：

① $[2,x-1][2,x-1]$

② $[x+1,2\ast n][x+1,2\; *\; n]$

由于$a_{x}a\_x$是最后拿的，因此①中的元素拿走都属于L，②中的元素拿走都属于R。

为了保证拿走元素的顺序不被破坏，我们分别将①②两个部分的元素放到两个不同的双端队列中。

例如样例1：

5

4 1 2 4 5 3 1 2 3 5

先取出$a_{1}a\_1$，剩余两部分为[2,3]和[5,10]。

根据题意限制，我们接下来取元素只能在队列1的左端和队列2的右端获取。

若在在队列1的左端获取a2，那么a2对应的$a_{y}a\_y$出现的位置，无法在两个队列的中间。即：y必须出现在队列1的右端，或者出现在队列2的左端。(为了保持回文，当前取到的元素，在回文串中另一个位置必须是最晚被获取)

至此，我们的解决方案就已经出来了，对当前队列进行分类讨论：

每次取2个元素，一个表示当前要获取的第bi个元素，另一个表示回文对应的$b_{2n-i+1}b\_\{2n-i+1\}$的元素。这两个元素数值相同，并且必须在同一个队列的首尾，或者一个队首一个队尾。否则就是无解。

为了保证字典序最小，每获取2个元素我们依次判断LL，LR，RL，RR是否可行。只要有一个可行，就不必去看其他情况。

由于每个元素只会出队1次，总复杂度为O(n)

代码：

using namespace std;
const int maxn = 500005;
int n,m;
int a[2*maxn];
int ed1, ed2;
char ans[2*maxn];
deque<int>dq1, dq2;
int solve(int k){
    dq1.clear();dq2.clear();
    if(k == 1)m = ed1, ans[1] = 'L';
    else m = ed2, ans[1] = 'R';
    
    ans[2*n] = 'L';
    
    for (int i = 3 - k; i < m; i++)dq1.push_back(a[i]);
    for (int i = m + 1; i <= 2*n - k + 1; i++)dq2.push_back(a[i]);
    
    int L = 2, R = 2*n-1;
    while(!dq1.empty() || !dq2.empty()){
        if(dq1.size() >= 2 && dq1.front() == dq1.back()){
            ans[L] = 'L'; ans[R] = 'L';
            dq1.pop_front();dq1.pop_back();
            L++; R--;
        }
        else if(dq1.size() && dq2.size() && dq1.front() == dq2.front()){
            ans[L] = 'L'; ans[R] = 'R';
            dq1.pop_front();dq2.pop_front();
            L++; R--;
        }
        else if(dq1.size() && dq2.size() && dq1.back() == dq2.back()){
            ans[L] = 'R'; ans[R] = 'L';
            dq1.pop_back();dq2.pop_back();
            L++; R--;
        }
        else if(dq2.size() >= 2 && dq2.front() == dq2.back()){
            ans[L] = 'R'; ans[R] = 'R';
            dq2.pop_front();dq2.pop_back();
            L++; R--;
        }
        else return -1;
    }
    return 0;
}
int main()
{
    int T;
    cin >> T;
    while (T--){
        cin >> n;
        ans[2*n + 1]='\0';
        for (int i = 1; i <= 2*n; i++)scanf("%d",&a[i]);
        for (int i = 2; i <= 2*n; i++){
            if(a[i] == a[1])ed1 = i;
        }
        for (int i = 1; i < 2*n; i++){
            if(a[i] == a[2*n])ed2 = i;
        }
        if(solve(1) == -1){
            if(solve(2) == -1)cout << -1 << endl;
            else cout << ans + 1 << endl;
        }
        else cout <<ans + 1 << endl;
    }
    return 0;
}

小结：

本题主要是贪心思想和双端队列的使用，如果不熟悉STL中的双端队列，也可以手动模拟。关键是对问题的转化，难度上来说，我认为与T1相当。