A. Codeforces Checking
题意
给定字符是否是codeforces 当中的一个
思路
调用string类的find方法
代码
void solve() { string s = "codeforces"; string a; cin >> a; if (s.find(a) != -1) { cout << "YES" << endl; } else { cout << "NO" << endl; } }
B. Following Directions
题意
给定一串字符串，形如“LUDR”，问能否按字符串走法从（0，0）途经（1，1）。
思路
直接模拟即可
代码
void solve() { cin >> n; string s; cin >> s; int walk[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; auto f = [=](char c){ if (c == 'L') return 3; if (c == 'D') return 2; if (c == 'R') return 1; return 0; }; int x = 0, y = 0; for (auto c: s) { auto d = f(c); x += walk[d][0]; y += walk[d][1]; if (x == 1 && y == 1) { cout << "YES" << endl; return ;} } cout << "NO" << endl; return ; }
C. Prepend and Append
题意
给定01串，每次可以删除两侧各一个字符，但是这两个同时删除的字符必需不同，即（01，10）。问最后能剩下的字符串最小值。
思路
贪心，能删则删，维护删除的次数。
代码
void solve() { cin >> n; string s; cin >> s; int cnt = 0; for (int i = 0, j = s.sz - 1; i < j; i++, j--) { if (s[i] != s[j]) cnt++; else break; } cout << n - cnt * 2 << endl; }
D. Distinct Split
进阶一点的相似题型 -> 【传送门】
题意
规定 f ( " a b c " ) f("abc")f("abc") 表示字符串 “abc” 的不同字符数，即f ( " a b c " ) = 3 f("abc")=3f("abc")=3。
现在给定一个字符串 s ss，问：s ss分为两个字符串(a , b a,ba,b)后求值 f ( a ) + f ( b ) f(a) + f(b)f(a)+f(b) 的最大值。
思路
显然需要动态维护一串字符串的不同字符数，那么用 map 维护，当字符数变0需要erase掉当前的键，而 map.size() 就是当前该字符串的不同字符数，即是不同的键的数量。
先预处理整个串的 f ( s ) f(s)f(s)作为后缀，然后正序遍历进行分割，动态增加前缀串，删除后缀串的 map 所维护的键值对。
代码
void solve() { cin >> n; string s; cin >> s; map<char, int> f, g; for (auto c: s) g[c]++; int res = 0; for (int i = 0; i < n; i++) { auto c = s[i]; f[c]++; g[c]--; if (g[c] == 0) g.erase(c); res = max(res, (int)(f.size() + g.size())); } cout << res << endl; }
E. Negatives and Positives
题意
思路
可以发现的性质是，一段区间内的修改实际上等价于区间两侧的修改，即任意位置的一对可以同时变为其相反数。
那么如果数组中有偶数个负数，可以直接全变为正数。
否则数组有奇数个负数，那么第一想法肯定是选最大的负数留下。
但是考虑到会有比该负数的绝对值更小的正数，这样最优应是让这个正数变负。
实现：以上描述实际上就是挑一个绝对值最小的数作为负数处理，前提是当前数组中有奇数个负数。
代码
void solve() { cin >> n; vi v; int sum = 0; int cnt = 0; rep (i, 1, n) { int x; cin >> x; if (x < 0) { cnt ++; x = -x; } v.pb(x); sum += x; } sort(all(v)); if (cnt & 1) sum -= 2 * v[0]; cout << sum << endl; }
F. Range Update Point Query
题意
数组 a aa，有 q qq 个询问，每次询问如下：
l r：表示 l , r 区间的数进行操作。【操作：a i变为a i
各个数位之和】
2 x：表示输出当前的 a x
思路
代码
线段树
维护当前区间是否还需要更改，即存在 >= 10 的数。
int n, m; int a[N]; struct node { int l, r; int val, mx; } tr[N << 2]; void pushup(int u) { tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx); } int f(int x) { int res = 0; while (x) { res += x % 10; x /= 10; } return res; } void build(int u, int l, int r) { tr[u].l = l, tr[u].r = r; if(l == r) { tr[u].val = a[l]; tr[u].mx = a[l]; return ; } int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } void modify(int u, int l, int r) { if (tr[u].mx < 10) return ; if(tr[u].l == tr[u].r) { int x = f(a[tr[u].l]); a[tr[u].l] = x; tr[u].val = x; tr[u].mx = x; return ; } int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(u << 1, l, r); if(r > mid) modify(u << 1 | 1, l, r); pushup(u); } int query(int u, int x) { if(x == tr[u].l && x == tr[u].r) return tr[u].val; int mid = tr[u].l + tr[u].r >> 1; if(x <= mid) return query(u << 1, x); return query(u << 1 | 1, x); } void solve() { cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> a[i]; build(1, 1, n); while(m --) { int op, l, r; cin >> op; if(op == 1) { cin >> l >> r; modify(1, l, r); } else { int x; cin >> x; cout << query(1, x) << endl; } } }
- 树状数组
- 差分，前缀维护当前更改的次数。预处理每个数的修改。
class BIT { public: BIT() { memset(tr, 0, sizeof tr); } int tr[N]; void add(int x, int v = 1) { for (; x < N; x += x & -x) tr[x] += v; } int sum(int x) { int res = 0; for (; x; x -= x & -x) res += tr[x]; return res; } }; int n, m; void solve() { cin >> n >> m; auto f = [=](int x){ int res=0;while(x){res+=x%10;x/=10;}return res;}; vi v[n + 1]; for(int i = 1; i <= n; i ++) { int x; cin >> x; while (1) { v[i].pb(x); if (x < 10) break; x = f(x); } } BIT t; while(m --) { int op, l, r; cin >> op; if(op == 1) { cin >> l >> r; t.add(l, 1); t.add(r + 1, -1); } else { int x; cin >> x; cout << v[x][min(t.sum(x), (int)v[x].sz - 1)] << endl; } } }
G1. Teleporters (Easy Version)
题意
0为原点，1~n有n个数，总共体力k点。在k点体力下，要求能拿到最多几个数。拿数的要求是：从0开始走到x，花费x点体力，从x拿到数返回0，花费a[x]点体力。每次拿完一个数需要返回0点。
思路
贪心
代码
int n, m; int a[N]; void solve() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; a[i] += i; } sort(a + 1, a + 1 + n); int res = 0; for (int i = 1; i <= n; i++) { if (m >= a[i]) res++, m -= a[i]; } cout << res << endl; }
