Lut本科回忆录

更新至M,C…
这家呆不下去了，想去学校了

题M

题意：给定一个数字 $n$，问从 $1$ 到 $n$， $n$ 个数中一共有多少单个数，如 $123$ 由 $1，2，3$ 三个单个数字构成。

解：我们可以枚举一个数由几个单个数构成，当 $n=1234$ 时, 可以将其拆解为 $0-9$， $10-99$ ， $100-999$， $1000-1234$，那么答案就是 $1*(9-0)+2*(99-10+1)+3*(999-100+1)+4*(1234-1000+1)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int get(int x){
    int k = 0; x /= 10;
    while(x){
        k = k * 10 + 9;
        x /= 10;
    }
    return k;
}
int main(){
    int n; cin >> n;
    while(n --){
        int x; cin >> x;
        ll ans = 0;
        for(int i = 1, j = 9; i <= 10; ++ i, j = j * 10 + 9){
            int mx = min(j, x);
            ans = ans + 1ll * (mx - get(mx)) * i;
            if(mx == x) break;
        }
        cout << ans << '\n';
    }
}

题C

题意：给定 $n,k$，并且有长为 $n$ 的数组 $A$ 和长为 $n-1$ 的数组 $B$，其中 $A_i\oplus A_{i+1} =B_i$,
同时对于数组 $A$，满足 A_1\le A_2\le \dots\le A_n,0\le A_i,B_i \le 2\^{30},
对于满足的数组 $A$, 求排列第 $k$ 小的数组 $A$

解：由于 $A_i\oplus A_{i+1} =B_i$，一个 $A_1$ 即可得出所有 $A_i$, 我们求 $B$ 的前缀异或和 $Pre$，那么我们就可以得到 $Pre_i=A_1\oplus A_{i+1}$。

由 $Pre_i=A_1\oplus A_{i+1}$ 得 $A_{i+1} = A_1 \oplus Pre_i$, 即 $A_{i} = A_1 \oplus Pre_{i-1}$。
我们由 $A_1\le A_2\le \dots\le A_n$, 得 $(A_1\oplus Pre_0) \le (A_1\oplus Pre_1)\le \dots\le (A_1 \oplus Pre_{n-1})$。
问题就转成了求第 $k$ 小的 $A_1$。
于是，我们便可以枚举 $A_1$ 的每个二进制位，假设 $A_1$ 某个二进制位为 $x$, 如果要满足上面不递减情况的话结果如下。

即当且仅当 $Pre_i$ 和 $Pre_{i+1}$ 的同一二进制位上两数一样，否则这个 $A_1$ 的这个二进制位就是固定的。最终我们可以知道 $A_1$ 有多少个不固定的二进制位，将其转化为十进制，在满足 $\ge k$ 的条件下，将二进制位补齐乃便是第 $k$ 小的 $A_1$。

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define PII pair<int, int>
#define INF 1ll << 30
#define ll long long
using namespace std;
const int N = 2e6 + 10, MOD = 1e9 + 7;
int b[N], a[35], pre[N];
void solve(){
    ll n, k, num = 1 << 30, a1 = 0; cin >> n >> k;
    for(int i = 1; i < n; ++ i) cin >> b[i]; pre[0] = 0;
    for(int i = 1; i < n; ++ i) pre[i] = pre[i - 1] ^ b[i];
    for(int i = 0; i <= 30; ++ i) a[i] = -1;
    for(int i = 1; i < n; ++ i){
        for(int j = 29; j >= 0; -- j){
            int x = (pre[i - 1] >> j) & 1;
            int y = (pre[i] >> j) & 1;
            if(x + y == 1){
                if(a[j] == -1) a[j] = x, num /= 2;
                else if(a[j] != x){
                    cout << "-1\n";
                    return ;
                }
                break;
            }
        }
    }
    if(k > num) {cout << "-1\n"; return ;} 
    else k --;
    for(int i = 0; k; k >>= 1){
        while(a[i] != -1) i ++;
        a[i] = k & 1;
    }
    for(int i = 0; i < 30; ++ i) if(a[i] == 1) a1 += (1 << i);
    for(int i = 1; i <= n; ++ i){
        a1 ^= b[i - 1];
        cout << a1 << " \n"[i == n];
    }
}
int main(){
    //ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    while(n--) solve();
    return 0;
}