专栏文章

【0】做题心得 - 2025 NOIP #70 - T1 / 题解：P10026 「HCOI-R1」哀之变化【位运算】【构造】

EExFish
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mimznzh2
此快照首次捕获于
2025/12/01 18:10
3 个月前
此快照最后确认于
2025/12/01 18:10
3 个月前
查看原文
你考虑一个不停 ×2\times 2 的方法，来取得最高位。然后你就发现 ×2\times 2 再 −1-1 就可以做到不停不变为 11，显然直接发现只要奇偶性相同就可以。然后你考虑如何最小化操作次数。这个的话你发现在前面放可以被后面的 ×2\times 2 多次放大，于是找到需要调整的值类似二进制去做就可以了。还有一个问题就是最小的不一定奇偶性一致，你考虑把一个高次操作拆成两个低次操作，就可以省去一次操作变多 22 次操作，总操作次数 +1+1。然后就是简单做了，不知道为什么是绿色的。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pl __builtin_popcountll
ll n,k;
int main(){
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        cin>>k>>n;
        bool fl=0;
        for(int i=60;~i;i--){
        	if((1ll<<i)>=n){
        		ll op=i+(1ll<<i)-n, pc=pl((1ll<<i)-n);
				if(k>=op&&op%2==k%2) fl=1;
        		op=i+pc;
				if((1ll<<i)-n>=2){ if(k>=op+1&&(op+1)%2==k%2) fl=1; }
				if(k>=op&&op%2==k%2) fl=1;
			}
		}
		cout<<(fl?"Yes\n":"No\n");
	}
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...