2024.7.20 暑期训练记录（6）

2024-07-21 20:26:04
开发
15

CF

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

首先简化问题，发现一个矩阵如果要满足条件，那它其中的每一个 $2\times 2$ 的小矩阵都要满足条件，于是很容易发现 $4\times4$ 的矩阵是一定不满足条件的（因为是由四个 $2\times2$ 的矩阵拼起来的，所以里面的 $1$ 一定是偶数个），既然如此，更大的矩阵就更不行了，因为里面肯定会包含 $4\times4$ 的矩阵，所以就把问题简化到 $n\le3$ 的情况了
$n = 1$ 时，没有边长为偶数的子矩阵，所以一定是好矩阵
$n = 2$ 时，枚举一下第一列有 $0/1/2$ 个 $1$ 的情况，取最小操作数
$n = 3$ 时，状压dp，用二进制表示每一列的情况， $d p [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，可以积累一下
$d p [i]$ 表示从 $[i,\ n]$ 的最长下降子序列长度， $ma xx [i]$ 表示从字母 $i +^{'} a^{'}$ 到 $^{'} z^{'}$ 开头的最长下降子序列长度

#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();
	}
}

原文地址:https://blog.csdn.net/dhxbshbdjzxy/article/details/140568951 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1815000284305428480.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部