bzoj1042 [HAOI2008]硬币购物

2019-11-06 07:39:02

字体：大中小

来源：转载

供稿：网友

传送门吐槽：老师~~居然两次~~拿这道题出模拟赛。普通背包显然药丸于是窝们考虑容斥窝们可以先用O（N）的时间处理处一个无限背包然后枚举哪一些物品超限。超限的话先强行加入limit+1个物品，之后任取。容斥一下就行了时间O（N+16Q）一些新闻：两个题目输入格式不同。 ~~某头姓同学~~将第一题的代码直接拷到第二题上于是乎收获一WA

#include<cstdio> #include<cstring>#include<algorithm>#include<cstdlib>#include<iostream>#define ll long longusing namespace std;ll b[5],a[5],c[5],f[200005],n,v,sum,p,s;ll get(ll x){ if (x>v) return 0; return f[v-x];}int main(){ c[1]=1; c[2]=2; c[3]=4; c[4]=8; for (ll i=1;i<=4;i++) scanf("%lld",&a[i]); scanf("%lld",&n); f[0]=1; for (int i=1;i<=4;i++) for (int j=0;j<=100000;j++) f[j+a[i]]+=f[j]; for (ll i=1;i<=n;i++){ for (int j=1;j<=4;j++) scanf("%lld",&b[j]); scanf("%lld",&v); sum=0; for (int j=0;j<=15;j++){ s=0; p=0; for (int k=1;k<=4;k++) if ((j&c[k])!=0){ s++; p+=(b[k]+1)*a[k]; } if (s%2==0) sum+=get(p); else sum-=get(p); } PRintf("%lld/n",sum); } return 0;}

上一篇：Leetcode 319 - Bulb Switcher（Math）

下一篇：properties文件