2020牛客国庆集训派对day5 C Great Deceiver

Description

一句话翻译：找到 [0, n] 上符合k进制和-k进制下表示相同的数字个数

Solution

思路：思维、二进制模拟
显然，对于k和-k进制下相同表示的数字，在偶数位上必须为0(不妨打个表自己看看)
所以只需分析奇数位的排列组合情况，先对n进行k进制下的转换，长度为 , 然后分情况讨论：

• 当位数是偶数时，只需考虑每个奇位数，有k种情况(0, 1, 2.... k - 1)，所以最终答案是
• 当位数是奇数时，从高位开始，找每个偶数位中是否存在大于0，如果存在，该位后面的奇数位都是k种情况,否则就是当前奇数位对应数字种情况。当然，这样计算我们会多次计算到000000这种情况，做一下特殊处理即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll n, k;
int main() {
    #ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false), cin.tie(nullptr);
    #endif
    while(cin >> n >> k) {
      vector<int> v;
      while(n) v.push_back(n % k), n /= k;
      if(v.size() % 2 == 0) { // 偶数位
        ll ans = 1;
        for(int i = 0; i < v.size() / 2; i++) {
          ans *= k;
        }
        cout << ans << "\n";
      } else { // 奇数位
        int i = v.size() - 2;
        for(int flag = 1; i >= 1 && flag; i -= 2) { // 找到大于0的偶数位
          if(v[i]) {
            for(int j = i - 1; j >= 0; j -= 2) {
              v[j] = k - 1;
              flag = 0;
            }
          }
        }
        ll ans = 0, res = 1;
        for(int i = 0; i < v.size(); i += 2) {
          ans += res * v[i]; // 这里不计算0的贡献
          res *= k;
        }
        cout << ans + 1 << "\n"; // 把00000加回来
      }
    }
    return 0;
}