P10172 Pick Stone 题解

· · 题解

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<<' '; 
        }
    }
}

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