题解 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
#include
#include

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=lr[0][s[1]].l){
					t=lr[0][s[1]].r+1;
					continue;
				}
				break;
			}
			if(t+lr[1][j].tt+lr[1][j].t){
					f[to]=t+lr[1][j].t;
					pre[to]=j;
                    //这里要存j，不然无法减去t[j]
				}
			}
		}
	}
	if(p==1)calc((1<