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

『模拟赛』csp-s模拟赛6

时间:2024-09-28 20:36:16浏览次数:9  
标签:cnt int pos else vis ans csp 模拟

『模拟赛』csp-s模拟赛6

挂分日寄:0+20+0+0

喵喵赛时对拍拍了10000个点都没拍出来,赛后一下就拍出错来了,我谔谔。

T1

DP喵~

首先 sort 一遍方便处理 其实转移时加一个 abs 取绝对值就可,纯纯多此一举

设 \(f[i,j,1/0]\) 为前 \(i\) 个数中选 \(j\) 个的最小值

若选当前这个数,则 \(f[i,j,1]=f[i-1,j-1,0]+a[i]-a[i-1]\)

若不选当前这个数,则 \(f[i,j,0]=min(f[i-1,j,0],f[i-1,j,1]\)

考虑到可以用滚动数组滚调一维。

优化一下即可。

没了。

int n,m;
int f[2][N][2],a[N];

signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	
	n=rd,m=rd;
	for(int i=1;i<=n;i++) a[i]=rd;

	sort(a+1,a+1+n);
	
	mst(f,0x3f);
	
	for(int i=2;i<=n;i++){
		int g=i&1;
		for(int j=0;j<=m;j++)
			f[g][j][0]=f[g][j][1]=inf;
			
		f[g^1][0][0]=0;
		for(int j=1;j<=m;j++){
			f[g][j][0]=min(f[g^1][j][0],f[g^1][j][1]);
			f[g][j][1]=f[g^1][j-1][0]+a[i]-a[i-1];
		}
	}
	
	printf("%lld",min(f[n&1][m][1],f[n&1][m][0]));
	return Elaina;
}

赛后听GGrun可反悔贪心的思路也不错。懒得打。遂咕咕。

T2

赛时近300行巨大贪心分讨。

总的来说就是手模几组数据发现最优解也就只有那几种操作。

比如说:把第一个数删掉;如果数组中有 \(1\) 那么删去 \(1\)...等等。

接下来码就完事了。

复杂度是 \(O(nq \times 常数)\)

Code(不建议点开) int n,m,len; int a[N]; int now[N],ans[N]; map<int,int> vis;

bool cmp(int *x,int *y){//x<y?
// for(int i=1;i<=n;i++){
// cout<<x[i]<<' ';
// }
// cout<<endl;
for(int i=1;i<=n;i++){
if(x[i]<y[i]) return 1;
else if(x[i]>y[i]) return 0;
else continue;
}
return 1;
}

void work(){
// n=rd;
cin>>n;

vis.clear();
fill(ans,ans+1+n,inf);

bool _0=1;int fst=0;
for(int i=1;i<=n;i++){
	cin>>a[i];

// a[i]=rd,
_0=_0&&(a[i]!=0),vis[a[i]]=i;
if(!fst && a[i]==0) fst=i;
}

if(!fst){
	for(int i=1;i<n;i++){
		cout<<i<<' ';
	}
	cout<<'\n';
	return ;
}

int pre;

/---------------------------------------------/
len=0;
pre=vis[a[1]];
vis[a[1]]=0;
for(int i=2,cnt=0;i<=n;i++){
if(a[i]!=0){
now[++len]=a[i];
}else{
++cnt;
while(vis[cnt]) ++cnt;
now[++len]=cnt;
}
}

if(cmp(now,ans)){
	memcpy(ans,now,sizeof(int) *(n+1));
}

vis[a[1]]=pre;

/---------------------------------------------/
len=0;

int mx=0,pos;
for(int i=1;i<=n;i++){
	if(a[i]>mx) mx=a[i],pos=i;
	else if(a[i]==mx) continue;
	else break;
}

pre=vis[a[pos]];
vis[a[pos]]=0;

for(int i=1,cnt=0;i<=n;i++){
	if(i==pos) continue;
	if(a[i]!=0){
		now[++len]=a[i];
	}else{
		++cnt;
		while(vis[cnt]) ++cnt;
		now[++len]=cnt;
	}
}

// for(int i=1;i<n;i++){
// cout<<now[i]<<' ';
// }
// cout<<endl;

if(cmp(now,ans)){
	memcpy(ans,now,sizeof(int) *(n+1));
}

vis[a[pos]]=pre;

/---------------------------------------------/
len=0,mx=0;
pos=1;
for(int i=1;i<=n;i++){
if(a[i]i||a[i]0){
if(vis[i]&&vis[i]!=i){
pos=vis[i];
break;
}
}else break;
}

pre=vis[a[pos]];
vis[a[pos]]=0;

for(int i=1,cnt=0;i<=n;i++){
	if(i==pos) continue;
	if(a[i]!=0){
		now[++len]=a[i];
	}else{
		++cnt;
		while(vis[cnt]) ++cnt;
		now[++len]=cnt;
	}
}

if(cmp(now,ans)){
	memcpy(ans,now,sizeof(int) *(n+1));
}

vis[a[pos]]=pre;

/---------------------------------------------/
len=0,mx=0,pos=0;
for(int i=1;i<=n;i++){
if(a[i]i||a[i]0) continue;
else if(a[i]>mx) mx=a[i],pos=i;
else break;
}

if(!pos){
	for(int i=1;i<n;i++) now[i]=i;
	if(cmp(now,ans)){
		memcpy(ans,now,sizeof(int) *(n+1));
	}
}

pre=vis[a[pos]];
vis[a[pos]]=0;

for(int i=1,cnt=0;i<=n;i++){
	if(i==pos) continue;
	if(a[i]!=0){
		now[++len]=a[i];
	}else{
		++cnt;
		while(vis[cnt]) ++cnt;
		now[++len]=cnt;
	}
}

if(cmp(now,ans)){
	memcpy(ans,now,sizeof(int) *(n+1));
}

vis[a[pos]]=pre;

/---------------------------------------------/
len=0;
if(vis[1]){
int mn=1,fnd=0;

	while(a[1]>mn){
		if(!vis[mn]){
			fnd=1;
			break;
		}
		++mn;
	}
	
	if(fnd){
		int mx=0;
		for(int i=1;i<=n;i++){
			if(!a[i]){
				break;
			}
			if(a[i]>mx){
				mx=a[i];
				pos=i;
			}
		}
		
		vis[a[pos]]=0;
		
		for(int i=1,cnt=0;i<=n;i++){
			if(i==pos) continue;
			
			if(a[i]!=0){
				now[++len]=a[i];
			}else{
				++cnt;
				while(vis[cnt]) ++cnt;
				now[++len]=cnt;
			}
		}
	}else{
		pos=vis[1];
		vis[1]=0;
		for(int i=1,cnt=0;i<=n;i++){
			if(i==pos) continue;
			if(a[i]!=0){
				now[++len]=a[i];
			}else{
				++cnt;
				while(vis[cnt]) ++cnt;
				now[++len]=cnt;
			}
		}
	}
}else{
	if(fst)
	vis[a[1]]=0;
	a[fst]=1;
	vis[1]=fst;
	for(int i=1,cnt=0;i<=n;i++){
		if(i==fst) continue;
		if(a[i]!=0){
			now[++len]=a[i];
		}else{
			++cnt;
			while(vis[cnt]) ++cnt;
			now[++len]=cnt;
		}
	}
}

if(cmp(now,ans)){
	memcpy(ans,now,sizeof(int) *(n+1));
}

for(int i=1;i<n;i++){
	cout<<ans[i]<<' ';

// printf("%lld ",ans[i]);
}
cout<<'\n';
// putchar('\n');
}

signed main(){
// freopen("repeat.in","r",stdin);
// freopen("repeat.out","w",stdout);

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

// int T=rd;
int T;
cin>>T;

while(T--)
	work();

return Elaina;

}

T3

考虑到样例有个都是 \(1\),所以我们直接 cout<<1 喜提 15pts

贴个官方题解吧,感觉挺详细的。


int n,m,sum,idx,a[N],ans[N];
int fa[N],cnt[N],son[N];
set<int> st[N];
struct EDGE{
	int frm,to;
}e[N];

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

void del(int x){
	if(st[x].size()<=2 && !cnt[x]){
		--sum;
		int num=0;

		for(auto to:st[x])
			son[++num]=to;

		st[x].clear();

		for(int i=1;i<=num;i++){
			for(int j=1;j<=num;j++){
				if(i==j) continue;
				st[son[i]].insert(son[j]);
			}
			st[son[i]].erase(x);
		}
			
		for(int i=1;i<=num;i++)
			del(son[i]);

	}
}

signed 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,x,y,z;i<n;i++){
		cin>>x>>y>>z;

		if(!z){
			int a=find(x),b=find(y);
			if(a>b) swap(a,b);
			fa[b]=a;
		}else
			e[++idx].frm=x,e[idx].to=y;
	}

	for(int i=1;i<n;i++)
		st[find(e[i].frm)].insert(find(e[i].to)),st[fa[e[i].to]].insert(fa[e[i].frm]);

	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]=find(a[i]);
		++cnt[a[i]];
	}
	
	for(int i=n;i>=1;i--){
		ans[i]=(sum==0),--cnt[a[i]];
		if(!cnt[a[i]]) ++sum,del(a[i]);
	}

	for(int i=1;i<=n;i++)
		cout<<ans[i];
	
	return Elaina;
}

T4

考虑到样例有几个都是 \(1\),所以我们直接 cout<<1 喜提 10pts

诶 这句话怎么感觉在哪见过

正解奇妙 \(O(n^6log(n))\) DP。

标签:cnt,int,pos,else,vis,ans,csp,模拟
From: https://www.cnblogs.com/Elaina-0/p/18438223

相关文章

  • 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^......
  • CSP & NOIP 模拟赛记录
    9.18(lanos212)T1签到,10mins内过了。T2乍一看有点困难,题目太形式化,不太直观,先跳过去思考T3了,T3没有什么DP的思路,但是这种题显然需要DP。看了一眼T4,被一堆式子糊脸恶心了,没有怎么思考。接下来一个小时在思考T2和T3,突然发现T2只需要每次求最短路就可以了,那么就是......
  • 信息学奥赛复赛复习06-CSP-J2020-02直播获奖-向上取整、向下取整、整数除法、最大值、
    PDF文档公众号回复关键字:2024092812020CSP-J题目1优秀的拆分[题目描述]NOI2130即将举行。为了增加观赏性,CCF决定逐一评出每个选手的成绩,并直播即时的获奖分数线。本次竞赛的获奖率为w%,即当前排名前w%的选手的最低成绩就是即时的分数线更具体地,若当前已评出了p个......
  • 项目实战:Qt+OSG爆破动力学仿真三维引擎测试工具v1.1.0(加载.K模型,子弹轨迹模拟动画,支持
    若该文为原创文章,转载请注明出处本文章博客地址:https://hpzwl.blog.csdn.net/article/details/142454993长沙红胖子Qt(长沙创微智科)博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV、OpenGL、ffmpeg、OSG、单片机、软硬结合等等)持续更新中…Qt开发专栏:项目实战......
  • 第一章数据管理【4’】(DAMA-CDGA 2022年以后历年模拟题真题汇总,基本包含所有考点。)
    1、以下哪个不是DAMA-DMBOK的数据管理框架图?(知识点:第一章数据管理)A.DAMA车轮图B.DMBOK金字塔图C.环境因素六边形图D.知识领域语境关系图参考答案:B题目解析:DMBOK2第一章数据管理1.3.3,DAMA-DMBOK框架2、以下关于数据管理原则描述正确的是?(知识点:第一章数据管理)A.......