T0

昨天BLOG又吃掉了一题的内容，并且它还懂得如何把它拼起来不露出破绽（手动赞扬）。
刚才写的时候Markdown还没炸，现在又双叒叕炸了。

T1

题意

给定 n 个区间 ，两个区间 [l_i,r_i][l_j,r_j] 不交当且仅当 l_i \le r_i 或 l_j \le r_j。你需要选出尽可能多对区间，满足每对区间都不交，一个区间只能被选一次。（一对区间是两个）

考场

第一眼：肯定贪心，然后按右端点排序后，用双指针模拟就可以了。
(15mins后)
诶不对，大样例过不去了，肯定是排序规则有问题。
(1h后，试尽了所有的排序方法)
排序方法都不能保证正确性，那就都来一遍吧（气急败坏）。
考场喜提20pts 。

正解

的确，通过1h的尝试后，我们发现似乎什么排序方法，其实都有缺点。
比如对于这组样例:

3
1 1
2 2
3 3
2 3

如果按右端点排序再用双指针，无论怎样，答案都会是1，但通过人肉模拟，我们知道答案是2。
所以我们要承认一个事实，程序的确会错误匹配，但是我们可以纠正，接下来你会发现，正解其实就运用了这种思想。
将所有区间按 l 从小到大排序，一个一个贪心加入，加入的时候有两种情况：

1. 之前的区间中存在未匹配的区间，且可以跟当前区间匹配。由于之后的区间的 l 都不会小于当前区间的 l，我们随便选择一个区间跟当前区间匹配即可。
2. 找不到可以跟当前区间匹配的未匹配的区间。我们在已经匹配的区间对 (i,j) 中找到 r_j 最小的一个区间对，如果 r_j 比当前区间的 r 小，我们可以交换这两个区间，让 i 跟当前区间匹配，把 j 变成未匹配区间。

怎么理解上面两句话呢？

(图例解释：序列中的数字代表右端点，如果一个数字有两种颜色，则代表是一个匹配对)
我们还是以上面的样例作为例子。
我们定义两个堆， unmatch 和 match ，分别代表未匹配的区间和已经匹配的区间对（队列中均为右端点）。
-首先将第一段加入未匹配队列中。
-然后第二段来了，发现其可以与第一段匹配，于是成为匹配对，加入匹配队列中。
-然后第三段来了，发现未匹配序列为空，但其可以与第一段匹配，就将第二段踢出进入未匹配队列，自己与第一段加入匹配队列。
-最后是第四段，发现其可以与第二段匹配，成为匹配对，加入匹配队列中。
所以最后答案是2。
到这里，思路就很明朗了。

CODE

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5;
typedef pair<int,int>PII;
#define l first
#define r second
PII seg[N];
priority_queue<int,vector<int>,greater<int> >unmatch,match;
int n;
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&seg[i].l,&seg[i].r);
    sort(seg+1,seg+n+1);
    for(int i=1;i<=n;i++)
    {
        if(!unmatch.size()||unmatch.top()>=seg[i].l)
        {
            if(!match.size()||match.top()>=seg[i].r)unmatch.push(seg[i].r);
            else
            {
                unmatch.push(match.top());
                match.pop();
                match.push(seg[i].r);
            }
        }
        else
        {
            unmatch.pop();
            match.push(seg[i].r);
        }
    }
    printf("%d\n",match.size());
    return 0;
}

到这里字数统计就已经超过1k了。
NFLS你是不是在培养宇航员啊！

T2

原题链接
（注：在此题中操作次数要 \le 6000）
还是挺新的题目，也真的不是人可以做的。

考场

存在 k_0=1 的情况？这不 O(n^3) 暴力？
然后出题人临时修改数据点就获得了0pts的好成绩。

正解

如果从小到大处理每个 i ，设 p 为 i 当前的位置，则操作 [i,p] 或 (i,p] ，发现容易超时，原因是操作后 i 只会变到 \frac{i+p}{2} 的位置。
因此我们考虑对原排列的逆排列排序，且只能使用原操作的逆操作，最后将操作序列倒序输出。
现在要考虑如何将 i 移到 n 。

1. $2 \cdot i \le n$，操作 $(1,2 \cdot i)$
2. 剩下情况，操作 (2 \cdot i-n+1, n)

操作其实就是一个模拟。
TIPS:

1. 为防止出题人构造数据卡掉，因此应在开始操作前先随机 100-200 次操作用于打乱数组。
2. 在最后一个子任务中可能会出现就算随机依然操作数量大于 6000 的情况，此时需要像模拟退火一样，整个算法再跑一次。

CODE

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=3005;
vector<PII>res;
int n,a[N],Y[N],pos[N],tmp[N];
void Trans(int l,int r)
{
    res.push_back({l,r});
    for(int i=l;i<=r;i++)tmp[i]=pos[i];
    int i,j;
    for(i=l,j=l+1;j<=r;i++,j+=2)pos[j]=tmp[i];
    for(j=l;j<=r;i++,j+=2)pos[j]=tmp[i];
    for(int i=l;i<=r;i++)a[pos[i]]=i;
}
void RANDOM()
{
    int l=rand()%n+1,r=rand()%n+1;
    Trans(min(l,r),max(l,r));
}
void work(int x)
{
    int cnt=0;
    for(int i=a[x];i<x;i=a[x])
    {
        if(i*2<=x)Trans(1,i*2);
        else Trans(i*2-x+1,x);
    }
}
int main()
{
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    srand(time(0));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&Y[i]);
    do
    {
        res.clear();
        for(int i=1;i<=n;i++)
        {
            a[i]=Y[i];
            pos[a[i]]=i;
        }
        for(int i=1;i<=105;i++)RANDOM();
        for(int i=n;i;i--)work(i);
    }
    while(res.size()>6000);
    printf("%d\n",res.size());
    for(int i=res.size()-1;~i;i--)printf("%d %d\n",res[i].first,res[i].second);
    return 0;
}

再次感叹NFLS的出题套路深。

T3

原题链接
无法理解

T4

无法理解

T5

DP入门+莫队乱搞完哩~