「五校联考」Round#1 Day1&Day2 T1

八月 26, 2018 4521

由于权限原因，暂不提供题面 & 评测地址

Day1 T1 dice.cpp

解析

题目让我们求一个骰子每次滚动时最顶数字之和

随意观察可知一个骰子滚4圈所得的和 =14

那么我们可以先让ans += ((m - 1) / 4) * 14

这样来处理每一行的主要部分

要是剩下还有点没求呢？

那就直接暴力模拟，反正时间复杂度高不了多少

代码实现

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

long long int ans;

struct Dice {
    long long int top;
    long long int front;
    long long int bottom;
    long long int behind;
    long long int left;
    long long int right;
    Dice() {
        top = 1;
        front = 2;
        bottom = 6;
        behind = 5;
        left = 4;
        right = 3;
    }
    void toTheRight() {
        long long int origTop = top;
        top = left;
        left = bottom;
        bottom = right;
        right = origTop;
        ans += top;
    }
    
    void toTheLeft() {
        long long int origTop = top;
        top = right;
        right = bottom;
        bottom = left;
        left = origTop;
        ans += top;
    }
    
    void toTheDownLine() {
        long long int origTop = top;
        top = behind;
        behind = bottom;
        bottom = front;
        front = origTop;
        ans += top;
    }
} d;

long long int n, m;

inline int getint() {
    int s = 0, x = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') x = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * x;
}

inline void putint(int x, bool returnValue) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x >= 10) putint(x / 10, false);
    putchar(x % 10 + '0');
    if (returnValue) putchar('\n');
}

int main(int argc, char *const argv[]) {
    cin >> n >> m;
    ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans += ((m - 1) / 4 ) * 14;
        if (i & 1) 
            for (int j = 1; j <= (m - 1) % 4; ++j) d.toTheRight();
        else 
            for (int j = 1; j <= (m - 1) % 4; ++j) d.toTheLeft();
        // 在 toTheRight 和 toTheLeft 和 toTheDownLine 中已经更新过答案
        // 不必再更新 
        if (i != n) d.toTheDownLine();
    }
    cout << ans << endl;
    return 0;
}


Day2 T1 meizi.cpp

解析

前言：

1
zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！zzs人赢！

考虑一下暴力怎么写

把区间[l, r]全部+1，最终取个max

那么我们就可以把区间首+1，区间尾-1，然后做一遍前缀和

我们首先对每个区间差分，再把差分的区间加起来

最终做一遍前缀和，取一遍max

注意要先进行离散化，因为 1 \le l_i \le\ r_i \le 10^9

代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

const int MAXN = 2 * 1e5 + 20;

int n;

int l[MAXN], r[MAXN];
int tmp[MAXN * 2];
// 离散化数组

int s[MAXN * 2];
// 前缀和数组
// 开两倍是因为对于每一个妹子都需要记录l和r两个变量

inline int getint() {
    int s = 0, x = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') x = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * x;
}

inline void putint(int x, bool returnValue) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x >= 10) putint(x / 10, false);
    putchar(x % 10 + '0');
    if (returnValue) putchar('\n');
}

int main(int argc, char *const argv[]) {
    n = getint();
    for (int i = 1; i <= n; ++i) {
        l[i] = getint();
        r[i] = getint();
        // 记录离散化数组
        tmp[2 * i - 1] = l[i];
        tmp[2 * i] = r[i];
    }
    // 开始离散化
    sort(tmp + 1, tmp + 1 + 2 * n);
    for (int i = 1; i <= n; ++i) {
        l[i] = lower_bound(tmp + 1, tmp + 1 + 2 * n, l[i]) - tmp;
        r[i] = lower_bound(tmp + 1, tmp + 1 + 2 * n, r[i]) - tmp;
        // 在离散化中顺便记录前缀和数组
        ++s[l[i]];
        --s[r[i] + 1];
    }
    // 处理前缀和
    for (int i = 1; i <= 2 * n; ++i) {
        s[i] += s[i-1];
    }
    int ans = 0;
    for (int i = 1; i <= 2 * n; ++i) ans = std::max(ans, s[i]);
    putint(ans, true);
    return 0;
}