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

Great Deceiver

https://ac.nowcoder.com/acm/contest/7852/C

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;
}

全部评论

相关推荐

用户64975461947315:这不很正常吗,2个月开实习证明,这个薪资也还算合理,深圳Java好多150不包吃不包住呢,而且也提前和你说了没有转正机会,现在贼多牛马公司骗你说毕业转正,你辛辛苦苦干了半年拿到毕业证,后面和你说没hc了😂
点赞 评论 收藏
分享
昨天 11:16
湖南大学 Web前端
我看到好多人都在说0offer好焦虑,结果一看是投了百度快手字节啥的。好像大家都是只想通过校招进大厂,对小公司是不考虑的吗😂可是能进大厂的难道不是只有少部分人吗,真心发问
梦想是成为七海千秋:沉默的大多数吧,喜欢晒的都是能引起共鸣的大厂,找小厂的人,别人也不认识你这个小厂,就自己偷偷找了实际上大多数人哪有什么机会能找到大厂
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务