【题解】USACO 2020Feb Gold Help Yourself

先放结论

首先把线段按左端点升序排序

我们设 $sum_i$ 为坐标小于等于i的右端点个数

$dp_i$ 为考虑到第 $i$ 条线段时的答案

则递推式为 $dp_i=2dp_{i-1}+2^{sum_{l_i-1}}$

答案为 $dp_n$

证明？

当我们从 $dp_{i-1}$ 转移到 $dp_i$ 的时候，新增了一条线段 $i$，我们可以选或不选它，这样总复杂度 $\times2$。

不选线段 $i$ 的那部分没什么好说的，那我们考虑选了线段$i$之后发生的变化。

由“不与线段 $i$ 相交的线段且编号小于$i$的线段”组成的子集在加上线段 $i$ 之后复杂度 $+1$

这样的子集一共有 $2^{\text{不与线段i相交的线段且编号小于i的线段的个数}}$ 个。（这样其实包括了单独选一个线段 $i$ 在内了）

我们发现“不与线段 $i$ 相交的线段且编号小于 $i$ 的线段的个数”其实就是 $sum_{l_i-1}$（$l_i$ 是线段 $i$ 的左端点坐标）。

感性理解一下就是有 $sum_{l_i-1}$ 条线段在坐标 $l_i$ 之前结束了。

代码

更没什么好说的了

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
#define int long long
const int MAXN=200005;
const int MOD=1e9+7;
int n;
pair<int,int> a[MAXN];
int l[MAXN],r[MAXN];
int tmp[MAXN];
int sum[MAXN];
int dp[MAXN];

inline int pow(int x,int y){
	int ans=1;
	while (y>0){
		if (y%2==0){
			x*=x;
			x%=MOD;
			y/=2;
		}
		ans*=x;
		ans%=MOD;
		y--;
	}
	return ans;
}

signed main()

{
	freopen("help.in","r",stdin);
	freopen("help.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++)
		cin>>a[i].first>>a[i].second;

	sort(a+1,a+1+n);

	for (int i=1;i<=n;i++){
		l[i]=a[i].first;
		r[i]=a[i].second;
		tmp[r[i]]++;
	}

	for (int i=1;i<=MAXN-5;i++)
		sum[i]=sum[i-1]+tmp[i];

	for (int i=1;i<=n;i++)
		dp[i]=(dp[i-1]*2ll+pow(2ll,sum[l[i]-1]))%MOD;
	
	cout<<dp[n]<<endl;
	return 0;
}