泉一集训DAY2

今天没时间了，放过博客（不整活了）
视频讲解

T1 赛时打dfs骗到 20。试图打正解的都挂了。正解是贪心，但赛时集一个机房的智慧也没搞出来。
正解采用了一种很神奇的贪心，它通过对贪心前的状态分类并适当更改前面的状态来避免前面的贪心导致的非最优解。也就是说手动解决了后效性。然后贪心就是对的了。这样一来可以用优先队列维护前面的状态并实现转移。代码见下：

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>>x,y;
int n,ans;
struct tni
{
    int l,r;
};
tni a[400005];
int cmp(tni aa,tni bb)
{
    return aa.l<bb.l;
}
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].l>>a[i].r;
    }
    sort(a+1,a+n+1,cmp);
//  for(int i=1;i<=n;i++)
//  {
//      cout<<a[i].l<<" "<<a[i].r<<endl;
//  }
    for(int i=1;i<=n;i++)
    {
        if (!x.empty()&&a[i].l>x.top())
        {           
//          cout<<"AA"<<endl;
            y.push(a[i].r);
            x.pop();
            ans++;
        }           
        else 
        if(!y.empty()&&a[i].r>y.top())
        {
//          cout<<"BB"<<endl;
            x.push(y.top());
            y.pop();
            y.push(a[i].r);
        }        
        else
        {
//          cout<<"BOOM"<<"  "<<i<<endl;
            x.push(a[i].r);
        }           
//      cout<<ans<<endl;
    }
    cout<<ans<<endl;
}

T2 本来打了部分分，然后成绩刚出来时也 70 分了，但出题人改数据，居然把一个子任务给整个删掉了。然后爆 0。正解是找规律每次选择一个位置使那个位置上的数是对的，类似排序算法。然后随机数多次操作防卡（挺玄学的，有一定概率TLE）。
代码见下

#include<bits/stdc++.h>
using namespace std;
int n,a[300005],b[300005],aa[300005],q,v,ans[1390000][2],cnt,p,x,y,mx;
int work(int l,int r)
{   
//  cout<<l<<"   "<<r<<endl;
    ans[cnt][0]=l;
    ans[cnt][1]=r;
    for(int i=l;i<=l+r;i++)
    {
        b[i]=a[i];
    }
    p=l;
    for(int i=l+1;i<=r;i+=2)
    {
        a[i]=b[p++];//-------------!
//      p++;
    }
    for(int i=l;i<=r;i+=2)
    {
        a[i]=b[p++];
//      p++;
    }
    return 0;
}
int main()
{
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);
    srand(time(0));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>q;
        mx=max(mx,q);
        aa[q]=i;
    }
    while(cnt==0||cnt>3000)
    {
        cnt=0;
        for(int i=1;i<=mx;i++)
        {
            a[i]=aa[i];
        }
        for(int i=1;i<=2;i++)
        {
            x=rand()%n;
            y=rand()%n;
//          cout<<x<<" "<<y<<endl;
            if(x!=y)
            {
                cnt++;
                work(min(x,y),max(x,y));
            }
        }
        for(int i=n;i>=1;i--)
        {
            if(a[i]!=i)
            {
                v=i;
//              cout<<i<<endl;
                for(;a[v]!=i;v--);
                while(v*2<=i)
                {
//                  cout<<v<<endl;              
                    cnt++;
                    v*=2;
                    work(1,v);
                }
                if(v!=i) 
                {
                    cnt++;
                    work(2*v-i+1,i);
                }
//              cout<<v<<" "<<i<<endl;
            }
        }
        if(cnt<=2)
        {
            break;
        }
    }   
    cout<<cnt<<endl;
    for(int i=cnt;i>=1;i--)
    {
        cout<<ans[i][0]<<" "<<ans[i][1]<<endl;
    }
//  cout<<ans[cnt][0]<<" "<<ans[cnt][1]<<endl;
}