首页 > 其他分享 >CSP模拟6

CSP模拟6

时间：2024-09-29 20:46:15浏览次数：8  
标签：nxt ch int vis while CSP 模拟 getchar

T1一般图最小匹配

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=5000+107;
int n,m,a[N];

int read()
{
	int f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
	return f*s;
}

int f[N][N];

signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	sort(a+1,a+1+n);
	memset(f,0x3f,sizeof f);
	f[0][0]=0;
	f[1][0]=0;
	for(int i=2;i<=n;i++)
	{
		f[i][0]=f[i-1][0];
		for(int j=1;j<=m;j++)
		{
			f[i][j]=min(f[i-1][j],f[i-2][j-1]+a[i]-a[i-1]);
		}
	}
	
	printf("%lld",f[n][m]);
}

T2重定向

无任何算法，我们直接考虑即可，那我们先想，自然是把所有的空位按递增序列填就行，我们用一个 \(set\) 来维护，那我们考虑什么用删除，这删除肯定是越早用越好。

如果我们遍历到的数是 \(0\) ，我们直接比较它要被填上的数和它后面最小的数，如果后面的数更优，直接删掉，在加到 \(set\) 里面，否则直接为它附上值。

如果遍历到的数非零且后一个数也非零，我们直接比较判断即可。如果后一个数为 \(0\) ,我们比较那一位要填上的数和现在的数即可。

额，好像就没了……

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

const int N=4e5+107;
int n,a[N];
int nxt[N];
bool vis[N];
set<int>s;

int read()
{
	int f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
	return f*s;
}



int main()
{
	freopen("repeat.in","r",stdin);
	freopen("repeat.out","w",stdout);
	int T=read();
	while(T--)
	{
		s.clear();
		memset(vis,0,sizeof vis);
		memset(nxt,0x3f,sizeof nxt);
		n=read();
		for(int i=1;i<=n;i++) a[i]=read(),vis[a[i]]=1;
		for(int i=1;i<=n;i++) if(!vis[i]) s.insert(i);
		for(int i=n;i>=1;i--)
		{
			if(a[i+1]!=0) nxt[i]=min(nxt[i+1],a[i+1]);
			else nxt[i]=nxt[i+1];
		}
		
		int cnt=1,pos=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]==0)
			{
				if(*s.begin()>nxt[i])
				{
					pos=nxt[i];
					s.insert(nxt[i]);
					cnt--;
					break;
				}
			}
			else
			{
				if(a[i+1]==0&&*s.begin()<a[i])
				{
					pos=a[i],cnt--;
					s.insert(a[i]);
					break;
				}
				if(a[i+1]!=0&&a[i+1]<a[i])
				{
					pos=a[i],cnt--;
					s.insert(a[i]);
					break;
				}
			}
			if(a[i]==0) a[i]=*s.begin(),s.erase(*s.begin());
		}
		if(cnt) pos=a[n];
		
		for(int i=1;i<=n;i++)
		{
			if(a[i]==pos) continue;
			if(a[i]!=0) printf("%d ",a[i]);
			if(a[i]==0) 
			{
				printf("%d ",*s.begin());
				s.erase(*s.begin());
			}
		}
		printf("\n");
	}
}

T3 斯坦纳树

我们每经过一条路径，我们就把每个点标记上，在拓展一个新点的时候，我们直接让它往它和上一个节点的 \(lca\) 上跳，跳到第一个被标记且之前没有拓展过，我们把它存到 \(set\) 里，每拓展一个新数，如果 \(set\) 里面有对应的值，把它删掉，至于边权为 \(0\) ，我们直接合并成一个点。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+107;
int n,p[N];
int bel[N];
int read()
{
	int f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
	return f*s;
}

int h[N<<1],to[N<<1],nxt[N<<1],tot;
void add(int x,int y)
{
	to[++tot]=y;
	nxt[tot]=h[x];
	h[x]=tot;
}

int f[N][40],dep[N];
void dfs(int u,int fa)
{
	f[u][0]=fa,dep[u]=dep[fa]+1;
	for(int i=1;i<=30;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		dfs(v,u);
	}
}

int get_lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=30;i>=0;i--)
	{
		if(dep[f[x][i]]>=dep[y])
		{
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=30;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

set<int> s;
bool vis[N];
int flag[N];
void label(int x,int lca)
{
	if(vis[x]) return ;
	if(x==lca) return ;
	while(1)
	{
		vis[x]=1;
		x=f[x][0];
		if(x==lca) 
		{
			if(vis[x]&&!flag[x]) s.insert(x);
			else vis[x]=1;
			break;
		}
		if(vis[x]) 
		{
			if(!flag[x]) s.insert(x);
			break;
		}
	}
}

struct lmy
{
	int x,y,w;
}e[N];
bool comp(lmy a,lmy b)
{
	if(a.w==b.w) return a.x<b.x;
	return a.w<b.w;
}

int find(int x)
{
	return bel[x]==x?x:bel[x]=find(bel[x]);
}

signed main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n=read();
	for(int i=1;i<=n*2;i++) bel[i]=i;
	for(int i=1;i<n;i++) 
	{
		int x=read(),y=read(),w=read();
		if(y<x) swap(x,y);
		e[i]={x,y,w};
	}
	sort(e+1,e+1+n-1,comp);
	
	for(int i=1;i<n;i++)
	{
		if(e[i].w==0) 
		{
			int x=e[i].x,y=e[i].y;
			if(bel[x]==x&&bel[y]==y) bel[x]=n+i,bel[y]=n+i;
			else if(bel[x]!=x) bel[find(bel[y])]=find(bel[x]);
			else if(bel[y]!=y) bel[find(bel[x])]=find(bel[y]);
		}
		else break;
	}
	for(int i=1;i<=n*2;i++) bel[i]=find(bel[i]);
	for(int i=1;i<n;i++)
	{
		if(e[i].w==0) continue;
		add(bel[e[i].x],bel[e[i].y]);
		add(bel[e[i].y],bel[e[i].x]);
	}
	
	for(int i=1;i<=n;i++) p[i]=read();
	
	dfs(bel[p[1]],bel[p[1]]);
	flag[bel[p[1]]]=1;
	printf("1");
	
	for(int i=2;i<=n;i++)
	{
		s.erase(bel[p[i]]);
		int lca=get_lca(bel[p[i]],bel[p[i-1]]);
		flag[bel[p[i]]]=1;
		if(i==2) label(bel[p[i-1]],lca);
		label(bel[p[i]],lca);
		if(!s.empty()) printf("0");
		else printf("1");
	}
}

标签：nxt,ch,int,vis,while,CSP,模拟,getchar
From： https://www.cnblogs.com/zhengchenxi/p/18440667

相关文章

  • NOIP 模拟赛小丑记录
    太小丑了。\(8.17\)排名：1/23小周模拟赛，\(\rmT4\)乱写了一个东西过了，赛后发现好像正确性是对的，但是复杂度有点寄。估分：\(100+100+100+?=300+?\)。实际得分：\(100+100+100+100=400\)。\(8.24\)排名：8/25紊莫模拟赛，赛时四个题都会做，但是\(\rmT4\)没写完，只写了前三个，还挂了......
  • CSP-J历年真题（部分）解析与题解
    目录序言：[CSP-J2020]直播获奖前言：题目描述输入格式输出格式输入输出样例说明/提示样例1解释数据规模与约定提示65分思路及代码前言：思路：代码：85分代码及思路：前言：插入排序：思路：代码： AC思路及代码：前言：思路：   代码： [CSP-J2022]乘方前言：题目描......
  • CSP模拟5
    T1光我们来考虑一个格加\(4\)或者减\(4\),这样有一个比较好的性质，它能提供\(4,2,2,1\)的贡献还不会溢出，这样我们就有一个比较好的思路，我们枚举\(4,2,2,1\)所无法造成的贡献，很明显只有\(16\)种，然后我们就可以再枚举\(4,2,2,1\)来算贡献.点击查看代码#include<bits/......
  • CSP 模拟 36
    A一般图最小匹配首先排完序后肯定选连续两个。直接DP，\(f_{i,j}\)就是表面意思，\(f_{i,j}=min(f_{i-1,j},f_{i-2,j-1}+a_i-a_i-2)\)。差分后发现问题转化成了选择的数不能相邻，这时候也可以直接考虑DP，但是这是一个经典的反悔贪心。记下\(pre\)和\(nex\)，直接扔到堆里，选择一......
  • C++学习：stack queue模拟
    stack和queue可以复用其他容器的函数如dequevector这两个是空间适配器，所以都没有迭代器一：stack模拟namespacebit{ template<classT,classContainer=deque<T>> classstack { public: voidpush(constT&x) { _con.push_back(x); } voidpop() ......
  • 「CSP-J」做题记录
    「CSP-J」做题记录记号：A：自己做出来的。B：看题解提示做出来的。C：对着题解做出来的。[CSP-J2019江西]道路拆除（A）我们可以把问题转化一下：求出最少要留下多少边，使得从首都出发，能到达\(s_1\)号与\(s_2\)号城市，且所要花费的最短时间分别不超过\(t_1\)与\(t_2\)。最终答......
  • 「CSP-S」 做题记录
    「CSP-S」做题记录[CSP-S2019江西]多叉堆自己做出来了，开心捏。先考虑对于一棵特定的树，如何计算答案（对应特殊性质1）。首先，根节点一定只能填\(0\)。其次，可以发现各个子树不会互相影响，所以可以分别考虑如何填各个子树。设填满以节点\(u\)为根的子树的方案数为\(f(u)\)，\(......
  • NOIP2024模拟赛9 赛后总结
    前言听说把枕头哭湿，晚上可以梦见大海先说明一下情况。我\(\text{T2}\)，同样的数据，本地\(\text{500ms}\to\)\(\text{sxyz:}1.7\texttt{s}\)。\(\text{T3},\text{CF3s}\)的时限，什么烂机子开\(\text{1s}\)。我们都有光明的未来。我尽量克制住自己的情绪。B/ABC176F......
  • NOIP 模拟赛：2024-9-28
    打的挺好，好在最后40min想起来给B对拍一下捡回来\(100\)pts。T1观察到若每个间隔\(0\)的个数为\(i\)，则\(1\)的个数\(\le\dfrac{n}{i}\)，这启示我们枚举\(0\)的个数，然后快速找到下一个\(1\)的位置。记录\(0\)的前缀个数+二分可以做到\(O(n\log^2n)\)。另外，如......
  • csp-s模拟6
    A.一般图最小匹配\(m\)小于\(\frac{n}{2}\)所以对原数组排序后做差分，差分后的数不能选相邻的，设\(f_{i,j,0/1}\)表示前\(i\)个，选了\(j\)个，第\(i\)个选没选直接\(dp\)求最小值就行点击查看代码#include<bits/stdc++.h>constintmaxn=5001;usingnamespacestd......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99