526互联

CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)（持续更新）

发布时间 2023-04-06 10:13:34作者: 空気力学の詩

Preface

唉难得熬夜打一把还天天掉分，苦路西

这把状态奇差，CD两个傻逼题都写的很慢，然后做E的时间太少最后又是经典比赛结束才调出来

虽然很想骂傻逼室友打游戏鬼叫的超级响导致我注意力很难集中，不过终究还是自己抗干扰水平不够，不能怨天尤人

A. Beautiful Sequence

傻逼题，显然若一个位置\(i\)满足\(i\ge a_i\)则通过删除\(i\)之前的某些数一定可以满足题意，直接判断即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=105;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
		bool flag=0; for (i=1;i<=n;++i) if (i>=a[i]) flag=1;
		puts(flag?"YES":"NO");
	}
}

B. Candies

首先一个很naive的结论，我们只能生成奇数，因此先特判掉偶数的情况

然后我们手玩一下画一下前几次操作的图出来，就一眼能找到规律，所有数之间形成了一棵二叉树的结果，并且所有数从大到小在树上依次分布

那么这个题就很好处理了，我们把每个奇数的排名（就是第几小的奇数）搞出来做一个类似二进制分解的东西即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,n;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		if (scanf("%d",&n),!(n&1)) { puts("-1"); continue; }
		if (n==1) { puts("0"); continue; }
		RI i,j; for (n=(n-1)/2,i=30;~i;--i) if (n&(1<<i)) break;
		for (printf("%d\n",i+1);~i;--i) printf("%c%c",n&(1<<i)?'2':'1'," \n"[i==0]);
	}
	return 0;
}

C. Make It Permutation

一个朴素的想法，先把所有重复的元素删成一个，然后我们可以直接枚举最后排列的长度，就很容易写出一个式子

其中要插入的次数就是排列的长度\(x\)减去小于等于\(x\)的元素个数，要删除的次数就是大于\(x\)的元素个数

但是有一个问题是最终排列的长度可能是\(10^9\)级别的，不能直接枚举

不过我们对上面的式子稍加观察，我们会发现这个式子要取得最小值只能在“小于等于\(x\)的元素个数”这个值发生改变的时候取

换而言之我们只要枚举所有出现过的数作为最后排列的长度即可，枚举的复杂度就降到\(O(n)\)了

#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,c,d,a[N]; long long ans;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; for (scanf("%lld%lld%lld",&n,&c,&d),i=1;i<=n;++i) scanf("%lld",&a[i]);
		sort(a+1,a+n+1); int m=unique(a+1,a+n+1)-a-1;
		for (ans=1e18,i=1;i<=m;++i)
		ans=min(ans,1LL*(a[i]-i)*d+1LL*(m-i)*c);
		printf("%lld\n",min(1LL*n*c+d,ans+1LL*(n-m)*c));
	}
	return 0;
}

D. Climbing the Tree

感觉没啥好说的，就一大力模拟题

首先对于每一个\(1\)操作，我们都可以计算出它对应的一个\(h\)的区间，然后我们把这个区间和之前所有\(1\)操作的区间取交集就是现在\(h\)可能的取值区间\([L,R]\)了

具体的计算也很简单，考虑下界就是让蜗牛第\(n-1\)天恰好爬不到，上界就是第\(n\)天刚好爬到，但要注意一些边界情况

然后考虑处理询问，很明显蜗牛要爬的天数关于树高是单调不减的，因此如果对于\(h=L\)和\(h=R\)的树高都需要爬相同的天数那\([L,R]\)之间的任意一天都需要爬相同的天数

然后就模拟一下就完了，只能说这场的CD是真的简单（1300、1700），但我感觉对比周三的那场（1900，2100）我好像写的更久

#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005,INF=1e18;
int t,q,tp,a,b,n;
inline int calc(CI h)
{
	if (a>=h) return 1; return (h-a+(a-b-1))/(a-b)+1;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i; int L=1,R=INF;
		for (scanf("%lld",&q),i=1;i<=q;++i)
		{
			if (scanf("%lld%lld%lld",&tp,&a,&b),tp==2)
			{
				if (R==INF) { printf("-1 "); continue; }
				int c1=calc(L),c2=calc(R);
				if (c1!=c2) printf("-1 "); else printf("%lld ",c1);
			} else
			{
				scanf("%lld",&n); int l=n>1?(a-b)*(n-2)+a+1:1,r=(a-b)*(n-1)+a;
				if (max(l,L)>min(r,R)) printf("0 "); else L=max(l,L),R=min(r,R),printf("1 ");
			}
		}
		putchar('\n');
	}
	return 0;
}

E. Monsters

唉只能说我想题和写题的速度都还是有点慢，每次比赛都有一道题要血战到最后一刻

虽然以前有几次也能堪堪压时过，但分数也是寥寥无几了，这次还比较可惜没调出来（其实就是个傻逼下标写反了）

好了说回题目，这题我本来的思路是按照每条边两端的点权值的差的绝对值从小到大排序

然后每次处理一条边的时候就尝试合并，通过并查集来维护每个连通块的大小，看起来就挺正确

后面写完调试样例的时候感觉不对劲，有些比如联通了权值为\((3,3)\)的边显然不应该先处理，因为它们还有等一些比如\((1,2)\)这样的边处理之后再联通的机会

因此后面改成了按照每条边两端的点的权值的最大值从小到大来排序就很正确了，代码也是十分好写

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,m,a[N],x,y,fa[N],sz[N],vis[N];
struct edge
{
	int v,x,y;
	friend inline bool operator < (const edge& A,const edge& B)
	{
		return A.v<B.v;
	}
}e[N];
inline int getfa(CI x)
{
	return fa[x]!=x?fa[x]=getfa(fa[x]):x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
		scanf("%d",&a[i]),fa[i]=i,sz[i]=1,vis[i]=a[i]==0;
		for (i=1;i<=m;++i) scanf("%d%d",&e[i].x,&e[i].y),e[i].v=max(a[e[i].y],a[e[i].x]);
		for (sort(e+1,e+m+1),i=1;i<=m;++i)
		{
			int fx=getfa(e[i].x),fy=getfa(e[i].y);
			if (fx==fy) continue; 
			vis[fx]=((vis[fx]&&sz[fx]>=e[i].v)||(vis[fy]&&sz[fy]>=e[i].v));
			fa[fy]=fx; sz[fx]+=sz[fy];
		}
		puts(sz[getfa(1)]==n&&vis[getfa(1)]?"YES":"NO");
	}
}

后来ztc跟我讲了一个BFS的做法啊，但是他的做法一些维护细节我也不是很理解，不过后来顺着想想发现了我的另一种实现方法

就是我们从所有\(a_i=0\)的点为源点做BFS，然后每次向外走之后可以把当前走到的所有点合并看作一个大的连通块来看待

然后考虑对于每个连通块我们每次要找到这些点向外的连边可达的节点中，\(a_i\)最小的那个来扩展，如果找得到并且这个值小于等于当前连通块就扩展，否则这个连通块就没用了

我们考虑对每一个连通块用堆维护它出点的\(a_i\)，然后考虑在合并的时候用启发式合并合并两个堆，最后由于查询次数是\(O(n)\)的，所以均摊复杂度是\(O(n\log n)\)的

代码就没写了，口胡一下