数字游戏【牛客tracker 每日一题】

发布时间：2026/7/1 3:01:33

数字游戏时间限制3秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述d d dddd在玩数字游戏首先他拿到一个x xx当x xx不为零时进行如下操作如果二进制x xx中有奇数个1 11则x xx二进制形式下最低位取反即0 00变成1 11,1 11变成0 00如果二进制x xx中有偶数个1 11则x xx二进制形式下非前导零最高位取反询问对于一个x xx操作几次后变为零输入描述第一行一个正整数( 1 ≤ T ≤ 1000000 ) (1≤T≤1000000)(1≤T≤1000000)表示询问组数接下来T TT行每行一个数x 0 ≤ x ≤ 1000000000 x0≤x≤1000000000x0≤x≤1000000000表示询问的数字由于本题数据量比较大请选择较快的读入方式输出描述输出T TT行每行是对应的答案示例1输入3 0 1 5输出0 1 2解题思路本题属于模拟优化类问题通过分析操作规则的奇偶性交替规律将操作过程提炼为“消最高位调最低位”的固定循环避免逐次重复判断1的个数实现高效求解完美适配百万级查询规模。核心规律推导根据操作规则二进制中1的个数的奇偶性会随操作交替翻转形成固定循环偶数个1时翻转最高位的11的个数减1变为奇数操作数1。奇数个1时翻转最低位1的个数奇偶性翻转变回偶数操作数1。因此除初始奇偶调整与最终零值收尾外操作过程以“翻最高位翻最低位”为两步固定循环逐步消去高位的1最终将x变为0。算法执行步骤初始奇偶调整统计x的二进制中1的总个数若为奇数先执行一次最低位翻转将状态统一为“偶数个1”的循环初始态操作数加1。循环消去高位当x非零时重复执行定位当前x的最高有效位将其翻转1变0操作数1。若翻转后x已为0直接退出循环无需再执行最低位翻转。否则翻转最低位操作数1回到循环开头继续处理。输出累计的总操作次数。由于x最大不超过10 9 10^9109二进制位数不超过30位单次查询最多循环30次总时间复杂度为O ( T × 30 ) O(T \times 30)O(T×30)可轻松应对百万级查询规模。总结核心逻辑利用操作的奇偶交替特性将过程简化为固定两步循环从高位到低位逐步消去1快速计算操作次数。关键操作初始奇偶性统一、最高位定位与翻转、零值提前终止、最低位同步调整。效率保障单轮查询仅需常数次位运算配合快速IO读写轻松处理百万级查询数据。代码简要说明快速读入函数rd通过getchar实现高速数字读取适配百万级输入量避免IO超时。1的个数统计遍历32个二进制位统计x中1的总数用于判断初始是否需要调整最低位。初始状态统一若1的个数为奇数翻转最低位并累加操作数将所有输入统一为偶数个1的初始循环态。主循环处理变量now跟踪当前最高位的权值通过右移快速定位当前x的最高有效位避免重复遍历。翻转最高位后累加操作数若x变为0则直接跳出循环省略多余的最低位翻转。非零则翻转最低位再次累加操作数进入下一轮循环。高效输出使用printf输出每组查询的答案保证大规模输出下的运行效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;llrd(){charcgetchar();ll d0,f1;while(c0||c9){if(c-)f-1;cgetchar();}while(c0c9){d(d3)(d1)c-48;cgetchar();}returnd*f;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll nrd();while(n--){ll xrd();ll now1;ll g0;for(ll i0;i32;i){if(xnow)g;now1;}ll ans0;if(g1){x^1;ans;}while(x){while(!(xnow))now1;x^now;ans;if(!x)break;x^1;ans;}printf(%lld\n,ans);}return0;}

数字游戏【牛客tracker 每日一题】

相关新闻

3分钟掌握深度学习漫画翻译神器：BallonsTranslator完全指南

FastAPI 基础篇：类型注解驱动的 Python Web 开发范式

村花云 - 高性价比云服务器服务平台

OmAI联汇发布全球首个端侧流式多模态模型VLX，开启物理世界AI全新范式

深度学习记录-CNN

外卖接单出餐一体机实测报告：500家门店踩坑总结 + 架构级避坑指南

【RTL8733BU `rtw_proc.c` WiFi Feature 查询说明】

Start Setup Orcad

2026 年人形机器人产能扩张、价格暴跌，C 端普及之路还有多远？

管理者的六个层次

AI Coding 六个月真实ROI账本：产品经理的血泪教训，研发的冷静忠告

审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？

Coze与Dify对比指南：低代码AI应用开发从入门到实战

AI生图工具怎么选？2026年6月版实测对比

国产DSP FT-M6678 DDR3配置避坑指南：从PLL时钟到PHY寄存器，手把手调通你的第一块板

Coze与Dify对比指南：低代码AI应用开发从入门到实战

AI生图工具怎么选？2026年6月版实测对比

国产DSP FT-M6678 DDR3配置避坑指南：从PLL时钟到PHY寄存器，手把手调通你的第一块板