AT2163 [AGC006B] Median Pyramid Easy

洛谷题面

题目大意

给出一个 \(n\) 层的方格金字塔,自顶向下依次标号为第 \(1\) 到第 \(n\) 层。

其中第 \(i(1\le i\le n)\) 层有 \(2i-1\) 个方格。

AT2163 [AGC006B] Median Pyramid Easy

第 \(n\) 层有一个 \(1\) 到 \(2n-1\) 的排列,其他层的数字按以下规则生成:方格 \(b\) 中填写的整数,是方格 \(b\) 正下方,左下方和右下方方格中所写整数的中位数。

现在请你构造出一组第 \(n\) 层的数字,使得求得的第一层的数字为 \(x\)。

题目分析

考虑最后一层为以下情况:

\[\cdots,y,x-1,x,x+1,z\cdots \]

若 \(y\ge x\),则有:

\[\cdots,x,x,\cdots \]

\[\cdots,y,x-1,x,x+1,z\cdots \]

若 \(y\lt x\),则显然有:

\[\cdots,x-1,x,\cdots \]

\[\cdots,y,x-1,x,x+1,z\cdots \]

\(z\) 也是类似的。

这个情况可以向上类推,直到第一层。

于是可以发现:最后一层中,不论除中间三个数之外的数如何排列,都不会影响中间的顺序。

得出结论:只需要将 \(x\) 放在第 \(n\) 层的中间即可满足条件。

代码

//2021/11/29

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <climits>//need "INT_MAX","INT_MIN"

#define enter() putchar(10)

#define debug(c,que) cerr<<#c<<" = "<<c<<que

#define cek(c) puts(c)

#define blow(arr,st,ed,w) for(register int i=(st);i<=(ed);i++)cout<<arr[i]<<w;

#define speed_up() cin.tie(0),cout.tie(0)

#define endl "\n"

#define Input_Int(n,a) for(register int i=1;i<=n;i++)scanf("%d",a+i);

#define Input_Long(n,a) for(register long long i=1;i<=n;i++)scanf("%lld",a+i);

namespace Newstd
{
	inline int read()
	{
		int x=0,k=1;
		char ch=getchar();
		while(ch<'0' || ch>'9')
		{
			if(ch=='-')
			{
				k=-1;
			}
			ch=getchar();
		}
		while(ch>='0' && ch<='9')
		{
			x=(x<<1)+(x<<3)+ch-'0';
			ch=getchar();
		}
		return x*k;
	}
	inline void write(int x)
	{
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		if(x>9)
		{
			write(x/10);
		}
		putchar(x%10+'0');
	}
}

using namespace Newstd;

using namespace std;

const int MA=100005;

int a[MA*2];

int n,x;

int main(void)
{
	n=read(),x=read();
	
	if(x==1 || x==2*n-1)
	{
		puts("No");
		
		return 0;
	}
	
	puts("Yes");
	
	a[n-1]=x-1,a[n]=x,a[n+1]=x+1;
	
	int now=1;
	
	for(register int i=1;i<=n-2;)
	{
		if(now==x-1 || now==x || now==x+1)
		{
			now++;
		}
		
		else
		{
			a[i]=now;
			
			now++;
			
			i++;
		}
	}
	
	for(register int i=n+2;i<=2*n-1;)
	{
		if(now==x-1 || now==x || now==x+1)
		{
			now++;
		}
		
		else
		{
			a[i]=now;
			
			now++;
			
			i++;
		}
	}
	
	blow(a,1,2*n-1,endl);
	
	return 0;
}
上一篇:O - Median Maximization


下一篇:模块的多级导入,或者叫嵌套的处理。如何避免修改模块