部门网站建设管理报告,提供商城网站,青海住房和城乡建设厅网站,设计素材网站破解文章目录第一题 AcWing 4867. 整除数一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第二题 AcWing 4868. 数字替换一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第三题 AcWing 4869. 异或值一、题目1、原题…
文章目录第一题 AcWing 4867. 整除数一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第二题 AcWing 4868. 数字替换一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第三题 AcWing 4869. 异或值一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解第一题 AcWing 4867. 整除数
一、题目
1、原题链接 4867. 整除数 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/k1)*k。 4如果当前数不是k的倍数则答案也为(n/k1)*k。 4所以直接输出(n/k1)*k即为答案。
2、时间复杂度
时间复杂度为O(1)
3、代码详解
我的思路的代码
#include iostream
using namespace std;
int n,k;
int main(){scanf(%d%d,n,k);int tn/k;while(1){if(t*kn){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 tn/k;cout(t1)*k;return 0;
}第二题 AcWing 4868. 数字替换
一、题目
1、原题链接 4868. 数字替换 2、题目描述 给定两个整数 n,x。 你可以对 x 进行任意次以下操作 选择 x 的一位数字 y将 x 替换为 x * y。 请你计算通过使用上述操作将 x 变为一个 n 位数字不含前导 0所需要的最少操作次数。 例如当 n3,x2 时对 2 进行如下 4 次操作即可使其变为 3 位数字 将 2 替换为 2×24。将 4 替换为 4×416。将 16 替换为 16×696。将 96 替换为 96×9864。 输入格式 共一行包含两个整数 n,x。 输出格式 一个整数表示将 x 变为一个 n 位数字所需要的最少操作次数。 如果无解则输出 -1。 数据范围 所有测试点满足 2≤n≤191≤x10n−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 ans0x3f3f3f3f;
void dfs(LL x,int sum){ //sum代表当前操作次数bool st[10]{0}; //st[]存储0~9是否在x的某一位数字出现过int cnt0; //记录x一共有多少位数LL kx; //为避免后续统计x一共有多少位数时改变x的值将k暂存x的值用k来完成后续统计//统计x一共有多少位数已经0~9是否出现过while(k){cnt; st[k%10]true;k/10;}if(sumn-cntans) return ; //如果当前操作次数相差的位数比已经搜到的总操作次数要大或相等则说明该分枝的情况一定不如已收获的结果最优没有必要向下搜索直接回溯即可if(cntn){ //搜到一组答案记录结果 ansmin(ans,sum);return ;}//从大到小枚举看是否在x中出现过如果出现过继续向下搜索for(int i9;i2;i--){ //相乘0或1只会让结果更差不会得到最优解没必要枚举if(st[i])dfs(x*i,sum1); //自带回溯}
}
int main(){cinnx;dfs(x,0); //记得调用if(ans0x3f3f3f3f) cout-1;else coutans;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≤1050≤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]最高位^1d最高位异或值为1所以需要加上该位代表的数d为最高位的位置。这两个分枝的最大值即为左子树的最大值的最小值。如果x的最高位为1走0分枝所求应为dp[l]最高位^1d最高位异或值为1所以需要加上该位代表的数d为最高位的位置如果走0分枝所求应为dp[r]。这两个分枝的最大值即为右子树的最大值的最小值。
然后求解完毕后因为求的是最小值所以直接将两种情况求出的结果取一个最小值即为答案。
2、时间复杂度
时间复杂度为O(nlogn)
3、代码详解
#include iostream
#include algorithm
using namespace std;
const int N3000010; //Tire数总结点数总共10^5个数每个数30位所以需要开到大于3*10^6
int son[N][2],idx;
int n;
//Tire树按二进制形式从高位到低位按从根到结点的顺序插入每个数
void insert(int n){int p0;for(int i29;i0;i--){int uni1;if(!son[p][u]) son[p][u]idx;pson[p][u];}
}
int dfs(int u,int d){ //u表示结点d表示高度最高位的位置if(d-1) return 0; //已经遍历完叶结点回溯int dp[2];//求子树的确定的最大值的最小值for(int i0;i2;i){int pson[u][i];if(p) dp[i]dfs(p,d-1); //递归求子树确定的最大值的最小值else dp[i]-1; //如果当前结点不存在返回-1}int ans2e9;for(int i0;i2;i){ //枚举x最高位int t0;//枚举左右子树for(int j0;j2;j){if(dp[j]!-1)tmax(t,dp[j]((i^j)d)); //对于左右子树的子树需要左右子树的子树中分枝的最大值即为该左/右子树确定的最大值的最小值}ansmin(ans,t); //在左右子树确定的值中取最小值即为答案}return ans;
}
int main(){cinn;while(n--){int a;cina;insert(a);}coutdfs(0,29);return 0;
}
