首页 > 其他分享 >Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)

Codeforces Round 977 (Div. 2, based on COMPFEST 16 - Final Round)

时间：2024-10-31 19:44:00浏览次数：1  
标签：977 include based int RI const now Round define

Preface

这场其实是上周四 VP 的，因为当时马上要出发打济南站了，但因为挺久没写代码了所以打算临阵磨枪一下

好家伙结果 Div.2 D 不会做直接给人整麻了，不过好在看了眼榜把 E2 写了，后面发现这个 D 想到了就不难

A. Meaning Mean

容易发现从小到大操作一定最优

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=55;
int t,n,a[N];
int main()
{
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d",&n);
		for (RI i=1;i<=n;++i) scanf("%d",&a[i]);
		sort(a+1,a+n+1); int ans=a[1];
		for (RI i=2;i<=n;++i) ans=(ans+a[i])/2;
		printf("%d\n",ans);
	}
	return 0;
}

B. Maximize Mex

由于 \(n\) 个数的 mex 最大就是 \(n\)，因此我们从小到大贪心复杂度就是对的

具体地，用一个桶记一下每个数的数量，如果出现次数超过 \(1\) 就把多出的移动到后面即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,x,a[N],c[N];
int main()
{
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d",&n,&x);
		for (RI i=0;i<=n;++i) c[i]=0;
		for (RI i=1;i<=n;++i)
		{
			scanf("%d",&a[i]);
			if (a[i]<=n) ++c[a[i]];
		}
		int mex=0;
		while (c[mex]>0)
		{
			if (mex+x<=n) c[mex+x]+=c[mex]-1;
			++mex;
		}
		printf("%d\n",mex);
	}
	return 0;
}

C1. Adjust The Presentation (Easy Version)

简单猜一手结论，发现只保留 \(\{b\}\) 序列中每种数第一次出现的一个，然后看剩下的部分是否为 \(\{a\}\) 的前缀即可

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,m,q,a[N],b[N],vis[N];
int main()
{
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&n,&m,&q);
		for (RI i=1;i<=n;++i) scanf("%d",&a[i]),vis[i]=0;
		vector <int> vec;
		for (RI i=1;i<=m;++i)
		{
			scanf("%d",&b[i]);
			if (!vis[b[i]]) vec.push_back(b[i]),vis[b[i]]=1;
		}
		bool flag=1;
		for (RI i=0;i<vec.size();++i)
		if (vec[i]!=a[i+1]) { flag=0; break; }
		puts(flag?"YA":"TIDAK");
	}
	return 0;
}

C2. Adjust The Presentation (Hard Version)

考虑带修怎么做，不妨将上面的结论换个形式描述

令 \(c_i\) 表示 \(a_i\) 在 \(\{b\}\) 序列中第一次出现的位置（没出现就置为 \(m+1\)），显然有解的充要条件为 \(\forall i\in[1,n-1],c_i\le c_{i+1}\)

由于单点操作一次会影响的位置很少，可以拿 set 维护每种数出现的位置，然后讨论修改后的影响即可

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,m,q,a[N],b[N],pos[N],val[N]; set <int> s[N];
int main()
{
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&n,&m,&q);
		for (RI i=1;i<=n;++i)
		scanf("%d",&a[i]),pos[a[i]]=i,s[i].clear(),s[i].insert(m+1);
		for (RI i=1;i<=m;++i)
		scanf("%d",&b[i]),s[b[i]].insert(i);
		for (RI i=1;i<=n;++i) val[pos[i]]=*s[i].begin();
		int cnt=0;
		auto calc=[&](CI x)
		{
			if (x<1||x>=n) return 0;
			return (int)(val[x]<=val[x+1]);
		};
		for (RI i=1;i<n;++i) cnt+=calc(i);
		puts(cnt==n-1?"YA":"TIDAK");
		while (q--)
		{
			int x,y; scanf("%d%d",&x,&y);
			vector <int> key={pos[b[x]],pos[b[x]]-1,pos[y],pos[y]-1};
			sort(key.begin(),key.end());
			key.erase(unique(key.begin(),key.end()),key.end());
			for (auto it:key) cnt-=calc(it);
			s[b[x]].erase(x); s[y].insert(x);
			val[pos[b[x]]]=*s[b[x]].begin();
			val[pos[y]]=*s[y].begin();
			for (auto it:key) cnt+=calc(it);
			b[x]=y; puts(cnt==n-1?"YA":"TIDAK");
		}
	}
	return 0;
}

D. Boss, Thirsty

挺神秘的一个题，需要对限制有一定的观察才能入手

朴素的按行 DP 复杂度一眼寄，考虑这种方法不行的根本原因就是状态需要记录区间两个端点，这样显然没有前途

假设上一行选择的区间为 \([l_1,r_1]\)，这行选择的区间为 \([l_2,r_2]\)，不妨把左端点 \(l_2\) 固定下来，看下此时右端点需要满足哪些性质

  • 若 \(l_2<l_1\)，此时所有 \(r_2\ge l_1\) 的区间都是合法的；
  • 若 \(l_2=l_1\)，此时所有 \(r_2>r_1\) 的区间都是合法的；

右端点固定的情况同理，根据这个性质我们发现两个端点的转移其实十分独立

具体地，令 \(f_{i,j,0/1}\) 表示第 \(i\) 行的左/右端点为 \(j\) 时的最大贡献，转移画画图用前缀和优化一下非常显然

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,INF=1e18;
int t,n,m,a[N],pfx[N],mnp[N],mxs[N],f[2][2][N];
signed main()
{
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld%lld",&n,&m);
		for (RI p=0;p<2;++p) for (RI q=0;q<2;++q)
		for (RI i=1;i<=m;++i) f[p][q][i]=-INF;
		pfx[0]=0; mnp[0]=0; mxs[m+1]=-INF;
		for (RI i=1;i<=m;++i) scanf("%lld",&a[i]);
		for (RI i=1;i<=m;++i) pfx[i]=pfx[i-1]+a[i];
		for (RI i=1;i<=m;++i) mnp[i]=min(mnp[i-1],pfx[i]);
		for (RI i=m;i>=1;--i) mxs[i]=max(mxs[i+1],pfx[i]);
		for (RI i=1;i<=m;++i)
		{
			f[1][0][i]=mxs[i]-pfx[i-1];
			f[1][1][i]=pfx[i]-mnp[i-1];
		}
//		for (RI i=1;i<=m;++i) printf("%lld%c",f[1][0][i]," \n"[i==m]);
//		for (RI i=1;i<=m;++i) printf("%lld%c",f[1][1][i]," \n"[i==m]);
		for (RI j=2;j<=n;++j)
		{
			int now=j&1,lst=now^1;
			for (RI i=1;i<=m;++i) f[now][0][i]=f[now][1][i]=-INF;
			for (RI i=1;i<=m;++i) scanf("%lld",&a[i]);
			for (RI i=1;i<=m;++i) pfx[i]=pfx[i-1]+a[i];
			for (RI i=1;i<=m;++i) mnp[i]=min(mnp[i-1],pfx[i]);
			for (RI i=m;i>=1;--i) mxs[i]=max(mxs[i+1],pfx[i]);
			int tmp1=-INF,tmp2=-INF;
			for (RI i=m;i>=1;--i)
			{
				tmp1=max(tmp1,mxs[i+1]+f[lst][0][i+1]);
				tmp2=max(tmp2,mxs[i+1]+f[lst][1][i]);
				f[now][0][i]=max(f[now][0][i],tmp1-pfx[i-1]);
				f[now][0][i]=max(f[now][0][i],tmp2-pfx[i-1]);
			}
			tmp1=-INF; tmp2=-INF;
			for (RI i=1;i<=m;++i)
			{
				tmp1=max(tmp1,f[lst][0][i]-(i-2>=0?mnp[i-2]:INF));
				tmp2=max(tmp2,f[lst][1][i-1]-(i-2>=0?mnp[i-2]:INF));
				f[now][1][i]=max(f[now][1][i],tmp1+pfx[i]);
				f[now][1][i]=max(f[now][1][i],tmp2+pfx[i]);
			}
//			for (RI i=1;i<=m;++i) printf("%lld%c",f[now][0][i]," \n"[i==m]);
//			for (RI i=1;i<=m;++i) printf("%lld%c",f[now][1][i]," \n"[i==m]);
		}
		int ans=-INF;
		for (RI i=1;i<=m;++i) ans=max(ans,max(f[n&1][0][i],f[n&1][1][i]));
		printf("%lld\n",ans);
	}
	return 0;
}

E1. Digital Village (Easy Version) && E2. Digital Village (Hard Version)

这种涉及到路径上最大值的问题一眼克鲁斯卡尔重构树，因此考虑把重构树先搞出来

将选中的点成为关键点，则某个需要网络的点对应的贡献，就是重构树上距离其最近的且子树里含有关键点的祖先对应的权值

不难发现这个东西很适合 DP，令 \(f_{i,j}\) 表示点 \(i\) 的子树里选了 \(j\) 个关键点时对应的贡献，转移类似树上背包，不过由于重构树是棵二叉树因此写起来比较方便

需要注意的是当某一边子树中没有关键点时就要在这个点出合并贡献，维护子树内需要网络的点的个数后就很容易转移

总复杂度同树上背包，\(O(n^2)\)，E3 估计要神秘多项式优化，弃疗

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<array>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=10005,INF=1e18;
int t,n,m,p,key[N],w[N],sz[N],x,y,z,fa[N],ls[N],rs[N]; vector <int> f[N];
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
inline void DFS(CI now)
{
	sz[now]=key[now];
	if (ls[now]==0) return (void)(f[now]={0,0});
	DFS(ls[now]); DFS(rs[now]);
	sz[now]+=sz[ls[now]]+sz[rs[now]];
	f[now].resize(sz[now]+1);
	for (RI i=1;i<=sz[now];++i) f[now][i]=INF;
	for (RI i=1;i<=sz[ls[now]];++i)
	for (RI j=1;j<=sz[rs[now]];++j)
	f[now][i+j]=min(f[now][i+j],f[ls[now]][i]+f[rs[now]][j]);
	for (RI i=1;i<=sz[ls[now]];++i)
	f[now][i]=min(f[now][i],f[ls[now]][i]+sz[rs[now]]*w[now]);
	for (RI j=1;j<=sz[rs[now]];++j)
	f[now][j]=min(f[now][j],f[rs[now]][j]+sz[ls[now]]*w[now]);
}
signed main()
{
	for (scanf("%lld",&t);t;--t)
	{
		scanf("%lld%lld%lld",&n,&m,&p);
		for (RI i=1;i<=2*n;++i) ls[i]=rs[i]=key[i]=0,fa[i]=i;
		for (RI i=1;i<=p;++i) scanf("%lld",&x),key[x]=1;
		vector <array <int,3>> E;
		for (RI i=1;i<=m;++i)
		scanf("%lld%lld%lld",&x,&y,&z),E.push_back({z,x,y});
		sort(E.begin(),E.end()); int idx=n;
		for (auto [z,x,y]:E)
		{
			if (getfa(x)==getfa(y)) continue;
			w[++idx]=z;
			ls[idx]=getfa(x); rs[idx]=getfa(y);
			fa[getfa(x)]=fa[getfa(y)]=idx;
		}
		DFS(idx);
		for (RI i=1;i<=n;++i) printf("%lld%c",i<=p?f[idx][i]:0," \n"[i==n]);
	}
	return 0;
}

Postscript

本来今天打算再开一场 VP 的，但结果 CF 好巧不巧爆炸了，看评测队列的样子感觉要炸很久，这下不得不白兰了

标签：977,include,based,int,RI,const,now,Round,define
From： https://www.cnblogs.com/cjjsb/p/18518737

相关文章

  • FirstRound-博客中文翻译-五-
    FirstRound博客中文翻译（五）原文：FirstRoundBlog协议：CCBY-NC-SA4.0为什么这位工程领导者认为你不应该以零遗憾减员为目标原文：https://review.firstround.com/why-this-engineering-leader-thinks-you-shouldnt-aim-for-zero-regrettable-attrition作为【温室】****的首......
  • Educational Codeforces Round 171 (Rated for Div. 2)B-D
    B.BlackCells题目:思路:首先我们发现要分奇偶讨论。偶数:很简单,取a[2]-a[1],a[4]-a[3],.........a[n]-[n-1]的最大值。奇数:我只需要知道假如删除当前的这个数剩下的数最大的间隔值,注意只能删除1,3,等奇数位,因为要保证删除后左右的数为偶数。(我的代码里面是偶数位因......
  • Codeforces Round 978(div.2) D1
    #感觉挺有意思的一道题题目:思路:观察发现对于两个人a,b如果两个人里面没有Impostor那么,你得到的回答是一样的,如果有impostor那么结果不同,那么我们就可以两个两个的询问,先找到2个人里面有impostor然后在找另外一个人来询问就行了。代码:#include<bits/stdc++.h>usin......
  • Codeforces Global Round 27，D. Yet Another Real Number Problem 题解
    单调栈+贪心题意：给定一个序列从左往右对于每个索引iii，求出其前缀的数组可以进行任意次以下操作的条件下：选择......
  • Codeforces Round 981 (Div. 3) ABCDE
    CodeforcesRound981(Div.3)ABCDEA.SakurakoandKosuke藕是看样例直接猜了结论......
  • Codeforces Round 982 (Div. 2)
    CodeforcesRound982(Div.2)总结A猜结论，最后的图形的周长都能移成一个长方形的周长，这个长方形就是\(w\)和\(h\)的最大值。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<vector>#include<q......
  • # [Educational Codeforces Round 171](https://codeforces.com/contest/2026)
    EducationalCodeforcesRound171D.SumsofSegments定义四个前缀和：\(s_i=a_1+a_2+\dots+a_i\)\(u_i=s_1+s_2+\dots+s_i\)\(t_i=s(i,i)+s(i,i+1)+\dots+s(i,n)\)\(ts_i=t_1+t_2+\dots+t_i\)\(s_i\)为\(a_i\)的前缀和，\(u_i\)为\(s_i\)的前缀和，\(t_i\)为分块之后第......
  • Educational Codeforces Round 171 (Rated for Div. 2) 10.28 ABCD题解
    EducationalCodeforcesRound171(RatedforDiv.2)10.28（ABCD）题解A.PerpendicularSegments数学（math）计算几何（geometry）题意：给定一个\(X,Y,K\)。需要求解出二维坐标系中的四个点\(A,B,C,D\)，满足：\(0\leqA_x，B_x，C_x，D_x\leqX\)，\(0\leqA_y，B_y，C_y，D_y\leqY\)。并......
  • Educational Codeforces Round 171 (Div. 2)
    EducationalCodeforcesRound171(Div.2)A猜结论，两条边的最小值最大时，两条边相等。所以取\(min(x,y)\)为边长的正方形，对角线就是所求。#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>usingnamespacestd;intx,y,k;voidsolve(){......
  • Codeforces Global Round 27
    CodeforcesGlobalRound27总结A将红色的位置\((r,c)\)移走，分为三块来考虑，蓝色的块移动\(m-c\)，黄色的块移动\(m*(n-r)\)，绿色的块移动\((m-1)*(n-r)\)。#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#in......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99