数据范围比较小 ，可以子集枚举 3 的幂，打表，然后lower_bound()输出， \(O(n \log n)\)
#include <bits/stdc++.h>
using namespace std;
int powi[20],a[1000];
int go[1051]={
0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,81,82,84,85,90,91,93,94,108,
109,111,112,117,118,120,121,243,244,246,247,252,253,255,256,270,271,273,
274,279,280,282,283,324,325,327,328,333,334,336,337,351,352,354,355,360,
361,363,364,729,730,732,733,738,739,741,742,756,757,759,760,765,766,768,
769,810,811,813,814,819,820,822,823,837,838,840,841,846,847,849,850,972,
973,975,976,981,982,984,985,999,1000,1002,1003,1008,1009,1011,1012,1053,
1054,1056,1057,1062,1063,1065,1066,1080,1081,1083,1084,1089,1090,1092,1093,
2187,2188,2190,2191,2196,2197,2199,2200,2214,2215,2217,2218,2223,2224,2226,
2227,2268,2269,2271,2272,2277,2278,2280,2281,2295,2296,2298,2299,2304,2305,
2307,2308,2430,2431,2433,2434,2439,2440,2442,2443,2457,2458,2460,2461,2466,
2467,2469,2470,2511,2512,2514,2515,2520,2521,2523,2524,2538,2539,2541,2542,
2547,2548,2550,2551,2916,2917,2919,2920,2925,2926,2928,2929,2943,2944,2946,
2947,2952,2953,2955,2956,2997,2998,3000,3001,3006,3007,3009,3010,3024,3025,
3027,3028,3033,3034,3036,3037,3159,3160,3162,3163,3168,3169,3171,3172,3186,
3187,3189,3190,3195,3196,3198,3199,3240,3241,3243,3244,3249,3250,3252,3253,
3267,3268,3270,3271,3276,3277,3279,3280,6561,6562,6564,6565,6570,6571,6573,
6574,6588,6589,6591,6592,6597,6598,6600,6601,6642,6643,6645,6646,6651,6652,
6654,6655,6669,6670,6672,6673,6678,6679,6681,6682,6804,6805,6807,6808,6813,
6814,6816,6817,6831,6832,6834,6835,6840,6841,6843,6844,6885,6886,6888,6889,
6894,6895,6897,6898,6912,6913,6915,6916,6921,6922,6924,6925,7290,7291,7293,
7294,7299,7300,7302,7303,7317,7318,7320,7321,7326,7327,7329,7330,7371,7372,
7374,7375,7380,7381,7383,7384,7398,7399,7401,7402,7407,7408,7410,7411,7533,
7534,7536,7537,7542,7543,7545,7546,7560,7561,7563,7564,7569,7570,7572,7573,
7614,7615,7617,7618,7623,7624,7626,7627,7641,7642,7644,7645,7650,7651,7653,
7654,8748,8749,8751,8752,8757,8758,8760,8761,8775,8776,8778,8779,8784,8785,
8787,8788,8829,8830,8832,8833,8838,8839,8841,8842,8856,8857,8859,8860,8865,
8866,8868,8869,8991,8992,8994,8995,9000,9001,9003,9004,9018,9019,9021,9022,
9027,9028,9030,9031,9072,9073,9075,9076,9081,9082,9084,9085,9099,9100,9102,
9103,9108,9109,9111,9112,9477,9478,9480,9481,9486,9487,9489,9490,9504,9505,
9507,9508,9513,9514,9516,9517,9558,9559,9561,9562,9567,9568,9570,9571,9585,
9586,9588,9589,9594,9595,9597,9598,9720,9721,9723,9724,9729,9730,9732,9733,
9747,9748,9750,9751,9756,9757,9759,9760,9801,9802,9804,9805,9810,9811,9813,
9814,9828,9829,9831,9832,9837,9838,9840,9841,19683,19684,19686,19687,19692,
19693,19695,19696,19710,19711,19713,19714,19719,19720,19722,19723,19764,19765,
19767,19768,19773,19774,19776,19777,19791,19792,19794,19795,19800,19801,19803,
19804,19925,19926,19927,19928,19929,19930,19935,19936,19938,19939,19953,19954,
19956,19957,19962,19963,19965,19966,20007,20008,20010,20011,20016,20017,20019,
20020,20034,20035,20037,20038,20043,20044,20045,20046,20047,20412,20413,20415,
20416,20421,20422,20424,20425,20439,20440,20442,20443,20448,20449,20451,20452,
20493,20494,20496,20497,20502,20503,20505,20506,20520,20521,20523,20524,20529,
20530,20532,20533,20655,20656,20658,20659,20664,20665,20667,20668,20682,20683,
20685,20686,20691,20692,20694,20695,20736,20737,20739,20740,20745,20746,20748,
20749,20763,20764,20766,20767,20772,20773,20775,20776,21870,21871,21873,21874,
21879,21880,21882,21883,21897,21898,21900,21901,21906,21907,21909,21910,21951,
21952,21954,21955,21960,21961,21963,21964,21978,21979,21981,21982,21987,21988,
21990,21991,22113,22114,22116,22117,22122,22123,22125,22126,22140,22141,22143,
22144,22149,22150,22152,22153,22194,22195,22197,22198,22203,22204,22206,22207,
22221,22222,22224,22225,22230,22231,22233,22234,22599,22600,22602,22603,22608,
22609,22611,22612,22626,22627,22629,22630,22635,22636,22638,22639,22680,22681,
22683,22684,22689,22690,22692,22693,22707,22708,22710,22711,22716,22717,22719,
22720,22842,22843,22845,22846,22851,22852,22854,22855,22869,22870,22872,22873,
22878,22879,22881,22882,22923,22924,22926,22927,22932,22933,22935,22936,22950,
22951,22953,22954,22959,22960,22962,22963,26244,26245,26247,26248,26253,26254,
26256,26257,26271,26272,26274,26275,26280,26281,26283,26284,26325,26326,26328,
26329,26334,26335,26337,26338,26352,26353,26355,26356,26361,26362,26364,26365,
26487,26488,26490,26491,26496,26497,26499,26500,26514,26515,26517,26518,26523,
26524,26526,26527,26568,26569,26571,26572,26577,26578,26580,26581,26595,26596,
26598,26599,26604,26605,26607,26608,26973,26974,26976,26977,26982,26983,26985,
26986,27000,27001,27003,27004,27009,27010,27012,27013,27054,27055,27057,27058,
27063,27064,27066,27067,27081,27082,27084,27085,27090,27091,27093,27094,27216,
27217,27219,27220,27225,27226,27228,27229,27243,27244,27246,27247,27252,27253,
27255,27256,27297,27298,27300,27301,27306,27307,27309,27310,27324,27325,27327,
27328,27333,27334,27336,27337,28431,28432,28434,28435,28440,28441,28443,28444,
28458,28459,28461,28462,28467,28468,28470,28471,28512,28513,28515,28516,28521,
28522,28524,28525,28539,28540,28542,28543,28548,28549,28551,28552,28674,28675,
28677,28678,28683,28684,28686,28687,28701,28702,28704,28705,28710,28711,28713,
28714,28755,28756,28758,28759,28764,28765,28767,28768,28782,28783,28785,28786,
28791,28792,28794,28795,29160,29161,29163,29164,29169,29170,29172,29173,29187,
29188,29190,29191,29196,29197,29199,29200,29241,29242,29244,29245,29250,29251,
29253,29254,29268,29269,29271,29272,29277,29278,29280,29281,29403,29404,29406,
29407,29412,29413,29415,29416,29430,29431,29433,29434,29439,29440,29442,29443,
29485,29487,29488,29494,29496,29497,29511,29512,29514,29515,29520,29521,29523,
29524,70308,70510,70797,70862,71116,71351,71439,71466,71532,71555,71583,71608,
71639,71660,71692,71711,72400,72655,72705,4214341,4218416,6690937,8029282,33576385};
int main(){
// 注释掉的 是子集枚举 3 的幂
// freopen("out.txt","w",stdout);
// int k = 0;
// powi[0] = 1;
// for(int i = 1;i < 10; ++i){ // 3^9 == 19683
// powi[i] = powi[i-1]*3;
// }
// for(int i = 0;i < (2<<10); ++i){
// for(int j = 0;j < 10; ++j){
// if(i&(1<<j)){
// a[k] += powi[j];
// }
// }
// k++;
// }
// sort(a,a+k);
// k = unique(a,a+k) - a;
// for(int i = 0;i < k; ++i){
// cout << a[i]<<",";
// }
// cout << endl << k << endl;
int q,x;
cin >> q;
while(q--){
cin >> x;
cout << go[lower_bound(go,go+1051,x)-go] << endl;
}
return 0;
}
正解
题目要求 3的幂不能重复，因此在 3进制下，每个数字的 基数只能是 0 或者 1，不能是 2
可以用 十进制 转 n进制的方法， %n 取余，只需要判断即可，不用关心倒序输出。
从 n 开始向上找寻，第一个good 数，输出即可
#include <bits/stdc++.h>
using namespace std;
int main(){
int q,n;
cin >> q;
while(q--){
cin >> n;
while(1){
bool ok = 1;
int cur = n;
while(cur > 0){
if(ok && cur%3 == 2) ok = 0;
cur /= 3;
}
if(ok) break;
n++;
}
cout << n <<endl;
}
return 0;
}数据范围变大之后，可以考虑一般性
在3进制下，找到最大的基数 2 ，然后再从 2 到 end() 找到第一个为 0 的缺口
（可能存在 2 之后全是 1 的情况，所以要 在最后，手动push(1)
把 这个 0 变成 1，他的左边所有数字全变成 0 ，就可以保证，他为目标答案。
（在二进制下想一想吧，$2^0 + 2^1+2^2+2^3 < 2^4 $
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
int q;
LL n;
cin >> q;
while(q--){
cin >> n;
LL ans = 0,pw = 1;
vector<int> val;
int pos2 = -1;
while(n > 0){
val.push_back(n % 3);
if(val.back() == 2) pos2 = int(val.size()) - 1;
n /= 3;
}
val.push_back(0);
if(pos2 != -1){
int pos0 = find(val.begin() + pos2,val.end(),0) - val.begin();
val[pos0] = 1;
for(int i = pos0 - 1;i >= 0; --i){
val[i] = 0;
}
}
for(int i = 0;i < int(val.size()); ++i){
ans += pw*val[i];
pw *= 3;
}
cout << ans << endl;
}
return 0;
}
原文：https://www.cnblogs.com/lukelmouse/p/11743898.html