GYM 105310 C
题目描述
有 \(N\) 个煎饼店围成一圈，第 \(i\) 个店中有 \(p_i\) 个煎饼。接下来两只红熊猫会进行以下操作：
- 两只熊猫分别选择一个不同的店 \(a,b\)。第一只先选。
- 接着第一个熊猫选择一个不为 \(b\) 的店，从 \(a\) 开始沿着一条不经过 \(b\) 的路线走到该店，并把路径上的店中的煎饼全部吃掉。
- 然后第二个熊猫选择一个没被第一个熊猫经过的店，从 \(b\) 开始沿着一条不经过第一只熊猫经过的店的路线走到该店，并把路径上的店中的煎饼全部吃掉。
两只熊猫都想最大化自己吃的煎饼数量，求第一只熊猫会吃多少个煎饼。
思路
我们考虑枚举 \(a\)，并看第二只熊猫会怎么做。
假设此时第二只熊猫已经选好 \(b\) 了，那么此时在第一只熊猫面前有两条路，第一只熊猫肯定会把这条路上能吃的吃完，并且选择煎饼更多的那条。此时第二只就只能吃更少的那条。
所以第二只熊猫得到的煎饼 \(f(b)\) 是一个单峰函数，因为这是两个单调函数的 \(\min\)。我们就可以使用二分，在峰的位置是最后一个 \(f(b)-f(b-1)\ge 0\) 的位置。通过二分出的 \(b\) 就可以求出第一只熊猫的煎饼数。
空间复杂度 \(O(N)\)，时间复杂度 \(O(N\log N)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int MAXN = 300001;int t, n, a[MAXN];
ll sum[MAXN], ans;ll Calc(int a, int b) {return min(sum[b] - sum[a], sum[a + n - 1] - sum[b - 1]);
}int Binary_Search(int x) {int l = x + 1, r = x + n - 1;for(; l < r; ) {int mid = (l + r + 1) >> 1;(Calc(x, mid) - Calc(x, mid - 1) >= 0 ? l = mid : r = mid - 1);}return l;
}void Solve() {cin >> n;for(int i = 1; i <= n; ++i) {cin >> a[i];a[n + i] = a[2 * n + i] = a[i];sum[i] = sum[i - 1] + a[i];}for(int i = n + 1; i <= 3 * n; ++i) {sum[i] = sum[i - 1] + a[i];}ans = 0;for(int i = 1; i <= n; ++i) {int x = Binary_Search(i);x -= (x > 2 * n ? 2 : (x > n ? 1 : 0)) * n;if(x < i) {ans = max({ans, sum[i] - sum[x], sum[x + n - 1] - sum[i - 1]});}else {ans = max({ans, sum[x - 1] - sum[i - 1], sum[i + n] - sum[x]});}}cout << ans << "\n";
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);for(cin >> t; t--; Solve()) {}return 0;
}
GYM 105310 D
题目描述
给定两个字符串 \(s,t\)，我们定义字母 \(x\) 的值为其在字母表中的下表（a 为 \(0\)）。我们还定义：
- 一个字母 \(x\) 的反转为值为 \(25-x\) 的字母。
- 一个字母 \(x\) 的相对为值为 \((x+13)\bmod 26\) 的字母。
每次你可以将一个区间变成他的反转或相对，求将 \(s\) 变为 \(t\) 的最少次数。如果不行输出 \(-1\)。
思路
推一推便可以发现，先做反转再做相对和先做相对再做反转是一样的，而且这两种操作只有可能做 \(0/1\) 次。
所以令 \(dp_{0/1,0/1,i}\) 表示考虑将前 \(i\) 个字符变相同，最后一个位置是/否做反转，是/否做相对的最少次数。
转移时，如果上一个位置没做反转，但当前做了，那么要多进行一次操作，如果上一个位置没相对，但当前相对了，那么也要多进行一次操作。
时空复杂度均为 \(O(N)\)。
代码
#include<bits/stdc++.h>
using namespace std;const int MAXN = 1000001, INF = 2 * MAXN;int n, dp[2][2][MAXN];
string s, t;int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> s >> t;s = ' ' + s, t = ' ' + t;for(int i = 0; i <= n; ++i) {for(bool op : {0, 1}) {for(bool op2 : {0, 1}) {dp[op][op2][i] = INF;}}}dp[0][0][0] = 0;for(int i = 1; i <= n; ++i) {for(bool op : {0, 1}) {for(bool op2 : {0, 1}) {int x = ((op ? 25 - (s[i] - 'a') : (s[i] - 'a')) + op2 * 13) % 26;if(x == t[i] - 'a') {for(bool lop : {0, 1}) {for(bool lop2 : {0, 1}) {dp[op][op2][i] = min(dp[op][op2][i], dp[lop][lop2][i - 1] + (op && !lop) + (op2 && !lop2));}}}}}}int ans = min({dp[0][0][n], dp[0][1][n], dp[1][0][n], dp[1][1][n]});cout << (ans == INF ? -1 : ans);return 0;
}
