Codeforces Round 849 (Div. 4)
摘要
Title: Codeforces Round 799 (Div. 4)
Tag: set，dp
Problem: A, B, C, D, E, F, G1
Powered by:NEFU AB-IN
- A Codeforces Checking
- B. Following Directions
- C. Prepend and Append
- D. Distinct Split
- E. Negatives and Positives
- F. Range Update Point Query
- G1. Teleporters (Easy Version)
Codeforces Round 849 (Div. 4)
-
A Codeforces Checking
-
题意
Given a lowercase Latin character (letter), check if it appears in the string codeforces codeforces .
-
思路
模拟
-
代码
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
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
void solve()
{
char a;
cin >> a;
string s = "codeforces";
for (auto x : s)
{
if (x == a)
{
cout << "YES\n";
return;
}
}
cout << "NO\n";
return;
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
solve();
return 0;
}
-
-
B. Following Directions
-
题意
略
-
思路
模拟
-
代码
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/*
* @Author: NEFU AB-IN
* @Date: 2023-02-03 22:35:26
* @FilePath: \CF\1791\b\b.cpp
* @LastEditTime: 2023-02-03 22:40:58
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int xs = 0, ys = 0;
for (auto x : s)
{
if (x == 'U')
ys++;
if (x == 'D')
ys--;
if (x == 'L')
xs--;
if (x == 'R')
xs++;
if (ys == 1 && xs == 1)
{
cout << "YES\n";
return;
}
}
cout << "NO\n";
return;
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
solve();
return 0;
}
-
-
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
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/*
* @Author: NEFU AB-IN
* @Date: 2023-02-03 22:35:26
* @FilePath: \CF\1791\c\c.cpp
* @LastEditTime: 2023-02-03 22:46:12
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
int ans = n;
for (int i = 0; i < SZ(s); ++i)
{
if (ans == 0)
break;
if (s[i] == '0' && s[SZ(s) - i - 1] == '1')
ans -= 2;
else if (s[i] == '1' && s[SZ(s) - i - 1] == '0')
ans -= 2;
else
{
cout << ans << '\n';
return;
}
}
cout << ans << '\n';
return;
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
solve();
return 0;
}
-
-
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
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
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
void solve()
{
int n;
cin >> n;
string s;
cin >> s;
s = '0' + s;
unordered_map<char, int> st;
vector<int> a(n + 10), b(n + 10);
for (int i = 1; i < SZ(s); ++i)
{
if (!st.count(s[i]))
a[i]++;
st[s[i]]++;
}
for (int i = 1; i < SZ(s); ++i)
{
a[i] += a[i - 1];
}
st.clear();
for (int i = SZ(s) - 1; i >= 1; --i)
{
if (!st.count(s[i]))
b[i]++;
st[s[i]]++;
}
for (int i = SZ(s) - 1; i >= 1; --i)
{
b[i] += b[i + 1];
}
int mx = 0;
for (int i = 1; i + 1 < SZ(s); ++i)
{
int ans = a[i] + b[i + 1];
mx = max(ans, mx);
}
cout << mx << '\n';
return;
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
solve();
return 0;
}
-
-
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
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/*
* @Author: NEFU AB-IN
* @Date: 2023-02-04 14:02:33
* @FilePath: \CF\1791\e\e1.cpp
* @LastEditTime: 2023-02-04 14:28:27
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
void solve()
{
int n, sum = 0, neg = 0;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
{
cin >> a[i];
if (a[i] < 0)
{
neg++;
a[i] = -a[i];
}
sum += a[i];
}
if (neg % 2)
{
int mn = *min_element(ALL(a));
sum -= 2 * mn;
}
cout << sum << '\n';
return;
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
solve();
return 0;
}
线性dp
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/*
* @Author: NEFU AB-IN
* @Date: 2023-02-03 22:35:26
* @FilePath: \CF\1791\e\e.cpp
* @LastEditTime: 2023-02-04 11:07:18
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int dp[N][2], a[N];
void solve()
{
memset(a, 0, sizeof a);
memset(dp, 0, sizeof dp);
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
dp[1][0] = a[1], dp[1][1] = -a[1];
dp[2][0] = a[1] + a[2], dp[2][1] = -a[1] - a[2];
for (int i = 3; i <= n; ++i)
{
dp[i][0] = a[i] + max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = -a[i] + max(dp[i - 1][0] - 2 * a[i - 1], dp[i - 1][1] + 2 * a[i - 1]);
}
cout << max(dp[n][0], dp[n][1]) << '\n';
return;
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
solve();
return 0;
}
-
-
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
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
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int f(int x)
{
int ans = 0;
while (x)
{
ans += x % 10;
x /= 10;
}
return ans;
}
int a[N];
void solve()
{
int n, m;
cin >> n >> m;
set<int> st;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (f(a[i]) != a[i])
st.insert(i);
}
st.insert(n + 1);
for (int i = 1; i <= m; i++)
{
int op;
cin >> op;
if (op == 1)
{
int l, r;
cin >> l >> r;
int val = l;
while (1)
{
auto t1 = st.lower_bound(val);
int pos = *t1;
if (pos > r)
break;
a[pos] = f(a[pos]);
if (f(a[pos]) == a[pos])
st.erase(pos);
val = pos + 1;
}
}
else
{
int pos;
cin >> pos;
cout << a[pos] << '\n';
}
}
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
solve();
return 0;
}
-
-
G1. Teleporters (Easy Version)
-
题意
题意：有0,1,…n个地点，其中1到n处有传送门，现在有m个金币，往左往右走会耗费一个金币，走到第i个传送门，如果该处的传送门还存在的话，那么就可以做这个传送门回0（即原点）并花费此处的金币，这个传送门就不可以再用了
求用传送门的最多次数 -
思路
其实就是个典型的贪心，类似于背包，总体积为m，物体体积为金币+下标，价值为1
由于价值都是一样的，所以一定是体积越小越好，所以直接贪即可之前一直想的是01背包，还写了01背包的逆过程，结果就是浪费时间…
-
代码
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
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int dp[N], v[N], V;
void solve()
{
int n;
cin >> n >> V;
for (int i = 1; i <= n; ++i)
{
cin >> v[i];
v[i] += i;
}
sort(v + 1, v + n + 1);
int ans = 0;
for (int i = 1; i <= n; ++i)
{
if (V >= v[i])
{
V -= v[i];
ans++;
}
else
break;
}
cout << ans << '\n';
return;
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
solve();
return 0;
}
-