洛谷10月月赛R2·浴谷八连测R3 -Chtholly- 浮游大陆的68号岛

洛谷题号:3932
一个前缀和的破题改了两个钟头,真是罪过。。。
借鉴了xsun2001同学的思路……在此表示感谢。。。
原来xsun2001同学代码中有可能存在的两点错误:第一个,有可能错在read函数里,读入进来的是int。第二,中间的所有计算过程全部需要取模。我把这两点改好之后就没问题了。

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define MOD 19260817
long long n, m;
long long dis[200005], goods[200005];
long long prefixsum_dis[200005], prefixsum_goods[200005], prefixsum_cost[200005];
//从1到i点的距离/物品数/距离*物品数
#define LeftDis(l,r,x) ((prefixsum_cost[r] - prefixsum_cost[l - 1] + MOD)% MOD - (prefixsum_dis[x] * (prefixsum_goods[r] - prefixsum_goods[l - 1] + MOD) % MOD) + MOD) % MOD
#define RightDis(l,r,x) ((prefixsum_dis[x] * (prefixsum_goods[r] - prefixsum_goods[l - 1] + MOD) % MOD) - (prefixsum_cost[r] - prefixsum_cost[l - 1] + MOD) % MOD +MOD ) % MOD
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 2; i <= n; i++){
        cin >> dis[i];
        dis[i] %= MOD;
    }
    for (int i = 1; i <= n; i++){
        cin >> goods[i];
        goods[i] %= MOD;
    }
    for (int i = 1; i <= n; i++){
        prefixsum_dis[i] = (prefixsum_dis[i - 1] + dis[i]) % MOD;
        prefixsum_goods[i] = (prefixsum_goods[i - 1] + goods[i] % MOD) % MOD;
        prefixsum_cost[i] = (prefixsum_cost[i - 1] + prefixsum_dis[i] * goods[i] % MOD) % MOD;
    }
    for (long long i = 1; i <= m; i++){
        long long result = 0;
        long long x, l, r;
        cin >> x >> l >> r;
        if (l >= x){
            result += LeftDis(l,r,x);
        }
        else if (r <= x){
            result += RightDis(l,r,x);
        }
        else{
            result += LeftDis(x + 1, r, x);
            result += RightDis(l, x - 1, x);
        }

        cout << result%MOD << endl;
    }
    return 0;
}

题解地址:
洛谷月赛R2训练营R3

发表评论

电子邮件地址不会被公开。 必填项已用*标注