首页 > 其他分享 >AT_ARC161B解题报告

AT_ARC161B解题报告

时间:2023-12-02 14:45:45浏览次数:39  
标签:cnt return 报告 int long ARC161B 二进制 解题

AT_ARC161B 解题报告

题意

题目传送门

给你一个正整数 \(N\),求小于等于 \(N\) 的所有数中最大的一个在二进制下拥有 \(3\) 个 \(1\) 的数。

思路

我们先看无解的情况,因为题目要求必须有 \(3\) 个 \(1\),所以当 \(n \leq 6\) 时,直接输出 \(-1\)。

我们可以考虑使用递归,设 \(f(X)\) 为 \(X\) 在二进制下 \(1\) 的个数,我们可以得到以下几种情况。

  1. 当 \(f(X) \lt 3\) 时,将 \(X\) 减去 \(1\)(因为在递归过程中,每一步都是将 \(X\) 变得更小,即比 \(X\) 大的数都不满足要求,只能去比 \(X\) 小的数去找可行情况)。

  2. 当 \(f(X) =3\) 时,\(X\) 即为答案。

  3. 当 \(f(X) \gt 3\) 时,将 \(X\) 在二进制下最右边的 \(1\) 变为 \(0\)(满足贪心,减去一个最小的数,使答案最大化)。

不开 long long 见祖宗。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n;

int f(int x){
    int cnt = 0;
    while (x){
        cnt++;
        x ^= (x & -x);
        /*
         N & -N 用于获取 N 的最低位的 1。
         这是通过将 N 的二进制表示与其负值(按位取反再加 1)进行按位与操作得到的。
         N ^ (N & -N) 则是将 N 的最低位的 1 置为 0,其它位保持不变。
        */
    }
    return cnt;
}

int solve(int x, int k){//x 表示当前数值,k 表示 x 在二进制数下有多少个 1。
    if (k < 3) return solve(x - 1, f(x - 1));
    if (k == 3) return x;
    if (k > 3) return solve(x ^ (x & -x), k - 1);
}

signed main(){
    cin >> t;
    while (t--){
        cin >> n;
        if (n <= 6) cout << -1 << endl;
        else cout << solve(n, f(n)) << endl;
    }
    return 0;
}

标签:cnt,return,报告,int,long,ARC161B,二进制,解题
From: https://www.cnblogs.com/ccf-ioi/p/17871576.html

相关文章

  • AT_ARC158A解题报告
    AT_ARC158A解题报告题意题目传送门给你3个数\(a,b,c\),通过若干次操作使得\(a=b=c\)。一次操作指将\(a,b,c\)按任意顺序分别\(+3,+5,+7\)。若可以使\(a=b=c\),输出最小操作次数,否则输出\(-1\)。思路我们可以将\(+3,+5,+7\)每一项都减去\(5\)得到\(-2,0,+2\)。......
  • CF200D解题报告
    CF200D解题报告题意给你\(n\)个函数,由函数类型、函数名和参数类型组成。给你\(m\)个变量,由变量类型和变量名组成。给你\(k\)个调用关系,由调用的函数名和参数名构成。参数类型和变量类型保证为int,double,string和T中的一个,其中T表示可以匹配任意类型。分析很明......
  • CF718A解题报告
    CF718A解题报告题意给你一个长度为\(n\)的浮点数,最多四舍五入\(t\)次,求可以得到的最大值。注意:四舍五入之针对小数部分,不针对整数部分。输出时不能有前缀\(0\),和后缀\(0\)。当最大的数变成整数了,就不输出小数点。分析根据题面,很容易想到要用贪心,只需要再加那么一......
  • P4162解题报告
    P4162解题报告题意给你一张\(n\timesm\)的图,其中\(a_{i,j}=1\)表示有障碍,否则没有障碍,其中可以消除\(t\)个障碍,求所有格子的最大距离。分析这其实就是一道搜索的版子题。根据数据范围很容易想到可以枚举起点,然后通过广搜遍历起点到每一个点的距离和需要消除障碍的个......
  • 袋鼠云产品功能更新报告08期|近百项全新功能和优化,你要的都在这里!
    欢迎来到袋鼠云08期产品功能更新报告!在瞬息万变的市场环境中,我们深知客户的需求与期待,因此,我们及时推出袋鼠云最新产品更新及优化,包括数据治理中心、HiveSQL性能优化、新插件等,助力企业在数字世界中勇往直前。以下为袋鼠云产品功能更新报告08期内容,更多探索,请继续阅读。离线开发......
  • CMO 2023 P1 解题报告
    \zihao{4}\textbf{Problem:}\large求最小的实数$\lambda$,使得对任意正整数$n$,存在正整数$x_1,x_2,\dots,x_{2023}$,满足$n=x_1x_2\dotsx_{2023}$,且对于$i\in\{1,2,\dots,2023\}$,要么$x_i$为素数,要么$x_i\len^{\lambda}$。\\\zihao{......
  • 软件测试外包公司怎么选择?软件测试报告如何收费?
    随着科技信息的发展,软件产品质量成为企业和用户共同关注话题,因此有效保障软件产品质量的测试手段必不可少。一般为了获取更客观权威的检测报告,企业会将测试工作交由软件测试外包公司进行,也就是专门从事软件测评服务的第三方检测机构。软件测试外包有2种形式可进行:一种是甲......
  • 『Jmeter超级干货』| Linux下Jmeter安装配置、脚本设计执行、监控及报告完整过程
    (『Jmeter超级干货』|Linux下Jmeter安装配置、脚本设计执行、监控及报告完整过程)注意:1、之前写过一个是windows平台的,本文是Linux平台的;2、另外需要注意的是,本文仅为示例过程,所以将客户端和服务器都用在同一台机器上。一般情况下不建议这么做,会影响性能结果的准确性。1JDK......
  • 【专题】从新能源车险看财险经营模式变革报告PDF合集分享(附原数据表)
    原文链接:https://tecdat.cn/?p=34418原文出处:拓端数据部落公众号报告合集对中国新能源汽车市场的发展机遇、当前行业状况及未来趋势进行了详细分析。同时,从专业角度分享了海外市场的前沿经验以及中国新能源汽车生态的案例。报告合集总结指出,新能源汽车专属车险的发展和完善不仅......
  • 【专题】2022年中国跨境电商行业研究报告PDF合集分享(附原数据表)
    报告链接:http://tecdat.cn/?p=32044近年来,我国的跨境电子商务发展迅速,在过去五年中,其贸易额增长率达到了16.2%,已经成为稳定对外贸易的一支重要力量。阅读原文,获取专题报告合集全文,解锁文末52份跨境电商行业相关报告。一方面,随着跨境电子商务的发展,跨境电子商务的监管政策得到了......