葵桥

用户名：uq_42639897424

访问量：611

签　名：

等　　级
排　　名	37797
经　　验	385
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

c++ 参考代码
浏览：205

你可能喜欢

c++ 参考代码

　　作者: 葵桥　　　　发表时间：2023-06-05 16:48:57 浏览：205　|　评论：0　

原题链接：蓝桥杯2022年第十三届决赛真题-最少的 1（C/C++/Java组）

// 任何一个数字都可以通过二进制表示

```c++
// 任何一个数字都可以通过二进制表示
// 也就是通过对 初始值为 1 的数字反复的左移（乘以 2） 和 + 1 可以得到任意的数字
// 例如 1101 (括号为进行的操作)
// 1 -> 10(x2) -> 11(+1) -> 110(x2) -> 1100(x2) -> 1101(+1)
// x2 操作记作消耗为 0（不会改变 1 的数目）， +1 操作记作消耗为1
// 而 n 的倍数 mod n 一定等于 0
// 所以 对 1 进行上述操作使得其 mod n 为 0 需要进行的最小消耗即为答案
// 转换为了 最短路问题

#include<iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 1E6 + 10;
int d[N];
int n;
bool st[N];

void dijkstra() {
    memset(st, 0, sizeof st);
    memset(d, 0x3f, sizeof d);

deque<int> q;
    q.push_back(1);
    d[1] = 1;
    while(q.size()) {
        auto t = q.front();
        q.pop_front();
        if(st[t]) continue;
        st[t] = true;
        // if(!t) return ;
        int tt;
        // 操作1 
        tt = (2 * t) % n;
        if(d[tt] > d[t]) {
            d[tt] = d[t];
            q.push_front(tt);
        }
        // cout << tt << " ";
        // 操作2
        tt = (t + 1) % n;
        if(d[tt] > d[t] + 1) {
            d[tt] = d[t] + 1;
            q.push_back(tt);
        }
        // cout << tt << endl;
    } 
}

int main(){
    cin >> n;
    dijkstra();

cout << d[0] << endl;
    return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

葵桥

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列（C语言代码）

【明明的随机数】（C语言代码）

整除问题（C语言代码）

IP判断（C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

c++ 参考代码

评论区

精彩推荐

简单编码（C++代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

简单的a+b （C++语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

淘淘的名单（C语言代码）答案错误？？？

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【偶数求和】（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

Tom数（C语言代码）

葵桥

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列 （C语言代码）

【明明的随机数】 （C语言代码）

整除问题 （C语言代码）

IP判断 （C++代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

c++ 参考代码

评论区

精彩推荐

简单编码 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

简单的a+b （C++语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

淘淘的名单 （C语言代码）答案错误？？？

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

【偶数求和】 （C语言代码）

三角形 （C++代码）递归（存在大量重复计算，容易出现时间超限）

Tom数 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

【明明的随机数】（C语言代码）

整除问题（C语言代码）

IP判断（C++代码）

　　评论区

简单编码（C++代码）

淘淘的名单（C语言代码）答案错误？？？

【偶数求和】（C语言代码）

三角形（C++代码）递归（存在大量重复计算，容易出现时间超限）

Tom数（C语言代码）