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

Codeforces Round 893 (Div. 2)题解记录

时间：2024-10-17 23:31:52浏览次数：6  
标签：sz 893 题解 ll Codeforces ans front include mod

题目链接：https://codeforces.com/contest/1858

A. Buttons


从自身角度出发,我想赢就得保证我的按钮尽可能多所以，大家都优先按\(c\)，然后分析先后顺序即可

	#include<iostream>
	#include<string.h>
	#include<map>
	#include<vector>
	#include<set>
	#include<unordered_set>
	#include<stack>
	#include<queue>
	#include<algorithm>
	#include<time.h>
	#include<random>
	#include<string>
	#include<string.h>
	#include<cctype>
	using namespace std;
	typedef long long ll;
	mt19937 rnd(time(0));
	const ll mod = 1e9 + 7;
	void fio()
	{
		ios::sync_with_stdio(0);
		cin.tie(0);
		cout.tie(0);
	}
	ll gcd(ll x, ll y)
	{
		if (y == 0)
			return x;
		else
			return gcd(y, x % y);
	}
	ll ksm(ll x, ll y)
	{
		ll ans = 1;
		while (y)
		{
			if (y & 1)
				ans = ans%mod*(x%mod)%mod;
			x = x%mod*(x%mod)%mod;
			y >>= 1;
		}
		return ans%mod%mod;
	}
	int main()
	{
		ll t;
		cin>>t;
		while(t--)
		{
			ll a,b,c;
			cin>>a>>b>>c;
			//swap(b,c);
			ll j=c%2;
			if(j==0)
			{
				if(a<=b)
				{
					cout<<"Second"<<endl;
				}
				else
				cout<<"First"<<endl;
			}
			else
			{
				if(b<=a)
				{
					cout<<"First"<<endl;
				}
				else
				cout<<"Second"<<endl;
			}
		}
	}

B. The Walkway

题目乍看比较繁琐且翻译有问题？

一个饼干店的有无只会影响周围饼干店到这个饼干店的途中的吃饼干次数
分类讨论下即可

	#include<iostream>
	#include<string.h>
	#include<map>
	#include<vector>
	#include<set>
	#include<unordered_set>
	#include<stack>
	#include<queue>
	#include<algorithm>
	#include<time.h>
	#include<random>
	#include<string>
	#include<string.h>
	#include<cctype>
	using namespace std;
	typedef long long ll;
	mt19937 rnd(time(0));
	const ll mod = 1e9 + 7;
	void fio()
	{
		ios::sync_with_stdio(0);
		cin.tie(0);
		cout.tie(0);
	}
	ll gcd(ll x, ll y)
	{
		if (y == 0)
			return x;
		else
			return gcd(y, x % y);
	}
	ll ksm(ll x, ll y)
	{
		ll ans = 1;
		while (y)
		{
			if (y & 1)
				ans = ans%mod*(x%mod)%mod;
			x = x%mod*(x%mod)%mod;
			y >>= 1;
		}
		return ans%mod%mod;
	}
	ll a[250000];
	ll b[250000];
	int main()
	{
		ll t;
		cin>>t;
		while(t--)
		{
			ll n,m,d;
			cin>>n>>m>>d;
			for(ll i=0;i<=m;i++)b[i]=0;
			for(ll i=1;i<=m;i++)
			{
				cin>>a[i];
			}
			ll op=0;ll k=0;
			ll ok=0;
			for(ll i=1;i<=m;i++)
			{
				ll ans=0;
				ll cnt=0;
				if(i==1)
				{
					if(a[i]==1)
					{
						op=0;
						k=1;
						ok++;
					}
					else
					{
						ans=(a[i]-1-1)/d+2+((a[i+1]-1)-a[i])/d+1;
						cnt=(a[i+1]-1-1)/d+2;
						//cout<<ans<<" "<<cnt<<endl;
						ok+=(a[i]-1-1)/d+2;
						if(ans-cnt>op)
						{
							op=ans-cnt;
							k=1;
						}
						else if(ans-cnt==op)k++;
					}
				}
				else if(i==m)
				{
					ans=(a[i]-1-a[i-1])/d+1+(n-a[i])/d;
					cnt=(n-a[i-1])/d;
					ok+=ans;
					if(ans-cnt>op)
					{
						op=ans-cnt;
							k=1;
					}
					else if(ans-cnt==op)k++;
				}
				else
				{
					ans=(a[i]-1-a[i-1])/d+1+(a[i+1]-1-a[i])/d+1;
					cnt=(a[i+1]-1-a[i-1])/d+1;
					ok+=(a[i]-1-a[i-1])/d+1;
					if(ans-cnt>op)
					{
						op=ans-cnt;
							k=1;
					}
					else if(ans-cnt==op)k++;
				}
			}
		//	cout<<ok<<endl;
			cout<<ok-op<<" "<<k<<endl;
		}
	}

C. Yet Another Permutation Problem


优先考虑二倍递增，这样子一定gcd种类最多

	#include<iostream>
	#include<string.h>
	#include<map>
	#include<vector>
	#include<set>
	#include<unordered_set>
	#include<stack>
	#include<queue>
	#include<algorithm>
	#include<time.h>
	#include<random>
	#include<string>
	#include<string.h>
	#include<cctype>
	using namespace std;
	typedef long long ll;
	mt19937 rnd(time(0));
	const ll mod = 1e9 + 7;
	void fio()
	{
		ios::sync_with_stdio(0);
		cin.tie(0);
		cout.tie(0);
	}
	ll gcd(ll x, ll y)
	{
		if (y == 0)
			return x;
		else
			return gcd(y, x % y);
	}
	ll ksm(ll x, ll y)
	{
		ll ans = 1;
		while (y)
		{
			if (y & 1)
				ans = ans%mod*(x%mod)%mod;
			x = x%mod*(x%mod)%mod;
			y >>= 1;
		}
		return ans%mod%mod;
	}
	ll a[250000];
	int main()
	{
		ll t;
		cin>>t;
		while(t--)
		{
			ll n;
			cin>>n;
			//map<ll,ll>q;
			set<ll>f;
			for(ll i=1;i<=n;i++)
			{
				f.insert(i);
			}
			ll pd=0;
			for(ll i=1;i<=n;i++)
			{
				if(pd==0)
				{
					pd=*f.begin();
					a[i]=pd;	
					f.erase(pd);
				}
				else
				{
					while(pd<=n)
					{
						pd*=2;
						if(f.find(pd)!=f.end())
						{
						a[i]=pd;
						f.erase(pd);
						break;
						}
					}
					if(pd>n)
					{
						pd=*f.begin();
						a[i]=pd;
						f.erase(pd);
					}
				}
			}
			//cout<<f.size()<<endl;
			for(ll i=1;i<=n;i++)cout<<a[i]<<" ";
			cout<<endl;
		}
	}

D. Trees and Segments

首先发现如果要求出\(a⋅l0+l1\)的最大值，并不是\(l0\)越大越好。所以考虑前缀求出每个\(l0\)对应的每个\(l1\)最大值
由于不能\((n^3)\)，所以直接用前缀和后缀数组去维护从某个点（且有多少改变机会）出发后的最长冷杉长度。
于是最后暴力下\(l0\)对应的\(l1\)最大值，答案得解

	#include<iostream>
	#include<string.h>
	#include<map>
	#include<vector>
	#include<set>
	#include<unordered_set>
	#include<stack>
	#include<queue>
	#include<algorithm>
	#include<time.h>
	#include<random>
	#include<string>
	#include<string.h>
	#include<cctype>
	using namespace std;
	typedef int ll;
	mt19937 rnd(time(0));
	const ll mod = 1e9 + 7;
	void fio()
	{
		ios::sync_with_stdio(0);
		cin.tie(0);
		cout.tie(0);
	}
	ll gcd(ll x, ll y)
	{
		if (y == 0)
			return x;
		else
			return gcd(y, x % y);
	}
	ll ksm(ll x, ll y)
	{
		ll ans = 1;
		while (y)
		{
			if (y & 1)
				ans = ans%mod*(x%mod)%mod;
			x = x%mod*(x%mod)%mod;
			y >>= 1;
		}
		return ans%mod%mod;
	}
	ll a[3500];
	ll b[3005][3005];
	ll c[3005][3005];
	int main()
	{
		ll t;
		cin>>t;
		while(t--)
		{
		ll n,g;
		cin>>n>>g;
		string f;
		cin>>f;
		for(ll i=0;i<=n+1;i++)
		{
			for(ll k=0;k<=g+1;k++)
			{
				b[i][k]=0;
				c[i][k]=0;
			}
		}
		//cout<<99<<endl;
		for(ll i=0;i<=g;i++)
		{
			ll sz=0;
			deque<ll>q;
			for(ll j=0;j<n;j++)
			{
				if(q.empty())
				{
					q.push_back(j);
					if(f[j]=='0')sz++;
					while(sz>i)
					{
						if(f[q.front()]=='0')sz--;
						b[q.front()][i]=max(b[q.front()][i],(ll)q.size()-1);
						q.pop_front();
					}
				}
				else
				{
					q.push_back(j);
					if(f[j]=='0')sz++;
					while(sz>i)
					{
						if(f[q.front()]=='0')sz--;
						b[q.front()][i]=max(b[q.front()][i],(ll)q.size()-1);
						q.pop_front();
					}
				}
				if(!q.empty())
				b[q.front()][i]=max((ll)q.size(),b[q.front()][i]);
			}
			while(!q.empty())
			{
				b[q.front()][i]=max(b[q.front()][i],(ll)q.size());
				q.pop_front();
			}
			for(ll j=n-1;j>=0;j--)b[j][i]=max(b[j+1][i],b[j][i]);
		}
		for(ll i=0;i<=g;i++)
		{
			ll sz=0;
			deque<ll>q;
			for(ll j=n-1;j>=0;j--)
			{
				if(q.empty())
				{
					q.push_back(j);
					if(f[j]=='0')sz++;
					while(sz>i)
					{
						if(f[q.front()]=='0')sz--;
							c[q.front()][i]=max(c[q.front()][i],(ll)q.size()-1);
						q.pop_front();
					}
				}
				else
				{
					q.push_back(j);
					if(f[j]=='0')sz++;
					while(sz>i)
					{
						if(f[q.front()]=='0')sz--;
						c[q.front()][i]=max(c[q.front()][i],(ll)q.size()-1);
						q.pop_front();
					}
				}
				if(!q.empty())
				c[q.front()][i]=max((ll)q.size(),c[q.front()][i]);
			}
			while(!q.empty())
			{
				c[q.front()][i]=max(c[q.front()][i],(ll)q.size());
				q.pop_front();
			}
			for(ll j=1;j<=n-1;j++)c[j][i]=max(c[j-1][i],c[j][i]);
		}
		for(ll i=0;i<=n-1;i++)
		{
		for(ll j=g;j>=1;j--)
		{
			b[i][j]=max(b[i][j-1],b[i][j]);	
			c[i][j]=max(c[i][j],c[i][j-1]);
		}
		}
	//	cout<<b[0][0]<<endl;
	/*for(ll i=0;i<n;i++)
	{
		for(ll j=0;j<=g;j++)
		cout<<b[i][j]<<" "<<c[i][j]<<endl;
	}*/
       pair<ll,ll>ans[5000];
	   ll op=0;
	   op=1;
	   ans[op]={0,b[0][g]};
	   //cout<<99<<endl;
        for(ll i=1;i<=n;i++)
		{
			ll cnt=0;
			ll sz=0;
			ll u=0;
			ll pd=0;
			deque<ll>q;
			for(ll j=0;j<n;j++)
			{
				q.push_back(j);
				if(f[j]=='1')sz++;
				while(sz>g)
				{
					if(f[q.front()]=='1')sz--;
					q.pop_front();
				}
				while((ll)q.size()>i)
				{
					if(f[q.front()]=='1')sz--;
					q.pop_front();
				}
				if(q.size()==i)
				{
					pd=1;
					if(q.front()==0&&q.back()==n-1)
					u=max(u,0);
					else if(q.front()==0)
					u=max(u,b[q.back()+1][g-sz]);
					else if(q.back()==n-1)
					u=max(u,c[q.front()-1][g-sz]);
					else
					u=max({u,b[q.back()+1][g-sz],c[q.front()-1][g-sz]});
				}
			}
			if(pd)
			{
				op++;
				ans[op]={i,u};
			}
		}
		//cout<<55<<endl;
		for(ll i=1;i<=n;i++)
		{
			ll u=0;
			for(ll j=1;j<=op;j++)
			{
				ll x=ans[j].first;
				ll y=ans[j].second;
				u=max(u,i*x+y);
			}
			cout<<u<<" ";
		}
		cout<<endl;
		}
	}

标签：sz,893,题解,ll,Codeforces,ans,front,include,mod
From： https://www.cnblogs.com/cjcf/p/18473313

相关文章

  • [ABC134F] Permutation Oddness 题解
    [ABC134F]PermutationOddness题解朴素的想法显然是状压dp，枚举选择的子集，但复杂度不可接受。考虑优化。注意到对于\(p_i\)，它的贡献只会有两种可能性，\(+p_i,-p_i\)。于是初步的想法是按照\(p_i\)的正负性选择分类。考虑到对于相同正负性的选择\(p\)，其是等价的。于是我们......
  • P4229 某位歌姬的故事 题解
    P4229某位歌姬的故事题解\(n\le9\times10^8\)，显然复杂度不与\(n\)相关。\(m\le500\)，显然可以接受\(O(Tm^2)\)的做法。对于\([l,r]\)，考虑套路地将端点离散化，使得复杂度只和关键点个数有关。考虑对于\([l,r,m]\)，离散化后被分成了\(a_1,a_2,\cdots,a_p\)段，那么这些段的......
  • ZZJC新生训练赛第四场题解
    ZZJCACM新生训练赛-2024.10.16题目难度Easy(简单):B,C,D,GMedium(中等):A,EAnti-AK(防AK):EC题解题思路A页既可以是彩印也可以是黑白印，B页只能是彩印，所以只要比较A页彩印和A页黑白印的价格高低就好。因为a,b,x,y最大都是1e9，用int直接相乘的话会爆掉，所以......
  • DMA连续发送多帧但是只有最后一帧数据发出问题解决方法
    问题描述DMA连续发送多帧但是只有最后一帧数据发出原因分析DMA发送未完成时，下次DMA请求启动，导致之前的数据被放弃传输了解决办法创建DMA发送缓冲区，当启动DMA请求的时候，检测DMA设备是不是正在忙，如果正在忙，就把数据放入发送缓冲区等待，上次DMA发送完成的时会产生DMA发送完......
  • 【学校训练记录】10月个人训练赛3个人题解
    A：根据题意我们可知，第一种事件为从1到i的和，第二种事件为从y到i的和故我们可以通过前缀和来保存从i到i+1所化的时间。再遍历寻找最小值即可#include<bits/stdc++.h>#defineendl"\n"#defineintlonglongusingnamespacestd;intn,a[1010];voidsolve(){ cin>>n;......
  • 题解：GZOI2024 D2T2 乒乓球
    考场上切了，但是比较神奇的题，应该是蓝/紫。Discription乒乓球\(\text{}\)时间限制：\(\bold{3}\)秒众所周知，一场乒乓球比赛共有两个玩家\(A\)和\(B\)参与，其中一场比赛由多局比赛组成，而每局比赛中又由多盘比赛组成。每盘比赛\(A\)或\(B\)只有一名选手获胜。当其中一名......
  • Codeforces Round 924 (Div. 2) D. Lonely Mountain Dungeons（推式子，思维，差分，前缀和）
    题目链接CodeforcesRound924(Div.2)D.LonelyMountainDungeons思路令f(n,m......
  • [题解]P1311 [NOIP2011 提高组] 选择客栈
    P1311[NOIP2011提高组]选择客栈P6032选择客栈加强版只要\([l,r]\)区间之内存在一个\(i\)使得\(w[i]\lep\)，这个区间就是符合条件的。所以我们遍历每一个元素\(i\)，根据贪心的思想我们维护\([1,i]\)区间内满足\(w[i]\lep\)的最大\(i\)，记为\(mp\)。对于每个元素\(i\)，寻找\(......
  • Codeforces Beta Round 93 (Div. 1 Only) B. Password 一题三吃
    https://codeforces.com/problemset/problem/126/B学完Z函数，先用哈希做了一遍，再用Z函数做了一遍，然后搜其他人的题解发现用next数组也能做，就又做了一遍B.Password题意给一串字符串\(s\)，要求找一个最长的\(t\)\(t\)既是\(s\)的前缀串，也是后缀串，还是除了前缀后缀外的一个......
  • 【题解】twt studio2024 萌新欢乐赛
    迟来的题解本文更新到个人主页中，后续如果有任何修正变动也只会在网页端更新~特别鸣谢小羽毛在羽猫球一题的题解：)感谢兴航学弟在T3的题解。比赛链接：https://www.luogu.com.cn/contest/196515T1签到题，所有参与选手均满分。略。T2https://www.luogu.com.cn/article/37n1idam......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99