題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)數(shù)n，求出一個(gè)大于等于n的“好數(shù)”，“好數(shù)”的規(guī)定是只由3的冪次之和構(gòu)成

題目分析：直接將n拆成三進(jìn)制，然后貪心從最高位開始找等于2的位置，找到后從這個(gè)位置開始，前面的位全部置零，后面找到一個(gè)等于零的位變成一就行了，因?yàn)槿绻胂ミ@個(gè)二，而且要滿足大于等于原數(shù)，那么就必須讓這個(gè)二進(jìn)位，既然進(jìn)位就會影響到后面較高的位，依次類推，只有到了第一個(gè)等于零的位置才能容納這個(gè)進(jìn)位

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=5e3+100;int bit[100],cnt;LL q_pow(LL a,LL b) {LL ans=1;while(b){if(b&1)ans*=a;a*=a;b>>=1;}return ans; }void init() {memset(bit,0,sizeof(bit));cnt=0; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){init();LL num;scanf("%lld",&num);while(num){bit[++cnt]=num%3;num/=3;}int pos=cnt;while(bit[pos]!=2&&pos>=1)pos--;if(pos!=0){while(pos<=cnt+1){if(bit[pos]==0){bit[pos]=1;break;}pos++;}}LL ans=0;for(int i=pos;i<=cnt+1;i++){if(bit[i])ans+=q_pow(3,i-1);}printf("%lld\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1249C2 Good Numbers (hard version)(进制转换)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。