Codeforces Round #810 (Div. 2)D~A

D. Rain

Problem - D - Codeforces

某一个数是下雨的中心位置，强度向左右两侧递减，公差为1.有删除第i次降水的能力，回答是否可以在删除第i次降雨的情况下让它不产生洪水（最大值

二阶差分/前缀和。

对于一个点 j，要转换成如下方式判断是否造成洪水，因为如果通过消去(xi,pi)的影响并不能保证第二大的值小于m：

当j>=xi时，pi + xi >= sum - m + j;

当j= sum - m - j;

#include 
typedef long long ll;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;

const int maxn = 2e5 + 6;
int n, m;
ll x[maxn], p[maxn];
struct node {
    ll id, d;
};
std::map<ll, ll> v;
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        v.clear();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld", x + i, p + i);
            v[x[i] + p[i]]++;
            v[x[i]] -= 2;
            v[x[i] - p[i]]++;
        }
        ll val1 = -1e18, val2 = -1e18;
        ll sd = 0, lst = 0, sum = 0;
        for (auto &k : v) {
            sum += (k.first - lst) * sd;
            sd += k.second;
            lst = k.first;
            if (sum > m) {
                val1 = max(val1, sum - m - k.first);
                val2 = max(val2, sum - m + k.first);
            }
        }
        for (int i = 1; i <= n; i++) {
            if (p[i] - x[i] >= val1 && p[i] + x[i] >= val2) putchar('1');
            else putchar('0');
        }
        puts("");
    }
}
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

C. Color the Picture

Problem - C - Codeforces

给定一定大小的矩形，和k种颜料，每种颜料ai个。问有没有可能将矩形涂得漂亮。

涂漂亮就是至少两行或者两列颜色一致，拼一块。当m为奇数时，ai/n不能全为2.另外，能够涂的总列数c要开long long.

#include 
typedef long long ll;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;

const int maxn = 1e5 + 6;
int n, m, k;
int a[maxn];
bool check() {
    ll c = 0;
    bool fl = 0;
    if (m & 1) {
        for (int i = 1; i <= k; i++) {
            if (a[i] / n > 2)
                fl = 1;
            if (a[i] / n > 1)
                c += a[i] / n;
        }
        if (fl && c >= m) return 1;
        else return 0;
    } else {
        for (int i = 1; i <= k; i++) {
            if (a[i] / n > 1)
                c += a[i] / n;
        }
        if (c >= m) return 1;
        else return 0;
    }
}
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1; i <= k; i++)
            scanf("%d", a + i);
        if (check()) {
            puts("Yes");
        } else {
            swap(n, m);
            if (check()) puts("Yes");
            else puts("No");
        }
    }
}
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

B. Party

Problem - B - Codeforces

给定一个图，每个节点有一定权值，可以删除若干节点，使剩下来的边数是偶数条，要求删掉的权值和最小。

如果本身就是偶数条，那么没必要删。如果是奇数条，要么删掉相邻的两个度数为偶数的节点，要么删掉1个度数为奇数的节点。

#include 
typedef long long ll;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;

const int maxn = 1e5 + 6;
int n, m;
int a[maxn], d[maxn];
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        int minx = 1e9;
        for (int i = 1; i <= n; i++)
            scanf("%d", a + i), d[i] = 0;
        for (int i = 1; i <= m; i++) {
            int s, k;
            scanf("%d%d", &s, &k);
            d[s]++, d[k]++;
            minx = min(minx, a[s] + a[k]);
        }
        if ((m & 1)  == 0) {
            puts("0");
            continue;
        }
        for (int i = 1; i <= n; i++)
            if (d[i] & 1)
                minx = min(minx, a[i]);
        printf("%d\n", minx);
    }
}
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

A. Perfect Permutation

Problem - A - Codeforces

给定数列的长度n，其中数列是1~n的全排列的一种。要求构造出一个a[i]%i==0个数最小的数列。

令a[i]=i+1(i

#include 
typedef long long ll;
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(a) cout << #a << "=" << a << endl;
using namespace std;

const int maxn = 1e5 + 6;
int a[maxn];
int main() {
    int t; scanf("%d", &t);
    while (t--) {
        int n; scanf("%d", &n);
        for (int i = 1; i < n; i++) {
            printf("%d ", i + 1);
        }
        puts("1");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19