P10026 「HCOI-R1」哀之变化

题目背景

哀喜欢数字。

她还喜欢变化。

题目描述

有一整数 $a$ 初始为 $1$。

哀想让 $a$ 进行恰好 $k$ 次变化，每次从以下两种变化中选择一个：

• $a\leftarrow a-1$；
• $a\leftarrow a\times 2$。

哀很好奇，经过 恰好 $k$ 次变化后 $a$ 能否变成 $n$。

输入格式

本题有多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行两个整数，依次为 $k$ 和 $n$，表示哀的一次询问。

输出格式

共 $T$ 行，对于每次询问，若 $a$ 可以变成 $n$，输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

3
2 5
2 4
3 3

输出 #1

No
Yes
Yes

输入输出样例 #2

输入 #2

5
4 869
48 69
8 328
66 114514
168 1919810

输出 #2

No
Yes
No
Yes
Yes

说明/提示

样例解释 1

• 若 $k=2$，$n=5$，可以证明无解。
• 若 $k=2$，$n=4$，一种可能的操作方式如下：
  • 第一步，$a\leftarrow a\times 2=2$；
  • 第二步，$a\leftarrow a\times 2=4$。
• 若 $k=3$，$n=3$，一种可能的操作方式如下：
  • 第一步，$a\leftarrow a\times 2=2$；
  • 第二步，$a\leftarrow a\times 2=4$。
  • 第三步，$a\leftarrow a-1=3$。

数据规模与约定

本题采用捆绑测试。

• Subtask 0（10 pts）：$T\le 10$，$k\le 15$。
• Subtask 1（25 pts）：$n,k\le 2\times 10^3$。
• Subtask 2（65 pts）：无特殊限制。

对于所有数据，$1\le T\le 10^5$，$0\le n,k\le 10^{18}$。

C++实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,k,n,res,ans;
inline ll Q(ll x){
    res=0;
    while(x!=1){
        if(x&1)
            x++;
        else
            x>>=1;
        res++;
    }
    return res;
}
inline bool check(ll x){
    if(x&1)
        x++;
    return (x&(-x))==x;
}
int main(){
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld",&k,&n);
        if(!k)
            puts(n==1?"Yes":"No");
        else if(!n)
            puts("Yes");
        else if(n==1)
            puts(k%2==0||k>=5&&k%2?"Yes":"No");
        else{
            ans=Q(n);
            puts(ans>k||ans+1==k&&check(n)?"No":"Yes");
        }
    }
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容