AtCoder Beginner Contest 403

再来一场atCoder，这一场简直血虐，让你回忆起了审题的重要性

A - Odd Position Sum 

思路：题意很简单，求一个数组奇数位上数字和。很简单的问题，但你如果不仔细审题，就会浪费大量的时间

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int n;cin >> n;int oddSum = 0;for (int i = 0; i < n; i++) {int a;cin >> a;if (i % 2 == 0) {oddSum += a;}}cout << oddSum << '\n';return 0;
}

B - Four Hidden 

思路：第二题，简单的字符串子串题，暴力匹配一下即可

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;bool streamContains(string t, string u, int startT) {bool yes = true;int uLen = int(u.size());for (int i = 0; yes && i < uLen; i++) {if (u[i] != t[i + startT] && t[i + startT] != '?') {yes = false;;}}return yes;
}int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);string t, u;cin >> t >> u;int tLen = int(t.size());int uLen = int(u.size());for (int i = 0; i + uLen <= tLen; i++) {if (streamContains(t, u, i)) {cout << "Yes" << '\n';return 0;}}cout << "No" << '\n';return 0;
}

C - 403 Forbidden 

思路：又是熟悉的模拟，与上次的模拟登录类似，这次换成了模拟授权。没什么难度，但却因为没读清题目，要求输出Yes/No，结果输出了YES/NO，导致了三次无意义的WA，实属可惜

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 5;set<int> g[N];
bool all[N];int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int n, m, q;cin >> n >> m >> q;while (q--) {int o, x, y;cin >> o;if (o == 1) {cin >> x >> y;g[x].insert(y);} else if (o == 2) {cin >> x;all[x] = true;} else {cin >> x >> y;if (all[x] || g[x].contains(y)) {cout << "Yes" << endl;} else {cout << "No" << endl;}}}return 0;
}

D - Forbidden Difference 

思路：给定一个数组a（2e5的数据量，最大值为1e6）和一个特定的数d，要求删除最少得数量是的数组内所有数的距离都不为d

题意倒是很简单，首先想到的将距离为d的数通过并查集连接，再通过遍历每一个连通集，进行间隔删除，最后找出最小的删除方案。

第一次提交出现了部分re，显然，并查集记得初始化，这个也算是一个坑点了

注意特判一下d为0的场景

发现问题了间隔删除并非是最优策略，看来还是要用dp来做。

最后整理一下，其实并查集的主要就是为了优化连通集，但是这题的数组最大值只有1e6，因此可以直接用计数数组而放弃并查集优化，这样会使代码简洁一些。

整体的dp方案，当然是根据数组内的值是否去除来进行转移。由于要去除最小值，我们完全可以转换为保留的最大值进行转移，最终用总和进行相减即可。

不难发现，连通数组的数量最大即为特定间隔数 ，于是遍历每一个连通集，将每个连通数组中的dp最大值进行求和，即为最终要保留的最大值。

那么dp转移方程就出来了，假设当前要判断的数为，当前数总计出现了  次

那么  表示当前数要保留，那面，前一个数一定不能保留，于是 

而  表示当前数要去除，则前一个数保留与否均可，取个最大值即可，即 

接下来看一下代码，我将原始求解写在了 first_pass_function() 函数中，将整理后的简易方法写在了 main() 函数中

/*
Author Owen_Q
*/
#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 5;
const int M = 1e6 + 1;int a[N];
int pre[M];
bool in[M];
int cnt[M];
set<int> col[M];
set<int> colSet;
// bool re[N];
int dp[M][2];int findX(int x) {if (pre[x] == x) {return x;}return pre[x] = findX(pre[x]);
}void unionXY(int x, int y) {int preX = findX(x);int preY = findX(y);if (preX > preY) {pre[x] = preY;} else if (preX < preY) {pre[y] = preX;}
}int first_pass_function() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int n, d;cin >> n >> d;int rere = 0;// 初始化for (int i = 0; i < M; i++) {pre[i] = i;in[i] = false;cnt[i] = 0;col[i].clear();}colSet.clear();for (int i = 1; i <= n; i++) {cin >> a[i];cnt[a[i]]++;in[a[i]] = true;if (cnt[a[i]] == 1) {if (a[i] - d >= 0 && in[a[i] - d]) {unionXY(a[i], a[i] - d);}if (a[i] + d < M && in[a[i] + d]) {unionXY(a[i], a[i] + d);}}}for (int i = 1; i <= n; i++) {int preA = findX(a[i]);col[preA].insert(a[i]);colSet.insert(preA);}for (auto colSetIt = colSet.begin(); colSetIt != colSet.end(); ++colSetIt) {int curPre = *colSetIt;int colSize = col[curPre].size();int colCnt = 0;// bool colStart = true;int colStartCnt = 0;memset(dp, 0, sizeof(dp));int nowPos = 1;for (auto colPreIt = col[curPre].begin(); colPreIt != col[curPre].end(); ++colPreIt) {int now = *colPreIt;// cout << now << "**" << endl;// 以下为间隔删除，该方法不正确，更换为dp// if (colStart) {//     colStart = false;// } else {//     colStart = true;// }// if (colStart) {//     colStartCnt += cnt[now];// }colCnt += cnt[now];dp[nowPos][1] = dp[nowPos-1][0] + cnt[now];dp[nowPos][0] = max(dp[nowPos-1][0], dp[nowPos-1][1]);nowPos ++;}colStartCnt = max(dp[colSize][0], dp[colSize][1]);// cout << colCnt << "*"  << colStartCnt <<  "\n";// 特判逻辑if (d == 0) {rere += colCnt - 1;} else if (colStartCnt > colCnt / 2) {rere += colCnt - colStartCnt;// colStart = true;} else {rere += colStartCnt;// colStart = false;}// cout << rere << "***" << endl;// colStartPre = -1;// for (auto colPreIt = col[curPre].begin(); colPreIt != col[curPre].end(); ++colPreIt) {//     int now = *colPreIt;//     if (now != colStartPre) {//         colStartPre = now;//         if (colStart) {//             colStart = false;//         } else {//             colStart = true;//         }//     }//     if (colStart) {//         re[now] = true;//     }// }}// int reDelCnt = 0;// for (int i = 1; i <= n; i++) {//     if (!re[a[i]]) {//        reDelCnt++;//     }// }cout << rere << endl;return 0;
}int main() {ios_base::sync_with_stdio(false), cin.tie(nullptr);int n, d;cin >> n >> d;// 初始化memset(cnt, 0, sizeof(cnt));// memset(dp, 0, sizeof(dp));int difCnt = 0;int maxA = 0;for (int i = 1; i <= n; i++) {int A;cin >> A;cnt[A]++;if (cnt[A] == 1) {difCnt++;maxA = max(maxA, A);}}if (d == 0) {cout << n - difCnt << endl;} else {int maxRe = 0;for (int i = 0; i < d; i++) {// 第一轮dp初始化dp[i][1] = cnt[i];dp[i][0] = 0;int curRe = cnt[i];for (int j = i+d; j <= maxA; j+=d) {// 后续dp转移dp[j][1] = dp[j-d][0] + cnt[j];dp[j][0] = curRe;curRe = max(dp[j][0], dp[j][1]);}maxRe += curRe;}cout << n - maxRe << endl;}
}