【cf】Codeforces Round 941（Div.2）题解 A

【cf】Codeforces Round 941（Div.2）题解 A - D

前三题出的最快的一次，但是d没出
在这里插入图片描述

A. Card Exchange

只要有一种颜色大于等于 k，那就是 k-1，否则就是 n

#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 = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n, k;
	cin >> n >> k;
	map<int, int> mp;
	for (int i = 0; i < n; i ++ )
	{
		int x; cin >> x;
		mp[x] ++ ;
	}
	bool flag = false;
	for (auto t : mp)
	{
		if (t.second >= k)
		{
			flag = true;
			break;
		}
	}
	if (flag) cout << k - 1 << '\n';
	else cout << n << '\n';
}

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

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

B. Rectangle Filling

首先看如果有对角颜色一样，就直接 Yes

如果对角颜色都不一样，就看四条边的颜色情况，看每条边是否有两种不一样的颜色，如果上边和左边有不一样的颜色，就可以直接改变左上角端点的颜色，其他端点也类似，只要有一个端点的颜色可以被改变，就能完成任务

#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 = 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 (g[1][1] == g[n][m] || g[1][m] == g[n][1])
	{
		cout << "YES\n";
		return;
	}
	vector<bool> flag(4);
	map<char, int> mp;
	for (int i = 1; i <= n; i ++ )
	{
		mp[g[i][1]] ++ ;
	}
	if (mp.size() == 2) flag[0] = true;
	mp.clear();
	
	for (int i = 1; i <= n; i ++ )
	{
		mp[g[i][m]] ++ ;
	}
	if (mp.size() == 2) flag[1] = true;
	mp.clear();

	for (int i = 1; i <= m; i ++ )
	{
		mp[g[1][i]] ++ ;
	}
	if (mp.size() == 2) flag[2] = true;
	mp.clear();
	
	for (int i = 1; i <= m; i ++ )
	{
		mp[g[n][i]] ++ ;
	}
	if (mp.size() == 2) flag[3] = true;
	mp.clear();
	if ((flag[2] && flag[0]) || (flag[2] && flag[1]) || (flag[1] && flag[3]) || (flag[0] && flag[3]))
	{
		cout << "YES\n";
		return;
	}
	cout << "NO\n";
	return;
}

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

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

C. Everything Nim

首先要想明白一点就是，如果序列中有 1，那操作是被固定的，只能选择 1，但是如果序列中没有 1，我可以使用操作使得序列中出现 1，这样对方的操作就被固定了

举个栗子，如果序列是 3 5 7 9，第一个操作的人可以使它变成 1 3 5 7，这样第二个操作的只能变成 2 4 6，第一个人再变成 1 3 5，第二个人只能 2 4……也就是通过我的操作使得序列最小是 1，去限制对方的操作

但是如果序列有 1，首先就会限制自己的操作，一直到 1 2 3 4 … 连续序列被打断为止

如果这样被限制的操作是奇数次，那下一个可以自由操作的人就是Bob，所以Bob赢（除非已经没有可以操作的序列了）

如果这样被限制的操作是偶数次，那下一个可以自由操作的人就是Alice，所以Alice赢（除非已经没有可以操作的序列了）

#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 = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
	if (a[0] != 1)
	{
		cout << "Alice\n";
		return;
	}
	int pos = 1;
	for (int i = 1; i < a.size(); i ++ )
	{
		if (a[i] == i + 1) pos = i + 1;
		else break;
	}
	if ((pos % 2 != 0 && pos != a.size()) || (pos % 2 == 0 && pos == a.size())) cout << "Bob\n";
	else cout<< "Alice\n";
}

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

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

D. Missing Subsequence Sum

因为我们要把 k 这个位置空出来，首先我们需要保证前 k - 1 个构造出来：

int tmp = k - 1;
for (int i = 1; i <= tmp; i *= 2)
{
	ans.push_back(i);
	tmp -= i;
}

此时 tmp 不为 0 的话还要把 tmp 也放进去

接下来从 k + 1 开始构造到 n：

for (int i = k + 1; i <= n; i *= 2) ans.push_back(i);

观察一下这一次构造出来的数：k+1 2k+2 4k+4 …

从 k+1 到下一个不能直接表示的最大的数（也就是 2k+1）需要加 k ，显然不能直接给 k ，于是直接给 2k+1

再往后看，从 2k+2 到下一个不能直接表示的最大的数（也就是 4k+3）需要加 2k+1，已经有了

从 4k+4 到下一个不能直接表示的最大的数（也就是 8k+7）需要加 4k+3，已经有了

……

（上面只是在说为什么要在最后给 2k+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 = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n, k;
	cin >> n >> k;
	int tmp = k - 1;
	vector<int> ans;
	for (int i = 1; i <= tmp; i *= 2)
	{
		ans.push_back(i);
		tmp -= i;
	}
	if (tmp > 0) ans.push_back(tmp);
	for (int i = k + 1; i <= n; i *= 2) ans.push_back(i);
	ans.push_back(2 * k + 1);
	cout << ans.size() << '\n';
	for (auto t : ans) cout << t << ' ';
	cout << '\n';
}

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

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