deforces Round #851 (Div. 2) 1788

发表于 更新于 分类于 ，

    题意

    思路

    代码

    题意

    思路

    代码

    题意

    思路

    代码

    题意

    思路

    代码

    题意

    思路

    代码

Codeforces Round #851 (Div. 2) 1788

Complete problemset

A. One and Two

题意

给出一个只由1和2组成的数组，问能否找到k使得a[1:k]的乘积等于a[k+1:n]的乘积。

思路

统计2的个数c，若为奇数则无解。

否则找到第一个满足a[1:k]中2个数等于c/2的位置k。

代码

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

int a[N];

void sol() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int c = count(a + 1, a + n + 1, 2);
    if (c % 2) {
        cout << "-1\n";
        return;
    }
    for (int i = 1, p = 0; i <= n; i++) {
        p += a[i] == 2;
        if (p == c / 2) {
            cout << i << "\n";
            return;
        }
    }
}
int main() {
    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. Sum of Two Numbers

题意

寻找两个数a，b使得a+b=n

且cnt(a) 与cnt(b)的差值不超过1

cnt(a)为a的十进制各个位之和

思路

设$x = \lfloor \frac{n}{2} \rfloor$，$y = \lceil \frac{n}{2} \rceil$

一种特殊情况就是x低位是连续的9，y的低位是连续的0.

我们将9拆成5和4分配到x和y对应位上。保证差值不超过1

代码

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

ll cnt(ll x) {
    ll rt = 0;
    while (x) {
        rt += x % 10;
        x /= 10;
    }
    return rt;
}

void sol() {
    ll n;
    cin >> n;
    ll a = n / 2, b = n - n / 2;
    if (abs(cnt(a) - cnt(b)) <= 1) {
        cout << a << " " << b << "\n";
        return;
    }
    string sa = to_string(a), sb = to_string(b);
    int sz = sa.size();
    reverse(sa.begin(), sa.end());
    reverse(sb.begin(), sb.end());
    for (int i = 0, c = 0; i < sz; i++) {
        if (sa[i] == '9' && sb[i] == '0') {
            if (c % 2) {
                sa[i] = '4';
                sb[i] = '5';
            } else {
                sa[i] = '5';
                sb[i] = '4';
            }
            c++;
        }
    }
    reverse(sa.begin(), sa.end());
    reverse(sb.begin(), sb.end());
    cout << sa << " " << sb << "\n";
}
int main() {
    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. Matching Numbers

题意

1到2n共2n个数，能否两两相加形成n个数，且n个数构成公差为1的等差数列。

思路

设构成的n个数起始为a，结束于b

则有

b-a=n-1

(1+2n)*2n/2 = (a+b)n/2

得a=(3+3n)/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
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    if ((3 + 3 * n) % 2) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    int s = (3 + 3 * n) / 2;
    for (int i = 2; i <= n; i += 2) {
        cout << i << " " << s - i << "\n";
        s++;
    }
    for (int i = 1; i <= n; i += 2) {
        cout << i << " " << s - i << "\n";
        s++;
    }
}
int main() {
    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. Moving Dots

题意

给出数轴上的n个点，每个点会朝向离自己最近的点移动，如果两侧的点离自己同样远，则朝左移动。当两个点相遇则停止。

求最后所有点都停止后，停止点的个数。

这个问题很简单。

所以现在问n个点的所有大于2的子集所有停止位置个数之和。

思路

同一个停止位置可能在多个子集中出现过。

考虑任意两个相向运动的x，y（x<y）的停止位置在多少个子集中出现过。

设d=y-x，所有小于x-d的点个数为cntl，所有大于等于y+d的点个数为cntr

x和y相遇停止的点的贡献为$2^{cntl}*2^{cntr}$

枚举x和y，二分法可找出cntl和cntr

时间复杂度$O(n^2logn)$

代码

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 ll long long
#define N 500005
#define MOD 1000000007
using namespace std;

ll p[N];
ll a[N];

void sol() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * 2 % MOD;
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            ll d = a[j] - a[i];
            ll lcnt = lower_bound(a, a + n, a[i] - d) - a;
            ll rcnt = n - (lower_bound(a, a + n, a[j] + d) - a);
            ans += p[lcnt] * p[rcnt] % MOD;
            ans %= MOD;
        }
    }
    cout << ans << "\n";
}
int main() {
    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. Sum Over Zero

题意

给出一个长度为n的数组a，现在要选取若干不相交的区间且区间和不小于0，使得所有区间的长度之和最大。

思路

dp

设$f_i$为前i个数中选取若干区间且区间和不小于0，的区间最大值。

$f_0 = 0$

对于$f_i$的求解考虑最后一个区间包不包含$a_i$

若不含$a_i$，则$f_i$由$f_{i-1}$转移

若包含$a_i$，则需要找到sum(a[j…i])≥0的所有j，$f_i$由最大的$f_j+i-j$转移。

设$p_i$为前i个数之和。$p_0 = 0, p_i = p_{i-1}+a_i,i>0$

状态转移方程$f_0 = 0, f_i = \max(f_{i-1}, \max \limits_{p_j\le p_i} (f_j+i-j)),i>0$

可以离散化前缀和数组，然后用线段树或树状数组维护$f_i-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
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
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define NINF 0xf3f3f3f3f3f3f3f3
#define MOD 998244353
using namespace std;

ll p[N], f[N], a[N];

ll ask(int x) {
    ll mx = NINF;
    for (int i = x; i; i -= i & -i) {
        mx = max(mx, a[i]);
    }
    return mx;
}

void add(int x, ll val) {
    for (int i = x; i < N; i += i & -i) {
        a[i] = max(a[i], val);
    }
}

void sol() {
    memset(a, 0xf3, sizeof(a));
    int n;
    cin >> n;
    map<ll, int> idx;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        p[i] += p[i - 1];
        idx[p[i]];
    }
    idx[0];
    int sz = 1;
    for (auto& [i, j] : idx)
        j = sz++;
    add(idx[0], 0);  // add(idx[p[0]], f[0]-0);
    for (int i = 1; i <= n; i++) {
        f[i] = max(f[i - 1], ask(idx[p[i]]) + i);
        add(idx[p[i]], f[i] - i);
    }
    cout << f[n] << "\n";
}
int main() {
    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;
}