首页 > 其他分享 >2024.9.28 模拟赛 CSP6

2024.9.28 模拟赛 CSP6

时间：2024-10-10 16:48:39浏览次数：1  
标签：连通 const CSP6 2024.9 28 long int dfn freopen

模拟赛

单 \(log\) 双 \(log\) 不如三 \(log\)。

T1 一般图最小匹配

简单 dp，水。\(O(n^2)\)

其实也是可反悔贪心的板子，可以 \(O(n\log(n))\) 做。

考虑排序后求差分数组，就变成不能选相邻的。然后就是可反悔贪心板子。

用双向链表（记录前驱后继）维护，然后放进堆里。

板

dp 
#include<bits/stdc++.h>
using namespace std;
#define ab(x) ((x>=0)?(x):(-x))
#define mi(x,y) ((x>y)?(y):(x))
#define LL long long
const int N = 5005;
int n,m;
LL f[2][N][2],a[N];

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	memset(f,0x3f,sizeof(f));
	f[0][1][1]=ab(a[2]-a[1]); f[0][0][0]=0;
	for(int i=3;i<=n;i++)
	{
		f[i&1][0][0]=0;
		for(int j=1;j<=i>>1;j++)
		{
			f[i&1][j][1]=f[(i-1)&1][j-1][0]+ab(a[i]-a[i-1]);
			f[i&1][j][0]=mi(f[(i-1)&1][j][0],f[(i-1)&1][j][1]);
		}
	}
	printf("%lld\n",mi(f[n&1][m][0],f[n&1][m][1]));
	return 0;
}
贪心 
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+5;
int n,m,pre[N],nxt[N];
long long ans,b[N],a[N];
struct A
{
	int id; long long d;
	bool operator < (const A &x) const
	{
		return d>x.d;
	}
};
bool vs[N];
priority_queue<A> q;
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	for(int i=1;i<n;i++) b[i]=a[i+1]-a[i],q.push({i,b[i]}),pre[i]=i-1,nxt[i]=i+1;
	b[0]=b[n]=1e9;
	while(m)
	{
		while(vs[q.top().id]) q.pop();
		int u=q.top().id; long long d=q.top().d; q.pop();
		m--; vs[pre[u]]=vs[nxt[u]]=1; b[u]=b[pre[u]]+b[nxt[u]]-b[u];
		q.push({u,b[u]});
		pre[u]=pre[pre[u]],nxt[u]=nxt[nxt[u]],nxt[pre[u]]=u,pre[nxt[u]]=u;
		ans+=d;
	}
	printf("%lld\n",ans);
	return 0;
}

T2 重定向

大力分讨，不停贪心。

细节处理挂 \(30 pts\)。

code 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,T;
int l,cnt,ans[N],a[N],tot;
bool vs[N];

int main()
{
	freopen("repeat.in","r",stdin);
	freopen("repeat.out","w",stdout);
	scanf("%d",&T);
	while(T--)
	{
		cnt=tot=0;
		set<int> h,p;
		memset(vs,0,sizeof(vs));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]); vs[a[i]]=1; 
			if(a[i]!=0) h.insert(a[i]);
		}
		p.insert(100000000);
		for(int i=1;i<=n;i++) if(!vs[i]) p.insert(i);
		bool fl=0; int _1=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]!=0&&a[i]==_1) continue;
			if(a[i]!=0) h.erase(a[i]);
			
			if(i+1<=n&&fl==0)
			{
				if(a[i]==0)
				{
					if(a[i+1]!=0)
					{
						if(!_1&&!h.empty()&&(*h.begin()<a[i+1])&&(*h.begin()<*p.begin()))
						{
							_1=(*h.begin());
							ans[++tot]=_1;
							fl=1; continue;
						}	
						else if(a[i+1]<*p.begin())
						{
							fl=1; continue;
						}					
						else
						{
							ans[++tot]=*p.begin(); p.erase(p.begin()); continue;
						}
					}
					else 
					{
						if(!_1&&!h.empty()&&*p.begin()>*h.begin())
						{
							_1=(*h.begin());
							ans[++tot]=_1;
							fl=1; continue;							
						}
						else
						{
							ans[++tot]=*p.begin(); p.erase(p.begin()); continue;
						}
					}
				}
				else
				{
					if(a[i+1]!=0&&a[i+1]<a[i]) 
					{
						p.insert(a[i]);
						fl=1; continue;
					}
					else if(a[i+1]==0&&*p.begin()<a[i])
					{
						p.insert(a[i]);
						fl=1; continue;
					}
					else
					{
						ans[++tot]=a[i]; continue;
					}			
				}
			}
			else if(fl==0)
			{
				continue;
			}
			else
			{
				if(a[i]==0) ans[++tot]=*p.begin(), p.erase(p.begin());
				else ans[++tot]=a[i];
			}
		}
		for(int i=1;i<=tot;i++) printf("%d ",ans[i]); putchar('\n');
	}
	return 0;
}

T3 斯坦纳树

转化题意，发现如果有重边那就是不合法的，考虑什么时候会有重边。

加入的点会形成一个最小连通块，这就是我们要判断的区域。

我们可以将所有点分成三类：

  1. 已经加入的。

  2. 未被加入但在连通块中的。

  3. 不在连通块中的。

考虑一个不在连通块中的点想接入连通块，那么一定会与连通块有一个交点。

假如上图中三号点想加入连通块，那么这个交点就是二号点。

如果二号点已经被加入的话，那么三号点不会造成影响，否则一定会有重边。

所以我们就是想找到这个交点并判断它是否加入。

赛时唐氏做法，线段树维护并查集，每次区间推平维护连通块，单点查询是否是交点，是否选过。

好处就是信息全在线段树里，复杂度能多一个 \(log\) 和大常熟。

最后 \(O(qlog^3(n))\) 的复杂度（很松很松）过了（\(O(qlog(n))\) 和 \(O(qlog^2(n))\) 没过）。

code 
#include<bits/stdc++.h>
using namespace std;
const int N =3e5+5;
int n,a[N];
int head[N],tot,xx[N],yy[N],zz[N];
struct E {int u,v,w;} e[N<<1];
inline void add(int u,int v,int w) {e[++tot]={head[u],v,w}; head[u]=tot;}
bool fl=1;
int b[N];
inline int find(int x) {return x==b[x]?(x):(b[x]=find(b[x]));}
int sz[N],fa[N][30],dis[N],son[N],dfn[N],dep[N],rk[N],top[N],cnt;

void dfs1(int u,int f)
{
	sz[u]=1; fa[u][0]=f; son[u]=-1; dep[u]=dep[f]+1;
	for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].u)
	{
		int v=e[i].v; if(v==f) continue; dis[v]=dis[u]+e[i].w;
		dfs1(v,u); sz[u]+=sz[v];
		if(son[u]==-1||sz[son[u]]<sz[v]) son[u]=v;
	}
}
void dfs2(int u,int t)
{
	top[u]=t; dfn[u]=++cnt; rk[cnt]=u;
	// printf("%d %d\n",u,dfn[u]);
	if(son[u]==-1) return ;
	dfs2(son[u],t);
	for(int i=head[u];i;i=e[i].u)
	{
		int v=e[i].v; if(v==fa[u][0]||v==son[u]) continue;
		dfs2(v,v);
	}
}
namespace SEG
{
	struct T
	{
		int l,r,cnt; bool xu,yo,za,lz;
	} tr[N<<2];
	inline void pushup(int k) {tr[k].cnt=tr[k<<1].cnt+tr[k<<1|1].cnt;}
	inline void pushdown(int k)
	{
		if(tr[k].lz)
		{
			tr[k].lz=0;
			tr[k<<1].lz=1; tr[k<<1].za=1;
			tr[k<<1|1].lz=1; tr[k<<1|1].za=1;
		}
	}
	void bui(int k,int l,int r)
	{
		
		tr[k].l=l; tr[k].r=r;
		if(l>=r) return ; 
		int mid=l+r>>1;
		bui(k<<1,l,mid); bui(k<<1|1,mid+1,r);
	}
	void mdf(int k,int p,int tp)
	{
		if(tr[k].l==tr[k].r)
		{
			if(tp==0)//yo
			{
				if(!tr[k].yo)
				{
					tr[k].cnt-=tr[k].xu; tr[k].yo=1;
				} 				
			}
			else//xu
			{
				if(!tr[k].xu&&!tr[k].yo)
				{
					tr[k].cnt++; tr[k].xu=1;
					// printf("*****\n");
				} 					
			}
			return;
		}
		pushdown(k);
		int mid=tr[k].l+tr[k].r>>1;
		if(p<=mid) mdf(k<<1,p,tp);
		else mdf(k<<1|1,p,tp);
		pushup(k);
	}
	void qmdf(int k,int L,int R)
	{
		if(tr[k].l>=L&&tr[k].r<=R)
		{
			tr[k].za=1; tr[k].lz=1; return;
		}
		pushdown(k);
		int mid=tr[k].l+tr[k].r>>1;
		if(L<=mid) qmdf(k<<1,L,R);
		if(R>mid) qmdf(k<<1|1,L,R);
		pushup(k);
	}
	bool que(int k,int p)
	{
		if(tr[k].l==tr[k].r) return tr[k].za;
		pushdown(k);
		int mid=tr[k].l+tr[k].r>>1;
		if(p<=mid) return que(k<<1,p);
		else return que(k<<1|1,p);
	}
} using namespace SEG;

void mdfpath(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		qmdf(1,dfn[top[x]],dfn[x]);
		x=fa[top[x]][0];
		
	}
	if(dfn[x]>dfn[y]) swap(x,y);
	qmdf(1,dfn[x],dfn[y]);
	return;
}

void change(int x)
{
	int tmp=x;
	mdf(1,dfn[x],0);
	if(que(1,dfn[x])) return;
	for(int i=20;i>=0;i--)
	{
		if(!fa[x][i]) continue;
		if(que(1,dfn[fa[x][i]])) continue;
		else x=fa[x][i];
	}
	mdf(1,dfn[fa[x][0]],1);
	mdfpath(fa[x][0],tmp);
}

int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) b[i]=i;
	for(int i=1;i<n;i++)
	{
		int x,y,z; scanf("%d%d%d",&x,&y,&z);
		x=find(x); y=find(y);
		if(z==0) b[x]=y; 
		xx[i]=x; yy[i]=y; zz[i]=z;
	}
	for(int i=1;i<n;i++)
	{
		if(zz[i]!=0) 
		{
			int x=find(xx[i]),y=find(yy[i]);
			add(x,y,zz[i]); add(y,x,zz[i]);
		}
	}
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs1(find(a[1]),0);
	dfs2(find(a[1]),find(a[1]));
	bui(1,1,n);
	int v=dfn[find(a[1])];
	mdf(1,v,0); 
	qmdf(1,v,v); 
	printf("1");
	for(int i=2;i<=n;i++)
	{
		v=find(a[i]); 
		change(v);
		if(tr[1].cnt==0) printf("1");
		else printf("0");
	}
	return 0;
}

T4 直径

咕咕咕

标签：连通,const,CSP6,2024.9,28,long,int,dfn,freopen
From： https://www.cnblogs.com/ppllxx-9G/p/18448826

相关文章

  • 【刷题笔记】[ABC281G] Farthest City
    【刷题笔记】[ABC281G]FarthestCity题意求构造一个没有重边和自环【简单联通】的无向连通图，使得\(d[n]\)严格大于\(d[i]\)，问有几种构造方案思路一道\(DP\)好题\(DP\)有\(2\)种题型，求最优值问题，和计数问题。本题为计数问题。因为在边权为1的最短路中\[d[i]=d[i-1]+1\]所......
  • 28. 找出字符串中第一个匹配项的下标 Golang实现
    题目描述：给你两个字符串haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从0开始）。如果needle不是haystack的一部分，则返回-1。示例1：输入：haystack="sadbutsad",needle="sad"输出：0解释："sad"在下标0和6处匹配。......
  • AT_abc283_g [ABC283G] Partial Xor Enumeration 题解
    题目传送门前置知识线性基解法考虑线性基。因为有可空子序列也参与运算，所以第\(1\)小的数是\(0\)；但线性基中是不允许有异或和为\(0\)的存在，故线性空间内第\(k-1\)小的数就是所求的第\(k\)小的数。令每一个二进制位仅在它这一位的基底上出现，其他位上的基底直接异或......
  • 游戏革命！Series AI获2800万美元融资，携手Netflix、戴尔打造GenAI游戏开发平台
     一句话定位Series是一家通过生成式AI技术，为游戏开发者提供全栈游戏创作平台的公司，致力于革新未来的游戏开发模式。一、数据概览成立时间：2023年种子轮融资：790万美元，由a16z领投A轮融资：2800万美元，投资方包括Netflix、DellTechnologiesCapital、a16z、BITKRAFT和F4Fu......
  • 2024-9-28
    新闻周刊2024.9.28导入:建立"定点医药机构相干人员"实行驾照式经分传统监管机构将从医药机构进一步精确到人的进步,让少部分违规人员收到更加严厉的处罚防止医保滥用,让违规者付出应有代价,确保医保资金真正惠民,让所有人都共同收益.视点:秋收"惠农"时农条机械化农......
  • 2024.9.27 模拟赛 CSP5
    模拟赛无T1光题贪心，发现首先让最大的减\(4\)，这样最优并且不会涉及向下取整，等到数据范围小了以后直接\(O(n^4)\)暴力枚举。code#include<bits/stdc++.h>usingnamespacestd;inta,b,c,d;intans=1e9;#definemx(x,y)(x>y?(x):(y))#definemi(x,y)(x<y?(x):(y......
  • SSM湘农乐市农产品交易平台-计算机毕业设计源码28246
    目 录SSM湘农乐市农产品交易平台1绪论1.1研究背景1.2研究意义1.3研究方法1.4论文结构与章节安排2 湘农乐市农产品交易平台系统分析2.1可行性分析2.2系统流程分析2.3 系统功能分析2.4 系统用例分析2.5本章小结3湘农乐市农产品交易平台总体设......
  • LED显示驱动/高亮数显屏驱动芯片VK16K33A 采用SOP28封装形式，可支持16SEGx8GRID的点阵L
    VK16K33A是一种带按键扫描接口的数码管或点阵LED驱动控制专用芯片，邱婷：188-2366-8825内部集成有数据锁存器、键盘扫描、LED驱动模块等电路。数据通过I2C通讯接口与MCU通信。SEG脚接LED阳极，GRID脚接LED阴极，可支持16SEGx8GRID的点阵LED显示面板。最大支持13×3的按键。内置上电......
  • 2018_10_28_01
    动态替换图片最简单的示例<divclass="img-wrapper"><divonclick='replacement'><imgsrc='[图片1]'></div><!-----------------><!--忽略同类型代码.--><!----------------->......
  • 代码随想录算法训练营day9|●151.翻转字符串里的单词 ●卡码网：55.右旋转字符串 ●28.
    学习资料：https://programmercarl.com/0151.翻转字符串里的单词.html学习记录：151.翻转字符串里的单词（感觉C语言能考虑巧妙解法，而python直接搞就对了）c语言：把字符串整体反转，再用双指针法（slow,fast）依次翻转每一个单词，关键在于如何移除多余空格，用slow指针找到要替换到的位置，用fast......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99