CF930E Coins Exhibition

题意：平面上一共有k个硬币(k<=1e9)，给你n个区间这些区间中至少有一个硬币反面朝上，m个区间中至少有一个硬币正面朝上。问有多少种硬币放置方案？n,m<=100005.

标程：

 #include<bits/stdc++.h>

 using namespace std;

 const int mod=1e9+;

 const int N=;

 typedef long long ll;

 struct node{int l,r;}a[N],b[N];

 int k,n,m,p[N],rg[N][],g[],f[N][],t;

 int ksm(int x,int y)

 {

     int res=;

     while (y){if (y&) res=(ll)res*x%mod; x=(ll)x*x%mod;y>>=;}

     return res;

 }

 int main()

 {

     scanf("%d%d%d",&k,&n,&m);

     for (int i=;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r),p[++t]=--a[i].l,p[++t]=a[i].r;

     for (int i=;i<=m;i++) scanf("%d%d",&b[i].l,&b[i].r),p[++t]=--b[i].l,p[++t]=b[i].r;

     p[++t]=;p[++t]=k;

     sort(p+,p+t+);t=unique(p+,p+t+)-p-;

     for (int i=;i<=t;i++) rg[i][]=rg[i][]=t+;

     for (int i=;i<=n;i++)

     {

        a[i].l=lower_bound(p+,p+t+,a[i].l)-p;

         a[i].r=lower_bound(p+,p+t+,a[i].r)-p;

         rg[a[i].l][]=min(rg[a[i].l][],a[i].r);

    }

     for (int i=;i<=m;i++)

     {

         b[i].l=lower_bound(p+,p+t+,b[i].l)-p;

         b[i].r=lower_bound(p+,p+t+,b[i].r)-p;

         rg[b[i].l][]=min(rg[b[i].l][],b[i].r);

     }

     for (int i=t-;i>=;i--) rg[i][]=min(rg[i][],rg[i+][]),rg[i][]=min(rg[i][],rg[i+][]);

    f[t][]=f[t][]=f[t][]=;

     for (int i=t-;i>=;i--)

    {

        g[]=(ll)f[i+][]*(ksm(,p[i+]-p[i])-+mod)%mod;//这一段有0有1

        for (int j=;j<=;j++) g[j]=((ll)f[i+][j]-f[rg[i][j]][j]+mod)%mod;//g[1/0]表示这一段全0/1且符合限制的方案数。

        f[i][]=((ll)f[i+][]+g[]+g[])%mod;

         f[i][]=((ll)f[i+][]+g[]+g[])%mod;

         f[i][]=((ll)g[]+g[]+g[])%mod;

     }

     printf("%d\n",f[][]);

     return ;

 }

易错点：1.离散化数组的大小需要注意，此题应该开4倍。

2.注意左端点要-1，因而统计的时候都是左开右闭的区间。

题解：前缀和优化dp

朴素思路：将区间按照左端点排序，dp[i:走到第i个格子][j:满足前j个0区间][k:满足前k个1区间]。状态数太大。

可以按照端点离散化，之后就可以按照关键点跳。官方题解:dp0[i][l1]表示最后一个位置为0，当前统计完前i个关键点，l1表示上一个1的位置在哪个关键点区间，dp1同设。状态数还是太大。

继续优化：中间部分按照全1，全0，有1有0讨论。后面两维可以合并掉。f[i:走到第i个关键点，后面的所有关键点都满足其开头限制][0/1:pos[i]~pos[i+1]的区间包含0/1（最后一个0/1在i区间），2:全集]的方案数。f[i][0/1]是最后一个0/1在i~t区间的方案后缀和。f[i][2]是当前的最后一段有0有1的方案数全集（不是后缀和）。

对于限制的处理，对于有相同左端点的区间，取右端点min。对于有包含关系的区间，两个限制都取较小的一个右端点，保证右端点单调，可以直接避免最靠前的一个01位置的不合法情况。

O((n+m)logk)。

巴特西

CF930E Coins Exhibition

最新文章

热门文章