P6533 RELATIVNOST 题解

· · 题解

P6533 RELATIVNOST 题解

题目

洛谷 P6533 RELATIVNOST

分析

题目中要求至少有 c 人买走至少一张彩色画，那暴力的思路就是选取 i (c\leq i\leq n) 到 n 个人，这 i 个人满足题意的购买方案数就是他们的 a 乘上剩下的人的 b。

我们注意到 c 的数据范围小于 20，于是就可以考虑使用动态规划解决问题。

又因为对于每组数据有 q 组改变，普通的动态规划会T掉，所以我们使用线段树进行优化。

思路

对于线段树上的每一个节点 tree[i]，我们设 tree[i].dp[j] 表示 tree[i].l 到 tree[i].r 个人（即该节点覆盖的区间）中有 j 个人购买了至少一幅彩色画的方案数，根据乘法原理，每个节点购买至少 i+j 张彩色画方案数就等于该节点的左子树对应的人数购买至少 i 幅彩色画的方案数乘以该节点的所有右子树对应的人数购买至少 j 幅彩色画的方案数，于是我们就可以推出转移方程：

tree[id].dp[i+j]=\sum_{i=0}^{c}{\sum_{j=0}^{c}{tree[id\cdot 2].dp[i]\cdot tree[id\cdot 2+1].dp[j]}}

这一部分可能有点绕，如果不清楚的话建议感性理解结合代码看一看（在 update 函数里面）。

对于有 c 个人以上的人购买了彩色画的情况，我们都将其存到 dp[c] 里面，所以代码中上面式子里面的 i+j 应该换成 \min(i+j,c)。

而对于线段树的每个叶子节点，即单独一个人，他购买了彩色画的方案数就是他最多会买的彩色画的数量（即 a[i]），他购买了黑白画的方案数就是他最多会购买的黑白画的数量（即 b[i]），于是我们就可以得到以下的式子：

tree[i].dp[0]=b[i],tree[i].dp[1]=a[i]

对于每一个人 a_i 和 b_i 的改变，我们就将线段树更新一下就好了，最后总共的情况数就是线段树根节点的 dp[c] 的值（代表所有顾客中至少有 c 人购买彩色画的方案数）。

更详细的实现步骤详见代码注释。

代码

#pragma gcc optimize(2)//不开O2会T最后一个点
#include<iostream>
using namespace std;
const int MAXN=100005,MOD=10007;
int a[MAXN],b[MAXN],c,n;//对应题目中的a,b,c,n
struct Node
{
    int l,r,dp[21];
}tree[MAXN*4];//因为这道题的空间限制只有32MB，有些OJ可能过不了，但是洛谷上这么写还是过了
inline void update(int id)//更新一个节点的dp数组
{
    for(register int i=0;i<=c;i++)
    {
        tree[id].dp[i]=0;//每次更新一个节点时先将其清零
    }
    for(register int i=0;i<=c;i++)
    {
        for(register int j=0;j<=c;j++)
        {
            tree[id].dp[min(i+j,c)]=((tree[id*2].dp[i]*tree[id*2+1].dp[j])%MOD+tree[id].dp[min(i+j,c)])%MOD;
            //这行代码比较长，其实去掉取模就是tree[id].dp[min(i+j,c)]+=tree[id*2].dp[i]*tree[id*2+1].dp[j];
            //为啥要用+=？举个例子，左子树两个右子树两个人买彩色画跟左子树一个右子树三个人买彩色画
            //都会计算在有四个人购买彩色画的方案数内。
        }
    }
}
void build(int l,int r,int id)//建树操作
{
    tree[id].l=l,tree[id].r=r;
    if(l==r)//如果是叶子结点
    {
        tree[id].dp[0]=b[l],tree[id].dp[1]=a[l];//那么按照上文所说的修改它的dp[0]和dp[1]
        return;
    }
    build(l,(l+r)/2,id*2);
    build((l+r)/2+1,r,id*2+1);
    update(id);//当该节点的左儿子和右儿子建立完成之后更新该节点的dp值
}
void change(int id,int A,int B,int fxid)//单点修改操作
{//id是当前节点的下标，fxid是要修改的节点的下标
    if(tree[id].l==tree[id].r)
    {
        tree[id].dp[0]=B,tree[id].dp[1]=A;
        return;
    }
    if(fxid<=((tree[id].r+tree[id].l)/2))
        change(id*2,A,B,fxid);
    if(fxid> ((tree[id].r+tree[id].l)/2))
        change(id*2+1,A,B,fxid);
    update(id);//跟上面建树操作一个道理，左右儿子修改完之后更新
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]%=MOD;//读入之后先取模
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        b[i]%=MOD;
    }
    build(1,n,1);//建树
    int q,A,B,changeid;
    cin>>q;
    while(q--)
    {
        cin>>changeid>>A>>B;
        A%=MOD,B%=MOD;
        change(1,A,B,changeid);
        cout<<tree[1].dp[c]<<endl;
        //tree[1].dp[c]就是所有人至少买了c张及以上的彩色画的方案数
    }
}

更新