2024.5.20-5.26 训练记录（30）

发布于：2024-05-24 ⋅ 阅读:(119) ⋅ 点赞:(0)
微信交流群：https://732903.hlcode.cn/?id=NK1fWUR

文章目录

CF 1325D Ehab the Xorcist（*1700 思维）

题目链接

题意是给你两个数 u , v u, v u,v ，构造一个最短的数组，让异或和为 u，总和为 v

首先分类讨论：

  • 如果 u > v ，那一定不存在，因为 u 要求一定要有一个数高位为 1，但如果高位为 1 就不满足 v 的要求，所以直接输出 -1
  • 如果 u == v == 0，直接输出 0
  • 如果 u == v != 0，一个数 v 就可以满足条件
  • 然后就是一般情况了，我们注意到异或的性质，两个相等的数异或等于 0，所以我们可以用三个数 a、a、u 让满足异或和为 u，同时还要满足总和为 v，所以 a + a + u == v，也就是 a = (v - u) / 2，所以 v - u 为奇数时一定不存在，为偶数的话，我们一定可以通过三个数满足题目条件
    那有没有只用两个数就可以满足的情况呢？我们可以将 a + u 合并成一个数，也就是整个数组为 a、a + u，此时满足了总和为 v 的条件，只需要判断一下异或和是否为 u 即可
#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 xr, sum;
	cin >> xr >> sum;
	if (xr == 0 && xr == sum) cout << 0 << '\n';
	else if (xr == sum) cout << "1\n" << xr << '\n';
	else if (xr > sum) cout << -1 << '\n';
	else
	{
		if (((sum - xr) % 2) & 1)
		{
			cout << -1 << '\n';
			return;
		}
		int ans1 = (sum - xr) / 2;
		if ((ans1 ^ xr) == (ans1 + xr))
		{
			cout << 2 << '\n' << ans1 + xr << ' ' << ans1 << '\n';
			return;
		}
		else
		{
			cout << 3 << '\n' << ans1 << ' ' << ans1 << ' ' << xr << '\n';
			return;
		}
	}
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 1516C Baby Ehab Partitions Again（*1700 01背包+思维）

题目链接

题意是给你一个数组，让你删掉最少的数，使得操作之后的数组不满足这个条件：能将数组分成两个部分，每个部分总和相等

首先求总和，如果总和为奇数，肯定不能分，直接输出0

总和是偶数的话，就看看原数组里有没有奇数，如果有的话，删掉它，数组总和就变成奇数了，成立

如果原数组没有奇数，用01背包看看原数组能不能分成两个相等的部分，不能分的话直接输出0，可以分的话，就将所有数除以他们的最大公约数，这样肯定会制造出奇数，删掉它即可

#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);
	int sum = 0;
	for (int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		sum += a[i];
	}
	if (sum & 1) cout << 0 << '\n';
	else
	{
		sum /= 2;
		vector<int> dp(sum + 1);
		dp[0] = 1;
		for (int i = 1; i <= n; i ++ )
		{
			for (int j = sum; j >= a[i]; j -- )
			{
				dp[j] = (dp[j] | dp[j - a[i]]);
			}
		}
		if (!dp[sum])
		{
			cout << 0 << '\n';
			return;
		}
		int tmp = a[0];
		for (int i = 1; i <= n; i ++ )
		{
			if (a[i] & 1)
			{
				cout << 1 << '\n' << i << '\n';
				return;
			}
			tmp = __gcd(tmp, a[i]);
		}
		for (int i = 1; i <= n; i ++ )
		{
			a[i] /= tmp;
			if (a[i] & 1)
			{
				cout << 1 << '\n' << i << '\n';
				return;
			}
		}
	}
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 486C Palindrome Transformation（*1700 思维）

题目链接

题意是给你一个字符串，要让它变成回文串，首先告诉你现在的位置下标，你可以进行这些操作：

  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 m, p;
	cin >> m >> p;
	string s;
	cin >> s;
	int n = (s.size() + 1) / 2;
	vector<int> a(n + 1);
	s = " " + s;
	int ans = 0;
	for (int i = 1; i <= n; i ++ )
	{
		a[i] = min(abs(s[i] - s[m - i + 1]), min(s[i], s[m - i + 1]) - 'a' + 'z' - max(s[i], s[m - i + 1]) + 1);
		ans += a[i];
	}
	if (p > n) p = m - p + 1;
	int tmp1 = 0, tmp2 = 0;
	for (int i = 1; i <= p; i ++ )
	{
		if (a[i] != 0)
		{
			tmp1 = p - i;
			break;
		}
	}
	for (int i = n; i >= p; i -- )
	{
		if (a[i] != 0)
		{
			tmp2 = i - p;
			break;
		}
	}
	if (tmp1 > tmp2) ans += tmp1 + 2 * tmp2;
	else ans += tmp2 + tmp1 * 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();
	}
}

CF 1368D AND, OR and square sum（*1700 位运算+思维）

题目链接

题意是：给你一个数列，每次操作可以选择两个数，将其中一个数变为两数按位与，另一个数变为两数按位或，你可以进行无数次操作，最后要让 ∑ i = 1 n a i 2 \sum_{i=1}^n a_i^2 ∑i=1n​ai2​ 最大

思考按位与和按位或，可以发现每一位上 1 的数量是不变的，只是从一个数挪到另一个，所以保存下每一位 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 n;
	cin >> n;
	vector<int> cnt(35);
	for (int i = 0; i < n; i ++ )
	{
		int x; cin >> x;
		int idx = 0;
		while (x)
		{
			cnt[idx] += (x & 1);
			x >>= 1;
			idx ++ ;
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i ++ )
	{
		int x = 0;
		for (int j = 0; j < 34; j ++ )
		{
			if (cnt[j])
			{
				x += (1 << j);
				cnt[j] -- ;
			}
		}
		ans += x * x;
	}
	cout << ans << '\n';
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 1628B Peculiar Movie Preferences（*1700 思维）

题目链接

题意是给你几个字符串，长度最多是3，问有没有办法选择其中一部分拼在一起变成回文串

可以发现，如果有大于2个字符串拼起来是回文串，那选择首尾两个依旧是回文串，所以只需要考虑两个字符串拼在一起的情况

遍历每个字符串，想象这个字符串在尾部的情况：

  • 如果这个字符串长度为1，本身就是回文串，所以直接yes
  • 如果这个字符串长度为2,：
    • 如果是 “2 + 2” 的形式，查找一下前面是否出现过这个字符串倒过来的情况，出现过就直接yes
    • 如果是 “3 + 2” 的形式，查找一下前面是否出现过这个字符倒过来，再随便加一个字符的情况，出现过就直接yes
  • 如果这个字符串长度为3：
    • 如果是 “2 + 3” 的形式，查找一下前面是否出现过这个字符串后两个字符倒过来的情况，出现过就yes
    • 如果是 “3 + 3” 的形式，查找一下前面是否出现过这个字符串倒过来的情况，出现过就yes

都没出现就 no

#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<string> s(n + 1);
	set<string> st;
	for (int i = 1; i <= n; i ++ ) cin >> s[i];
	for (int i = 1; i <= n; i ++ )
	{
		if (s[i].size() == 1)
		{
			cout << "YES\n";
			return;
		}
		else if (s[i].size() == 2)
		{
			if (s[i][0] == s[i][1])
			{
				cout << "YES\n";
				return;
			}
			string tmp = "";
			tmp += s[i][1];
			tmp += s[i][0];
			if (st.find(tmp) != st.end())
			{
				cout << "YES\n";
				return;
			}
			for (int i = 0; i < 26; i ++ )
			{
				tmp += ('a' + i);
				if (st.find(tmp) != st.end())
				{
					cout << "YES\n";
					return;
				}
				tmp.pop_back();
			}
		}
		else
		{
			if (s[i][0] == s[i][2])
			{
				cout << "YES\n";
				return;
			}
			string tmp = "";
			tmp += s[i][2];
			tmp += s[i][1];
			if (st.find(tmp) != st.end())
			{
				cout << "YES\n";
				return;
			}
			tmp += s[i][0];
			if (st.find(tmp) != st.end())
			{
				cout << "YES\n";
				return;
			}
		}
		st.insert(s[i]);
	}
	cout << "NO\n";
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 1479A Searching Local Minimum（*1700 二分+交互）

题目链接

题意是：给你一个1-n的排列，每次可以询问第 i 个位置上的数是多少，找到一个位置，它前一个数和后一个数都比这个数大，最多询问100次

考虑二分，每次维护一个区间 [l, r]，使得 a[l] < a[l - 1] a[r] < a[r + 1]

每次询问 mid 和 mid + 1 这两个位置，如果满足 a[mid] < a[mid + 1]，就将 l 更新为 mid ，否则将 r 更新为 mid + 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;
 
int ask(int x)
{
	cout << "? " << x << endl;
	int m; cin >> m;
	return m;
}
 
void solve()
{
    int n;
	cin >> n;
	int l = 1, r = n;
	while (l < r)
	{
		int mid = l + r >> 1;
		int t1 = ask(mid), t2 = ask(mid + 1);
		if (t1 < t2) r = mid;
		else l = mid + 1;
	}
	cout << "! " << r << endl;
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 778A String Game（*1700 二分）

题目链接

题意是：给你两个字符串，和一个1-n的排列，使用这个排列给出的数据删第一个字符串的字符，目标是获得第二个字符串，问最多删多少次就不能再按给定的排列删了

很明显的二分，每次 O ( n ) O(n) O(n) 判断一下删 mid 次行不行就可以了

#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 t, p;
	cin >> t >> p;
	vector<int> a(t.size() + 1);
	for (int i = 1; i <= t.size(); i ++ ) cin >> a[i];
	int l = 0, r = t.size();
	t = " " + t, p = " " + p;
	auto check = [&](int x)
	{
		vector<bool> st(t.size());
		for (int i = 1; i <= x; i ++ ) st[a[i]] = true;
		int idx = 1;
		for (int i = 1; i < t.size(); i ++ )
		{
			if (st[i] || t[i] != p[idx]) continue;
			idx ++ ;
		}
		if (idx != p.size()) return false;
		else return true;
	};
	while (l < r)
	{
		int mid = l + r + 1 >> 1;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << r << '\n';
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 1336B Xenia and Colorful Gems（*1700 分类讨论+二分）

题目链接

题意是：给你三个数组，在每个数组里选一个数，使选出来的三个数两两之差的平方和最小

想让答案最小，就是让三个数尽可能接近，但是我们还不知道三个数的大小，所以枚举六种大小情况，每种情况二分算一下最小的结果

#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;

int ans = INF;

void work(vector<int> &a, vector<int> &b, vector<int> &c)
{
	for (int i = 0; i < a.size(); i ++ )
	{
		int b1 = -1, b2 = -1, c1 = -1, c2 = -1;

		int pos1 = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
		int pos2 = pos1 - 1;
		if (pos1 >= 0 && pos1 < b.size()) b1 = b[pos1];
		if (pos2 >= 0 && pos2 < b.size()) b2 = b[pos2];

		pos1 = lower_bound(c.begin(), c.end(), a[i]) - c.begin();
		pos2 = pos1 - 1;
		if (pos1 >= 0 && pos1 < c.size()) c1 = c[pos1];
		if (pos2 >= 0 && pos2 < c.size()) c2 = c[pos2];

		if (b1 != -1 && c1 != -1) ans = min(1ll * (b1 - a[i]) * (b1 - a[i]) + 1ll * (c1 - a[i]) * (c1 - a[i]) + 1ll * (b1 - c1) * (b1 - c1), ans);
		if (b1 != -1 && c2 != -1) ans = min(1ll * (b1 - a[i]) * (b1 - a[i]) + 1ll * (c2 - a[i]) * (c2 - a[i]) + 1ll * (b1 - c2) * (b1 - c2), ans);
		if (b2 != -1 && c1 != -1) ans = min(1ll * (b2 - a[i]) * (b2 - a[i]) + 1ll * (c1 - a[i]) * (c1 - a[i]) + 1ll * (b2 - c1) * (b2 - c1), ans);
		if (b2 != -1 && c2 != -1) ans = min(1ll * (b2 - a[i]) * (b2 - a[i]) + 1ll * (c2 - a[i]) * (c2 - a[i]) + 1ll * (b2 - c2) * (b2 - c2), ans);
	}
}

void solve()
{
    int aa, bb, cc;
	cin >> aa >> bb >> cc;
	vector<int> a(aa), b(bb), c(cc);
	for (int i = 0; i < aa; i ++ ) cin >> a[i];
	for (int i = 0; i < bb; i ++ ) cin >> b[i];
	for (int i = 0; i < cc; i ++ ) cin >> c[i];
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	sort(c.begin(), c.end());

	ans = INF;
	
	work(a, b, c);
	work(a, c, b);
	work(b, a, c);
	work(b, c, a);
	work(c, a, b);
	work(c, b, a);

	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 1400B RPG Protagonist（*1700 枚举）

题意是：有两个人，一个人可以拿a重量的东西，另一个人可以拿b重量的东西，现在有两个东西，告诉你数量和重量，问最多能拿多少样东西

首先保证第一样东西比第二样轻，这样我们首先肯定是拿第一样东西

然后只需要枚举第一个人拿了多少样第一个东西即可

#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;
	int cnt1, cnt2;
	cin >> cnt1 >> cnt2;
	int w1, w2;
	cin >> w1 >> w2;
	if (w1 > w2)
	{
		swap(w1, w2);
		swap(cnt1, cnt2);
	}

	int ans = 0;
	for (int i = 0; i <= cnt1; i ++ )
	{
		if (i * w1 > a) break;
		int c11 = i;
		int c12 = (a - w1 * c11) / w2;
		int tmp = c11 + c12;
		int c21 = min(cnt1 - i, b / w1);
		int c22 = min(cnt2 - c12, (b - c21 * w1) / w2);
		tmp += c21 + c22;
		ans = max(tmp, ans);
	}

	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

CF 1144F Graph Without Long Directed Paths

题目链接

题意是：给一个无向图，要求给每条边标记方向，使没有一条路径长度超过1

题意转化一下就是某个点只有入度或者只有出度，只需要bfs给每个点染色就可以，相邻两个点颜色不同，如果做不到的话就no

#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, m;
	cin >> n >> m;
	vector<vector<int>> g(n + 1);
	vector<PII> ed(m);
	for (int i = 0; i < m; i ++ )
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		ed[i] = {u, v};
	}
	queue<PII> q;
	q.push({1, 1});
	vector<int> ans(n + 1);
	ans[1] = 1;
	while (q.size())
	{
		auto t = q.front();
		q.pop();

		int ver = t.first, op = t.second;

		for (int i = 0; i < g[ver].size(); i ++ )
		{
			int j = g[ver][i];
			int nt;
			if (op == 1) nt = 2;
			else nt = 1;
			if (ans[j] && ans[j] != nt)
			{
				cout << "NO\n";
				return;
			}
			else if (ans[j]) continue;
			ans[j] = nt;
			q.push({j, nt});
		}
	}
	vector<int> res(m);
	for (int i = 0; i < m; i ++ )
	{
		int u = ed[i].first, v = ed[i].second;
		if (ans[u] == ans[v])
		{
			cout << "NO\n";
			return;
		}
		else if (ans[u] > ans[v]) res[i] = 1;
		else res[i] = 0;
	}
	cout << "YES\n";
	for (auto t : res)
	{
		if (t) cout << 1;
		else cout << 0;
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t -- )
	{
		solve();
	}
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布