Loading...

蒟蒻$Decoration$的简单题 题解

check评论:0 条 remove_red_eye浏览量:374 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-20

蒟蒻$Decoration$的简单题 题解

题目要求你支持两个操作

$1$:给定区间$[l,r]$,设$f[i]$表示$i$在$[l,r]$内出现次数,求出$\sum_{i=0}^{maxi} C_{f[i]}^2 (2 \leq f[i])$

2:给定区间$[l,r]$,$opt1$的所有操作的答案设为一个序列,求这个序列中$[l,r]$的总和

这个题目一看就是离线的,所以第一个操作我们直接莫队

第二个操作其实是骗人的,我们求出第一个操作的答案后,前缀和搞一下,再搞第二个操作的答案,最后直接输出即可

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int a[100010],ans[100010],opts[100010],cnt,ls[100010],rs[100010],tot,queryans[100010];
int n,m,block,tong[100010],fixans[100010];
struct query
{
    int l,r,id;
}q[150010];
bool cmp(query a,query b)
{
    return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}
main()
{
    //freopen("data1.in","r",stdin);
    //freopen("qwq.out","w",stdout); 
    cin>>n>>m;
    block=sqrt((n+2)/3);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%lld%lld%lld",&opts[i],&x,&y);
        if(opts[i]==1)
        {
            cnt++;
            q[cnt].l=x;
            q[cnt].r=y;
            q[cnt].id=cnt;
        }
        else
        {
            tot++;
            ls[tot]=x;
            rs[tot]=y;
        }
    }
    sort(q+1,q+cnt+1,cmp);
    int l=1,r=0,nowans=0;
    for(int i=1;i<=cnt;i++)
    {
        while(l>q[i].l)
        {
            l--;
            tong[a[l]]++;
            nowans+=(tong[a[l]]-1);
        }
        while(l<q[i].l)
        {
            nowans-=(tong[a[l]]-1);
            tong[a[l]]--;
            l++;
        }
        while(r<q[i].r)
        {
            r++;
            tong[a[r]]++;
            nowans+=(tong[a[r]]-1);
        }
        while(r>q[i].r)
        {
            nowans-=(tong[a[r]]-1);
            tong[a[r]]--;
            r--;
        }
        ans[q[i].id]=nowans;
          ans[q[i].id]%=19260817; 
    }
    for(int i=1;i<=cnt;i++)
    {
        fixans[i]=fixans[i-1]+ans[i];
    }
    for(int i=1;i<=tot;i++)
    {
        queryans[i]=fixans[rs[i]]-fixans[ls[i]-1];
        queryans[i]%=19260817;
    }
    int lf=1,rg=1;
    for(int i=1;i<=m;i++)
    {
        if(opts[i]==1)
        {
            printf("%lld\n",ans[lf]);
            lf++;
        }
        else
        {
            printf("%lld\n",queryans[rg]);
            rg++;
        }
    }
}
  • $CP$构图

题目的大意,就是给定一个$n\times n$的矩阵,每个点上面可以填$1$或$0$,规定填了$1$的点上下左右都只能是$0$,求出总方案数

一看$n$的范围那么小,就知道是状压$dp$

每一行内部可行的状态,我们只要判断$i\&(i<<1)==0$就代表这是一个可行状态

两两行间枚举也一样,只要$k\&j==0$就可以递推了

#include <bits/stdc++.h>
#define mod 19260817
using namespace std;
int f[30][1<<22];
int s[1<<22],cnt;
int main()
{
    int n;
    cin>>n;
    for(int i=(1<<n)-1;i>=0;i--)
    {
        if((i&(i<<1))==0)
        {
            cnt++;
            s[cnt]=i;
            f[1][s[cnt]]=1;
        }
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=cnt;j++)
        {
            for(int k=1;k<=cnt;k++)
            {
                if(s[k]&s[j])
                {
                    continue;
                }
                f[i][s[j]]+=f[i-1][s[k]];
                f[i][s[j]]%=mod;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=cnt;i++)
    {
        ans+=f[n][s[i]];
        ans%=mod;
    }
    cout<<ans;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名