Codeforces Round #835 (Div.4) A-G题解

原题链接：

https://codeforces.com/contest/1744

A. Medium Number

题意：给定三个数，求中间那个数（倒数第二小or倒数第二大）。

题解：直接用数组存，sort一下输出中间的数即可。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll a[N];
void solve()
{
	cin >> a[1] >> a[2] >> a[3];
	sort(a + 1, a + 4);
	cout << a[2] << endl;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

B. Atilla's Favorite Problem

题意：对于给定由小写字母构成的字符串，问书写这样的字符串要会写多少个字符（如写b需要学会a）。

题解：对字符串排序一下，只需要找到字符串中最靠后的字母，就能知道答案。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n;
string s;
void solve()
{
	string s;
	cin >> n >> s;
	sort(s.begin(), s.end());
	cout << s[s.size() - 1] - 'a' + 1 << endl;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

C. Advantage

题意：每个人有一个力量值，求每个人和出自己之外最强的那个人的差距。

题解：记录力量最大值和次大值，如果当前这个人已经是最强就和次强比较，其余都和最强比较。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n, c[N], a[N];
void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		c[i] = a[i];
	}
	sort(c + 1, c + n + 1);
	ll x = c[n], y = c[n - 1];//记录最强和次强
	for (int i = 1; i <= n; i++)
	{
		if (a[i] != x)//不是最强就和最强比
		{
			cout << a[i] - x << " ";
		}
		else//否则和次强比
		{
			cout << a[i] - y << " ";
		}
	}
	cout << endl;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

D. Challenging Valleys

题意：给定一个数组，判断当前数组是否只存在一个“山谷”，是则输出YES，否则输出NO。

山谷的定义：对于[l, r]的子串满足

0 ≤ l ≤ r ≤ n − 1 ,

a[l] = a[l + 1] = a[l + 2] = ⋯ = a[r],

l = 0 or a[l − 1] > a[l],

r = n − 1 or a[r] < a[r + 1]

emmm,一句话说就是当前这个数要小于右边第一个不等于自身的数和左边第一个不等于自身的数，边界默认比自身大。

题解：我的做法可能稍微代码量复杂了点，但是思路很明显~先把连续相等的数只保留一个，再在数组前和数组后插入一个较大值模拟边界，然后一遍循环判断每个值是否小于前面的和后面的值，并记录个数，最后判断一下输出即可。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n, m;
void solve()
{
	cin >> n;
	vector<ll> v, v1;
	v.push_back(INT_MAX);
	for (int i = 1; i <= n; i++)
	{
		cin >> m;
		v.push_back(m);
	}
	v.push_back(INT_MAX);
	if (n == 1)//特判
	{
		cout << "YES" << endl;
		return;
	}
	for (int i = 1; i < v.size(); i++)
	{
		if (v[i] != v[i - 1])//去除连续相等的数
		{
			v1.push_back(v[i - 1]);
		}
	}
	v1.push_back(INT_MAX);//别忘了加边界啊喂
	ll cnt = 0;
	for (int i = 1; i < v1.size() - 1; i++)
	{
		if (v1[i - 1] > v1[i] && v1[i + 1] > v1[i])
		{
			cnt++;
			if (cnt >= 2) break;
		}
	}
	if (cnt == 1) cout << "YES" << endl;
	else cout << "NO" << endl;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

E. Binary Inversions

题意：给定一个只包含10的数组，每个1对数组的贡献值为当前位置后面0的数量，你可以翻转任意一个位置的数（1变0, 0变1),最多只能翻转一次，问整个数组的最大贡献值是多少。

题解：我们只要用数组记录一下每个位置后0的个数，以及每个位置前1的个数（包括当前位置），对于每个位置的翻转操作我们就很容易知道翻转后的总贡献值，时间复杂度为O(1)，记录一下最大值输出即可。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n, m, af[N], a[N], be[N];
void solve()
{
	//别忘了初始化
	memset(af, 0, sizeof af);
	memset(be, 0, sizeof be);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		if (a[i] == 1) be[i] = be[i - 1] + 1;//每个位置前面1的个数
		else be[i] = be[i - 1];
	}
	for (int i = n; i >= 1; i--)
	{
		if (a[i] == 0) af[i] = af[i + 1] + 1;//每个位置后面0的个数
		else af[i] = af[i + 1];
	}
	ll ans = 0, res;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == 1)
			ans += af[i];
	}
	res = ans;//记录不翻转时的答案
	//cout << ans << endl;
	for (int i = 1; i <= n; i++)
	{
		//简单模拟一下翻转操作就能得到翻转后数组贡献值的式子，记录一下最大值
		if (a[i] == 0) ans = max(ans, res + af[i] - 1 - be[i]);
		else ans = max(ans, res + be[i] - 1 - af[i]);
	}
	cout << ans << endl;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

F. Quests

题意：有n个箱子，每天可以开一个，开完后会获得箱子里的硬币，箱子k天刷新，问在d天内获得至少c枚硬币的k的最大值是多少。如果k可以无限大输出Infinity，如果不可能取得c枚硬币及以上则输出Impossible。

题解：题意有点绕u1s1，贪心。我们尽可能每次开硬币最多的箱子，很明显当k已知时，我们取硬币的操作是一个循环，简单推一下式子就可以知道d天内我们能取得的硬币的最大值，和c比较一下即可。

对于Impossible的情况，很明显即我们每天开硬币最多的箱子都不能达到c。

对于Infinity的情况，是我们每个箱子都开一遍硬币数能达到c（因为无论k多大，我们至少能把每个箱子开一遍），那k也可以无限大。

注意当d < n时，我们只能开d个箱子。理清逻辑后，我们只要从大到小枚举k，输出答案即可。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
bool cmp(ll x, ll y) { return x > y; }
ll n, m, sum[N], a[N], d;
void solve()
{
	memset(sum, 0, sizeof sum);
	cin >> n >> m >> d;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1, cmp);//降序
	for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];//记录前缀和
	if (a[1] * d < m)
	{
		cout << "Impossible" << endl;
	}
	else if(sum[min(n, d)] >= m)
	{
		cout << "Infinity" << endl;
	}
	else
	{
		ll cnt;
		//从大到小枚举k
		for (ll i = d; i >= 0; i--)
		{
			//我们每轮循环可以开k + 1个箱子
			cnt = sum[min(i + 1, n)];
			//计算硬币数
			//硬币数 = 每轮循环取得的硬币数 cnt * 循环次数 d / (i + 1) + 剩下几天取得的硬币数 sum[min(n, d % (i + 1))]
			if (d / (i + 1) * cnt + sum[min(n, d % (i + 1))] >= m)
			{
				cout << i << endl;
				return;
			}
		}
	}
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

G. SlavicG's Favorite Problem

题意：给定一个树，每条边有一个权值，每经过一条边就会异或上边的权值，初始值为0，规定走到终点必须恰好权值为0才能走，并且允许无条件传送一次到任意点（除了终点），问能否从起点走到终点，能输出YES，不能输出NO。

题解：两个相等的数异或为0，那么走到终点其实就是两段路径的异或值相同，这两段路径可以理解为先从起点走了一段，再传送（或者不传送）到某个点，然后直接走到终点。我们先从终点dfs一遍到终点的所有路径，并记录过程中的异或值，用set来存方便判断，再从起点dfs一遍起点能走的所有路径，如果过程中的异或值在到终点的路径中出现过就直接传送咯。

注意从起点开始的路径不能直接走到终点！！！

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n, a[N], x, y, f[N];
map<pair<ll, ll>, ll> mp;
vector<ll> ve[N];
set<ll> st;
bool flag;
void dfs(ll x1, ll ans1)//枚举终点路径
{
	for (int i = 0; i < ve[x1].size(); i++)
	{
		if (f[ve[x1][i]] == 0)
		{
			f[ve[x1][i]] = 1;
			st.insert(ans1^mp[{x1, ve[x1][i]}]);
			dfs(ve[x1][i], (ans1^mp[{x1, ve[x1][i]}]));
			f[ve[x1][i]] = 0;
		}
	}
}
void dfs2(ll x2, ll ans2)//枚举起点
{
	for (int i = 0; i < ve[x2].size(); i++)
	{
		if (f[ve[x2][i]] == 0 && ve[x2][i] != y)//如果是终点就跳过
		{
			f[ve[x2][i]] = 1;
			if (st.count(ans2^mp[{x2, ve[x2][i]}]))//set判断就是方便嘿嘿
			{
				flag = true;
				return;
			}
			dfs2(ve[x2][i], (ans2^mp[{x2, ve[x2][i]}]));
			f[ve[x2][i]] = 0;
		}
	}
}
void solve()
{
	//初始化
	flag = false;
	st.clear();
	ll u, v, w;
	cin >> n >> x >> y;
	for (ll i = 1; i <= n; i++)
	{
		ve[i].clear();
	}
	for (int i = 1; i < n; i++)
	{
		cin >> u >> v >> w;
		mp[{u, v}] = w;//记录u到v的权值
		mp[{v, u}] = w;
		ve[u].push_back(v);//记录边
		ve[v].push_back(u);
	}
	memset(f, 0, sizeof f);
	f[y] = 1;
	dfs(y, 0);
	memset(f, 0, sizeof f);
	f[x] = 1;
	dfs2(x, 0);
	if (flag)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}