A 回文大师
B 价值序列
题意：价值定义为：sum( | ai - ai+1 | ) ，求有多少子序列价值等于 给定原序列的价值。
思路： 1. 结论：删除一个数，价值必定不增 2. 相等的数看成连通块： 1. 若a_i-1 < a_i = ... = a_j < a_j+1 或反向，则这样的区间对答案的贡献为：2^(j-i+1)。 2. 否则对答案的贡献为： 2^(j-i+1) - 1
int n; int a[N]; void solve() { cin >> n; Rep(i, 1, n) cin >> a[i]; int res = 1; for (int i = 1; i <= n; i++) { int j = i; while(j < n && a[j + 1] == a[i]) j++; if(i - 1 >= 1 && j + 1 <= n && (a[i - 1] < a[i] && a[j + 1] > a[i] || a[i - 1] > a[i] && a[j + 1] < a[i])) { res = res * qmi(2, j - i + 1) % mod; } else { res = res * (qmi(2, j - i + 1) + mod - 1) % mod; } i = j; } cout << res << endl; }
C 数组划分
D 删除子序列
题意：给定字符串s，t，问从s中能删除t的最大次数。
思路： 1. DP： dp[i]表示字符串t长度为i的删除次数。 2. 转移方程：dp[i] = min(dp[i - 1]，dp[i] + 1)
int dp[N]; string s, t; int n, m; void solve() { cin >> n >> m; cin >> s >> t; rep(i, 0, m + 1) dp[i] = 0; rep(i, 0, n) { rep(j, 0, m) { if(s[i] == t[j]) { if(j == 0) dp[j] += 1; else dp[j] = min(dp[j - 1], dp[j] + 1); } } } cout << dp[m - 1] << endl; }
E 骑士
找到最大，次大就行
void solve() { int n; cin >> n; int x = 0, y = 0; rep(i, 0, n) { cin >> e[i].a >> e[i].b >> e[i].h; if(e[i].a > x) { y = x; x = e[i].a; } else if(e[i].a == x) { y = x; } else if(e[i].a > y) { y = e[i].a; } } int res = 0; rep(i, 0, n) { if(e[i].a == x) { res += max(0ll, y - e[i].b - e[i].h + 1); } else if(e[i].a < x) { res += max(0ll, x - e[i].b - e[i].h + 1); } } cout << res << endl; }
F ±串
void solve() { string s; cin >> s; int k; cin >> k; int x = 0; for (int i = 0; i < s.sz; i++) if(s[i] == '+') x++; int d = abs(x - ((int)s.sz - x)); if(d >= 2 * k) { cout << abs(d - 2 * k) << endl; } else { int now = d; if(d & 1) d = 1, k -= (now - d) / 2; else d = 0, k -= (now - d) / 2; cout << abs(d - (k & 1) * 2) << endl; } }
G 迷宫2
H 寒冬信使2
I A+B问题
void solve() { int k; cin >> k; vector<int> a, b; string sa, sb; cin >> sa >> sb; if(sa.sz < sb.sz) swap(sa, sb); for (int i = sa.sz - 1; i >= 0; i--) a.pb(sa[i] - '0'); for (int i = sb.sz - 1; i >= 0; i--) b.pb(sb[i] - '0'); rep(i, 0, sb.sz) a[i] += b[i]; for (int i = 0; i < sa.sz - 1; i++) { a[i + 1] += a[i] / k; a[i] %= k; } if(a[sa.sz - 1] >= k) a.pb(a[sa.sz - 1] / k); a[sa.sz - 1] %= k; reverse(all(a)); rep(i, 0, a.sz) cout << a[i]; }
