「题解」P8588「JROI-8」雷雨天特别行动科

· · 题解

题目分析

本题题意不难理解，直接翻译题意即可得到朴素的算法：

//核心代码
while(k--)
{
    n++;
    if(!(n%3))
     n/=3;
}

但难点在数据范围：0\leqslant n,k \leqslant 10^{18} 。而上面的方法时间复杂度是 O(k)，无法通过全部数据。分析本题有两个思路，一是打表找规律，二是直接分析。

打表

由于时间复杂度与 k 直接相关，且与 n 的大小无关。故我们给 n 随意赋几个值，打出不同 k 值下的最终结果。

\\先打一个小的表看看
n=114514,k=0~100
[114515 , 38172 , 38173 , 38174 , 12725 , 4242 , 4243 , 4244 , 1415 , 472 ,
 473 , 158 , 53 , 18 , 19 , 20 , 7 , 8 , 3 , 4 , 5 , 2 , 1 , 2 , 1 , 2 , 
1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 
1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 
1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 
1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 1 , 2 , 
1 , 2 , 1]

本来想打一个数据量更大的表，但现在这个已经能看出规律了，我甚至怀疑直接输出1/2就能拿到一堆分数。那，为什么后面的数是1和2，并且呈周期变化呢？

分析

对于任意的 n，有

n=3k+m(k\in \mathbb{N};m=0,1,2).

当 m=0，数 n 的变化是：3k\to 3k+1 \to 3k+2\to (3k+3\to)k+1。

当 m=1，数 n 的变化是：3k+1 \to 3k+2\to (3k+3\to)k+1。

当 m=2，数 n 的变化是：3k+2\to (3k+3\to)k+1。

我们发现，当 k 非常大时，仍然只需要至多 3 步即可让 n 缩小到约为原来的 \frac{1}{3}，故只需要进行不超过 3\log_{3}n 次的运算即可使 n 缩小至 1\sim 2。

当 0\le n \le 2 时，数 n 的变化是：0\to 1\to 2\to 1\to 2\to1...

此时，不论 k 是多少，我们都能直接算出答案。

综上，我们便得到了一个新的算法：若 k 很小，可以直接循环算答案；若 k 很大，则先将 n 缩小至 0\sim 2 再直接算答案。

在这里，我们每循环一次，就直接让 3k+m\to k+1，然后减去相应的次数，最大为 3，因此当 k\le3，我们就可以退出循环。同时，当 n\le 2 时我们也可以退出循环。

注意事项

代码实现

//核心代码
while(k>3&&n>2) 
    {
        long long m=n%3;
        if(!m)
        {
            n=n/3+1;
            k-=3;
        }
        else if(m==1)
        {
            n=(n+2)/3;
            k-=2;
        }
        else if(m==2)
        {
            n=(n+1)/3;
            k--;
        }
    }
//将n缩小，或者k足够小可以直接算
    if(k<=3) //k足够小
     while(k--)
      {
        n++;
        if(!(n%3))n/=3;
      }
    else //或者n为0,1,2
    {
        if(!n)n++,k--;//n为0
        if(k%2)n=3-n;//n为1，2，找规律直接出结果
    }
    cout<<n<<endl;

尾声

这是我退役以来，写的第一道题，也是第一篇题解。

感谢 @MX_DMX ，将我重新拉回算法的世界。纵使没有考上理想的大学，纵使专业与计算机没啥关联，但是，算法，依旧值得热爱。

OI之后，我们仍有无限的未来。