首页 > 其他分享 >csp-s模拟6

csp-s模拟6

时间：2024-09-29 11:26:54浏览次数：1  
标签：cnt int sum break ++ maxn csp 模拟

A. 一般图最小匹配

\(m\) 小于 \(\frac{n}{2}\) 所以对原数组排序后做差分，差分后的数不能选相邻的，设 \(f_{i,j,0/1}\) 表示前 \(i\) 个，选了 \(j\) 个，第 \(i\) 个选没选

直接 \(dp\) 求最小值就行

点击查看代码 
#include<bits/stdc++.h>
const int maxn=5001;
using namespace std;
int n,m,a[maxn],d[maxn];
long long f[maxn][2501][2];

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+1+n);n--;
	for(int i=1;i<=n;i++)
		d[i]=a[i+1]-a[i];
		
	for(int i=0;i<=n;i++) 
		for(int j=0;j<=m;j++) 
			f[i][j][0]=f[i][j][1]=1e15;
			
	f[1][1][1]=d[1],f[1][0][0]=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0],f[i-1][j][1]));
			if(j!=0)f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]+d[i]);
//			cout<<i<<" "<<j<<" "<<f[i][j][1]<<" "<<f[i][j][0]<<endl;
		}
	}
	cout<<min(f[n][m][0],f[n][m][1]);

	return 0;
}
/*
4 1
2 4 7 3

8 3
9 2 3 12 11 7 6 5
*/

B. 重定向

大型分讨，我思路是考虑 \(1\) 和第一个 \(0\)，然后再向下细分是否考虑第一个使字典序变小的数，细节很多，5.8k代码，不建议观看

点击查看代码 
#include<bits/stdc++.h>
#define int long long
const int maxn=1e6+10;
using namespace std;
int t,n,a[maxn],d[maxn],cnt,tem[maxn];
bool vis[maxn];

signed main()
{
//	freopen("test.in","r",stdin);
//	freopen("ans.out","w",stdout);
	freopen("repeat.in","r",stdin);
	freopen("repeat.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--)
	{
		int flag=0,flag2=0;
		cin>>n;
		fill(vis,vis+1+n,0);
		fill(d,d+1+n,0);
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			if(a[i]==0) flag2=1;
			vis[a[i]]=1;
			if(a[i]==1) flag=1;
		} 
		if(!flag2)
		{
			for(int i=1;i<=n;i++)
			{
				if(a[i]>a[i+1])
				{
					a[i]=0;
					flag2=1;
					break;
				}
			}
			for(int i=1;i<=n-(flag2==0);i++)
				if(a[i]) cout<<a[i]<<" ";
			cout<<'\n';
			continue;
		}
		cnt=0;
		for(int i=1;i<=n;i++) if(!vis[i]) d[++cnt]=i;
		if(flag)
		{
//			cout<<"!";
			for(int i=1;i<=n;i++)
			{
				if(a[i]==1)
				{
					flag=0;
					break;
				}
				if(a[i]==0)break;
			}
			if(flag)
			{
				for(int i=1;a[i]!=0;i++)
				{
					if(a[i]>d[1]||(a[i]>a[i+1]&&a[i+1])) 
					{
						flag=0;
						break;
					}
				}
				if(flag)
				{
//					cout<<"!";
					cnt=-1;
					for(int i=1;i<=n;i++) if(a[i]==1) a[i]=-1;
					d[0]=1;
					for(int i=1;i<=n;i++)
					{
						if(a[i]==0) a[i]=d[++cnt];
					}
					for(int i=1;i<=n;i++)
					{
						if(a[i]!=-1) cout<<a[i]<<" ";
					}
					cout<<'\n';	
				}
				else
				{
//					cout<<"!";
					int temp=0;
					for(int i=1;a[i]!=0;i++)
					{
						if(a[i]>d[1]&&a[i]>d[0]||(a[i]>a[i+1]&&a[i+1]))
						{
//							d[0]=a[i];
							tem[++temp]=i;
//							break;
						}
					}
//					cout<<temp<<endl;
					if(!temp)
					{
						int s=0;
						for(int i=1;i<=n;i++)
							if(!a[i]) a[i]=-d[++s];
						for(int i=1;i<n;i++) 
							if(abs(a[i])>abs(a[i+1]))
							{
								d[0]=abs(a[i]);
								a[i]=0;
								sort(d,d+1+cnt);
								break;
							}
						int num=unique(d,d+1+cnt)-d-1;
						cnt=num;
						cnt=-1;
						if(!d[0])cnt++,a[n]=0;
						for(int i=1;i<=n;i++)
							if(a[i]<0) a[i]=d[++cnt];
						for(int i=1;i<=n;i++)
						{
							if(a[i])cout<<a[i]<<" ";
						}
						cout<<'\n';
					}
					else
					{
						for(int i=1;i<=temp;i++)
							if(a[tem[i]]>a[tem[i]+1])
							{
//								cout<<tem[i]<<" "<<tem[i]+1<<endl;
								temp=tem[i];
								d[0]=a[tem[i]];
								break;
							}
						a[temp]=-1;
						sort(d,d+1+cnt);
						int num=unique(d,d+1+cnt)-d-1;
						cnt=num;
						cnt=-1;
						for(int i=1;i<=n;i++)
						{
							if(a[i]==0) a[i]=d[++cnt];
						}
						for(int i=1;i<=n;i++)
						{
							if(a[i]!=-1)cout<<a[i]<<" ";
						}
						cout<<'\n';	
					}
				}
			}
			else
			{
//				cout<<"!";
				int s=0;
				for(int i=1;i<=n;i++)
					if(!a[i]) a[i]=-d[++s];
				for(int i=1;i<n;i++) 
					if(abs(a[i])>abs(a[i+1]))
					{
						s=i;
						break;
					}
				int minn=1e9,sum=0; 
				for(int i=1;i<=n;i++) if(a[i]<0) a[i]=0;
				for(int i=s+(s==0);i<=n;i++)
				{
					if(a[i])minn=min(minn,a[i]);
				}
				while(!a[s])s++;
				for(int i=1;i<s;i++) 
				{
					if(!a[i])sum++;
					if(minn<d[sum]) break;
					if(a[i]>minn)
					{
						sum=0;
						break;
					}
				}
//				cout<<minn<<endl;
				if(minn<d[sum]&&a[1]==1)
				{
//					cout<<"!";
//					cout<<sum<<endl;
					for(int i=1;i<=n;i++)
					{
						if(a[i]==minn) 
						{
							d[0]=a[i];
							a[i]=-1;
							sort(d,d+cnt+1);
							break;
						}
					}
					cnt=-1;
					for(int i=1;i<=n;i++)
					{
						if(!a[i])a[i]=d[++cnt];
					}
					for(int i=1;i<=n;i++)
					{
						if(a[i]!=-1)cout<<a[i]<<" ";
					}
					cout<<'\n';
				}
				else
				{
					int s=0;
					for(int i=1;i<=n;i++)
						if(!a[i]) a[i]=-d[++s];
					for(int i=1;i<n;i++) 
						if(abs(a[i])>abs(a[i+1]))
						{
							d[0]=abs(a[i]);
							a[i]=0;
							sort(d,d+1+cnt);
							break;
						}
					int num=unique(d,d+1+cnt)-d-1;
					cnt=num;
					cnt=-1;
					if(!d[0])cnt++,a[n]=0;
					for(int i=1;i<=n;i++)
						if(a[i]<0) a[i]=d[++cnt];
					for(int i=1;i<=n;i++)
					{
						if(a[i])cout<<a[i]<<" ";
					}
					cout<<'\n';
				}
			}
		}
		else
		{
//			cout<<"!";
			int s=0;
			for(int i=1;i<=n;i++)
				if(!a[i]) a[i]=-d[++s];
			for(int i=1;i<n;i++) 
				if(abs(a[i])>abs(a[i+1]))
				{
					s=i;
					break;
				}
			int minn=1e9,sum=0; 
			for(int i=1;i<=n;i++) if(a[i]<0) a[i]=0;
			for(int i=s+(s==0);i<=n;i++)
			{
				if(a[i])minn=min(minn,a[i]);
			}
			while(!a[s])s++;
			for(int i=1;i<s;i++) 
			{
				if(a[i]==minn) break;
				if(!a[i])sum++;
				if(minn<d[sum]) break;
				if(a[i]>d[sum+1])
				{
					sum=0;
					break;
				}
			}
//			cout<<minn<<" "<<sum<<endl;
			if(minn<d[sum]&&a[1]==0)
			{
//				cout<<"!";
				for(int i=1;i<=n;i++)
				{
					if(a[i]==minn) 
					{
						d[0]=a[i];
						a[i]=-1;
						sort(d,d+cnt+1);
						break;
					}
				}
				cnt=-1;
				for(int i=1;i<=n;i++)
				{
					if(!a[i])a[i]=d[++cnt];
				}
				for(int i=1;i<=n;i++)
				{
					if(a[i]!=-1)cout<<a[i]<<" ";
				}
				cout<<'\n';
			}
			else
			{
//				cout<<"!";
				int s=0;
				for(int i=1;i<=n;i++)
					if(!a[i]) a[i]=-d[++s];
				for(int i=1;i<n;i++) 
					if(abs(a[i])>abs(a[i+1]))
					{
						d[0]=abs(a[i]);
						a[i]=0;
						sort(d,d+1+cnt);
						break;
					}
				int num=unique(d,d+1+cnt)-d-1;
				cnt=num;
				cnt=-1;
				if(!d[0])cnt++,a[n]=0;
				for(int i=1;i<=n;i++)
					if(a[i]<0) a[i]=d[++cnt];
				for(int i=1;i<=n;i++)
				{
					if(a[i])cout<<a[i]<<" ";
				}
				cout<<'\n';
			}
		}
	}

	return 0;
}
/*
3
2
1 0 
2
0 1 
1
11
9 7 5 11 0 3 4 6 8 1 2   


*/

C. 斯坦纳树

牛牛方法错误当且仅当存在一个点不是关键点但他连了大于等于三个关键点的边，这样会导致有的边按牛牛方法求被重复算

倒着删点，如果这个点有大于等于三条边，那他就会导致做法错误，然后把与他相连的边删了，如果有一个之前被删的会导致

错误的点在这个点被删后不会导致错误了，就把他删去，答案为1但且仅当不存在这样被删去的会导致错误的点，边权为零的

用并查集维护连通块

点击查看代码 
#include<bits/stdc++.h>
const int maxn=3e5+10;
using namespace std;
int n,head[maxn],nxt[maxn<<1],to[maxn<<1],tot,p[maxn],fa[maxn],size[maxn],in[maxn];
int x[maxn],y[maxn],z[maxn],cnt,sum,son[maxn],ans[maxn];
bool vis[maxn];
set<int>q[maxn]; 
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void del(int x)
{	
	if(q[x].size()<=2&&!size[x])
	{
		sum--;int temp=0;
		for(auto i:q[x]) son[++temp]=i;
		q[x].clear();
		for(int i=1;i<=temp;i++)
		{
			q[son[i]].erase(x);
			for(int j=i+1;j<=temp;j++)
			{
				q[son[i]].insert(son[j]);
				q[son[j]].insert(son[i]);	
			}
		}
		for(int i=1;i<=temp;i++) del(son[i]);
	}
}

int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		if(!c)
		{
			a=find(a),b=find(b);
			if(a>b) swap(a,b);
			fa[b]=a;
			continue;
		}
		x[++cnt]=a,y[cnt]=b;
	}
	for(int i=1;i<n;i++) q[find(x[i])].insert(find(y[i])),q[find(y[i])].insert(find(x[i]));
	for(int i=1;i<=n;i++)
	{
		cin>>p[i];
		p[i]=find(p[i]);
		size[p[i]]++;
	}
	for(int i=n;i>=1;i--)
	{
		ans[i]=!sum;
		size[p[i]]--;
		if(!size[p[i]]) sum++,del(p[i]);
	}
	for(int i=1;i<=n;i++) cout<<ans[i];

	return 0;
}
/*
10
5 9 0
6 9 6
7 6 9
1 7 5
10 1 2
8 10 0
4 10 5
3 4 9
2 5 4
4 5 3 7 8 9 6 2 1 10

5
1 2 3
1 5 0
2 3 2
2 4 3
1 3 4 2 5
*/

标签：cnt,int,sum,break,++,maxn,csp,模拟
From： https://www.cnblogs.com/oceansofstars/p/18439278

相关文章

  • csp-s模拟5
    A.光来自\(K8\)的神奇做法，根据贪心思想，一个点减四个亮度可以收益最大化，所以枚举四个灯亮度都不足4时的最终态，然后看剩下需要亮度需要减的次数，每次选最大的那个操作就行，复杂度\(O(16n)\)点击查看代码#include<bits/stdc++.h>constintmaxn=1e5+10;usingnamespacestd;......
  • [赛记] csp-s模拟5
    光100pts赛时打的错解A了，就很神奇；其实可以发现答案有可二分性，考虑二分答案，每次check时枚举左上角和右下角的耗电量，然后对左下角的耗电量再进行二分，最后判定以下即可；赛时就这么打的，然后赛后拍出来了；其实这个思路是对的，只是$\lfloor\fracn4\rfloor$这个条件有误差，所以暴......
  • csp模拟赛 6 9.28
    0+40+10+0一言以蔽之曰“一上午白干”T1一般图最小匹配首先，对答案有贡献的点对一定在排序后的位于相邻位置所以排序后取出所有\(a_{i+1}-a_{i}\)但不能像Kruskal一样每次取最小，因为其只需要考虑连通性，不涉及其它限制。所以用dp或者可反悔贪心取最优解点击查看代码#in......
  • 『模拟赛』csp-s模拟赛6
    『模拟赛』csp-s模拟赛6挂分日寄：0+20+0+0喵喵赛时对拍拍了10000个点都没拍出来，赛后一下就拍出错来了，我谔谔。T1DP喵~首先sort一遍方便处理其实转移时加一个abs取绝对值就可，纯纯多此一举设\(f[i,j,1/0]\)为前\(i\)个数中选\(j\)个的最小值若选当前这个数，则\(f[i......
  • 2024.9.28 代码源模拟赛
    省流：\(45+20+5+0=70\)简称：唐诗在此膜拜\(klz\)\(Heldivis\)\(Sorato\)\(czl\)\(Ech0\_7\)yxanslihe_qwq大佬T1先看的T1，想了一个拓排（其实是看错题了），然后过了第一个样例，然后咋调都过不去，就去码暴力了。过了大概10min发现看错题了，然后一会就想出来个\(O(n^2)\)......
  • 代码源 2024 CSP-S 模拟赛 Day 6
    赛时开T1，发现立即有了\(O(n^2)\)的思路，能有\(45\)分，但是先不急，看看后面的题。T2、T3、T4似乎都可以写个暴力。又想了想，T1还需要求出个LCA，所以复杂度是\(O(n^2\logn)\)的，开写。很快写完，调不过，边界很不好处理。直到\(1.5\)h才调出来\(O(n^2\logn)\)。上个厕所......
  • CSP-S 2024 第六次
    A排序之后只会选相邻的，直接DP。B从前往后考虑每个数\(a_i\)要不要删。若不删\(a_i\)：若\(a_i\ne0\)，则\(a_i\)已经确定。若\(a_i=0\)，则\(a_i\)可取所有没出现过的数，以及\(i\)后最小的数（先删掉它再把\(a_i\)赋成它）若删掉\(a_i\)：若\(a_{i+1}\ne0\)，则\(a......
  • 『模拟赛』CSP-S模拟6
    Rank一般恼了怎么又狠狠挂分啊啊啊啊A.一般图最小匹配签。（这么多天终于签上了是吧）结论是，跟图完全没关系。题意转换完就是从\(n\)个数中选出\(m\)对差的绝对值之和最小的数。显然我们选的每一对数都应该是这\(n\)个数中相邻的一组，sort一下，设\(f_{i,j,k}\)表示到......
  • CSP-S 2022~2023 补题
    下面的代码都是远古代码，不打算重写了。CSP-S2023T1密码锁题意：一个密码锁上有\(5\)个位置，每个位置上的数字是\(0\sim9\)的循环，每次打乱会选择一或两个相邻位置同时循环移动。给定\(n\)个打乱后的状态，求有多少种可能的原状态。\(n\le8\)。容易发现可能的状态数......
  • [DMY]2024 CSP-S 模拟赛 Day 6
    前言离A掉一道题最近的一次。过程看完T1以后，想先构一个\(\mathcal{O}(n^3)\)的暴力，但是发现只有10pts，而且算法复杂度接近\(\mathcal{O}(n^4)\)，所以果断放弃。把链的限制写了（然后亏大了），然后开始在CS上面画画。画了一会发现一个简单的dp思路，但是是\(\mathcal{O}(n^......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99