首页 > 其他分享 >Codeforces Round 974 (Div. 3)题解记录

Codeforces Round 974 (Div. 3)题解记录

时间:2024-09-25 13:51:11浏览次数:14  
标签:974 return 题解 ll Codeforces cin else ans include

A.Robin Helps

签到模拟,遍历一遍即可,注意没钱时不给钱。\(O(n)\)

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
void fio()
{
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
}
int main()
{
	fio();
	ll t;
	cin >> t;
	while (t--)
	{
		ll n, k;
		cin >> n >> k;
		ll ans = 0;
		ll cnt = 0;
		for (ll i = 1; i <= n; i++)
		{
			ll x;
			cin >> x;
			if (x >= k)
			{
				ans += x;
			}
			if (x == 0)
			{
				if (ans > 0)
					ans--, cnt++;
			}
		}
		cout << cnt << endl;
	}
}

B.Robin Helps

一段区间\(i^i\)之和的奇偶性与这段区间内的i之和的奇偶性时相同的。本题注意是求符合区间到第n年的奇偶性.
这题看错成n年之内区间和是否出现偶数了,错了两次。代码写丑陋了.\(O(1)\)

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
void fio()
{
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
}
int main()
{
	fio();
	ll t;
	cin >> t;
	while (t--)
	{
		ll n, k;
		cin >> n >> k;
		if (n == 1)
		{
			cout << "NO" << endl;
				continue;
		}
		else if (n%2==0)
		{
			k = min(k, n);
			if ((k / 2) % 2 == 0)
			{
				cout << "YES" << endl;
			}
			else
				cout << "NO" << endl;
				continue;
		}
		else
		{
			if (n <= k)
			{
				if ((n / 2 + 1) % 2 == 0)
					cout << "YES" << endl;
				else
					cout << "NO" << endl;
				continue;
			}
			else
			{
				if (k % 2 == 0)
				{
					if ((k / 2) % 2 == 0)
						cout << "YES" << endl;
					else
						cout << "NO" << endl;
					continue;
				}
				else
				{
					if ((k / 2 + 1) % 2 == 0)
						cout << "YES" << endl;
					else
						cout << "NO" << endl;
				}
				continue;
			}
		}
	}
}

C. Robin Hood in Town

本题题意就是\(ai\)中最大值加多少可以使所有\(ai\)小于平均金额的一半的人的个数大于\(n/2\),直接二分.注意解决精度问题。
我是二分加多少,一开始\(r\)值写小了,错了一次,\(r\)值至少得大于等于\(1.99998e11\)。\(O(n*log(1e18))\)

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
void fio()
{
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
}
ll a[200005];
int main()
{
	fio();
	ll t;
	cin >> t;
	while (t--)
	{
		ll n;
		cin >> n;
		for (ll i = 1; i <= n; i++)cin >> a[i];
		if (n == 1 || n == 2)
		{
			cout << -1 << endl;
			continue;
		}
		sort(a + 1, a + 1 + n);
		ll sum = 0;
		for (ll i = 1; i <= n; i++)
		{
			sum += a[i];
		}
		ll l = 0, r = 1e18;
		while (l < r)
		{
			ll mid = (l + r) >> 1;
			ll k = sum + mid;
			ll cnt = 0;
			for (ll i = 1; i <= n-1; i++)
			{
				if (a[i] * n*2 < k)
				{
					cnt++;
				}
			}
			if (cnt * 2 > n)
			{
				r = mid;
			}
			else
				l = mid + 1;
		}
		cout << r << endl;
	}
}

D. Robert Hood and Mrs Hood

维护区间不同工作个数即可,同时维护一个最大值位置和最小值位置.
用了优先队列+双指针维护合理区间.\(O(nlogn)\)

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
void fio()
{
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
}
vector<ll>g[250000];
ll a[200005];
int main()
{
	fio();
	ll t;
	cin >> t;
	while (t--) 
	{
		ll n,d,k;
		cin >> n >> d >> k;
		for (ll i = 1; i <= k; i++)
		{
			ll l, r;
			cin >> l >> r;
			a[i] = l;
			g[l].push_back(r);
		}
	//	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>q1;
		priority_queue<ll,vector<ll>,greater<ll>>f;
		ll co = 0,ko=99999999999;
		ll ans = 0;
		ll s1, s2;
		ll l = 0, r = 0;
		for (ll i = 1; i <= n; i++)
		{
			if (l == 0 && r == 0)
			{
				l = 1, r = 1;
				for (auto j : g[i])
				{
					f.push(j);
					ans++;
				}
				if (r - l + 1 == d)
				{
					if (co < ans)
					{
						co = ans;
						s1 = l;
					}
					if (ko > ans)
					{
						ko = ans;
						s2 = l;
					}
				}
			}
			else if (r - l + 1 < d)
			{
				for (auto j : g[i])
				{
					f.push(j);
					ans++;
				}
				r++;
				if (r - l + 1 == d)
				{
					if (co < ans)
					{
						co = ans;
						s1 = l;
					}
					if (ko > ans)
					{
						ko = ans;
						s2 = l;
					}
				}
			}
			else
			{
				while (!f.empty() && f.top() <= l)
				{
					ans--;
					f.pop();
				}
				for (auto j : g[i])
				{
					f.push(j);
					ans++;
				}
				l++;
				r++;
				if (r - l + 1 == d)
				{
					if (co < ans)
					{
						co = ans;
						s1 = l;
					}
					if (ko > ans)
					{
						ko = ans;
						s2 = l;
					}
				}
			}
		}
		cout << s1 << " " << s2 << endl;
		for (ll i = 1; i <= n; i++)
		{
			g[i].clear();
		}
	}
}

E. Rendez-vous de Marian et Robin

感觉是div3里对我来说最难得题了
先处理一遍1到所有点的最短路,再考虑马点的最短路。由于dijkstra特性每次到了最近的马点再返回,后续到了新马点就不用再走之前返回过了的点,vis起作用了
于是一次dijkstra的时间复杂度最大为\(2*(m+nlogn)\).
最后再处理n到所有点的最短路,总时间复杂度为\(4*(m+nlogn)\)
最后答案走一遍\(max(dp1[i],dp2[i])\)的最小值即可\(O(4*(m+nlogn))\)

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
ll ksm(ll x, ll y)
{
	ll ans = 1;
	while (y)
	{
		if (y & 1)
			ans *= x;
		x *= x;
		y >>= 1;
	}
	return ans;
}
ll house[200005];
vector<pair<ll, ll>>g[200005];
ll n, m, h;
bool vis[200005][2];
void dij(ll a[][2], ll x)
{
	priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>>q;
	a[x][0] = 0;
	q.push({ a[x][0],{x,0} });
	for (ll i = 1; i <= n; i++)vis[i][0] = vis[i][1] = 0;
	while (!q.empty())
	{
		ll x = q.top().second.first;
		ll hu = q.top().second.second;
		q.pop();
		if (vis[x][hu])continue;
		vis[x][hu] = 1;
		if (hu == 0 && house[x])
		{
			a[x][1] = min(a[x][0],a[x][1]);
			q.push({ a[x][1],{x,1} });
		}
		for (auto j : g[x])
		{
			ll nx = j.first;
			ll w = j.second;
			if (!vis[nx][hu])
			{
				if (hu == 0)
				{
					if (a[nx][hu] > a[x][hu] + w)
					{
						a[nx][hu] = a[x][hu] + w;
						q.push({ a[nx][hu],{nx,hu} });
					}
				}
				else
				{
					if (a[nx][hu] > a[x][hu] + w/2)
					{
						a[nx][hu] = a[x][hu] + w/2;
						q.push({ a[nx][hu],{nx,hu} });
					}
				}
			}
		}
	}
	for (ll i = 1; i <= n; i++)
	{
		a[i][0] = min(a[i][1], a[i][0]);
	}
	return;
}
	ll dp1[200005][2];
		ll dp2[200005][2];
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		cin >> n >> m >> h;
		for (ll i = 1; i <= n; i++)house[i] = 0, g[i].clear();
		while (h--)
		{
			ll x;
			cin >> x;
			house[x] = 1;//表示马点
		}
		while (m--)
		{
			ll l, r, w;
			cin >> l >> r >> w;
			g[l].push_back({ r,w });
			swap(l, r);
			g[l].push_back({ r,w });
		}
		for (ll i = 1; i <= n; i++)
		{
			dp1[i][0] = dp1[i][1] = dp2[i][0] = dp2[i][1] = 999999999999999;
		}
		dij(dp1, 1);
		dij(dp2, n);
		if (dp1[n][0] == 999999999999999)
		{
			cout << -1 << endl;
		}
		else
		{
			ll ans = 999999999999999;
			for (ll i = 1; i <= n; i++)
			{
				ll u = max(dp1[i][0] , dp2[i][0]);
				ans = min(ans, u);
			}
			cout << ans << endl;
		}
	}
}

F. Sheriff's Defense

直接dp即可,保或者不保回溯即可
这里一开始想成优先队列枚举了,尴尬。没直接盯帧dp
\(O(1)\)

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
ll dp[200005][2];
void fio()
{
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
}
vector<ll>g[250000];
ll a[250000];
bool vs[250000];
ll n, m, k;
void dfs(ll x)
{
	if (vs[x])
		return;
	vs[x] = 1;
	dp[x][1] = a[x];
	dp[x][0] = 0;
	for (auto j : g[x])
	{
		if (vs[j])
			continue;
		dfs(j);
		dp[x][1] += max(dp[j][0], dp[j][1]-k*2);
		dp[x][0] += max(dp[j][0], dp[j][1]);
	}
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		cin >> n >> k;
		for (ll i = 1; i <= n; i++)cin >> a[i], vs[i] = 0, g[i].clear();
		for(ll i=1;i<=n-1;i++)
		{
			ll l, r;
			cin>> l >> r;
			g[l].push_back(r);
			g[r].push_back(l);
		}
		dfs(1);
		cout << max(dp[1][1], dp[1][0]) << endl;
	}
}

G. Milky Days

思路很明显,用堆栈维护最新的牛奶即可,考虑到没有新牛奶的时候和有新牛奶的时候
过保质期或者没牛奶了弹出。
写复杂了,哈哈。这里一开始错\(WA2\)了,原因在于\(u==uo\)的时候减少的数量不是理想数量\(jo\)
\(O(nlogn)\)

	//难改
	#include<iostream>
	#include<set>
	#include<map>
	#include<vector>
	#include<algorithm>
	#include<bitset>
	#include<math.h>
	#include<string>
	#include<string.h>
	#include<stack>
	#include<queue>
	#include<time.h>
	#include<random>
	using namespace std;
	typedef long long ll;
	mt19937 rnd(time(0));
	ll gcd(ll a, ll b) {
		if (b == 0) return a;
		else return gcd(b, a % b);
	}
	ll ksm(ll x, ll y)
	{
		ll ans = 1;
		while (y)
		{
			if (y & 1)
				ans *= x;
			x *= x;
			y >>= 1;
		}
		return ans;
	}
	ll a[250000];
	ll hh[250000];
	//stack<pair<ll, ll>>q;
	void fio()
	{
		ios::sync_with_stdio();
		cin.tie(0);
		cout.tie(0);
	}
	int main()
	{
		fio();
		ll t;
		cin >> t;
		while (t--)
		{
			ll n,m,k;
			cin >> n >> m >> k;
			for (ll i = 1; i <= n; i++)// 栈+模拟?
				cin >> a[i] >> hh[i];
			stack<pair<ll, ll>>q;
			ll u = 0;
			ll ans = 0;
			for (ll i = 1; i <= n; i++)
			{
				if (q.empty())
				{
					u = a[i];
					hh[i] -= m;
					if (hh[i] >= 0)ans++;
					if (hh[i] > 0)
						q.push({ a[i] + k - 1,hh[i] });
				}
				else
				{
					ll uo = a[i] - 1;
					ll cnt = 0;
					while (!q.empty())
					{
						if (q.top().first <= u)
						{
							q.pop();
							continue;
						}
						if (u == uo)
							break;
						if (cnt == 0)
						{
							ll of = q.top().first;
							ll ok = q.top().second;
							ll jo = ok / m;
							ll wc = u + jo;
							wc = min(wc, uo);
							wc = min(wc, of);
							ans += wc - u;
							ll zo = wc - u;
								u = wc;
							if (wc == uo)//最后一天
							{
								q.pop();
								if (ok > zo*m)
								{
									q.push({ of,ok - zo * m });
								}
								continue;
							}
							else if (wc == of)// 保质期
							{
								q.pop();
								continue;
							}
							else //非最后一天,非保质期
							{
								q.pop();
								cnt = ok % m;//看剩余
							}
						}
						else
						{
							while (!q.empty())
							{
								ll of = q.top().first;
								if (of <= u)//先把剩下的去除
								{
									q.pop();
									continue;
								}
								ll ok = q.top().second;
								if (cnt +ok >= m)
								{
									
									ok -= (m - cnt);
									cnt = 0;
									q.pop();
									q.push({ of,ok });
									ans++;
									break;
								}
								else
								{
									cnt += ok;
									q.pop();
								}
							}
							cnt = 0;
							u++;
						}
					}
					if (hh[i] >= m)
					{
						ans++;
						hh[i] -= m;
						if(hh[i]>0)
						q.push({ a[i] + k - 1,hh[i] });
						u = a[i];
						continue;
					}
					cnt = hh[i];
					while (!q.empty())
					{
						ll of = q.top().first;
						ll ok = q.top().second;
						if (of <= u)
						{
							q.pop();
							continue;
						}
						else
						{
							if (ok + cnt >= m)
							{
								ans++;
								ok -= (m - cnt);
								q.pop();
								if(ok>0)
								q.push({ of,ok });
								break;
							}
							else
							{
								cnt += ok;
								q.pop();
								continue;
							}
						}
					}
					u++;
				}
			}
			ll cnt = 0;
			while (!q.empty())
			{
				ll of = q.top().first;
				ll ok = q.top().second;
				if (of <= u)
				{
					q.pop();
					continue;
				}
				if (cnt == 0)
				{
					ll wc = ok / m + u;
					if (wc >= of)
					{
						wc = of;
						ans += wc-u;
						u = wc;
						cnt = 0;
						q.pop();
						continue;
					}
					else
					{
						ans += wc-u;
						u = wc;
						cnt = ok % m;
						q.pop();
					}
				}
				else
				{
					while (!q.empty())
					{
						ll of = q.top().first;
						ll ok = q.top().second;
						if (of <= u)
						{
							q.pop();
							continue;
						}
						if (cnt + ok >= m)
						{
							ans++;	
							ok -= (m - cnt);
							q.pop();
							cnt = 0;
							if(ok>0)
							q.push({ of,ok });
							break;
						}
						else
						{
							cnt += ok;
							q.pop();
						}
					}
					cnt = 0;
					u++;
				}
			}
			cout << ans << endl;
		}
	}

H. Robin Hood Archery

挺惊讶的一道题,思路从数组前缀异或和->线段树->随机数飘了一遍
最后随机数解决了这道题.偶数反例:2,4,8,14.
随机数大概率减少了这种情况发生。\(O(nlogn)\)级别左右

//看命
#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<bitset>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<time.h>
#include<random>
using namespace std;
typedef unsigned long long ll;
mt19937 rnd(time(0));
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
ll ksm(ll x, ll y)
{
	ll ans = 1;
	while (y)
	{
		if (y & 1)
			ans *= x;
		x *= x;
		y >>= 1;
	}
	return ans;
}
ll a[250000];
ll hh[250000];
map<ll, ll>q,f;
void fio()
{
	ios::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
}
int main()
{
	fio();
	ll t;
	cin >> t;
	while (t--)
	{
		ll n, m;
		cin >> n >> m;
		for (ll i = 1; i <= n; i++)
		{
			cin >> a[i];
			if (q[a[i]] == 0)
			{
				ll k = rnd();
				while (f[k] != 0)
				{
					k = rnd();
				}
				f[k]++;
				q[a[i]] = k;
				a[i] = k;
			}
			else
				a[i] = q[a[i]];
		}
		ll u = 0;
		for (ll i = 1; i <= n; i++)
		{
			hh[i] = a[i] ^ hh[i - 1];//异或前缀和?
		}
		while (m--)
		{
			ll l, r;
			cin >> l >> r;
			if ((r - l + 1) % 2)
			{
				cout << "NO" << endl;
			}
			else
			{
				if ((hh[r] ^ hh[l - 1]) == 0)
				{
					cout << "YES" << endl;
				}
				else
					cout << "NO" << endl;
			}
		}
	}
}

标签:974,return,题解,ll,Codeforces,cin,else,ans,include
From: https://www.cnblogs.com/cjcf/p/18431199

相关文章

  • [ARC122E] Increasing LCMs 题解
    感觉像比较套路的构造题。思路假如我们正着进行构造,可以发现我们加入一个数以后,对后面的数产生的影响是很大的。但是如果我们从最后一个数开始构造,那么可以发现它是不会对之后的构造产生任何影响的。应为越前面的数的限制会越少,那么可以填的数一定是不减的。一个数可以填在后......
  • 算法题之图论 [NOIP2001 提高组] Car的旅行路线详细题解
    P1027[NOIP2001提高组]Car的旅行路线这道题的思路呢,就是建个图,然后跑一遍Floyd,比较最小值就可以解决了。but!它每个城市只给三个点(共四个),所以还得计算出第四个点坐标。这里根据矩形的中点公式来表示未知点的坐标:(这个思路源于大佬 _jimmywang_       ......
  • [ARC121E] Directed Tree 题解
    简单容斥题。思路题面的条件相当于一个位置上填的点不能是自己的祖先。发现直接做并不好做。考虑容斥。我们想要求出\(f_i\)为至少有\(i\)个不合法位置的方案数。那么答案为:\[\sum_{i=0}^nf_i(-1)^i\]如何求解。设\(f_{i,j}\)为\(i\)子树下有\(j\)个不合法位......
  • 2024-2025专题一题单 - 题解
    A-Virus原题链接题解B-Coverage原题链接题解C-Sensors原题链接题解D-MakeTakahashiHappy原题链接题解E-Don’tbecycle原题链接题解F-AlmostEqual原题链接题解G-StepUpRobot原题链接题解H-SnukeMaze原题链接题解I-MEX原题链接......
  • P5329 [SNOI2019] 字符串 题解
    Description给出一个长度为\(n\)的由小写字母组成的字符串\(a\),设其中第\(i\)个字符为\(a_i\(1\leqi\leqn)\)。设删掉第\(i\)个字符之后得到的字符串为\(s_i\),请按照字典序对\(s_1,s_2,……,s_n\)从小到大排序。若两个字符串相等,则认为编号小的字符串字典序更小。......
  • CF164D Minimum Diameter 题解
    最小点覆盖模板题。思路考虑二分直径\(x\)。我们将距离\(>x\)的点对连一条边,那么每一条边的两端至少有一端需要被删掉。这是最小点覆盖的定义。那么就是判断最小点覆盖是否小于等于\(k\)。发现这个问题并不好用一些多项式复杂度的做法解决。考虑暴搜。每一次我们把度......
  • CF2003F Turtle and Three Sequences 题解
    个人觉得*2800有点虚高。如果做过类似的题(比如[THUSCH2017]巧克力),应该可以想到随机映射,状压dp也不难想。实际上,看到要选出\(m\)种不同的颜色,且\(m\le5\)就可以想到将每种颜色随机映射到\(1\)到\(m\)中,这样子得出来的答案不会更优,而当答案选择的\(m\)种颜色恰好......
  • 20240924 模拟赛 T4 题解
    Description这是一道交互题。有一棵\(n\)个节点的树,现在要求你通过若干次询问得到这棵树的每一条边连接哪两个点。每次询问你需要指定\(n\)个整数\(d_1,d_2,\ldots,d_n\),满足\(-1\leqd_i\leqn\),其中\(1\leqi\leqn\)。每次询问交互库会返回给你一个长度为\(n\)的......
  • CF974 Review
    CF974Review(以后比较简单的题就不写了)ABCskipD个人写了\(O(n\logn)\)的类模拟算法,能过,但不能做到$O(n)$。考虑什么时候一段\([st,st+d-1]\)的时间会和某一段区间有重合,也就是我自己写的算法的核心思想其实。那就是$st+d-1\gel_i\quadst\ler_i$,变形一......
  • P4780 Phi的反函数 题解
    因为\(\varphi(x)\)的值只与\(x\)的不同质因子有关,又因为\(2^{31}\)之内的数的质因子个数不超过\(10\),所以容易枚举\(10\)个位置上填入的质因子打出朴素的暴力,简单剪枝后得到\(20\)分。注意需要先判掉\(x=n+1\)的情况。考虑优化:因为\(\varphi\)的值只与质因......