第一题 AcWing 4867. 整除数

一、题目

1、原题链接

4867. 整除数

2、题目描述

给定两个整数 n,k，请你找到 大于 n 且能被 k 整除的最小整数 x。

输入格式*

共一行，包含两个整数 n,k。

输出格式

输出大于 n 且能被 k 整除的最小整数 x。

数据范围

前 4 个测试点满足 1≤n,k≤100。
所有测试点满足 1≤n,k≤10⁹。

输入样例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、原题链接

4868. 数字替换

2、题目描述

给定两个整数 n,x。

你可以对 x 进行任意次以下操作：

• 选择 x 的一位数字 y，将 x 替换为 x * y。

请你计算通过使用上述操作，将 x 变为一个 n 位数字（不含前导 0），所需要的最少操作次数。

例如，当 n=3,x=2 时，对 2 进行如下 4 次操作，即可使其变为 3 位数字：

1. 将 2 替换为 2×2=4。
2. 将 4 替换为 4×4=16。
3. 将 16 替换为 16×6=96。
4. 将 96 替换为 96×9=864。

输入格式

共一行，包含两个整数 n,x。

输出格式

一个整数，表示将 x 变为一个 n 位数字，所需要的最少操作次数。

如果无解，则输出 -1。

数据范围

所有测试点满足 2≤n≤19，1≤x<10ⁿ⁻¹。

输入样例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(n^h)（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、原题链接

4869. 异或值

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≤10⁵，0≤ai≤2³⁰−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]）：

1. 如果x最高位为0,走0分枝所求应为dp[l]；如果走1分枝，所求应为dp[r]+最高位^1<<d（最高位异或值为1，所以需要加上该位代表的数，d为最高位的位置）。这两个分枝的最大值即为左子树的最大值的最小值。
2. 如果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;
}