第一题 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;
}