题解 P6313 【[eJOI2018]护照】

· · 题解

很有趣的题

思路部分来自 @StudyingFather（Loj）

因为 1 \le P \le 2 ，同时注意到两本护照办理并不互相干扰，可以只考虑 P=1 的情况，如果 P=2 的话，选一个状态以及与它互补（就是两个集合没有相同的元素，且正好两个集合大小的和等于 n ）求解即可

考虑到 n \le 22 ，尝试使用状压，设 f[i] 为状态为 i 时，最小的把 i 所有包含的护照办完的时间。

对于当前转移点 j 考虑如何转移（即从 f[i] 转移到 f[i+2^{j-1}] ），首先令 f[i+2^{j-1}]=f[i]

1、看有哪些出国的时间段包含了 f[i+2^{j-1}] （即 l_x \le f[i+2^{j-1}] \le r_x(r_x=l_x+len_x-1,1 \le x \le n) ），这些区间内都不能办理护照（此时在国外，用哪本护照都办不了），所以 f[i+2^{j-1}]=\max\{r_x\}+1+t_j ，注意此时 f[i+2^{j-1}] 有变化，又可以进行转移。

2、然后考虑包含在 i 里面的点，此时因为我们只有一本护照，我们不能在有签证还没办完的情况下出国，即 f[i+2^{j-1}] \le l_x 且 l_x \le f[i]+t_j ，这时中间这一段只能抛弃，所以 f[i+2^{j-1}]=\max\{r_x\}+1+t_j 。

注意，注意，注意！这里两种状态是互相影响的

然后考虑时间复杂度，貌似是 O(n^2 \times 2^n) ，不知道能不能过，毕竟很多状态是转移不了的，可能能过。

但是不能停留在可能，我们尽量优化到 O(n \times 2^n) ，注意到这两种都是会把 l 弄得越来越大，所以考虑以 l 为关键字排序，但是还是没有用，因为对于不同的 j 因为 t_j 不同，又要从头再来。突然注意到，如果 t_j 以升序排列，那么 j 转移出来的答案一定比 j-1 更大（因为 t 越大越难满足条件），所以此时再copy一遍数组，以 t 为关键字排序即可。

具体实现看代码：

#include<cstdio>
#include<cctype>
#include<algorithm>

using namespace std;

#define maxn 55
#define maxN 5005005
#define INF 2000000002

inline int read(){
    int r=0,f=0;
    char c;
    while(!isdigit(c=getchar()))f|=(c=='-');
    while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
    return f?-r:r;
}

struct LR{
    int l,r,t;
    int num;
}lr[2][maxn];

int n,p,s[2],ans[maxn][2];

int pre[maxN],f[maxN];

inline bool cmp1(LR x,LR y){
    return x.l<y.l;
}

inline bool cmp2(LR x,LR y){
    return x.t<y.t;
}

inline void calc(int x,int i){
    if(f[x]==INF)return;
    while(x){
        int j=pre[x];
        int num=lr[1][j].num;
        ans[num][0]=i;
        ans[num][1]=f[x]-lr[1][j].t;
        x^=(1<<(num-1));//注意这里是num，理由见下
    }
}

int main(){
    n=read(),p=read();
    for(int i=1;i<=n;i++){
        lr[0][i].l=read();
        lr[0][i].r=lr[0][i].l+read()-1;
        lr[0][i].t=read(),lr[0][i].num=i;
        lr[1][i]=lr[0][i];//copy一下
    }
    sort(lr[0]+1,lr[0]+1+n,cmp1);
    sort(lr[1]+1,lr[1]+1+n,cmp2);
    for(int i=0;i<(1<<n);i++)f[i]=INF;
    f[0]=1;
    for(int i=0;i<(1<<n);i++){
        if(f[i]==INF)continue;
        int t=f[i];
        s[0]=s[1]=1;
        for(int j=1;j<=n;j++){
            //注意j是算枚举t从小到大，所以是lr[1][j]
            if(i&(1<<(lr[1][j].num-1)))continue;
            while(1){
                //这里是按l，所以是lr[0][s[]]
                while(s[0]<=n&&lr[0][s[0]].r<t)s[0]++;
                while(s[1]<=n&&(lr[0][s[1]].l<t||!(i&(1<<(lr[0][s[1]].num-1)))))s[1]++;
                //因为两种排序会导致顺序不同，所以这里的状态是用原本的num，这样方便统一
                if(s[0]<=n&&lr[0][s[0]].l<=t){
                    t=lr[0][s[0]].r+1;//两种情况
                    continue;
                }
                if(s[1]<=n&&t+lr[1][j].t>=lr[0][s[1]].l){
                    t=lr[0][s[1]].r+1;
                    continue;
                }
                break;
            }
            if(t+lr[1][j].t<lr[1][j].l){
                int to=i|(1<<(lr[1][j].num-1));
                //这里记得也是num
                if(f[to]>t+lr[1][j].t){
                    f[to]=t+lr[1][j].t;
                    pre[to]=j;
                    //这里要存j，不然无法减去t[j]
                }
            }
        }
    }
    if(p==1)calc((1<<n)-1,1);
    else {//P=2时取互补的两个状态即可
        for(int i=0;i<(1<<n);i++){
            if(f[i]!=INF&&f[(1<<n)-1-i]!=INF){
                calc(i,1);
                calc((1<<n)-1-i,2);
                break;
            }
        }
    }
    if(!ans[1][0])return puts("NO"),0;
    puts("YES");
    for(int i=1;i<=n;i++)
        printf("%d %d\n",ans[i][0],ans[i][1]);
    return 0;
}