一点资讯0921编程题参考解题报告

奇怪的电梯

分析

做个bfs,然后记录路径即可,注意打印格式

参考代码

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int maxn = 200 + 5;
int a[maxn], n;
bool flag[maxn];
int p, q;

struct node {
    int x;
    int t; 
} re[maxn];
int pr[205];

int BFS(int st, int et) {
    queue<node> Que;
    fill(flag, flag + maxn, 0);
    node temp;
    temp.x = st, temp.t = 0;
    Que.push(temp); 
    flag[st] = 1; 
    while (!Que.empty()) {
        node ppp = Que.front();
        Que.pop();
        if (ppp.x == et)return ppp.t;
        int x = ppp.x;
        if (x - a[x] >= 1 && !flag[x - a[x]]) {
            flag[x - a[x]] = 1;
            temp.x = x - a[x];
            temp.t = ppp.t + 1;
            pr[temp.x] = x;
            Que.push(temp);
        }
        if (x + a[x] <= n && !flag[x + a[x]]) {
            flag[x + a[x]] = 1;
            temp.x = x + a[x];
            temp.t = ppp.t + 1;
            pr[temp.x] = x;
            Que.push(temp);
        }
    }
    return -1;
}
void pri(int sx) {
    if( sx < 1) {
        return ;
    }
    pri(pr[sx]);
    if(sx == q)
        printf("%d\n", sx);
    else
        printf("%d ", sx);
}
int main() {
    scanf("%d%d%d", &n, &p, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int ans = BFS(p, q);
    printf("%d\n", ans);
    if(ans != -1) pri(q);
    return 0;
}

二进制1的个数

分析

直接统计每个数也行。这里使用了GCC的一个内置函数__builtin_popcount() 功能就是统计二进制1的个数，注意一下打印格式就好了。

参考代码

#include <iostream>

using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    if(n == 0){
        printf("[0]\n");
        return 0;
    }
    printf("[0,");
    for(int i = 1; i <= n; i++){
        if(i == n) printf("%d]",__builtin_popcount(i));
        else printf("%d,",__builtin_popcount(i));
    }
    printf("\n");
}