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 位数字：

1. 将 22 替换为 2×2=42×2=4。
2. 将 44 替换为 4×4=164×4=16。
3. 将 1616 替换为 16×6=9616×6=96。
4. 将 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;
}