日度归档：21 10 月, 2017

洛谷10月月赛R2·浴谷八连测R3 -Chtholly- Chtholly Nota Seniorious

发表评论

洛谷题号：3933
乱搞、二分答案+贪心，根本想不出来，打暴力30分……

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
78
79
80
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
int n, m;
int arr[2005][2005];
int arr_rotate[2005][2005];
int pos[2005];
int minnum = 2e9, maxnum = 0;
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] >minnum+value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (maxnum - value > arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
/*check问题搞不懂可以仔细阅读T2题解
check的等效写法：
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] < maxnum - value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (minnum + value < arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
*/
void rotate90degrees(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            arr_rotate[j][n-i+1] = arr[i][j];
        }
    }
    memcpy(arr, arr_rotate, sizeof(arr));
    swap(n, m);
}

int solve(){
    int low = 0, high = maxnum - minnum,mid;
    while (low < high){
        mid = (low + high) / 2;
        if (check(mid)){
            high= mid;
        }
        else{
            low = mid + 1;
        }
    }
    return low;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
            maxnum = max(maxnum,arr[i][j]);
            minnum = min(minnum,arr[i][j]);
        }
    }
    int re = 2e9;
    for (int i = 1; i <= 4; i++){
        re = min(re, solve());
        rotate90degrees();
    }
    cout << re;
    return 0;
}

洛谷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