2024.7.20 暑期训练记录（6）

CF

1391D - 505（思维+状压dp）

• 首先简化问题，发现一个矩阵如果要满足条件，那它其中的每一个 $2\times 2$ 的小矩阵都要满足条件，于是很容易发现 $4\times 4$ 的矩阵是一定不满足条件的（因为是由四个 $2\times 2$ 的矩阵拼起来的，所以里面的 $1$ 一定是偶数个），既然如此，更大的矩阵就更不行了，因为里面肯定会包含 $4\times 4$ 的矩阵，所以就把问题简化到 $n\le 3$ 的情况了
• $n=1$ 时，没有边长为偶数的子矩阵，所以一定是好矩阵
• $n=2$ 时，枚举一下第一列有 $0/1/2$ 个 $1$ 的情况，取最小操作数
• $n=3$ 时，状压dp，用二进制表示每一列的情况，$dp[i][j]$ 表示第 $i$ 列变成状态 $j$ 的最小操作数，转移方程 $dp[i][j]=\min (dp[i][j],dp[i-1][k]+change(i,j))$ （如果 $k$ 和 $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 = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin >> n >> m;vector<vector<char>> g(n + 1, vector<char>(m + 1));for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )cin >> g[i][j];if (n >= 4) cout << -1 << '\n';else if (n == 1) cout << 0 << '\n';else if (n == 2){vector<int> cnt(m + 1);for (int i = 1; i <= m; i ++ ){int tmp = 0;for (int j = 1; j <= n; j ++ ){if (g[j][i] == '1') tmp ++ ;}cnt[i] = tmp;}vector<int> ans(3);for (int k = 0; k < 3; k ++ ){ans[k] += abs(cnt[1] - k);int lst = k;for (int i = 2; i <= m; i ++ ){if (lst & 1){if (cnt[i] & 1) ans[k] ++ ;lst = 0;}else{if (cnt[i] % 2 == 0) ans[k] ++ ;lst = 1;}}}cout << min({ans[0], ans[1], ans[2]}) << '\n';}else if (n == 3){// 将每一列转化成二进制vector<int> mp(m + 1);for (int i = 1; i <= m; i ++ ){int tmp = 0;for (int j = 1; j <= n; j ++ ){if (g[j][i] == '1') tmp += (1ll << (j - 1));}mp[i] = tmp;}// 转化步数auto change = [&](int a, int b){int state = (a ^ b);int ans = 0;for (int i = 0; i < 3; i ++ ){if ((state >> i) & 1) ans ++ ;}return ans;};// 判断相邻状态合法性auto check = [&](int a, int b){int a1 = ((a >> 0) & 1), a2 = ((a >> 1) & 1), a3 = ((a >> 2) & 1);int b1 = ((b >> 0) & 1), b2 = ((b >> 1) & 1), b3 = ((b >> 2) & 1);if ((a1 + a2 + b1 + b2) % 2 == 0) return false;if ((a2 + a3 + b2 + b3) % 2 == 0) return false;return true; };// 初始化vector<vector<int>> dp(m + 1, vector<int>(8, INF));for (int i = 0; i < 8; i ++ ) dp[1][i] = change(mp[1], i);for (int i = 2; i <= m; i ++ ){for (int j = 0; j < 8; j ++ ) // i-1列的状态{for (int k = 0; k < 8; k ++ ) // i列的状态{if (!check(j, k)) continue; // jk作为相邻状态不合法dp[i][k] = min(dp[i][k], dp[i - 1][j] + change(mp[i], k));}}}int ans = INF;for (int i = 0; i < 8; i ++ ) ans = min(ans, dp[m][i]);if (ans == INF) cout << -1 << '\n';else cout << ans << '\n';}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}

1296E2 - String Coloring (hard version)（思维+dp）

• 首先想一想什么情况下需要交换呢，即一个字母在另一个字母前面，但是前面的字母比后面的字母大的时候，也就是说，涂同一种颜色的位置必须是单调不减的，我们把涂同一种颜色的位置放在一个集合里，可以证明，所有集合的最后一个位置上的字符一定是单调递减的（感性理解一下，如果有递增的，那直接放到前一个集合就好了，没必要放在下一个集合）所以问题就转化成了求最长下降子序列
• 应该是一个经典的trick，可以积累一下
• $dp[i]$ 表示从 $[i,n]$ 的最长下降子序列长度，$maxx[i]$ 表示从字母 $i{+}^{\prime }{a}^{\prime }$ 到 ${}^{\prime }{z}^{\prime }$ 开头的最长下降子序列长度

#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 = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin >> n;string s; cin >> s;s = " " + s;vector<int> dp(n + 1);vector<int> maxx(26);int ans = 0;for (int i = n; i >= 1; i -- ){int c = s[i] - 'a';dp[i] = maxx[c] + 1;for (int j = c + 1; j < 26; j ++ ) maxx[j] = max(maxx[j], dp[i]);ans = max(ans, dp[i]);}cout << ans << '\n';for (int i = 1; i <= n; i ++ ) cout << dp[i] << ' ';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t--){solve();}
}

1616D - Keep the Average High（思维）

• 好聪明的做法，先把所有数都减去 $x$，这样需要满足的条件就是 $a_l+a_r>=0$ 了
• 然后只需要看连续的长度为 $2$ 的串和长度为 $3$ 的串是否满足条件就好了，为什么只需要看这两种呢，因为其他长度的串都可以用这两种拼起来啊，这种想法在今天的第一道 dp 中已经出现过了

#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 = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];int x; cin >> x;for (int i = 1; i <= n; i ++ ) a[i] -= x;int ans = n;for (int i = 2; i <= n; i ++ ){if (a[i] + a[i - 1] + a[i - 2] < 0 || a[i] + a[i - 1] < 0){ans -- ;a[i] = INF;}}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

1978D - Elections（思维+前缀后缀）

• 贪心一下，想赢的话先删前面的人，前面的人删了还赢不了就删掉后面最大的

#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 = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, c;cin >> n >> c;vector<int> a(n + 1);vector<int> pre(n + 1), maxx_pre(n + 1), maxx_suff(n + 2);for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= n; i ++ ) pre[i] = pre[i - 1] + a[i];for (int i = 1; i <= n; i ++ ) maxx_pre[i] = max(maxx_pre[i - 1], a[i]);for (int i = n; i >= 1; i -- ) maxx_suff[i] = max(maxx_suff[i + 1], a[i]);for (int i = 1; i <= n; i ++ ){if (i == 1){if (a[i] + c >= maxx_suff[i + 1]) cout << 0 << ' ';else cout << 1 << ' ';}else if (i == n){if (a[i] > max(maxx_pre[i - 1], a[1] + c)) cout << 0 << ' ';else cout << n - 1 << ' ';}else{if (a[i] > max(a[1] + c, maxx_pre[i - 1])){if (a[i] >= maxx_suff[i + 1]) cout << 0 << ' ';else{if (a[i] + pre[i - 1] + c >= maxx_suff[i + 1]) cout << i - 1 << ' ';else cout << i << ' ';}}else{if (a[i] + pre[i - 1] + c >= maxx_suff[i + 1]) cout << i - 1 << ' ';else cout << i << ' ';}}}cout << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}

1979D - Fixing a Binary String（思维）

#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 = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;void solve()
{int n, k;cin >> n >> k;string s;cin >> s;vector<int> a(1);int tmp = 1;for (int i = 1; i < n; i ++ ){if (s[i] != s[i - 1]){a.push_back(tmp);tmp = 1;}else tmp ++ ;}if (tmp != 0) a.push_back(tmp);int pos = -1;int m = a.size() - 1;vector<int> pre(m + 1);for (int i = 1; i <= m; i ++ ) pre[i] = pre[i - 1] + a[i];for (int i = 1; i <= m - 1; i ++ ){if (a[i] != k){if (pos == -1) pos = i;else{cout << -1 << '\n';return;}}}if (pos == -1){if (a[m] == k) cout << n << '\n';else cout << -1 << '\n';}else{if (a[m] == k){if ((m % 2 == 0 && pos % 2 == 0) || (m % 2 != 0 && pos % 2 != 0)){cout << -1 << '\n';}else{if (a[pos] == 2 * k) cout << pre[pos - 1] + k << '\n';else cout << -1 << '\n';}}else{if (a[m] > k) cout << -1 << '\n';else{int tmp = k - a[m];if ((m % 2 == 0 && pos % 2 == 0) || (m % 2 != 0 && pos % 2 != 0)){if (a[pos] >= tmp && ((a[pos] - tmp) == k || (a[pos] - tmp) == 0)) cout << pre[pos - 1] + tmp << '\n';else cout << -1 << '\n';}else cout << -1 << '\n';}}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--){solve();}
}