地址:https://ac.nowcoder.com/acm/contest/8688/A
题意:
给出x,y,z,k的范围a,b,c,d
求能组成多少种x+y+z=k
解析:
这是差分数组推导过程的入口:https://www.cnblogs.com/liyexin/p/11014218.html
考虑先枚举a,得出所有的0~a+b的每个结果的数目。
然后在得知a+b的每个数目的情况下,再得到所有0~a+b+c的每个结果的数目。
实现过程,可以通过差分数组来实现。
先枚举a,那么对于每个a,a+b的范围在a~a+b之间,那么范围内每个结果的数目都要+1,有:f[i]++,f[i+b+1]--
前缀和操作一下,还原数组。
同理,在f[]已知各个a+b的种类情况下,枚举a+b,通过f[]来求0~a+b+c的每个出现次数
前缀和还原。
接下来把p[]加到d即可。
#include<iostream> #include<cmath> using namespace std; #include<map> typedef long long ll; const int maxn=1e8; ll f[maxn],p[maxn]; int main() { ll a,b,c,d; cin>>a>>b>>c>>d; for(int i=0;i<=a;i++) { f[i]++; f[i+b+1]--; } for(int i=0;i<=a+b;i++) f[i]+=f[i-1]; for(int i=0;i<=a+b;i++) { p[i]+=f[i]; p[i+c+1]-=f[i]; } for(int i=0;i<=a+b+c;i++) p[i]+=p[i-1]; ll all=0; for(int i=0;i<=d;i++) { all+=p[i]; } cout<<all<<endl; return 0; }
记在后面:
比赛前期过程中,队伍陷入了一个误区,总是在思考怎么去掉a+b+c!=d的方法。其实反向思考一下,把所有种类弄出来,想办法记录。取a+b+c==d不就可以了吗?