2020（ICPC）亚洲网上区域赛模拟赛 A-Easy Equation 差分 + 前缀和

传送门：https://ac.nowcoder.com/acm/contest/8688/A

题意

给出$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）$

思路

先考虑枚举x，则x+y的值域范围为[x, x + b]。 所以枚举x从0到a中，x到x+b中都要+1，这是就可以用一维差分即可。然后前缀和复原。

1
2
3
4
5
6
7
for(int i = 0;i <= a; i++) {
    d1[i]++;
    d1[i + a + 1]--;
}
for(int i = 1;i <= a + b; i++) {
    d1[i] += d1[i - 1];
}

同理，在考虑枚举x+y，则x+y+z的值域范围为[x+y，x+y+c]。 枚举x+y从0到a+b中，x+y到x+y+c中都要+1，差分在复原。

1
2
3
4
5
6
7
8
for(int i = 0;i <= a + b; i++) {
    d2[i] += d1[i];
    d2[i + c + 1] -= d1[i];
}

for(int i = 1;i <= a + b + c; i++) {
    d2[i] += d2[i - 1];
}

最后取0到d中的贡献即可。

Code

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
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int N = 1e7 + 10;
ll d1[N], d2[N];

void solve()
{
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    for(int i = 0;i <= a; i++) {
        d1[i]++;
        d1[i + a + 1]--;
    }
    for(int i = 1;i <= a + b; i++) {
        d1[i] += d1[i - 1];
    }

    for(int i = 0;i <= a + b; i++) {
        d2[i] += d1[i];
        d2[i + c + 1] -= d1[i];
    }

    for(int i = 1;i <= a + b + c; i++) {
        d2[i] += d2[i - 1];
    }

    ll ans = 0;
    for(int i = 0;i <= d; i++) {
        ans += d2[i];
    }

    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/11/03/2020-icpc-online-a/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！