Easy Equation【差分+前缀和】

题意

给出 \(4\) 个整数:\(a,b,c,d\),求出满足方程:\(x+y+z=k\) 的方案数,其中:\(0\leq x \leq a,0\leq y \leq b,0 \leq z \leq c,0\leq k \leq d\)。
\(0\leq a,b,c,d \leq 10^6\)
题目链接:https://ac.nowcoder.com/acm/contest/8688/A

分析

先求出 \(x+y=i\) 的方案数,然后将 \(x+y=i\) 视作一个数,求出 \(i+z\) 的方案数,然后枚举 \(k\) 的范围,求出答案。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 4e6 + 5;
ll f1[N], f2[N];

int main()
{
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    for (int i = 0; i <= a;i++)//求出x+y的方案数
    {
        f1[i] += 1;
        f1[i + b + 1] -= 1;
    }
    f1[0] = 1;
    for (int i = 1; i <= a + b;i++)//i=x+y时的方案数
        f1[i] += f1[i - 1];
    for (int i = 0; i <= a + b;i++)
    {
        f2[i] += f1[i];
        f2[i + c + 1] -= f1[i];
    }
    f2[0] = 1;
    for (int i = 1; i <= a + b + c;i++)
        f2[i] += f2[i - 1];
    ll ans = 0;
    for (int i = 0; i <= d;i++)
        ans += f2[i];
    printf("%lld\n", ans);
    return 0;
}
上一篇:Leetcode(easy Greedy)


下一篇:【leetcode - 20】有效的括号 easy