P7893 『JROI-3』Reversi 题解

· · 题解

PART 0：说些闲话

这是去年十月份打的比赛，应该算我打的第一场月赛吧，最近突然想起来就来看看，发现还可以交题解就写一篇。

我才不会说是来贺快读模板的呢

PART 1：题目大意

在 [1,n] 中取若干个整数，使得 k 和 k \times p 不同时被选中，求最多能够选择多少个整数。

PART 2：解题思路

首先阐述一下我们的策略，从大往小去选，一旦这个数 k 可以被选择，也就是说 k\times p 没有被选择，我们就选取它，这样一定是最优的。这是本蒟蒻比赛时的猜测。

当时水平太弱，误打误撞写出了正解，现在来想想为什么这样是对的？

原因很简单。我们依照这种方式，可以把 [1,n] 上的整数分为若干段：(\dfrac{n}{p},n],(\dfrac{n}{p^2},\dfrac{n}{p}],(\dfrac{n}{p^3},\dfrac{n}{p^2}],(\dfrac{n}{p^4},\dfrac{n}{p^3}]\dots。总共是 \left\lceil\log_pn\right\rceil 段，其中，第 i 段所含有的元素个数是 \dfrac{n(p - 1)}{p^i} 个。这样分段有什么好处呢？我们很容易发现，同一段中的任意数都可以被同时选中，于是我们来考虑一段一段的选。显而易见，选取越靠前的段，最终得到的元素个数就越多，所以显然是尽可能地选取较大的数，也就是我们这里较靠前的段是最优的。同时我们发现，相邻的两段是不能够被同时选取的，也就是说，最终的策略是选取第 1,3,5,7,\dots 段。

但是这样实现起来似乎很复杂，有没有什么简单的方式呢？

当然是有的，这里先放出代码来：

long long ans = 0;
for(long long i = 1; n > 0; i = -i, n /= p){
    ans += i * n;
}
printf("%lld\n",ans)

模拟一下即可理解：先加上 n，然后减去 \dfrac{n}{q}，再加上 \dfrac{n}{q^2}，……以此类推，这样的结果就和上面我们说的策略是一样的了。

PART 3：完整代码

#include<bits/stdc++.h>
#define MAXN 1000010
using namespace std;
long long t,n,p;
bool vis[MAXN];
inline long long read(){
   long long s = 0, w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); }
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}
int main(){
    t = read();
    while(t--){
        n = read(); p = read();
        if(p == 1){
            printf("0\n");
            continue;
        }
        long long ans = 0;
        for(long long i = 1; n > 0; i = -i, n /= p){
            ans += i * n;
        }
        printf("%lld\n",ans);
    }
}