Codeforces Round #849 (Div. 4)_闫鸿宇

irpas 02-07 5409

Dashboard - Codeforces Round #849 (Div. 4) - Codeforces

Codeforces Checking

参考代码:

#include <bits/stdc++.h> int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; while (t--){ char ch; std::cin >> ch; if (std::string("codeforces").find(ch) != std::string::npos) std::cout << "YES\n"; else std::cout << "NO\n"; } return 0; } B

Following Directions

参考代码：

#include <bits/stdc++.h> void solve(){ int n; std::string s; std::cin >> n >> s; int x{}, y{}; for (auto j : s) { if (j == 'L') x--; else if (j == 'R') x++; else if (j == 'U') y++; else y--; if (x == 1 && y == 1) { std::cout << "YES\n"; return; } } std::cout << "NO\n"; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; while (t--){ solve(); } return 0; } C

Prepend and Append

题意：

字符串 t?可以在一边加上一个?1?，另一边加上一个?0?，最后给定的结果为 s?。求 t?的最短长度。?

思路：

?双指针遍历，模拟。字符串 s?的一边为?1?另一边为?0?时左右指针各向中间移动。

参考代码：

#include <bits/stdc++.h> void solve(){ int n; std::string s; std::cin >> n >> s; int r = n - 1, l{}, ans{}; for (; l < r; l++,r--) { if (s[l] != s[r]) ans++; else break; } std::cout << n - 2 * ans << '\n'; } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int t; std::cin >> t; while (t--){ solve(); } return 0; } D

Distinct Split

题意：

定义 f(x)?为字符串 x?中不同字符的数量。

给定一个字符串 s?，将它分成两个非空字符串 a?和 b?，使得 f(a)+f(b)?是可能的最大值，求该最大值。

思路：

遍历字符串 s?确定每个位置出现的不同字符的数量 cnti?，再逆序遍历与 cnti+1?做比较取最大值。?

参考代码：

inline void solution() { int n, ans{}; string s; cin >> n >> s; vector<int> cnt(n + 1); unordered_set<char> hash; for (int i = n - 1; i >= 0; --i) { hash.emplace(s[i]); cnt[i] = hash.size(); } hash.clear(); for (int i = 0; i < n; ++i) { hash.emplace(s[i]); ans = max(ans, (int) hash.size() + cnt[i + 1]); } cout << ans << '\n'; } E

Negatives and Positives

题意：

给定一个包含 n?个元素的数组 a?，在执行以下操作任意次后，找到数组可能的最大和:

选择?2?个相邻元素并翻转它们的符号。

思路：

数组中第 i?个位置的最大前缀和 sum_i=sum_i?1 ± a_i?，满足无后效性，因此可以用动态规划求解。

另外可以发现若执行操作次数至少为?1?，则必定有一个元素的符号翻转，那么我们先假定这个元素的下标 i?为?0?。

定义 dp[0][i]?为第 i?个元素不执行操作的最大前缀和， dp[1][i]?为第 i?个元素执行操作的最大前缀和。

状态转移方程为：

dp[0][i]=max(dp[0][i?1]+a[i],dp[1][i?1]?a[i])dp[1][i]=max(dp[0][i?1]?a[i],dp[1][i?1]+a[i])?

参考代码：

inline void solution() { int n; cin >> n; vector<int> v(n); cin >> v; vector<vector<long long>> dp(2, vector<long long>(n)); dp[0][0] = v[0]; dp[1][0] = -v[0]; for (int i = 1; i < n; ++i) { dp[0][i] = max(dp[0][i - 1] + v[i], dp[1][i - 1] - v[i]); dp[1][i] = max(dp[0][i - 1] - v[i], dp[1][i - 1] + v[i]); } cout << dp[0][n - 1] << '\n'; } F

Range Update Point Query

思路：

模拟，用set存储数位大于?1?的元素下标，当要用时可以直接在set内查询，时间复杂度由 O(n)?降为 O(logn)。?

参考代码：

inline void solution() { int n, q; cin >> n >> q; vector<int> a(n + 1); set<int> idx; for(int i = 1; i <= n; ++i) { cin >> a[i]; if (a[i] >= 10) idx.emplace(i); } function<int(int)> value = [](int x) { int ret=0; while(x) ret += x % 10 , x /= 10; return ret; }; while(q--) { int cnt; cin >> cnt; if (cnt == 1) { int l, r; cin >> l >> r; auto p = idx.upper_bound(r); for (auto it = idx.lower_bound(l); it != p;) { int i = *it; a[i] = value(a[i]); if (a[i] < 10) it = idx.erase(it); else ++it; } } if (cnt == 2) { int x; cin >> x; cout << a[x] << '\n'; } } }