首页 > 其他分享 >2023牛客暑期多校训练营5

2023牛客暑期多校训练营5

时间:2023-08-02 18:27:41浏览次数:43  
标签:int rep 合并 多校 牛客 nex 2023 du define

之前落下的每一场比赛都是要补回来的。。。
G Go to Play Maimai DX
题解的想法比较简单,由于找到满足1,2,3出现至少一次,4出现至少k次的最短区间,所以可以双指针,双指针用于这种长度最短,长度越长越容易满足条件的题就很恰当。
我没想到双指针,就写的比较麻烦,预处理每个数后一个1,2,3的位置,以及4的特殊处理,每次枚举左端点,计算右端点即可。

点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define db double
#define endl '\n'
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int N=1e5+10;
int n,k,a[N],nex[N][5],pl[5],p[N],ct[N],tot; 

int main()
{
//	freopen("1.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k;
	rep(i,1,n) cin>>a[i];
	rep(i,1,3) pl[i]=n+1;
	fep(i,n,1)
	{
		rep(j,1,3) nex[i][j]=pl[j];
		pl[a[i]]=i;
		ct[i]=tot;
		if(a[i]==4)
		{
			p[++tot]=i;
			ct[i]=tot;
		}
	}
	int ans=n;
	rep(i,1,n)
	{
		int mx1=max(max(nex[i][1],nex[i][2]),nex[i][3]);
		if(mx1==n+1) continue;
		if(ct[i]<k) continue;
		mx1=max(mx1,p[ct[i]-k+1]);
		ans=min(ans,mx1-i+1); 
	}
	cout<<ans<<endl;
	return 0;
}

D Cirno's Perfect Equation Class
没啥难度,按照题意模拟,暴力枚举c的所有因子即可。

C Cheeeeen the Cute Cat
有意思的题目,题目让你明求最大匹配,那么说明正解要么和二分图没关系(大概率),要么就是二分图匹配算法上做一些优化。
其实题目已经提示的很明显了,当提到i和i+n无边,i和i+n,j和j+n之间只能存在一条边时,这就提示我们要将i和i+n合并看,而且题目规定边数为n*(n-1)/2,这个数字也很特殊,不就是完全图吗?合并的时候就有一个问题,考虑方向吗?这个时候我们就要观察二分图的匹配在合并时的特点,发现如果合并时按照无向边合并,则无法有效区分是i到j+n的连边还是j到i+n的连边,所以为了区分,按照有向的合并,i到j+n表示i到j有边,这个时候合并起来的图就是一个竞赛图,之后继续考虑匹配在合并后的图上的体现,简单手玩之后可以发现,一系列的匹配在合并后的图上体现为一些路径,也就是说我们要在新图上选择若干条互不相交的路径,这个时候就需要用到一些性质了。竞赛图必有哈密顿路径,所以答案至少为n-1,接下来只需要考虑答案什么时候是n,即存在哈密顿回路。对于有向图的一个点数大于等于3的强连通分量,肯定存在哈密顿环,(图中不存在强连通分量个数为2的)。即只需要判掉个数为1的强连通分量即可。

点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define db double
#define endl '\n'
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define fep(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int N=3010;
int n,du[N];

inline bool check()
{
	rep(i,1,n) rep(j,1,n)
	{
		if(i!=j&&du[i]+du[j]<n) return false;	
	} 
	return true;
}

int main()
{
//	freopen("1.in","r",stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	rep(i,1,n) rep(j,1,n)
	{
		int x;cin>>x;
		du[i]+=x;
	}
	sort(du+1,du+n+1);
	int j=0,s=0;
	rep(i,1,n)
	{
		s+=du[i];
		if(s==i*(i-1)/2)
		{
			if(i-j<3) 
			{
				cout<<n-1<<endl;
				return 0;
			}
			j=i;
		}
	}
	cout<<n<<endl;
	
	return 0;
}

标签:int,rep,合并,多校,牛客,nex,2023,du,define
From: https://www.cnblogs.com/gcfer/p/17600912.html

相关文章

  • 2023/08/02
    大家应该都会玩“锤子剪刀布”的游戏:两人同时给出手势,胜负规则如图所示:现要求你编写一个稳赢不输的程序,根据对方的出招,给出对应的赢招。但是!为了不让对方输得太惨,你需要每隔K次就让一个平局。输入格式:输入首先在第一行给出正整数K(≤10),即平局间隔的次数。随后每行给出对方......
  • 喜讯! WorkPlus入选中国信通院数字产品“2023全景图”!
    “2023数字生态发展大会”暨中国信通院“铸基计划”WorkPlus喜讯7月27日,中国信息通信研究院(下称“中国信通院”)主办的“2023数字生态发展大会”暨中国信通院“铸基计划”年中会议在京召开,大会全面地总结了“铸基计划”上半年度工作成果,帮助行业解析数字化转型发展趋势,以期推动我国......
  • 2023年DevOps和云趋势报告!
    要点●云创新已从革命性阶段转变为演进性阶段,重点是迁移和重新架构工作负载。云空间已发展为提供对可扩展资源和托管服务的按需访问,强调简化交互并减少团队的认知负担。●人工智能(AI)和大型语言模型(LLM)可以通过解决认知过载问题并支持即时管理、票务系统和代码生成等任务,在......
  • 2023年湖南省对口高考真题
    一、选择题1、下列关于算法的描述中,错误的是__________。A.算法可以用伪代码、流程图等多种形式描述B.一个正确的算法必须有输入C.一个正确的算法必须有输出D.能用流程图描述的算法,也可用计算机高级语言描述2、如用"scanf("%c%c",&c1,&c2)",为字符变量c1和c2分别赋值字符'A'和'B',正......
  • 【专题】2023全球智能家居市场报告PDF合集分享(附原数据表)
    全文链接:https://tecdat.cn/?p=33358智能家居行业目前已经基本实现了家用物联网的建设。为了满足用户个性化和弹性化的需求,智能家居3.0阶段着重于将云计算、边缘计算和人工智能等支持技术深化应用于智能家居产品中。阅读原文,获取专题报告合集全文,解锁文末74份智能家居行业相关报......
  • 2023年Java学习路线,史上最全Java学习路线-文中有送书福利
    小伙伴们大家好,这里是动力节点,我们从2009年开始一直在从事Java培训到今年已经整14年了,虽然现在不缺培训机构,更不缺Java培训,但是像我们这么多年专注这一件事的应该也不多。我们只希望在“专业”两个字上面不断精进,给每一位想学Java的同学带来更好的资源和学习规划。我们深知,有很多同......
  • 2023年多校联训NOIP层测试2
    2023年多校联训NOIP层测试2爆零了T1HDU4786FibonacciTree\(0pts\)@wangyunbiao:不可以,总司令我:不,可以,总司令T2期末考试\(0pts\)T3麻烦的工作\(0pts\)@wangyunbiao:不可以,总司令我:不,可以,总司令T4小X的Galgame\(0pts\)......
  • 【题解】HDOJ 7329 [2023杭电多校] Touhou Red Red Blue
    题目传送门:HDOJ7329[2023杭电多校]TouhouRedRedBlue题意有两个口袋(口袋容量为1,初始均为空),有若干个UFO按顺序来到你的面前,每个UFO有一个颜色(GRB),你可以选择扔掉它或者把它装进口袋中,如果口袋1空着必须装进口袋1;如果口袋都满了,算上面前的UFO共有三个,有如下三种情况:如......
  • NOI2023 打金记
    扔到cnblogs上。##Day-4最后一场模拟赛,肯定要用力打啊!然而一题不会,呜呜呜。于是开始拼暴力,写了$90+60+60=210$,结果挂成$40+60+60=160$。T1我将题目转化为:对于一个排列,每次只改动三个位置,要求某个数的出现位置,我用了fhq-treap!维护一个桶就好了,不知道自己......
  • Pycharm激活码2023年,Pycharm稳定专属激活码(持续更新)
    Windows上的安装步骤:步骤1:下载PyCharm访问JetBrains官网(https://www.jetbrains.com/pycharm/)下载PyCharm。网页上会提供Community版和Professional版的下载链接,根据您的需要选择合适的版本。步骤2:运行安装程序下载完成后,找到下载的安装程序(通常是一个.exe文件),双击......