2022JSCPCK

2022 JSCPC K 最构造的一集

原题链接：2022 JSCPC K

思路

为了方便，将nunhehhe称为x。

当n=0时显然随便一个数都可以。

当n=1时只需要再原字符串上加一个a即可。

先观察规律，在x后如果补一个h，此h后面a的个数为m，那么这个h的贡献为$2^m-1$。不是$2^m$是因为最后不能为空。

补h的作用就是和x最后的作替换，从而转换为一个按位运算的问题，由cnt记录多少个$2^m-1$，然后在最后一个a前补n个h即可。

代码

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
vector<int>arr;
int main() {
    cin>>t;
    while(t--){
        cin>>n;
        string s;
        if(n==0){
            cout<<"valorant"<<endl;//打瓦打的
            continue;
        }
        if(n==1){
            cout<<"nunhehheha"<<endl;
            continue;
        }
        int cnt=0;
        for(int i=1;i<=30;i++){
            if(n&(1<<i)){
                arr.push_back(i-1);//将为1的位放入arr中
                cnt++;
            }
        }
        if(n&1)cnt++;//特判
        int pre=0;
        for(int i=0;i<arr.size();i++){
            for(int j=0;j<arr[i]-pre;j++){
                s+='a';//由于是从最小位开始，故应将a放h前，最后倒置
            }
            s+='h';
            pre=arr[i];//当某位不为1时，应只输出a即可
        }
        reverse(s.begin(),s.end());
        for(int i=1;i<=cnt;i++)s+='h';
        s+='a';//在最后补a
        cout<<"nunhehhe"<<s<<endl;
        arr.clear();
    }
    return 0;
}
 

碎碎念

做这道题从读题，自己写，翻题解，到最终理解花了两个小时时间。

马上还有十几天就省赛了，虽然是打星队，但还是慌得一比，这种应该属于简单构造，自己还是做不好，正好又碰上蓝桥杯拉胯，感觉焦虑又无力。

唉唉，慢慢来吧。