首页 > 其他分享 >Getting Zero(Bfs)

Getting Zero(Bfs)

时间:2023-06-21 13:11:12浏览次数:40  
标签:integers Getting int step next Bfs Zero que now

Getting Zero time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Suppose you have an integer v. In one operation, you can:

  • either set v=(v+1)mod32768
  • or set v=(2⋅v)mod32768

You are given n integers a1,a2,…,an What is the minimum number of operations you need to make each ai equal to 0?

Input

The first line contains the single integer n (1≤n≤327681) — the number of integers.

The second line contains n integers a1,a2,… (0≤ai<32768).

Output

Print n integers. The i-th integer should be equal to the minimum number of operations required to make ai equal to 0.

Example input Copy
4
19 32764 10240 49
output Copy
14 4 4 15 
Note

Let's consider each ai:

  • a1=19. You can, firstly, increase it by one to get 2020 and then multiply it by two 1313 times. You'll get 00 in 1+13=14steps.
  • a2=32764. You can increase it by one 44 times: 32764→32765→32766→32767→0.
  • a3=10240. You can multiply it by two 44 times: 10240→20480→8192→16384→0
  • a4=49. You can multiply it by two 15 times.

       :

//Getting Zero:https://www.luogu.com.cn/problem/CF1661B
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,mod=32768;
string s;
int n,t,a[N],f[N],res,num,ans;
bool vis[N];
struct node
{
    int x,step;
};
int bfs(int u)
{
    queue<node>que;
    node str;
    str.x=u,str.step=0;
    que.push(str);
    while(!que.empty()){
        node now=que.front();
        que.pop();
        if(now.x==0) return now.step;
        if(vis[now.x]) continue;
        vis[now.x]=true;
        node next;
        next.x=(now.x+1)%mod,next.step=now.step+1;
        que.push(next);
        next.x=(now.x*2)%mod,next.step=now.step+1;
        que.push(next);
    }
}
int main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        cout<<bfs(n)<<" ";
        memset(vis,false,sizeof vis);
    }
    return 0;
}

 

标签:integers,Getting,int,step,next,Bfs,Zero,que,now
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/17495999.html

相关文章

  • 数据结构代码整理_基于邻接表的拓扑排序(C++_DFS_BFS_递归)
    目录Chat图解基于栈实现(dfs)基于队列实现(bfs)基于递归实现(dfs)Chat1.代码所属的类在数据结构代码整理_基于邻接表存储结构的有向图的实现(C++)2.拓扑排序的思想就是不断找入度为0的节点并将其输出并标记,标记后与他相连的节点的入度都会减一,不断进行标记直至所有的节点都被输出为止......
  • Educational Codeforces Round 82 (Rated for Div. 2)_A. Erasing Zeroes(C++_模拟)
    Youaregivenastring.Eachcharacteriseither0or1.Youwantall1’sinthestringtoformacontiguoussubsegment.Forexample,ifthestringis0,1,00111or01111100,thenall1’sformacontiguoussubsegment,andifthestringis0101,100001o......
  • 关于BFS
    BFS目录Content概述问题思考与性质典型应用优化与扩展Part1概述I.什么是BFS?广度优先搜索(breadthfirstsearch),是以同层可达状态优先,一层层向外扩展的搜索算法。一般以队列实现II.算法基本结构图源:CSDN@sigdIII.动画过程演示通常,bfs会用在遍历图,下面的图生......
  • Zero-Shot, One-Shot, and Few-Shot Learning概念介绍
    导语本文将介绍零样本学习、一次样本学习和少样本学习的概念,它们使得机器学习模型能够在仅有有限数量的示例情况下对对象或模式进行分类和识别。在机器学习中,我们通常需要大量的训练数据来训练模型,以便它能够准确地识别和分类新的输入。然而,在现实世界中,获取大规模标记数据集可能是......
  • 1100. 抓住那头牛(bfs)
    https://www.acwing.com/problem/content/1102/数据范围为1e5实际上还可以再继续细分,加入特判来优化耗时,但是意义不大#include<iostream>#include<cstring>#include<cstdio>#include<queue>usingnamespacestd;constintN=1e5+10;intn,k;boolvis[N];int......
  • 悟空派WuKongPi全志H3(香橙派orangepi zero)折腾记录(u-boot移植)
    最近在某宝上看到一个悟空派,仔细一看这不就是香橙派orangepizero吗,不过它的USB是Type-C,于是我买了一块打算折腾一下。 拿到了首先获取一下u-boot源码,因为板子和香橙派orangepizero一样就直接用香橙派的源码了gitclonehttps://github.com/orangepi-xunlong/u-boot-orange......
  • 马的遍历(对bfs的更深一层探讨)
    题目描述有一个 n×m 的棋盘,在某个点 (x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。输入格式输入只有一行四个整数,分别为 n,m,x,y。输出格式一个 n×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 −1)。输入输出样例输入#1复......
  • 实验 透视表 计数 len np.count_nonzero 正确与否
    实验透视表计数 len np.count_nonzero正确与否结果:len正确 np.count_nonzero错误结论:除去三行干扰行(原值均为缺失值)以外:未过账中,有1行无业务员名称无业务员名称中,有1行未过账即:未过账且无业务员名称有1行未过账且有业务员名称有57行已过账且无业务员名称有57行最......
  • Move Zeroes 移动零、Expression Add Operators 表达式增加操作符
    1.MoveZeroes移动零 Givenanarray nums,writeafunctiontomoveall 0'stotheendofitwhilemaintainingtherelativeorderofthenon-zeroelements.Forexample,given nums=[0,1,0,3,12],aftercallingyourfunction, nums shouldbe [1,3,12,......
  • 图的BFS与DFS
    图Graph1.图的基本介绍1.1为什么要有图众所周知,数据结构中已经有线性表和树结构,但是线性表局限于一个直接前驱和一个直接后继的关系(eg.链表),树也只能有一个直接前驱(即父节点),当我们需要表示多对多的关系时,就需要用到图这个数据结构。1.2举例说明图是一种数据结构,其中节点可......