题目大意
有 Q 种操作。
1、加入一个魔力为 x 的宝石;
2、删去一个魔力为 x 的宝石(保证操作合法);
3、询问有多少种选取宝石的方法,使得选取的魔力和为 x;(不同下标的宝石视为不同,即两种方法不同当且仅当两种方法选取的宝石有不同)
4、询问有多少种选取宝石的方法,使得选取的魔力和为 x。(不同魔力的宝石视为不同,即两种方法不同当且仅当某一种魔力值的宝石数量不同)
Q, x<=10^4,时限 3s。
解法1
这种东西肯定先想到 dp。
设 f[i] 表示操作3条件下,魔力和为 i 的方案数;设 g[i] 表示操作4的方案数。f 是个01背包,而 g 是个多重背包。
然后这就是个动态dp了。
f 的维护比较简单,插入就倒着扫一遍,删除就正着扫一遍。
g 的维护比较麻烦,主要是它的转移跟数量有关。实现程序时瞎搞一下也可以使其成为线性。
一次dp是 O(x) 的,所以总时间是 O(Qx)。
解法2
考虑dp的生成函数。贴题解了。
以下的 $cnt[i]$ 表示魔力值为 i 的宝石数量,$f[i][j]$ 表示01背包的dp
![](/images/jzoj4941.png)
代码
解法1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
| #include<cstdio> #include<cstring> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std;
typedef long long LL;
const int maxn=1e4+5; const LL mo=1e9+7;
int n,cnt[maxn]; LL f[maxn],g[maxn];
int ReadInt() { char ch=getchar(); int data=0; while (ch<'0' || ch>'9') ch=getchar(); do{ data=data*10+ch-'0'; ch=getchar(); } while (ch>='0' && ch<='9'); return data; } char ReadChar() { char ch=getchar(); while (ch!='i' && ch!='q' && ch!='d' && ch!='R' && ch!='T') ch=getchar(); return ch; }
LL gj[maxn],gp[maxn]; void NewG(int x,int z) { if (cnt[x]) { fo(i,0,x-1) gj[i]=g[i]; fo(i,x,n) { g[i]=(g[i]-gj[i-x]+mo)%mo; gj[i]=(gj[i-x]+g[i])%mo; if (i-cnt[x]*x>=0) gj[i]=(gj[i]-g[i-cnt[x]*x]+mo)%mo; } } cnt[x]+=z; if (cnt[x]) { memcpy(gp,g,sizeof(g)); fo(i,0,x-1) gj[i]=gp[i]; fo(i,x,n) { g[i]=(g[i]+gj[i-x])%mo; gj[i]=(gj[i-x]+gp[i])%mo; if (i-cnt[x]*x>=0) gj[i]=(gj[i]-gp[i-cnt[x]*x]+mo)%mo; } } }
int Q; int main() { n=10000; f[0]=g[0]=1; scanf("%d",&Q); while (Q--) { char ty=ReadChar(); if (ty=='i') { int x=ReadInt(); fd(i,n,x) f[i]=(f[i]+f[i-x])%mo; NewG(x,1); } else if (ty=='d') { int x=ReadInt(); fo(i,x,n) f[i]=(f[i]-f[i-x]+mo)%mo; NewG(x,-1); } else { char now=ReadChar(); int x=ReadInt(); printf("%lld\n",(now=='T') ?f[x] :g[x] ); } } }
|