Codeforces Round 905 (Div.2)

题目链接

Codeforces Round 905 (Div.2)

Problem A: Chemistry

  • 时间限制: 2秒
  • 内存限制: 256MB

题目描述

　　给定一个长度为$n$的仅由小写字母组成的字符串$S$，你需要删除$k$个字符，但是删除哪些字符由你决定，删除完$k$个字符之后剩余的字符你可以随意排列，请问你是否有机会得到一个回文串，即：存在一种删除方案和一种排列方案使得最终的字符串$T’=t_{1}t_{2}…t_{n-k}$满足：$t_1=t_{n-k}$ , $t_2=t_{n-k-1}$，…

  • 输入描述
    　　第一行，一个正整数$t(1 \le t \le 10^{4} )$，表示接下来有$t$组数据。
    　　接下来每组数据的第一行，正整数$n$和$k$ $(0\le k < n \le 10^5)$，分别表示字符串的长度$n$和要删除的字符个数$k$。
    　　第二行，一个长度为$n$的字符串。
    　　输入数据满足：$t$组数据的所有$n$的值总和不超过$2*10^5$。

  • 输出描述
    　　对于每一组数据，如果存在相应方案，则输出一行“YES”，否则输出一行“NO”。

解题思路

　　回文串的长度如果是偶数，那么任意字符都出现偶数次，如果是奇数，那么会恰好有一个字符出现奇数次。题目给出了n和k，那么最终串的长度的奇偶是可以确定的。
　　如果是偶数，那么我删除掉$k$个字符之后剩下字符的种类出现的次数应该都是偶数才能排成回文串。如果在我删掉之前，出现次数是奇数的字符种数的奇偶性和k的奇偶性一致,并且这个种数不大于k，那么就可以让最终剩下的都出现偶数次，反之则必然出现奇数次的，所以这种情况下希望它们一致。
　　如果是奇数，则希望它们不一致。当然，同样需要种数不大于k+1（这里+1是因为可以保留1个奇数次，就不需要动它了）。根据以上思路，想要解决这题就很简单了。

解题代码(C++)

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
#include <iostream>
#include <string>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        /* 此处处理一组独立数据 */
        int n, k;
        int count[128] = {0};
        cin >> n >> k;
        string s;
        cin >> s;
        for (auto &c : s)
        {
            count[c]++;
        }
        int oddCount = 0; // 出现奇数次的种数
        for (char c = 'a'; c <= 'z'; ++c)
        {
            if (count[c] % 2)
            {
                oddCount++;
            }
        }
        bool ans = false;
        /* 可以构造的条件1：最终长度偶数，oddCount和k奇偶一致 */
        if ((n - k) % 2 == 0 && (oddCount % 2) == (k % 2) && oddCount <= k)
        {
            ans = true;
        }
        /* 可以构造的条件2：最终长度奇数，oddCount和k奇偶不一致 */
        if ((n - k) % 2 && (oddCount % 2) != (k % 2) && oddCount <= k + 1)
        {
            ans = true;
        }
        if (ans)
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
    return 0;
}

Problem B: Raspberries

  • 时间限制：2秒
  • 内存限制：256 MB

题目描述

　　给定一个长度为$n$的数组$A = a_1,a_2,…,a_n$和一个正整数$k(2 \le k \le 5)$，你可以对数组执行以下操作若干次：
　　选取一个下标$i(1\le i \le n)$，令$a_i = a_i + 1$。
　　问：至少需要执行多少次操作才能使得数组所有元素的乘积能够被$k$整除？

  • 输入描述
    　　第一行，一个正整数$t(1 \le t \le 10^4)$，表示接下来有$t$组数据。
    　　每组数据第一行，正整数$n,k(2 \le n \le 10^5, 2\le k \le 5)$，分别表示数组$A$的长度和除数$k$。
    　　第二行，$n$个整数，分别表示$a_1,a_2,…,a_n( 1 \le a_i \le 10)$。
    　　输入数据满足：$t$组数据的所有$n$的值总和不超过$2*10^5$。

  • 输出描述
    　　对于每组数据，输出一个整数，表示你认为所需要的最少操作次数。

解题思路

　　$k$的范围很小，感觉可能是分类讨论，$k=2$时很好判断，就看数列里有没有偶数就可以了，有就0次，没有就1次。$k=3$时也很好判断，就是判断数列中哪个数离它下一个3的倍数最近，这个最近的距离就是答案。$k=5$时也很简单，同样是看离下一个5的倍数最近的那个距离，事实上，只要是质数，就可以按这样的方法处理。$k=4$呢？如果数列里已经有4的倍数了那就0次，除此之外，如果有1个2的倍数，那就需要再构建出一个2的倍数，只需要1次。如果有两个2的倍数，那么也是0，如果一个都没有，一种方案是构建4的倍数，一种方案是构建两个2的倍数，两种都计算一下次数取最小值就行。好像就这几种情况，分类讨论就可以了，然后把可以合并的情况给合并一下，减少无用代码。

解题代码(C++)

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
#include <iostream>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
int arr[100005];
void solve()
{
    int n, k;
    cin >> n >> k;
    int ans = 1000000;
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        ans = min(ans, (k - (arr[i] % k)) % k);
    }
    if (k == 4)
    {
        int count = 0;
        for (int i = 1; i <= n; ++i)
        {
            if (arr[i] % 2 == 0)
            {
                count++;
            }
        }
        ans = min(ans, 2 - min(2, count));
    }
    cout << ans << "\n";
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Problem C: You Are So Beautiful

  • 时间限制：1秒
  • 内存限制：256 MB

题目描述

　　给定一个长度为$n$的数组$A=a_1,a_2,…,a_n$，问该数组有多少个非空子数组是唯一存在而且在原数组位置上连续的？例如数组$[1,1,3,5,7]$，可以选中其中的第$1,3,5$个元素构成子数组$[1,3,7]$，但是它不是唯一存在的，因为我选取第$2,3,5$个元素也能构成一样的结果。而子数组$[3,5,7]$就是唯一存在且连续的，而若选取第$2,3,4$个元素得到$[1,3,5]$虽然连续，但是不唯一存在。

  • 输入描述
    　　第一行，一个正整数$t(1\le t \le 10^4)$，表示接下来有$t$组测试数据。
    　　对于每组数据的第一行，一个正整数$n(1\le n \le 10^5)$，表示数组的长度。
    　　第二行，$n$个正整数，表示$a_1,a_2,…,a_n(1\le a_i \le 10^9)$。
    　　输入数据满足：$t$组数据的所有$n$的值总和不超过$2*10^5$。

  • 输出描述
    　　对于每组数据，输出一个整数，表示你认为的符合条件的子数组的数量。

解题思路

　　假设一个连续的子数组$[a_i,a_{i+1},…,a_j]$是符合条件的，那么$a_i$的左边一定不会再有$a_i$出现了，同样的，$a_j$右边也不会再有$a_j$出现。我可以先统计一下每个元素出现的最左边的位置和最右边的位置，每个最左的位置和每个最右的位置相组合得到的区间$[L,R]$对应的连续子数组一定是唯一的！并且不会落下任何合法的子数组。
　　因此，我们可以借助C++的map来维护元素的最左位置和最右位置。再把它们汇总成两个数组，不需要知道这个位置上是哪个元素，只需要知道这个位置本身就行。然后将$L,R$两个数组按大小排个序，然后枚举一方，再通过二分法计算另一方的能够组成合法区间的分界位置（选取$L$中的元素作为左边界，$R$中的作为右边界，而左边界总不能在右边界的右边），从而计数。这样最终时间复杂度是$O(n*\log_2{n})$的，可以通过本题。

解题代码(C++)

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
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
int arr[200005];
void solve()
{
    int n;
    cin >> n;
    map<int, int> minIndex, maxIndex;
    vector<int> L, R;
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        maxIndex[arr[i]] = i;
    }
    for (int i = n; i >= 1; --i)
    {
        minIndex[arr[i]] = i;
    }
    for (auto &[u, v] : minIndex)
    {
        L.push_back(v);
    }
    for (auto &[u, v] : maxIndex)
    {
        R.push_back(v);
    }
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());
    long long ans = 0; //不开long long见祖宗
    for (auto l : L)
    {
        auto iter = lower_bound(R.begin(), R.end(), l);
        ans += R.end() - iter;
    }
    cout << ans << "\n";
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Problem D1: Dances (Easy version)

  • 时间限制：3秒
  • 内存限制：256 MB

题目描述

　　给定两个长度为$n$的数组$A,B$，现在有这样一个问题：你可以先各自将两个数组任意排列，然后在数列非空的前提下，你可以从$A,B$中各自删去一个任意位置上的数从$A$中删除的元素所在位置和$B$删除的位置不需要相同，然后剩下的元素会形成新的数组，这样的操作你可以执行任意次。最少需要执行多少次才能使得最终的数组满足：如果还存在$k$个元素，那么对于所有的$i \in [1,k] \cap \mathbb{Z}$，有：$a_i < b_i$，其中$\mathbb{Z}$代表整数域。
　　上述问题并不是你需要解决的最终问题，你需要解决的最终问题是：在给定上述的两个长度为$n$的数组的情况下，再给定一个正整数$m$。问，在数组$A$的首位元素$a_1$分别变为$1,2,…,m$的$m$种情况下，它们对应的上述问题的答案的总和是多少？
　　本题为简单版本，$m$的值恒定为$1$。在困难版本中，$m$的取值范围是$1\le m \le 10^9$。

  • 输入描述
    　　第一行，一个正整数$t$，表示接下来有$t$组测试数据。
    　　每组测试数据的第一行，正整数$n,m(2 \le n \le 10^5, m = 1)$，分别表示两个数组的长度以及要处理的子问题个数。
    　　第二行，$n-1$个整数，代表$a_2,a_3,…a_n(1 \le a_i \le 10^9)$，由于$a_1$的取值由$m$决定，因此此处不进行无意义的数据输入。
    　　第三行，$n$个整数，代表$b_1,b_2,…,b_n(1 \le b_i \le 10^9)$。
    　　输入数据满足：$t$组数据的所有$n$的值总和不超过$10^5$。

  • 输出描述
    　　对于每组测试数据，输出一个整数，表示该组数据的$m$个子问题答案的总和。

解题思路

　　没想出来（MD没注意到可以任意排序，想半天没想出来跟这个脱不了干系！），我去看了官方的题解。首先采用二分答案法，假定两数组各删去$k$个元素，判断在两数组都剩下$n-k$个元素的情况下是否可能存在合法的数组$A,B$满足题意。判断方式很简单，方法如下：将数组$A,B$升序排序，从$A$中删掉$k$个最大元素，从$B$中删掉$k$个最小元素，然后将最后剩下的元素配对比较一下看是否符合条件。
　　在困难版本下，$m$的取值范围是$1\le m \le 10^9$，由于改变的只会是$a_1$元素的值，它值的变化至多只会给问题的答案造成1的影响。比如，在$a_1$取值很小时，或许可以保留它的存在，而当它增大到越过某个临界点的时候，就需要将它删去，于是答案增加了1。可以通过二分法来找到这个临界点，从而得到两个范围$[1,k],[k+1,m]$，并计算一下其中一个范围时答案对应的值，比如$[1,k]$范围内需要删$x$次，那么$[k+1,m]$范围内就需要删除$x+1$次，于是最终答案就是$k*x + (m - k) * (x + 1)$。

解题代码(简单版本, C++)

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
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
int a[200005];
int b[200005];
void solve()
{
    int n, m;
    cin >> n >> m;
    a[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        cin >> b[i];
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    // 二分答案 求需要删除的最少次数
    int l = 0, r = n;
    // 假定删除k次时的校验函数
    auto check = [&](int k)
    {
        for (int i = 1; i <= n - k; ++i)
        {
            if (a[i] >= b[k + i])
            {
                return false;
            }
        }
        return true;
    };
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l << "\n";
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

解题代码(困难版本, C++)

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <vector>
#include <queue>
#include <map>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
int src_a[200005];
int src_b[200005];
int a[200005];
int b[200005];
int n;
int solve(int first)
{
    memcpy(a, src_a, sizeof(int) * (n + 1));
    memcpy(b, src_b, sizeof(int) * (n + 1));
    a[1] = first;
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    // 二分答案 求需要删除的最少次数
    int l = 0, r = n;
    // 假定删除k次时的校验函数
    auto check = [&](int k)
    {
        for (int i = 1; i <= n - k; ++i)
        {
            if (a[i] >= b[k + i])
            {
                return false;
            }
        }
        return true;
    };
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return l;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int m;
        cin >> n >> m;
        for (int i = 2; i <= n; ++i)
        {
            cin >> src_a[i];
        }

        for (int i = 1; i <= n; ++i)
        {
            cin >> src_b[i];
        }
        int ans_min = solve(1);
        int ans_max = solve(m);
        if (ans_min == ans_max)
        {
            cout << (long long)ans_min * m << "\n";
            continue;
        }
        /* 最终的l和r都会等于能让答案+1的首元素取值的最小值 */
        int l = 1, r = m;
        while (l < r)
        {
            int mid = (l + r) >> 1;
            if (solve(mid) > ans_min)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        cout << (long long)ans_min * (l - 1) + (long long)ans_max * (m - l + 1) << "\n";
    }
    return 0;
}

Problem E: Time Travel

  • 时间限制：2秒
  • 内存限制：512 MB

题目描述

　　现在有一个国家，内部有$n$个不同的地区，但是地区之间的交通道路并不总是可用的，只有在某几个特定的时间可以通行，而且道路是双向的。你有一台时光机，它可以让你穿梭于不同的时间。 但是它每次穿梭时间时到达的目标时间都是既定好的，你没法自主控制，不过你清楚地知道它穿梭的时间设定。在通过一条道路之后，时光机会自动执行一次，这意味着你无法在某个时间连续走完两条道路。现在给出地区的数量$n$，以及$t$个不同的特殊时间。对于每个特殊时间$t_i$，会给出一个可通行道路数量$m_i$和列表$[(u_1,v_1),(u_2,v_2),…,(u_{m_i},v_{m_i})]$。然后给出时光机可进行穿梭时间的次数$k$，以及这$k$次穿梭对应的目标时间$a_1,a_2,…,a_k$。你最初会在地区$1$，并且处于时间$a_1$。问：你最少需要经过多少次时间穿梭才能够到达区域$n$？（到达最终目标区域$n$之后时光机的自动执行不计入统计）

  • 输入描述
    　　第一行，正整数 $n,t(2\le n\le 2*10^5,1\le t\le 2*10^5)$ 分别表示区域个数和特定时间个数。
    　　接下来有 $t$ 组数据，第 $i$ 组数据的第一行，一个非负整数 $m_i(0 \le m_i \le \min(\frac{n(n-1)}{2}, 2*10^5))$ 代表在第 $i$ 个特定时间所能通行的道路数量。
    　　第 $i$ 组数据的接下来$m_i$行，每行两个正整数 $u_j,v_j(1\le u_j,v_j\le n, u_j \neq v_j)$ ，代表一条道路所连接的两个区域。
    　　接收完 $t$ 组时间点的道路数据之后，接下来一行，一个正整数 $k(1\le k \le 2*10^5)$ ，表示时光机可穿梭的次数。
    　　接下来一行， $k$ 个正整数 $a_1,a_2,…,a_k(1\le a_i \le t)$ ，表示时光机每次穿梭后的时间点。
    　　输入数据保证：所有的$m_i$总和不超过$2*10^5$。每个时间点对应的道路数据不会有重复（即使是 $(u,v)和(v,u)$ 也不会同时存在）。

  • 输出描述
    　　一个整数，表示从区域$1$到达区域$n$所需的最小穿梭次数，如果无法到达，那么输出$-1$。

解题思路

　　Dijkstra最短路(堆优化版本)，需要维护数组 $D={d_1,d_2,…,d_n}$ ， $d_i$ 表示到达第 $i$ 个区域时最早可以是在第几次穿梭之后。需要维护所有的边可通行的时间列表，在再维护所有时间所在的穿梭轮次列表，这样在后面处理数据的时候就可以根据边得到这条边对应的可行穿梭轮次列表（列表会有多个），每个列表都要升序排序（数据输入的顺序就是升序的，存下来后不需要额外排序），后面需要用到二分查找。 $(u,v)和(v,u)$ 是同一条边，共用所有的数据即可。
　　然后就是基本的Dijkstra最短路算法，只不过在更新邻近点的$d_v$值时需要找到能够前往$v$的最早轮次。当前我们到达 $u$ 时最早可能处于 $d_u$ 次穿梭之后，枚举与$u$相连的所有边 $(u,v)$ ，对于每条边$(u,v)$：先获取允许它通行的时间列表 $[t_1,t_2,…t_x]$ ，枚举所有的 $t_i$ ，获取到其所在的穿梭轮次列表 $[idx_1,idx_2,…idx_y]$ ，这样你得到的列表就是允许该边通行的穿梭轮次列表之一，通过二分法找到在当前列表允许它通行的晚于当前轮次的最早轮次，然后维护多个列表的最小轮次，最终得到的就是需要的允许该边通行而且晚于当前轮次的最早轮次。假设得到 $y$ ，那么令 $d_v = \min(d_v, y)$ ，就是假设等待到这个轮次之后前往 $v$ ，如果发现这样走能在更早的轮次到达，就更新数据，也就是Dijkstra的基本操作了。

解题代码(C++)

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <algorithm>
#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>
#include <list>
#include <map>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;
bool vis[200005];
int dis[200005];
map<pair<int, int>, vector<int>> edgeTime; /*边->可通行时间列表*/
vector<int> timeIndex[200005];             /*时间->穿梭轮次列表*/
vector<int> edge[200005];                  /*节点拥有的邻居列表*/
int main()
{
    int n, t;
    cin >> n >> t;
    for (int i = 1; i <= t; ++i)
    {
        int m;
        cin >> m;
        for (int j = 0; j < m; ++j)
        {
            int u, v;
            cin >> u >> v;
            edge[u].push_back(v);
            edge[v].push_back(u);
            if (u > v)
            {
                swap(u, v);
            }
            edgeTime[make_pair(u, v)].push_back(i);
        }
    }
    int k;
    cin >> k;
    for (int i = 1; i <= k; ++i)
    {
        int target;
        cin >> target;
        timeIndex[target].push_back(i);
    }
    for (int i = 1; i <= n; ++i)
    {
        dis[i] = 1e9;
        vis[i] = false;
    }
    dis[1] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    que.push(make_pair(dis[1], 1));
    while (!que.empty())
    {
        auto node = que.top();
        que.pop();
        if (vis[node.second])
        {
            continue;
        }
        vis[node.second] = true;
        for (int v : edge[node.second])
        {
            int u = node.second;
            // 当前节点u，目标节点v，需要边(u, v)
            // 需要找到让该边可通行的比现在晚的最早穿梭轮次（当前为node.first轮）
            int index = 1e7;
            // 遍历当前边可通行的时间列表（当前为node.first轮）
            vector<int> &passTimeList = edgeTime[make_pair(min(u, v), max(u, v))];
            for (auto _time : passTimeList)
            {
                vector<int> &vec = timeIndex[_time];
                auto iter = upper_bound(vec.begin(), vec.end(), node.first);
                if (iter != vec.end())
                {
                    index = min(index, *iter);
                }
            }
            if (index == 1e7)
            {
                continue;
            }
            if (index < dis[v])
            {
                dis[v] = index;
                que.push(make_pair(dis[v], v));
            }
        }
    }
    if (dis[n] == 1e9)
    {
        cout << "-1\n";
    }
    else
    {
        cout << dis[n] << '\n';
    }
    return 0;
}
Codeforces
#编程
Codeforces Round 905 (Div.2)
https://mxx23.github.io/2023/10/26/Codeforces-Round-905-Div-2/
作者
mxx
发布于
2023年10月26日
许可协议