题解：AT_arc112_b [ARC112B] -- - B

思路

步骤 1

若有一条数轴，可以将他分成正半轴、负半轴和

{0}

！

操作 1 不能连续用，因为 ${-1 \times -1 = 1}$ 。
操作 2 总是向左得到数。因为 ${C - 2}$ ， ${B - 1}$ 。

步骤 2

那，如何向右得到数呢？
很简单，只需要遵照这几步：

只需要先使用一次操作 1；（当且仅当 ${B}$ 是一个正数，负数跳过这一步）
再使用任意多次操作 2；
最后使用一次操作 1。

步骤 3

那么根据

{C}

的奇偶性来讨论：

若 ${C \bmod 2 = 1}$ ，说明我们应该可以使用奇数次操作 1（假设其是 ${p}$ 次）并且可以使用 ${(C - p) \div 2}$ 次操作 2。

奇数次使用操作 1，不代表不可以向右扩展！我们可以使用偶数 ${+1}$ 次，这样的话就可以向右扩展！

若 ${C \bmod 2=0}$ ，满足了向右扩展不会剩下任何钱；同时，也可以选择要么全部使用操作 2 或使用偶数次操作 1。

步骤 4

此时，可以使用桶来存储可以得到的数。

因为桶就有去重作用！

大体代码

CPP

#include<iostream>
using namespace std;
using ll=long long;
ll buk[1000000],tms,bse,s;
int main()
{
    /*这里我选择使用操作 1 和操作 2 连续使用，能保证要么最后的操作 1 可以用上，要么不操作*/
    scanf("%lld%lld",&bse,&tms);
    bse=bse<0?-bse,tms--:bse;                                   //跟下面的操作有关。
    buk[bse]=1;
    if(bse==0)
    {
        return printf("%d",tms/2+tms/1-1);//0不是负数，所以不能乘上 -1！
    }
    while(tms>=0)
    {
        if(tms>=1)
        {
            buk[bse]++;             //注意，由于 C++ 不能操纵负数组，我就将数组压缩成正负半轴一起用。
            tms--;
        }
        if(tms%2==0)
        {
            buk[--bse]++;
            tms-=2;
        }
    }
    for(int i=0;i<1000000;i++)
    {
        s+=buk[i];                   //完结撒花
    }
    return 0;
}

提示

使用 long long 来存储。因为 long long 的范围是 ${-2^{63}}$ 到 ${2^{63}-1}$ ，这个值的极限在 ${-10^{18}}$ 外或 ${10^{18}}$ 外。
对于 ${0}$ 的情况，两种（见步骤 3）都可以用！
岛国水题需要换行！

题解：AT_arc112_b [ARC112B] -- - B

文章操作

思路

步骤 1

步骤 2

步骤 3

步骤 4

大体代码

提示

相关推荐

评论

题解：AT_arc112_b [ARC112B] -- - B