目录
- cf1738C Even Number Addicts（博弈/记忆化搜索）
- cf1739E Reset K Edges (树，二分+贪心)
- cf1730D Prefixes and Suffixes (字符串，思维)
- cf1734D Slime Escape (双指针？)
- abc270 D - Stones (博弈，DP)
- abc271 E - Subsequence Path （dp,最短路）
cf1738C Even Number Addicts（博弈/记忆化搜索）
题意
有\(n\)个整数，Alice和Bob依次取数，如果Alice取的数和为偶数则Alice胜，否则Bob胜。
\(1\le n\le100,1\le T\le100\)
题解
首先注意一个大坑是整数不能用模二余一来判断是否为奇数，因为负数会炸...
大讨论当然是可以做的。这里写一下记忆化搜索的思路
设dp[odd][even][step0/1][sum0/1]表示当前有odd个奇数，even个偶数，当前玩家是Alice/Bob，Alice的和为偶数/奇数时，当前玩家的输赢情况。
然后按照“只要有一种走法能让对方必败，则当前玩家必胜”来转移即可。
总共不会超过40000个状态,记忆化搜索即可。
//
// Created by vv123 on 2022/10/3.
#include <bits/stdc++.h>
#define int long long
//#pragma GCC optimize(3)
using namespace std;
const int N = 110;
int n, dp[N][N][2][2];
int dfs(int odd, int even, int step, int sum) {
//printf("%d %d %d %d\n", odd, even, step, sum);
if (dp[odd][even][step][sum] != -1) return dp[odd][even][step][sum];
if (odd == 0 && even == 0) {
if (step == 0) return sum == 0;
else return sum != 0;
}
int res = 0;
if (step == 0) { //Alice's turn
if (odd) res |= !dfs(odd - 1, even, !step, !sum);
if (even) res |= !dfs(odd, even - 1, !step, sum);
} else { //Bob's turn
if (odd) res |= !dfs(odd - 1, even, !step, sum);
if (even) res |= !dfs(odd, even - 1, !step, sum);
}
return dp[odd][even][step][sum] = res;
}
void solve() {
memset(dp, -1, sizeof dp);
cin >> n;
int odd = 0, even = 0;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
if (x % 2 == 0) even++;
else odd++;
}
puts(dfs(odd, even, 0, 0) ? "Alice" : "Bob");
}
signed main() {
//ios::sync_with_stdio(false); cin.tie(nullptr);
int T = 1; cin >> T;
while (T--) {
solve();
}
return 0;
}
cf1739E Reset K Edges (树，二分+贪心)
题意
你有一颗根为1的树，可以进行k次操作：隔断一条边，把下方的子树连到根节点上。
问能够实现的叶节点最小深度。
\(n\le 2\cdot10^5\)
题解
二分深度mxd，在dfs回溯的过程中记录某个点离最深叶节点的距离d，显然在d=mxd的时候耗费一次操作将子树砍下来是最优的，然后d从0开始算就可以了。
//
// Created by vv123 on 2022/9/30.
//
#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize(3)
using namespace std;
const int N = 2e6 + 10;
int n, m, k, d[N], cnt[N];
vector<int> g[N];
int mxd, cost;
int dfs(int u, int pre) {
//cout << u << "\n";
int dis = 1;//到叶子节点的距离
for (auto v : g[u]) {
dis = max(dis, dfs(v, u) + 1);
}
//cout << u << " " << dis << endl;
if (u != 1 && pre != 1 && dis + 1 > mxd) {
cost++;
return 0;
}
return dis;
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
g[i].clear();
}
m = 0; d[1] = 0;
for (int i = 2; i <= n; i++) {
int x; cin >> x;
d[i] = d[x] + 1;
m = max(m, d[i]);
g[x].push_back(i);
}
int l = 1, r = m;
while (l < r) {
int mid = l + r >> 1;
mxd = mid;
cost = 0;
dfs(1, 0);
//printf("mxd:%lld cost:%lld\n", mxd, cost);
if (cost <= k) r = mid; else l = mid + 1;
}
cout << l << "\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int T; cin >> T;
while (T--) {
solve();
}
return 0;
}
cf1730D Prefixes and Suffixes (字符串，思维)
题意
给定两个字符串s1、s2，每次可以选择长度相同的s1前缀和s2后缀进行交换，问能否使得最后s1=s2.
\(1\le n\le 2\cdot10^5\)
题解
注意到一个结论：s1[i]与s1[n+1-i]不可能移到相同位置，其他都是可以的。
我们只需要考虑以上有限制的字母对，能否恰好分配即可。
//
// Created by vv123 on 2022/9/26.
//
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
//#define int long long
//typedef long long ll;
using namespace std;
//#include<bits/extc++.h>
//using namespace __gnu_pbds;
const int mod = 998244353;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
char s[N], t[N];
void solve() {
int n, cnt[26][26] = {0};
cin >> n >> s + 1 >> t + 1;
for (int i = 1; i <= n; i++) {
int a = s[i] - 'a', b = t[n + 1 - i] - 'a';
if (a > b) swap(a, b);
cnt[a][b]++;
}
bool ok = true;
for (int i = 0; i < 26; i++)
for (int j = i + 1; j < 26; j++)
if (cnt[i][j] & 1) ok = false;
int eqcnt = 0;
for (int i = 0; i < 26; i++) eqcnt += cnt[i][i] % 2;
if (!ok || eqcnt > n % 2) cout << "NO\n";
else cout << "YES\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1; cin >> T;
while (T--) solve();
return 0;
}
cf1734D Slime Escape (双指针？)
题意
一个长度为n的整数序列a，一开始你在位置s并拥有生命值a[s]，你可以向左或向右走得到那个位置的生命值，生命值为负就会死亡，问最后能否逃出边界。
题解
设lnow，lmax分别为向左走能达到的最远距离和途中的最大生命值，用它更新rnow和rmax，反复进行这个过程直到无法更新或者成功逃脱即可。
//
// Created by vv123 on 2022/9/23.
//
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10, inf = 0x3f3f3f3f;
int n, s, a[N];
void solve() {
cin >> n >> s;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
if (s == 1 || s == n) {
puts("YES");
return;
}
int l = s, r = s;
int lnow = 0, lmax = 0, rnow = 0, rmax = 0;
bool ok = true;
while (l > 1 && r < n && ok) {
ok = false;
while (l > 1 && a[s] + rmax + lnow + a[l - 1] >= 0) {
ok = true;
lnow += a[--l];
lmax = max(lmax, lnow);
}
while (r < n && a[s] + lmax + rnow + a[r + 1] >= 0) {
ok = true;
rnow += a[++r];
rmax = max(rmax, rnow);
}
}
puts(l == 1 || r == n ? "YES" : "NO");
}
signed main() {
ios::sync_with_stdio(false);
int T = 1; cin >> T;
while (T--) {
solve();
}
return 0;
}
abc270 D - Stones (博弈，DP)
题意
一开始有N个石子，两个人依次取石子，每次可以从A1...Ak选择一个不大于当前石子数的数，取走那么多石子。如果两个人都采取最佳策略让自己取尽可能多的石子，问先手最后取走多少石子。
\(N\le10^4,K\le100,A_1=1\)
题解
(如果发现可以把所有情况都dp出来就不要瞎贪心辣)
设\(dp_i\)表示石子数为n时先手取到的最多石子数
则有\(dp_i=\max_\limits{A_j\le i}(i-dp_{i-Aj})\)
这个dp包含了先后手转换的含义
//
// Created by vv123 on 2022/9/6.
//
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
//typedef long long ll;
using namespace std;
//#include<bits/extc++.h>
//using namespace __gnu_pbds;
const int mod = 998244353;
const int N = 2e6 + 10;
const int inf = 0x3f3f3f3f;
int n, k, a[N], dp[N];
void solve() {
cin >> n >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i];
}
//sort(a + 1, a + 1 + k);
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (a[j] > i) break;
dp[i] = max(dp[i], i - dp[i - a[j]]);
}
}
cout << dp[n] << "\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1; //cin >> T;
while (T--) solve();
return 0;
}
abc271 E - Subsequence Path （dp,最短路）
题意
给出张有边权的无向图和一个边的编号序列E。求1号点到N号点，满足路径编号是E的子序列的最短路径。
\(N,M,K\le2\times10^5\)
题解
设\(dp[i][u]\)表示考虑前\(i\)条边，1~u的最短路
然后加入每条边的时候更新以下dist数组就好了，不需要第一维的。
//
// Created by vv123 on 2022/10/3.
//
#include <bits/stdc++.h>
#define int long long
//#pragma GCC optimize(3)
using namespace std;
const int N = 2e5 + 10, inf = 1e18;
void solve() {
int n, m, k, x;
cin >> n >> m >> k;
vector<int> a(m + 1), b(m + 1), c(m + 1), d(n + 1, inf);
d[1] = 0;
for (int i = 1; i <= m; i++) cin >> a[i] >> b[i] >> c[i];
while (k--) {
cin >> x;
d[b[x]] = min(d[b[x]], d[a[x]] + c[x]);
}
if (d[n] == inf) cout << "-1\n";
else cout << d[n] << "\n";
}
signed main() {
//ios::sync_with_stdio(false); cin.tie(nullptr);
int T = 1; //cin >> T;
while (T--) {
solve();
}
return 0;
}