更新至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;
}