Codeforces Div4 849

发表于 更新于 阅读次数： 本文字数： 4.9k 阅读时长 ≈ 9 分钟

Codeforces Round #849 (Div. 4)

E. Negatives and Positives

题目大意

给定一个长度为$n$的数组$a$，问经历任意次下列操作后，数组中所有数之和的最大可能值是多少
每次操作可选定一个$i,1\leq i\leq n-1$，使得$a_i=-a_i,a_{i+1}=-a_{i+1}$

解题思路

典中典的$dp$模型
$dp[i][j]$表示考虑前$i$个数，$j$为$1$时末尾两个数取反，$j$为$0$时末尾两个数没有取反
不过官方正解是思维解法，类似于奇偶位置考虑那种

具体代码

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
#include <bits/stdc++.h>
typedef long long LL;
void E()
{
    int n;
    std::cin >> n;
    std::vector<LL> a(n + 10);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    std::vector<std::vector<LL>> dp(n + 10, std::vector<LL>(5, 0));
    dp[2][0] = a[1] + a[2];
    dp[2][1] = -a[1] - a[2];
    for (int i = 3; i <= n; ++i)
    {
        dp[i][0] = std::max(dp[i - 1][0] + a[i], dp[i - 1][1] + a[i]);
        dp[i][1] = std::max(dp[i - 1][0] - a[i] - 2 * a[i - 1], dp[i - 1][1] - a[i] + 2 * a[i - 1]);
    }
    std::cout << std::max(dp[n][0], dp[n][1]) << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
        E();
    return 0;
}

F. Range Update Point Query

题目大意

给定长度为$n$的数组$a$，处理$q$个询问
询问类型有两种
第一种操作是给定$l，r$使得所有$a_i，l\leq i\leq r$变成其本身的所有数位之和
第二种操作是给定$x$，输出$a_x$

解题思路

和前几天牛客寒假基础训练营的第一场的$G$题有异曲同工处
那道题是一个收敛到$100$的性质，而这道题可以发现
任何一个数字在经历几次第一种操作后都会快速变小，一直收敛到个位数然后不管怎么操作都不变
$a_i$最大才$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
72
73
74
#include <bits/stdc++.h>
typedef long long LL;
const int N = 2e5 + 10;
int n, q;
int a[N], c[N];
int digit_sum(int x)
{
    int res = 0;
    while (x)
    {
        res += x % 10;
        x /= 10;
    }
    return res;
}
void add(int x, int k)
{
    for (; x <= n; x += x & -x)
        c[x] += k;
}
int query(int x)
{
    int res = 0;
    for (; x; x -= x & -x)
        res += c[x];
    return res;
}
void F()
{
    std::cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        c[i] = 0;
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    while (q--)
    {
        int op;
        std::cin >> op;
        if (op == 1)
        {
            int l, r;
            std::cin >> l >> r;
            add(l, 1);
            if (r + 1 <= n)
                add(r + 1, -1);
        }
        else
        {
            int x;
            std::cin >> x;
            int times = query(x);
            int val = a[x];
            while (times)
            {
                val = digit_sum(val);
                --times;
                if (val < 10)
                    break;
            }
            std::cout << val << '\n';
        }
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
        F();
    return 0;
}

G1. Teleporters (Easy Version)

题目大意

数轴上有$0，1，2，3，\cdots，n，n+1$这些点，初始你在$0$这个点，并且有$c$枚金币
除了$0$和$n+1$这两个点，每个点上都有一个传送门，使用传送门的花费是$a_i$枚金币，$1\leq i\leq n$
你可执行三种操作：
$1.$花费$1$金币，向右一格
$2.$花费$1$金币，向左一格
$3.$使用传送门，花费相应金币，回到$0$点，每个传送门最多用一次
问最多可以用多少次传送门

解题思路

每次使用传送门都会回到$0$点，所以使用任意一个传送门的代价是$a_i+i$(向右走$i$格+使用传送门)
那么排序，做个前缀和二分即可(其实$G1$排完序直接遍历用金币减就行，这里是为了和$G2$衔接)

具体代码

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
#include <bits/stdc++.h>
typedef long long LL;
void G1()
{
    int n, c;
    std::cin >> n >> c;
    std::vector<int> a(n + 10);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i], a[i] = a[i] + i;
    std::sort(a.begin() + 1, a.begin() + n + 1);
    std::vector<LL> s(n + 10, 0);
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + (LL)a[i];
    int l = 0, r = n;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (s[mid] <= c)
            l = mid;
        else
            r = mid - 1;
    }
    std::cout << l << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
        G1();
    return 0;
}

G2. Teleporters (Hard Version)

题目大意

数轴上有$0，1，2，3，\cdots，n，n+1$这些点，初始你在$0$这个点，并且有$c$枚金币
除了$0$和$n+1$这两个点，每个点上都有一个传送门，使用传送门的花费是$a_i$枚金币，$1\leq i\leq n$
你可执行三种操作：
$1.$花费$1$金币，向右一格
$2.$花费$1$金币，向左一格
$3.$使用传送门，花费相应金币，回到$0$点或$n+1$点，每个传送门最多用一次
问最多可以用多少次传送门

解题思路

题意唯一的区别就是传送门可以传去$n+1$点
沿着$G1$的想法，容易错误地想成把处理$a_i$的地方改成

1
a[i] = std::min(a[i] + i, a[i] + n + 1 - i);

然后一切照旧即可
这样的错误原因是由于初始在$0$号点，所以一定至少有一个点要取$a_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
#include <bits/stdc++.h>
typedef long long LL;
void G2()
{
    int n, c;
    std::cin >> n >> c;
    std::vector<int> a(n + 10);
    std::vector<int> b(n + 10);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i], b[i] = std::min(a[i] + i, a[i] + n + 1 - i);
    std::sort(b.begin() + 1, b.begin() + n + 1);
    std::vector<LL> s(n + 10, 0);
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + (LL)b[i];
    int ans = 0;
    for (int i = 1; i <= n; ++i) // 这层循环枚举哪一个点作为第一次从左边出发用传送门的点
    {
        if (a[i] + i > c)
            continue;
        int t = std::min(a[i] + i, a[i] + n + 1 - i); // t是枚举的这个点在前缀和中的贡献
        int l = 0, r = n;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (s[mid] <= c - (a[i] + i))
                l = mid;
            else
                r = mid - 1;
        }
        if (b[l] < t) // 说明枚举的这个点没有影响到二分分界
            ans = std::max(ans, l + 1);
        else // 否则补上这个点的贡献再二分一次
        {
            l = 0, r = n;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (s[mid] <= c - (a[i] + i) + t)
                    l = mid;
                else
                    r = mid - 1;
            }
            ans = std::max(ans, l); //注意此时不用加一，因为枚举的这个点已经在二分的左半边
        }
    }
    std::cout << ans << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int T = 1;
    std::cin >> T;
    while (T--)
        G2();
    return 0;
}