Codeforces Round 688 (Div. 2)

发表于 分类于 ，

Codeforces Round 688 (Div. 2)

Complete problemset

A. Cancel the Trains

题意

现在有100条横向的铁路和100条纵向的铁路交错。

指定了哪些轨道上存在火车。

现在火车是同时出发，火车速度相同，可能存在火车相撞的情况（我们认为火车是质点），问要移除最少多少火车以避免事故。

思路

火车速度相同，所以只有横向移动和纵向移动的标号相同时才会相撞。

直接统计有多少相同的标号即可。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n, m;
    cin >> n >> m;
    vector<int> a(101);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[x]++;
    }
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        a[x]++;
    }
    cout << count(a.begin(), a.end(), 2) << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

B. Suffix Operations

题意

给出一个数组。

现在每次操作，
你可以对任意后缀中所有元素进行加一或减一操作。

你可以事先修改任意元素为任意其他值，然后求最少的后缀操作次数使得所有元素的值都相等。

思路

如果不考虑修改元素，其实答案就是任意两个相邻数的差的绝对值。

如果可以修改元素，实际上可以认为是移除了这个元素，再做新数组任意两个相邻数的差的绝对值。求一个最小值即可。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    for (auto& i : a)
        cin >> i;
    ll sum = 0;
    for (int i = 1; i < n; i++)
        sum += abs(a[i] - a[i - 1]);
    ll ans = sum - max(abs(a[0] - a[1]), abs(a[n - 1] - a[n - 2]));
    for (int i = 1; i < n - 1; i++) {
        ans = min(ans, sum - abs(a[i + 1] - a[i]) - abs(a[i] - a[i - 1]) +
                           abs(a[i + 1] - a[i - 1]));
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

C. Triangles

题意

现在给出一个$n\times n$的矩阵，矩阵中的每个元素范围在0到9。
你可以将任意一个元素修改为x，然后选三个x使得其组成的三角形面积最大化，且三角形至少有一条边垂直与矩形边框。然后将修改的值还原。

求出0到9作为三角形顶点时的三角形最大面积乘以2。

思路

我们分别维护每个值k出现位置的最小/大横坐标$mnr_k,mxr_k$，以及最小/大纵坐标$mnc_k, mxc_k$。

假设值为k的其中一个坐标是(x,y)，现在可以选择一条经过(x,y)且平行于x轴的最长边，长度为$max(n-x-1,x)$，然后选择一个最大的高，这个最大的高显然是$mnc_k$与$mnc_k$距离y最远的点，$max(y-mnc_k, mxc_k-y)$，至此把便可以维护答案k的最大值$ans_k = max(ans_k, max(y-mnc_k, mxc_k-y)*max(n-x-1,x))$。

选择一条经过(x,y)且平行于y轴的最长边，最后可提供贡献$max(y-mnr_k, mxr_k-y)*max(n-y-1,y)$

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n;
    cin >> n;
    vector<string> g(n);
    for (auto& i : g) {
        cin >> i;
    }
    vector<ll> ans(10), mxr(10, -1), mnr(10, 2005), mxc(10, -1), mnc(10, 2005);
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            int num = g[i][j] - '0';
            mxr[num] = max(mxr[num], i);
            mnr[num] = min(mnr[num], i);
            mxc[num] = max(mxc[num], j);
            mnc[num] = min(mnc[num], j);
        }
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            int num = g[i][j] - '0';
            ll r = max(n - i - 1, i);
            ll c = max(n - j - 1, j);
            ans[num] = max(ans[num], r * max(mxc[num] - j, j - mnc[num]));
            ans[num] = max(ans[num], c * max(mxr[num] - i, i - mnr[num]));
        }
    }
    for (ll i : ans) {
        cout << i << " ";
    }
    cout << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

D. Checkpoints

题意

你需要设计一款游戏，这个游戏最多就2000个关卡。

每次尝试一个关卡要么失败要么成功。当成功时进入下一关，当失败时回到上个存档点的关卡，失败与成功的概率都是1/2。

请构造关卡序列，并确定是否需要设置存档点（1代表需要，0代表不要）。使得游戏通关的期望尝试次数是k。

思路

可以看看经典问题的求解。

我们发现构造1就是需要两次尝试；构造11就4次尝试；构造101就要8次尝试；1001就要16次尝试；依次类推。

构造的关卡期望次数都是偶数，对于k如果是奇数那就不可能构造成功。

我们已经构造出了期望次数是2的幂次的关卡，根据期望的线性可加，k可以由这些2的幂次期望次数叠加组成。

我们可分解k的二进制得到组成k的2的幂次。

代码

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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    ll n;
    cin >> n;
    if (n % 2) {
        cout << "-1\n";
    } else {
        string ans;
        for (int i = 1; i < 63; i++) {
            if (n >> i & 1) {
                string s(i, '0');
                s[0] = '1';
                s.back() = '1';
                ans += s;
            }
        }
        cout << ans.size() << "\n";
        for (char i : ans) {
            cout << i << " ";
        }
        cout << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}

E. Dog Snacks

题意

思路

代码

1
2


F. Even Harder

题意

思路

代码

1
2