自动搬运

查看原文

来自洛谷，原作者为

	zSqr_Mahiro_Oyama 自宅一级警备员 || 你凭什么定义我的性别

搬运于2025-08-24 22:55:23，当前版本为作者最后更新于2024-02-20 13:48:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10172 Pick Stone 题解

题目传送门

分析部分：

$\text{Subtask 1}$

按顺序取走即可。取走石子数量为 $m$。

$\text{Subtask 2}$

第一行取完后，第二行从第一个石子开始取，隔一个取一个即可。取走石子数量为 $m+\displaystyle{\lceil \frac{m}{2} \rceil}$。

$\text{Subtask 3}$

构造第三行。

我们先看到第 $2$ 个样例。就是出了错的那个

输入：

3 5

我构造的输出：（稍微对齐了一点）

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

没看懂？再来一组：

输入：

3 10

我构造的输出：

23
1  2  3  4  5  6  7  8  9 10
11 -1 12 -1 13 -1 14 -1 15 -1
16 17 -1 19 18 20 -1 22 21 23

发现了什么？

取的棋子像这样分布：（*为取的石子，.为不取的）

**********
*.*.*.*.*.
**.***.***

即，先取前两个，隔一个，取三个，隔一个，取三个……

中间的石子上边一定是第二行中的第奇数个取到的石子。

取的顺序也有讲究。因为按顺序取的话，取完三个中左边的石子，中间的石子它的左边和上边的石子都被取了，它就不能取了。所以要先取中间的石子，再取它左边和右边的石子。

还有若是中间的取不到（在范围之外），左边的能取到，就不要多标记中间的，只要标记左边的那个就可以了。

取走数量为 $2m+\displaystyle{\lceil \frac{m}{4} \rceil}$。（或者，构造完第三行后统计取走数量与第一、二行数量相加，如果你不信任我的话。）

代码部分：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];//第三行中对应石子是第几个取的，不取为0
int main(){
	cin>>n>>m;
	if(n==1){
		cout<<m<<endl;
		for(int i=1;i<=m;i++)
			cout<<i<<' ';//顺序取走
	}
	if(n==2){
		cout<<m+(m+1)/2<<endl;
		for(int i=1;i<=m;i++)
			cout<<i<<' ';
		cout<<endl;
		int cnt=m+1;
		for(int i=1;i<=m;i++)
			cout<<(i&1?cnt++:-1)<<' ';//隔一个取一个
	}
	if(n==3){
		int cnt=0;//第三行中取到了多少个棋子
		for(int i=1;i<=m+1;i++){//构造，枚举中间石子，枚举到m+1是为了确保中间取不到而左边取得到的情况不被漏掉
			if((i&1)&&(i/2)%2==0){//第三行每组中间的石子必定与第二行中第奇数个取到的石子对齐
				if(i>=1&&i<=m)a[i]=++cnt;//中间
				if(i>1)a[i-1]=++cnt;//左边
				if(i<m)a[i+1]=++cnt;//右边
			}
		}
		cout<<2*m+(m+3)/4<<endl;
		for(int i=1;i<=m;i++)
			cout<<i<<' ';
		cout<<endl;
		for(int i=1;i<=m;i++)
			cout<<(i&1?m+(i+1)/2:-1)<<' ';
		cout<<endl;
		for(int i=1;i<=m;i++){
			if(a[i])cout<<m+(m+1)/2+a[i]<<' ';//前面取了m+(m+1)/2个
			else cout<<-1<<' '; 
		}
	}
} 

蒟蒻第一篇题解，求管理通过！