CF-[CF1836C] k-th equality 题解

XSean · 2023-06-20 11:55:06 · 题解

C：k-th equality

C - k-th equality

基本思路：

假设式子是 a + b = c。

由 A 暴力枚举 a 的范围，由 B 与 C 确定 b 的范围，也就知道了一个 a 对应了多少的 b，与 k 不断对比即可。

时间复杂度：O(10^A)

为什么可以这样的复杂度，t 都有 10^3 诶？请看这句话：

Each input file has at most 5 test cases which do not satisfy A, B, C \leq 3.

最多有 5 个测试用例不满足 A, B, C \leq 3。

代码实现：

核心代码：

int qmi(LL a, int k){
    int res = 1;
    for(; k; k >>= 1, a = a * a) if(k & 1) res = res * a;
    return res;
}
void ans(int a, int b){
    prf("%d + %d = %d\n", a, b, a + b);
}
int main(){
    int T; rd(T);
    while(T--){
        LL a, b, c, k; rd(a, b, c, k);
        bool f = true;
        int l = qmi(10, a - 1), r = qmi(10, a) - 1;
        rep(i, l, r){
            int L = max(qmi(10, b - 1), qmi(10, c - 1) - i);
            int R = min(qmi(10, b) - 1, qmi(10, c) - 1 - i);
            if(L > R) continue;
            int temp = R - L + 1;
            if(k <= temp){
                ans(i, L + k - 1);
                f = false;
                break;
            }
            k -= temp;
        }
        if(f) puts("-1");
    }   
    return 0;
}

完整代码