Codeforces Round 987 (Div. 2) - 比赛总结

Preface

我是若只。

A. Penchick and Modern Monument

先吃三发罚时。

最优策略应当是把所有数都调成众数，然而我一开始就忙着往后面做，胡乱猜了个结论就 WA 了，又猜了一个又 WA 了，再猜了一个再 WA 了。

const int N=105;
int n,a[N];

int main()
{
	int T; read(T);
	while(T--)
	{
		read(n);
		int con=0,maxcon=0;
		for(int i=1;i<=n;i++)
		{
			read(a[i]);
			if(a[i]==a[i-1]) con++;
			else con=1;
			maxcon=max(maxcon,con);
		}
		write(n-maxcon,'\n');
	}
	return 0;
}

B. Penchick and Satay Sticks

我的洛谷题解

这道题做得稍微细心了些。

从反面思考一下，一个有序序列里任意一个元素最多被交换一次，所以要让一个无序序列通过这种方式变得有序，每个元素也只能被交换最多一次。尝试交换所有可以交换的逆序对，最后判断是否有序即可。

const int N=2e5+5;
int n,a[N];

int main()
{
	int T; read(T);
	while(T--)
	{
		read(n);
		for(int i=1;i<=n;i++)
			read(a[i]);
		for(int i=2;i<=n;i++)
			if(a[i-1]-a[i]==1) swap(a[i-1],a[i]);
		puts(is_sorted(a+1,a+n+1)?"YES":"NO");
	}
	return 0;
}

C. Penchick and BBQ Buns

我的洛谷题解

从这里开始失衡。

偶数情况很简单，两个两个放就可以了，重点是奇数情况。

首先，如果要放奇数个，一定有至少一个数出现了奇数次。

其次，如果这个数出现了超过三次，因为放三个的约束条件小于放更多个，所以可以把多出来的那些给换成别的成对的数。

那么情况就转化成了如何放下三个同一个数。一旦放下同一个数三次，后面的就可以直接按照偶数的方法无脑放，所以考虑如何在最短的长度内放满 \(3\) 个同样的数。

设这个数三次分别出现在位置 \(p,p+X,p+X+Y\)，根据题目要求，\(X\) 和 \(Y\) 是平方数，且 \((X+Y)\) 也是平方数，所以设 \(x^2=X,y^2=Y,z^2=X+Y\)，那么有 \(x^2+y^2=z^2\)。

这一段的长度为 \(z^2+1\)，而使其最小的 \(z=5\)，对应的 \(x=3,y=4\)，所以思考如何向下面的数列中填数：

1 _ _ _ _ _ _ _ _ 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1

前一半有 \(8\) 个空，按照偶数方法填入；后一半有 \(15\) 个空，偶数方法填不完，但是剩下的一个可以考虑组合成距离 \(4\)：

1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 12 11 11 1 12

这样，只用 \(27\) 个数就可以放入三个相同的数，后面按照偶数方法加即可得到任意奇数，前面的无解（\(26\) 已经是放三个的理论最小长度）。

然后就做出来了：

int main()
{
	int T; read(T);
	while(T--)
	{
		int n; read(n);
		if(n&1)
		{
			if(n<27) puts("-1");
			else
			{
				printf("1 2 2 3 3 4 4 5 5 1 6 6 7 7 8 8 9 9 10 10 12 11 11 1 12 ");
				for(int i=1;i<=(n-27)>>1;i++)
					write(i+14,' '),write(i+14,' ');
				putchar('\n');
			}
		}
		else
		{
			for(int i=1;i<=n>>1;i++)
				write(i,' '),write(i,' ');
			putchar('\n');
		}
	}
	return 0;
}

D - Penchick and Desert Rabbit

第一眼：动态规划

第二眼：树状数组优化动态规划（然而打出来发现并不是）

第三眼：图论，拓扑排序，再动态规划（然而全是环，无法拓扑排序）

第四眼：全是环？那不是说每一个连通块都是强联通的咯！并查集维护连通块的同时找块内最大值和最小值，如果当前最大值大于之前的最小值，就可以和前面合并。

#include<cstdio>
#include<algorithm>
using namespace std;

namespace IO{
#ifndef JC_LOCAL
const int SIZE=1<<20; char buf[SIZE],*p1=buf,*p2=buf;
#define getchar() ((p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2))?EOF:*p1++)
#endif
template<typename TYPE> void read(TYPE &x)
{
	x=0; bool neg=false; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')neg=true;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
	if(neg){x=-x;} return;
}
template<typename TYPE> void write(TYPE x)
{
	if(!x){putchar('0');return;} if(x<0){putchar('-');x=-x;}
	static int sta[55];int statop=0; while(x){sta[++statop]=x%10;x/=10;}
	while(statop){putchar('0'+sta[statop--]);} return;
}
template<typename TYPE> void write(TYPE x,char ch){write(x);putchar(ch);return;}
} using namespace IO;

const int N=5e5+5;
int n,a[N],f[N];

namespace Union{

int fa[N],mx[N],mn[N];
void Init()
{
	for(int i=1;i<=n;i++)
		fa[i]=i,mx[i]=a[i],mn[i]=a[i];
	return;
}
int query(int x)
{
	return fa[x]==x?x:fa[x]=query(fa[x]);
}
void merge(int x,int y)
{
	x=query(x),y=query(y);
	mx[x]=max(mx[x],mx[y]);
	mn[x]=min(mn[x],mn[y]);
	fa[y]=x;
	return;
}

} using namespace Union;

pair<int,int> lmax[N];

int main()
{
	int T; read(T);
	while(T--)
	{
		read(n);
		for(int i=1;i<=n;i++)
			read(a[i]);
		Init();
		for(int i=1;i<=n;i++)
		{
			lmax[i]=max(lmax[i-1],{a[i],i});
			merge(i,lmax[i].second);
		}
		int low=0x3f3f3f3f;
		for(int i=n;i>=1;i--)
		{
			if(mx[query(i)]>low) merge(i,i+1);
			low=min(low,mn[query(i)]);
		}
		for(int i=1;i<=n;i++)
			write(mx[query(i)],' ');
		putchar('\n');
	}
	return 0;
}