All Possible Digits

Created by LXC on Sat Oct 21 08:15:45 2023

https://codeforces.com/problemset/problem/1759/F

ranting: 1800

tag: binary search, data structures, greedy, math, number theory

problem

给出一个数组$a_1, a_2, \cdots, a_n$以及一个整数p，代表着一个n位p进制数。

现在你可以对这个p进制数进行加1操作，求0到p-1每个数都曾出现过的操作次数。

solution

比较麻烦的模拟。

我们可以先统计$1…a_n$是否全部出现过，如果出现过则从p-1到$a_n$寻找第一个没有出现的数x。答案就是$x-a_n$

否则我们需要让$a_n$一直加一操作直到其进位，所花操作次数为$p-a_n$，并且进位后会导致高位连续进位。我们模拟这个进位过程，并统计新出现的数。

然后从$a_n$到0寻找第一个为出现的数x，答案为$x+p-a_n$

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    ll n, p;
    cin >> n >> p;
    set<ll> st;
    vector<ll> a(n+1);
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        st.insert(a[i]);
    }
    // 0 到 a[n-1] 都存在
    int ok = 1;
    for (int i=a[n]; i>=0; i--) {
        if (st.count(i) == 0) {
            ok = 0;
            break;
        }
    }
    if (ok) {
        int i;
        for (i=p-1; i>a[n]; i--) {
            if (st.count(i) == 0) {
                break;
            }
        }
        cout << (i-a[n]) << "\n";
    } else {
        st.insert(0);
        for (int i=n-1; i>=0; i--) {
            if (a[i] != p-1) {
                st.insert(a[i]+1);
                break;
            }
        }
        for (int i=a[n]-1; i>=0; i--) {
            if (st.count(i) == 0) {
                cout << i+p-a[n] << "\n";
                return ;
            }
        }
        cout << p-a[n] << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}