文章目录
第一题 AcWing 4867. 整除数
一、题目
1、原题链接
2、题目描述
给定两个整数 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
二、解题报告
1、思路分析
我的思路
求出当前的n已经是k的多少倍（即计算n/k），然后在这个倍数的基础上向后枚举，直到满足条件，退出循环，输出答案即可。
y总思路
思路来源：y总讲解视频
y总yyds
（1）分两种情况：如果当前数是k的倍数和当前数不是k的倍数。
（2）如果当前数是k的倍数，则答案应为(n/k+1)*k。
（4）如果当前数不是k的倍数，则答案也为(n/k+1)*k。
（4）所以，直接输出(n/k+1)*k即为答案。
2、时间复杂度
时间复杂度为O(1)
3、代码详解
我的思路的代码
#include <iostream>
using namespace std;
int n,k;
int main(){
scanf("%d%d",&n,&k);
int t=n/k;
while(1){
if(t*k>n){
printf("%d",t*k);
break;
}
t++;
}
return 0;
}
y总思路的代码
#include <iostream>
using namespace std;
int n,k;
int main(){
scanf("%d%d",&n,&k);
int t=n/k;
cout<<(t+1)*k;
return 0;
}
第二题 AcWing 4868. 数字替换
一、题目
1、原题链接
2、题目描述
给定两个整数 n,x。
你可以对 x 进行任意次以下操作：
- 选择 x 的一位数字 y，将 x 替换为
x * y。请你计算通过使用上述操作，将 x 变为一个 n 位数字（不含前导 0），所需要的最少操作次数。
例如，当 n=3,x=2 时，对 2 进行如下 4 次操作，即可使其变为 3 位数字：
- 将 2 替换为 2×2=4。
- 将 4 替换为 4×4=16。
- 将 16 替换为 16×6=96。
- 将 96 替换为 96×9=864。
输入格式
共一行，包含两个整数 n,x。
输出格式
一个整数，表示将 x 变为一个 n 位数字，所需要的最少操作次数。
如果无解，则输出
-1。数据范围
所有测试点满足 2≤n≤19，1≤x<10n−1。
输入样例1：
2 1输出样例1：
-1输入样例2：
3 2输出样例2：
4输入样例3：
13 42输出样例3：
12
二、解题报告
1、思路分析
思路来源：y总讲解视频
y总yyds
（1）利用dfs进行搜索，注意剪枝和优化。
（2）搜索顺序优化：如果需要快速增加x的位数，则乘的数应该越大越好，所以可以从从大到小来枚举是否可以乘（9~0）中的在x中出现过的数。
（3）剪枝：如果我们当前搜索的分枝中，当前已经的操作次数+还至少需要操作的次数（也就是还需要扩大的位数，因为每次操作最多只能扩大一位）>=当前已收获的最优答案，则该分枝一定不如已收获的答案最优，没必要继续搜索，直接回溯即可。
（4）利用上述剪枝与优化方法，进行深搜即可。
2、时间复杂度
时间复杂度为O(nh)（h为深度，n为每个点的分枝数）
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL; //注意数据范围，用long long存
int n;
LL x;
int ans=0x3f3f3f3f;
void dfs(LL x,int sum){ //sum代表当前操作次数
bool st[10]={0}; //st[]存储0~9是否在x的某一位数字出现过
int cnt=0; //记录x一共有多少位数
LL k=x; //为避免后续统计x一共有多少位数时改变x的值，将k暂存x的值，用k来完成后续统计
//统计x一共有多少位数，已经0~9是否出现过
while(k){
cnt++;
st[k%10]=true;
k/=10;
}
if(sum+n-cnt>=ans) return ; //如果当前操作次数+相差的位数比已经搜到的总操作次数要大或相等，则说明该分枝的情况一定不如已收获的结果最优，没有必要向下搜索，直接回溯即可
if(cnt==n){ //搜到一组答案，记录结果
ans=min(ans,sum);
return ;
}
//从大到小枚举，看是否在x中出现过，如果出现过继续向下搜索
for(int i=9;i>=2;i--){ //相乘0或1只会让结果更差，不会得到最优解，没必要枚举
if(st[i])
dfs(x*i,sum+1); //自带回溯
}
}
int main(){
cin>>n>>x;
dfs(x,0); //记得调用
if(ans==0x3f3f3f3f) cout<<-1;
else cout<<ans;
return 0;
}
第三题 AcWing 4869. 异或值
一、题目
1、原题链接
2、题目描述
给定一个长度为 n 的整数序列 a1,a2,…,an。
请你找到一个非负整数 X，使得 max1≤i≤n{ai⊕X} 的值尽可能小，其中 ⊕ 表示按位异或。
输出 max1≤i≤n{ai⊕X} 的最小可能值。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数，表示 max1≤i≤n{ai⊕X} 的最小可能值。
数据范围
前 3 个测试点满足 1≤n≤3。
所有测试点满足 1≤n≤105，0≤ai≤230−1。输入样例1：
3 1 2 3输出样例1：
2输入样例2：
2 1 5输出样例2：
4
二、解题报告
1、思路分析
思路来源：4869. 异或值
y总yyds
（1）首先将所有的数按其二进制的形式从最高位到最低位（Tire树中左分枝存储0，右分枝存储1），由根向结点延伸依次插入Tire树中。
（2）从最高位到最低位依次来确定x的值，x的最高位可能取0或1，针对两个分枝，递归地去求解左右子树确定的最大值的最小值（即dp[l]和dp[r]）：
- 如果
x最高位为0,走0分枝所求应为dp[l]；如果走1分枝，所求应为dp[r]+最高位^1<<d（最高位异或值为1，所以需要加上该位代表的数，d为最高位的位置）。这两个分枝的最大值即为左子树的最大值的最小值。 - 如果x的最高位为
1，走0分枝所求应为dp[l]+最高位^1<<d（最高位异或值为1所以需要加上该位代表的数，d为最高位的位置）；如果走0分枝，所求应为dp[r]。这两个分枝的最大值即为右子树的最大值的最小值。
然后求解完毕后，因为求的是最小值，所以直接将两种情况求出的结果取一个最小值，即为答案。
2、时间复杂度
时间复杂度为O(nlogn)
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
const int N=3000010; //Tire数总结点数，总共10^5个数，每个数30位，所以需要开到大于3*10^6
int son[N][2],idx;
int n;
//Tire树按二进制形式从高位到低位按从根到结点的顺序插入每个数
void insert(int n){
int p=0;
for(int i=29;i>=0;i--){
int u=n>>i&1;
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
}
int dfs(int u,int d){ //u表示结点，d表示高度（最高位的位置）
if(d==-1) return 0; //已经遍历完叶结点，回溯
int dp[2];
//求子树的确定的最大值的最小值
for(int i=0;i<2;i++){
int p=son[u][i];
if(p) dp[i]=dfs(p,d-1); //递归求子树确定的最大值的最小值
else dp[i]=-1; //如果当前结点不存在返回-1
}
int ans=2e9;
for(int i=0;i<2;i++){ //枚举x最高位
int t=0;
//枚举左右子树
for(int j=0;j<2;j++){
if(dp[j]!=-1)
t=max(t,dp[j]+((i^j)<<d)); //对于左右子树的子树，需要左右子树的子树中分枝的最大值，即为该左/右子树确定的最大值的最小值
}
ans=min(ans,t); //在左右子树确定的值中取最小值即为答案
}
return ans;
}
int main(){
cin>>n;
while(n--){
int a;
cin>>a;
insert(a);
}
cout<<dfs(0,29);
return 0;
}
