P7893 『JROI-3』黑白棋 题解

· · 题解

比较简单的一道题。

大致题意

第 k 个棋子和第 k \times p 个不能同时变成白色。

思路

对于每一次游戏，我们可以倒着进行染色。

这样就能分成一大段一大段来进行染色。

大致的操作就是，我们选一个变量 ans。

每一个奇数次。

都有：

ans += n - n / p;

至于偶数次，就不需要有这样的操作。

当然，每次操作后，都需要更新 n。

n /= p;

上面两行就是代码的核心部分了。

关于正确性

可以用调整法来证明。

由于我们上面的核心代码选的是这个数字区间可以同时选择所有最后面的一段。

所以我们发现若是将其中一个数调整成前面的某数，那么他不仅会对第 [\frac{k}{p}] 个数产生影响，同样会对第 kp 个数产生影响，所以答案不会更优。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t , n , p , ans , flag;

int read()
{
    int X = 0 , W = 1;
    char qwe = getchar();
    while(!isdigit(qwe))
    {
        if(qwe == '-') W=  -1;
        qwe =  getchar();
    }
    while(isdigit(qwe)) X = (X * 10 + (int)(qwe - '0')), qwe = getchar();
    return X * W;
}

signed main()
{
    t = read();
    while(t--)
    {
        n = read() , p = read() , ans = 0 , flag = 1;
        if(p == 1)
        {
            cout << 0 << endl;
            continue;
        }
        while(n)
        {
            if(flag) ans += n - n / p;
            n /= p;
            flag ^= 1;
        }
        printf("%lld\n" , ans);
    }
    return 0;
}

完结撒花！