Codeforces Round 849 (Div. 4)
Powered by:NEFU AB-IN
B站直播录像！
@TOC
Codeforces Round 849 (Div. 4)
A Codeforces Checking
题意
Given a lowercase Latin character (letter), check if it appears in the string codeforces codeforces .
思路
模拟
代码
1#include <bits/stdc++.h>
2using namespace std;
3#define int long long
4#undef int
5
6#define SZ(X) ((int)(X).size())
7#define ALL(X) (X).begin(), (X).end()
8#define IOS \
9 ios::sync_with_stdio(false); \
10 cin.tie(nullptr); \
11 cout.tie(nullptr)
12#define DEBUG(X) cout << #X << ": " << X << '\n'
13typedef pair<int, int> PII;
14
15const int N = 1e5 + 10, INF = 0x3f3f3f3f;
16
17void solve()
18{
19 char a;
20 cin >> a;
21 string s = "codeforces";
22 for (auto x : s)
23 {
24 if (x == a)
25 {
26 cout << "YES\n";
27 return;
28 }
29 }
30 cout << "NO\n";
31 return;
32}
33
34signed main()
35{
36 IOS;
37 int T;
38 cin >> T;
39 while (T--)
40 solve();
41 return 0;
42}B. Following Directions
题意
略
思路
模拟
代码
1/*
2* @Author: NEFU AB-IN
3* @Date: 2023-02-03 22:35:26
4* @FilePath: \CF\1791\b\b.cpp
5* @LastEditTime: 2023-02-03 22:40:58
6*/
7#include <bits/stdc++.h>
8using namespace std;
9#define int long long
10#undef int
11
12#define SZ(X) ((int)(X).size())
13#define ALL(X) (X).begin(), (X).end()
14#define IOS \
15 ios::sync_with_stdio(false); \
16 cin.tie(nullptr); \
17 cout.tie(nullptr)
18#define DEBUG(X) cout << #X << ": " << X << '\n'
19typedef pair<int, int> PII;
20
21const int N = 1e5 + 10, INF = 0x3f3f3f3f;
22
23void solve()
24{
25 int n;
26 cin >> n;
27 string s;
28 cin >> s;
29 int xs = 0, ys = 0;
30 for (auto x : s)
31 {
32 if (x == 'U')
33 ys++;
34 if (x == 'D')
35 ys--;
36 if (x == 'L')
37 xs--;
38 if (x == 'R')
39 xs++;
40 if (ys == 1 && xs == 1)
41 {
42 cout << "YES\n";
43 return;
44 }
45 }
46 cout << "NO\n";
47 return;
48}
49
50signed main()
51{
52 IOS;
53 int T;
54 cin >> T;
55 while (T--)
56 solve();
57 return 0;
58}C. Prepend and Append
题意
Timur initially had a binary string† s(possibly of length 0). He performed the following operation several (possibly zero) times:
Add 0to one end of the string and 1to the other end of the string. For example, starting from the string 1011, you can obtain either 010111or 110110.
You are given Timur's final string. What is the length of the shortest possible string he could have started with?†A binary string is a string (possibly the empty string) whose characters are either 0or 1.思路
模拟即可，两种选择，删到不能再删为止
代码
1/*
2* @Author: NEFU AB-IN
3* @Date: 2023-02-03 22:35:26
4* @FilePath: \CF\1791\c\c.cpp
5* @LastEditTime: 2023-02-03 22:46:12
6*/
7#include <bits/stdc++.h>
8using namespace std;
9#define int long long
10#undef int
11
12#define SZ(X) ((int)(X).size())
13#define ALL(X) (X).begin(), (X).end()
14#define IOS \
15 ios::sync_with_stdio(false); \
16 cin.tie(nullptr); \
17 cout.tie(nullptr)
18#define DEBUG(X) cout << #X << ": " << X << '\n'
19typedef pair<int, int> PII;
20
21const int N = 1e5 + 10, INF = 0x3f3f3f3f;
22
23void solve()
24{
25 int n;
26 cin >> n;
27 string s;
28 cin >> s;
29 int ans = n;
30 for (int i = 0; i < SZ(s); ++i)
31 {
32 if (ans == 0)
33 break;
34 if (s[i] == '0' && s[SZ(s) - i - 1] == '1')
35 ans -= 2;
36 else if (s[i] == '1' && s[SZ(s) - i - 1] == '0')
37 ans -= 2;
38 else
39 {
40 cout << ans << '\n';
41 return;
42 }
43 }
44 cout << ans << '\n';
45 return;
46}
47
48signed main()
49{
50 IOS;
51 int T;
52 cin >> T;
53 while (T--)
54 solve();
55 return 0;
56}D. Distinct Split
题意
Let's denote the f(x)function for a string xas the number of distinct characters that the string contains. For example f(abc)=3, f(bbbbb)=1, and f(babacaba)=3.
Given a string s, split it into two non-empty strings aand bsuch that f(a)+f(b)is the maximum possible. In other words, find the maximum possible value of f(a)+f(b)such that a+b=s(the concatenation of string aand string bis equal to string s).思路
注意这里分字符串，是两者必须连着，也就是两个子串
所以可以预处理到每个点的元素种类，从前往后，从后往前，都处理一遍，最后遍历求最值即可代码
1#include <bits/stdc++.h>
2using namespace std;
3#define int long long
4#undef int
5
6#define SZ(X) ((int)(X).size())
7#define ALL(X) (X).begin(), (X).end()
8#define IOS \
9 ios::sync_with_stdio(false); \
10 cin.tie(nullptr); \
11 cout.tie(nullptr)
12#define DEBUG(X) cout << #X << ": " << X << '\n'
13typedef pair<int, int> PII;
14
15const int N = 1e5 + 10, INF = 0x3f3f3f3f;
16
17void solve()
18{
19 int n;
20 cin >> n;
21 string s;
22 cin >> s;
23 s = '0' + s;
24 unordered_map<char, int> st;
25 vector<int> a(n + 10), b(n + 10);
26 for (int i = 1; i < SZ(s); ++i)
27 {
28 if (!st.count(s[i]))
29 a[i]++;
30 st[s[i]]++;
31 }
32 for (int i = 1; i < SZ(s); ++i)
33 {
34 a[i] += a[i - 1];
35 }
36 st.clear();
37 for (int i = SZ(s) - 1; i >= 1; --i)
38 {
39 if (!st.count(s[i]))
40 b[i]++;
41 st[s[i]]++;
42 }
43 for (int i = SZ(s) - 1; i >= 1; --i)
44 {
45 b[i] += b[i + 1];
46 }
47 int mx = 0;
48 for (int i = 1; i + 1 < SZ(s); ++i)
49 {
50 int ans = a[i] + b[i + 1];
51 mx = max(ans, mx);
52 }
53 cout << mx << '\n';
54 return;
55}
56
57signed main()
58{
59 IOS;
60 int T;
61 cin >> T;
62 while (T--)
63 solve();
64 return 0;
65}E. Negatives and Positives
题意
翻译：可以翻转相邻的两个元素的正负，也就是index isuch that 1≤i≤n−1 and assign a[i]=−a[i] and a[i+1]=−a[i+1]
问数组最大值思路
两种思路
思维
性质：可以发现，翻转相邻两元素正负，如果不限制次数，其实也就相当于，数组中两个任意元素翻转正负
那么就考虑非正数个数的奇偶性即可- 如果是偶数，那么内部消化
- 如果是奇数，绝对值最小的那个负数不翻转即可
线性dp
如果没发现我上面说的性质的话，可以采用dp直接推
我们这里规定：从下标为2开始，i和i-1同时翻转状态表示：
dp[i][0]代表到i处的最大值，此时i和i-1不翻转dp[i][1]代表到i处的最大值，此时i和i-1翻转- 此时i和i-1都必须具有可主动翻转的能力！！，也就是i-1也可策动i-2翻转，所以，i必须大于2
- 所以我们需要预处理
i=1和i=2的情况
状态方程
- 第二个方程解释一下，就是这个是a[i]翻的情况，那么由于dp[i-1][0]的情况是a[i-1]不翻的最大值，那么此时a[i]翻了，就会策动a[i-1]翻，所以要减去两倍的a[i-1]，后面同理
最后输出变或不变的最大值即可
代码
思维
1/*
2* @Author: NEFU AB-IN
3* @Date: 2023-02-04 14:02:33
4* @FilePath: \CF\1791\e\e1.cpp
5* @LastEditTime: 2023-02-04 14:28:27
6*/
7#include <bits/stdc++.h>
8using namespace std;
9#define int long long
10
11#define SZ(X) ((int)(X).size())
12#define ALL(X) (X).begin(), (X).end()
13#define IOS \
14 ios::sync_with_stdio(false); \
15 cin.tie(nullptr); \
16 cout.tie(nullptr)
17#define DEBUG(X) cout << #X << ": " << X << '\n'
18typedef pair<int, int> PII;
19
20const int N = 2e5 + 10, INF = 0x3f3f3f3f;
21
22void solve()
23{
24 int n, sum = 0, neg = 0;
25 cin >> n;
26 vector<int> a(n);
27 for (int i = 0; i < n; ++i)
28 {
29 cin >> a[i];
30 if (a[i] < 0)
31 {
32 neg++;
33 a[i] = -a[i];
34 }
35 sum += a[i];
36 }
37 if (neg % 2)
38 {
39 int mn = *min_element(ALL(a));
40 sum -= 2 * mn;
41 }
42 cout << sum << '\n';
43 return;
44}
45
46signed main()
47{
48 IOS;
49 int T;
50 cin >> T;
51 while (T--)
52 solve();
53 return 0;
54}线性dp
1/*
2* @Author: NEFU AB-IN
3* @Date: 2023-02-03 22:35:26
4* @FilePath: \CF\1791\e\e.cpp
5* @LastEditTime: 2023-02-04 11:07:18
6*/
7#include <bits/stdc++.h>
8using namespace std;
9#define int long long
10
11#define SZ(X) ((int)(X).size())
12#define ALL(X) (X).begin(), (X).end()
13#define IOS \
14 ios::sync_with_stdio(false); \
15 cin.tie(nullptr); \
16 cout.tie(nullptr)
17#define DEBUG(X) cout << #X << ": " << X << '\n'
18typedef pair<int, int> PII;
19
20const int N = 2e5 + 10, INF = 0x3f3f3f3f;
21
22int dp[N][2], a[N];
23
24void solve()
25{
26 memset(a, 0, sizeof a);
27 memset(dp, 0, sizeof dp);
28 int n;
29 cin >> n;
30 for (int i = 1; i <= n; ++i)
31 {
32 cin >> a[i];
33 }
34 dp[1][0] = a[1], dp[1][1] = -a[1];
35 dp[2][0] = a[1] + a[2], dp[2][1] = -a[1] - a[2];
36 for (int i = 3; i <= n; ++i)
37 {
38 dp[i][0] = a[i] + max(dp[i - 1][0], dp[i - 1][1]);
39 dp[i][1] = -a[i] + max(dp[i - 1][0] - 2 * a[i - 1], dp[i - 1][1] + 2 * a[i - 1]);
40 }
41 cout << max(dp[n][0], dp[n][1]) << '\n';
42 return;
43}
44
45signed main()
46{
47 IOS;
48 int T;
49 cin >> T;
50 while (T--)
51 solve();
52 return 0;
53}F. Range Update Point Query
题意
题意：有一个长度为n的数组a, f函数操作为将a[i] 转换为 a[i]每一位的数的和
1 l r: 代表数组中[l, r]中的所有数都进行一次f操作
2 x : 代表输出a[x]思路
此题是好题，可以好好记录一下，和2023牛客寒假训练营第一场的G一样的思路
可以采用DSU，线段树等，这里介绍一个set做法其实可以观察到这个f函数，梯度下降很快，由于数值最大只有1e9，最大的数就是 99999999->72->9，所以最多变两次，之后变成定值，就不会再变了
那么思路就是- 现将所有不是定值的数的下标加入set
- 当出现1操作，即修改时，首先二分找到比l大于等于的第一个下标 (因为可能[l, r]中已经有数是定值，被移出set了)，将其进行f操作并更新回原数组，如果它已经是定值了，则将其移出set。继续根据这个的下标往后找，直到下标超过r，就break
- 当出现2操作，直接输出a中的值即可
代码
1#include <bits/stdc++.h>
2using namespace std;
3#define int long long
4#undef int
5
6#define SZ(X) ((int)(X).size())
7#define ALL(X) (X).begin(), (X).end()
8#define IOS \
9 ios::sync_with_stdio(false); \
10 cin.tie(nullptr); \
11 cout.tie(nullptr)
12#define DEBUG(X) cout << #X << ": " << X << '\n'
13typedef pair<int, int> PII;
14
15const int N = 2e5 + 10, INF = 0x3f3f3f3f;
16
17int f(int x)
18{
19 int ans = 0;
20 while (x)
21 {
22 ans += x % 10;
23 x /= 10;
24 }
25 return ans;
26}
27int a[N];
28
29void solve()
30{
31 int n, m;
32 cin >> n >> m;
33 set<int> st;
34 for (int i = 1; i <= n; i++)
35 {
36 cin >> a[i];
37 if (f(a[i]) != a[i])
38 st.insert(i);
39 }
40 st.insert(n + 1);
41 for (int i = 1; i <= m; i++)
42 {
43 int op;
44 cin >> op;
45 if (op == 1)
46 {
47 int l, r;
48 cin >> l >> r;
49 int val = l;
50 while (1)
51 {
52 auto t1 = st.lower_bound(val);
53 int pos = *t1;
54 if (pos > r)
55 break;
56 a[pos] = f(a[pos]);
57 if (f(a[pos]) == a[pos])
58 st.erase(pos);
59 val = pos + 1;
60 }
61 }
62 else
63 {
64 int pos;
65 cin >> pos;
66 cout << a[pos] << '\n';
67 }
68 }
69}
70
71signed main()
72{
73 IOS;
74 int T;
75 cin >> T;
76 while (T--)
77 solve();
78 return 0;
79}G1. Teleporters (Easy Version)
题意
题意：有0,1,…n个地点，其中1到n处有传送门，现在有m个金币，往左往右走会耗费一个金币，走到第i个传送门，如果该处的传送门还存在的话，那么就可以做这个传送门回0（即原点）并花费此处的金币，这个传送门就不可以再用了
求用传送门的最多次数思路
其实就是个典型的贪心，类似于背包，总体积为m，物体体积为金币+下标，价值为1
由于价值都是一样的，所以一定是体积越小越好，所以直接贪即可之前一直想的是01背包，还写了01背包的逆过程，结果就是浪费时间…
代码
1#include <bits/stdc++.h>
2using namespace std;
3#define int long long
4
5#define SZ(X) ((int)(X).size())
6#define ALL(X) (X).begin(), (X).end()
7#define IOS \
8 ios::sync_with_stdio(false); \
9 cin.tie(nullptr); \
10 cout.tie(nullptr)
11#define DEBUG(X) cout << #X << ": " << X << '\n'
12typedef pair<int, int> PII;
13
14const int N = 2e5 + 10, INF = 0x3f3f3f3f;
15
16int dp[N], v[N], V;
17
18void solve()
19{
20 int n;
21 cin >> n >> V;
22 for (int i = 1; i <= n; ++i)
23 {
24 cin >> v[i];
25 v[i] += i;
26 }
27 sort(v + 1, v + n + 1);
28 int ans = 0;
29 for (int i = 1; i <= n; ++i)
30 {
31 if (V >= v[i])
32 {
33 V -= v[i];
34 ans++;
35 }
36 else
37 break;
38 }
39 cout << ans << '\n';
40 return;
41}
42
43signed main()
44{
45 IOS;
46 int T;
47 cin >> T;
48 while (T--)
49 solve();
50 return 0;
51}
