【题解】USACO 2020Feb Gold Help Yourself

· · 题解

更好的阅读

先放结论

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

我们设sum_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-1之前结束了。

代码

更没什么好说的了

#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;
}