AcWing第 93 场周赛
4867. 整除数
给定两个整数 n,k，请你找到大于 n 且能被 k 整除的最小整数 x。
输入格式
共一行，包含两个整数 n,k。
输出格式
输出大于 n 且能被 k 整除的最小整数 x。
数据范围
前 4 个测试点满足 1≤n,k≤100。
所有测试点满足 1≤n,k≤109。
输入样例1：
5 3
输出样例1：
6
输入样例2：
25 13
输出样例2：
26
输入样例3：
26 13
输出样例3：
39#include<bits/stdc++.h>
using namespace std;
int main(){long long n,k;cin>>n>>k;cout<<(n/k+1)*k;return 0;
}4868. 数字替换
给定两个整数 n,x。
你可以对 x 进行任意次以下操作：
- 选择 x� 的一位数字 y�，将 x� 替换为 x×y�×�。
请你计算通过使用上述操作，将 x� 变为一个 n� 位数字（不含前导 00），所需要的最少操作次数。
例如，当 n=3,x=2�=3,�=2 时，对 22 进行如下 44 次操作，即可使其变为 33 位数字：
- 将 22 替换为 2×2=42×2=4。
- 将 44 替换为 4×4=164×4=16。
- 将 1616 替换为 16×6=9616×6=96。
- 将 9696 替换为 96×9=86496×9=864。
输入格式
共一行，包含两个整数 n,x�,�。
输出格式
一个整数，表示将 x� 变为一个 n� 位数字，所需要的最少操作次数。
如果无解，则输出 -1。
数据范围
所有测试点满足 2≤n≤192≤�≤19，1≤x<10n−11≤�<10�−1。
输入样例1：
2 1
输出样例1：
-1
输入样例2：
3 2
输出样例2：
4
输入样例3：
13 42
输出样例3：
12#include <bits/stdc++.h>
using namespace std;int n, ans = 2e9;
long long x, st;
map<long long, int> used;int bfs()
{unordered_map<unsigned long long, int> s;queue<long long> q;q.push(x);while (q.size()){long long t = q.front();q.pop();for (long long p = t; p; p /= 10){if (p % 10 == 0 || p % 10 == 1) continue;unsigned long long k = p % 10 * t;if (s[p % 10 * t]) continue;q.push(k), s[k] = s[t] + 1;if (k >= st) return s[k];}}return -1;
}int main()
{scanf("%d%lld", &n, &x);st = pow(10, n - 1);printf("%d", bfs());return 0;
} 4869. 异或值
给定一个长度为 n� 的整数序列 a1,a2,…,an�1,�2,…,��。
请你找到一个非负整数 X�，使得 max1≤i≤n{ai⊕X}max1≤�≤�{��⊕�} 的值尽可能小，其中 ⊕⊕ 表示按位异或。
输出 max1≤i≤n{ai⊕X} 的最小可能值。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数，表示 max1≤i≤n{ai⊕X} 的最小可能值。
数据范围
前 33 个测试点满足 1≤n≤3。
所有测试点满足 1≤n≤105，0≤ai≤230−1。
输入样例1：
3
1 2 3
输出样例1：
2
输入样例2：
2
1 5
输出样例2：
4
#include <iostream>
using namespace std;
const int N = 100010,M = 31 * N;
int n;
int a[N];
int tr[M][2],cnt[M],idx;
void insert (int x) {int u = 0;for (int i = 30;i >= 0;i--) {int t = x >> i & 1;if (!tr[u][t]) tr[u][t] = ++idx;u = tr[u][t];}cnt[u]++;
}
int query (int u,int k) {if (tr[u][0] && tr[u][1]) return (1 << k) + min (query (tr[u][0],k - 1),query (tr[u][1],k - 1));if (tr[u][0]) return query (tr[u][0],k - 1);if (tr[u][1]) return query (tr[u][1],k - 1);return 0;
}
int main () {cin >> n;for (int i = 1;i <= n;i++) {cin >> a[i];insert (a[i]);}cout << query (0,30) << endl;return 0;
}