Codeforces Round #645 (Div. 2)

解题以及补题报告。

题目链接:Codeforces Round #645 (Div. 2)

A. Park Lighting

需要注意一下奇数乘奇数的情况。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m, T;

int main() {
    for (cin >> T; T--; ) {
        cin >> n >> m;
        if (n & 1 && m & 1) {
            cout << min(n / 2 * m + (m + 1) / 2, m / 2 * n + (n + 1) / 2) << endl;
        } else {
            cout << (n * m / 2) << endl;
        }
    }
    return 0;
}

B. Maria Breaks the Self-isolation

先排序,然后从小到大枚举,考虑让 a[i] 值一样的同时入场,看能不能满足条件,样例 3 比较强,可以知道,如果每次只考虑一组 a[i] 值相同的全部入场也不能满足条件,但是加上后面值更大的入场或许就能满足了,因此如果加上 a[i] 这一组仍然不能满足,还需要一直向后扫描,直到全部扫描完所有 a[i]

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

using namespace std;

typedef long long LL;

const int N = 100010;

int n, T;
int a[N];

int main() {
    for (cin >> T; T--; ) {
        cin >> n;
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        sort(a, a + n);
        int now = -1;
        for (int i = 0; i < n; i++) {
            while (a[i] > i + 1 && i < n) i++;
            if (i == n) break;
            now = i;
        }
        if (now == -1) puts("1");
        else cout << now + 2 << endl;
    }
    return 0;
}

C. Celex Update

思维题啊,虽然看出来先右后下是最小值,先下后右得到了最大值,就是没看出来这个最值区间是连续的,那么只要求这个区间的大小即可,但求这个也比较思维。

将先右后下的直角修改成先下后右的直角,就能使得当前路径比上一个路径和大 $1$,这样一层一层修改,最终能达到,最大值路径(即一直往下再一直往右)。共修改了 $\Delta{x}\cdot\Delta{y}$ 次,就有了这么多不同的路径和,还需要加上没有修改过的最小的路径和,答案就是 $\Delta{x}\cdot\Delta{y}+1$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <iostream>

using namespace std;

int a, b, c, d, T;

int main() {
    for (cin >> T; T--; ) {
        cin >> a >> b  >> c >> d;
        cout << 1ll * (a - c) * (b - d) + 1 << endl;
    }
    return 0;
}

D. The Best Vacation

贪心,双指针,前缀和。(双指针写炸了....另外还有各种细节错误

基于贪心,长度为 $x$ 的区间的右端点一定恰好是某一个月的结束的那天,否则,一定可以让这个区间向前平移,使得满足上述条件,从而使答案更优。首先 $d[\ ]$ 数组需要开两倍,复制一遍在后面,然后求 $d[i]$ 的前缀和 $sd[i]$,以及拥抱个数的前缀和 $s[i]$ 。然后我们枚举每一个月份 $i$ 作为结束月份(即 $x$ 区间的右端点),用 $j$ 指针表示 $x$ 区间左端点所在的月份,如果 $[j,i]$ 月份区间不够 $x$ 天,那么 $i$ 不断后移。然后更新对应的 $j$ 指针(就是这里写错了),如果 $[j+1,i]$ 月份区间的天数已经大于等于 $x$ 天了,那么 $j$ 后移动。通过这样双指针的移动,能保证 $x$ 区间的左端点一定在 $j$ 月份。因此计算这段区间的贡献就是:完整的 $[j+1,i]$ 月份的拥抱数量 + $j$ 月份月末连续的 $x-(sd[i]-sd[j])$ 天的拥抱数量。然后与答案取 $\max$ 即可。

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

using namespace std;

typedef long long LL;

const int N = 200010;

LL n, T, x;
LL d[N * 2];
LL s[N * 2];
LL sd[N * 2];

LL add(int i, LL cnt) {
    LL right = d[i], left = right - cnt + 1;
    return cnt * (left + right) / 2;
}

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        d[i + n] = d[i];
    }
    for (int i = 1; i <= 2 * n; i++) {
        s[i] = s[i - 1] + d[i] * (d[i] + 1) / 2;
        sd[i] = sd[i - 1] + d[i];
    }
    LL ans = 0;
    for (int i = 1, j = 1; i <= 2 * n; i++) {
        while (sd[i] - sd[j - 1] < x) i++;
        while (sd[i] - sd[j] >= x) j++;
        LL temp = s[i] - s[j] + add(j, x - (sd[i] - sd[j]));
        ans = max(ans, temp);
    }
    cout << ans << endl;
    return 0;
}
updatedupdated2020-05-272020-05-27
加载评论
点击刷新