A. Catch the Coin

y 小于 -1 就不可能拿到

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int a, b;cin >> a >> b;if (b < -1) cout << "NO\n";else cout << "YES\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

B. Substring and Subsequence（贪心）

最坏情况是 a + b，然后，考虑 a 是一定要整段出现在答案中，所以只需要枚举从 b 的第几个字符开始匹配即可，如果有 tmp 个字符匹配，答案就是 a.size() + b.size() - tmp

这题一开始的思路就是对的，为什么wa了很多发呢，因为没注意到 b 中所有字母都要按顺序出现在 a 里，所以，一旦 b 中有一个字符不能和 a 匹配，之后的所有字符都不能和 a 匹配了，直接break，就不能再往下计算了

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{string a, b;cin >> a >> b;int ans = a.size() + b.size();for (int k = 0; k < b.size(); k ++ ){int tmp = 0;int lst = -1;for (int i = k; i < b.size(); i ++ ){bool flag = false;for (int j = lst + 1; j < a.size(); j ++ ){if (b[i] == a[j]){flag = true;lst = j;tmp ++ ;break;}}if (!flag) break;}ans = min(ans, (i64)(a.size() + b.size() - tmp));}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

C. Two Movies（贪心）

赛时wa是因为写二分，然后check函数写错了，因为我把同加的数量和两个分数大于mid的部分加在一起作为多余的部分，其实并不是这样，因为第一个分数多出来的部分并不能挪到第二个分数缺少的部分

今天看蒋老师的代码，直接贪心就可以，前面都是一样的，能加就加，遇到同为 1 或者同为 -1 的情况：

• 同为1，将同加的数量+1
• 同为-1，将同加的数量+1后，两个分数都-1（思考一下可以发现确实是等价的）

之后最大值就是 第一个分数+同加数量 第二个分数+同加数量 （第一个分数+第二个分数+同加数量）/2 向下取整 三者的最小值

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin >> n;vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= n; i ++ ) cin >> b[i];int cnt1 = 0, cnt2 = 0; // 当前得分int same_plus = 0; // 同加for (int i = 1; i <= n; i ++ ){if (a[i] == b[i]){if (a[i] != 0) same_plus ++ ;if (a[i] == -1){cnt1 -- ;cnt2 -- ;}}else{if (a[i] == 1) cnt1 ++ ;else if (b[i] == 1) cnt2 ++ ;}}int ans = min(cnt1 + same_plus, cnt2 + same_plus);if (cnt1 + cnt2 + same_plus >= 0) ans = min(ans, (cnt1 + cnt2 + same_plus) / 2);else ans = min(ans, (cnt1 + cnt2 + same_plus - 1) / 2);cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

D. Smithing Skill（贪心+双指针）

首先需要考虑到，每次锻造会让我们的原料减少，那我们选择锻造方式的时候，一定会在原料数量满足条件的情况下，选择原料减少数量最小的

所以开一个vector，存pair（a[i] - b[i]，a[i]），先排序，然后遍历其中的每一个元素，删掉多余的

什么叫做多余的呢，排完序后，当前锻造方式一定比前面的锻造方式减少的原料更多，如果此时它还需要更高的门槛（也就是a[i]还比前面高的话），那我直接选前面的就好了，当前的就是多余的

所以最后我们得到的数组一定是 a[i] - b[i] 单增，a[i] 单减的

之后我们计算有 x （小于1e6）个原料时，能得到的最大经验值，存在 dp[i] 里

怎么计算呢，使用双指针，i 从前往后遍历表示当前有 i 个原料，j 从后往前遍历表示当前选择第 j 个锻造方式，每次 j 尽可能往前选（因为越前面减少的原料越少，但也不能一直往前，因为只有原料数超过 a[i] 的时候才能使用这种锻造方式），更新方程 dp[i] = dp[i - p[j].first] + 1]

到这里我们得到了原料小于1e6能够得到的经验值，那大于 1e6 的部分怎么办呢，因为每种锻造方法所需要的原料数量都小于 1e6 ，所以一开始一定是先用第一个锻造方法，直到原料数量小于1e6的时候，我们就可以直接使用刚刚求的 dp[i] 计算了

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;vector<int> a(n), b(n);for (int i = 0; i < n; i ++ ) cin >> a[i];for (int j = 0; j < n; j ++ ) cin >> b[j];vector<PII> p(n);for (int i = 0; i < n; i ++ ) p[i] = {a[i] - b[i], a[i]};sort(p.begin(), p.end());int maxx = 1e9;vector<PII> tmp;for (auto t : p){if (t.second < maxx) // 减少一样多的原料 必须要初始消耗原料更少才保留{tmp.push_back(t);maxx = t.second;}}swap(p, tmp);vector<int> dp(N);for (int i = 0, j = p.size(); i <= 1e6; i ++ ){while (j >= 1 && p[j - 1].second <= i) j -- ;if (j != p.size()) dp[i] = dp[i - p[j].first] + 1;}int ans = 0;while (m -- ){int x; cin >> x;if (x > 1e6){int cnt = (x - 1e6) / p[0].first;x -= cnt * p[0].first;if (x > p[0].second){x -= p[0].first;cnt ++ ;}ans += cnt;} ans += dp[x];}cout << ans * 2 << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}

E. Distance to Different（dp）

解法参考 jiangly 和 cup-pyy

求 b 的数量，可以转化成：将 a 分成几段，每段颜色相同，求这样的分法数量

如果直接这么求也不对，因为我们发现两个相同的颜色组成的一段，处在中间位置时，和两个不同的颜色组成的两段贡献一样，举个例子：1221和1231得到的 b 数组都是 1111，但是这样的相同两个颜色组成的一段处在两段时，贡献就和不同颜色组成的两段不一样，举个例子：112和312得到的 b 数组分别是 211 和 111，所以每次需要减去不处在两端的 由两个相同颜色组成的一段

考虑dp，设计 dp[i][j] 为前 i 个点被分成不少于 j 段的方案数

$dp[i][j]={\sum }_0^{i-1}dp[i][j-1]$

直接求这个式子复杂度 $O(n^2)$，所以定义 sum[i][j] 表示 dp[0][j] ~ dp[i][j] 之和，在每轮循环进行更新

当 $i>2$ 且 $i\ne n$ 时，减去 $dp[i-2][j]$

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, k;cin >> n >> k;// dp[i][j] 前i个点分成不少于j段的数量// sum[i][j] dp[0][j]~dp[i][j]之和vector<vector<int>> dp(n + 1, vector<int>(k + 1)), sum(n + 1, vector<int>(k + 1));dp[0][0] = 1;sum[0][0] = 1;for (int i = 1; i <= n; i ++ ){for (int j = 0; j <= k; j ++ ){dp[i][min(j + 1, k)] = (dp[i][min(j + 1, k)] + sum[i - 1][j]) % mod;if (i > 2 && i != n) dp[i][min(j + 1, k)] = (dp[i][min(j + 1, k)] - dp[i - 2][j] + mod) % mod;}for (int j = 0; j <= k; j ++ ){sum[i][j] = (sum[i - 1][j] + dp[i][j]) % mod;}}cout << dp[n][k] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}