Gym 100952H Special Palindrome 非递减的回文串、dfs打表、查数列网站OEIS

Source

UESTC 2016 Summer Training #21

Gym 100952H

My Solution

非递减的回文串、打表

比赛结束后看了下public 的代码就我们队是打表过的， 别人都是正规的过的， ⊙﹏⊙‖∣尴尬

分奇偶用 dfs 搞出非递减的左半边串， 然后求出这个的和 ans[sum + i]++;

对于偶数个的直接dfs， 对于奇数的则枚举mid， 然后依次dfs

void dfseven(int k, int sum)
{
    if(2*sum > 50) return;
    //cout<<"here1"<<endl;
    for(int i = k; i <= 50; i++){
        if(2*(sum + i) <= 50) {ans[2*(sum + i)]++; dfseven(i, sum + i);} else return; } } void dfsodd(int mid, int k, int sum) { if(2*sum + mid > 50) return;
    //cout<<"here2"<<endl;
    for(int i = k; i <= 50; i++){
        if(2*(sum + i) + mid <= 50 && i <= mid) {ans[2*(sum + i) + mid]++; dfsodd(mid, i, sum + i);}
        else return;
    }

}

然后只打了前ans[50] 及以前的， 因为后面的比较大时间不够的， 所以打出前50的表然后到数列网站
OEIS 查了一下， 还真有，☺☺

所以把那前250个ans贴到 txt里， 然后写一个中间程序 把这些数据 转换成 printf("ans[%d] = %d;", i, val);的样子打到另一个txt文件里， 然后复杂粘贴到上去， 整理下就好了

打表代码

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 250 + 8;

int ans[maxn];

//偶数个的
void dfseven(int k, int sum)
{
    if(2*sum > 50) return;
    //cout<<"here1"<<endl;
    for(int i = k; i <= 50; i++){
        if(2*(sum + i) <= 50) {ans[2*(sum + i)]++; dfseven(i, sum + i);} else return; } } void dfsodd(int mid, int k, int sum) { if(2*sum + mid > 50) return;
    //cout<<"here2"<<endl;
    for(int i = k; i <= 50; i++){
        if(2*(sum + i) + mid <= 50 && i <= mid) {ans[2*(sum + i) + mid]++; dfsodd(mid, i, sum + i);}
        else return;
    }

}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    freopen("b.txt", "w", stdout);
    #endif // LOCAL
    memset(ans, 0, sizeof ans);
    //ans[2]++;
    dfseven(1, 0);
    //ans[1]++;
    for(int i = 1; i <= 50; i++){
        dfsodd(i, 1, 0);
    }
    for(int i = 1; i <= 50; i++){
        printf("ans[%d] = %d;", i, ans[i] + 1);
    }

/*
    int n;
    while(scanf("%d", &n)){
        printf("%d", ans[n]);

    }
    */
    return 0;
}

最终代码

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 250 + 8;

LL ans[maxn];

int main()
{
    
ans[1] = 1;
ans[2] = 2;
ans[3] = 2;
ans[4] = 4;
ans[5] = 3;
ans[6] = 7;
ans[7] = 5;
ans[8] = 11;
ans[9] = 8;
ans[10] = 17;
ans[11] = 12;
ans[12] = 26;
ans[13] = 18;
ans[14] = 37;
ans[15] = 27;
ans[16] = 54;
ans[17] = 38;
ans[18] = 76;
ans[19] = 54;
ans[20] = 106;
ans[21] = 76;
ans[22] = 145;
ans[23] = 104;
ans[24] = 199;
ans[25] = 142;
ans[26] = 266;
ans[27] = 192;
ans[28] = 357;
ans[29] = 256;
ans[30] = 472;
ans[31] = 340;
ans[32] = 621;
ans[33] = 448;
ans[34] = 809;
ans[35] = 585;
ans[36] = 1053;
ans[37] = 760;
ans[38] = 1354;
ans[39] = 982;
ans[40] = 1740;
ans[41] = 1260;
ans[42] = 2218;
ans[43] = 1610;
ans[44] = 2818;
ans[45] = 2048;
ans[46] = 3559;
ans[47] = 2590;
ans[48] = 4485;
ans[49] = 3264;
ans[50] = 5616;
ans[51] = 4097;
ans[52] = 7018;
ans[53] = 5120;
ans[54] = 8728;
ans[55] = 6378;
ans[56] = 10826;
ans[57] = 7917;
ans[58] = 13373;
ans[59] = 9792;
ans[60] = 16484;
ans[61] = 12076;
ans[62] = 20236;
ans[63] = 14848;
ans[64] = 24793;
ans[65] = 18200;
ans[66] = 30275;
ans[67] = 22250;
ans[68] = 36886;
ans[69] = 27130;
ans[70] = 44810;
ans[71] = 32992;
ans[72] = 54329;
ans[73] = 40026;
ans[74] = 65683;
ans[75] = 48446;
ans[76] = 79265;
ans[77] = 58499;
ans[78] = 95419;
ans[79] = 70488;
ans[80] = 114650;
ans[81] = 84756;
ans[82] = 137447;
ans[83] = 101698;
ans[84] = 164496;
ans[85] = 121792;
ans[86] = 196445;
ans[87] = 145578;
ans[88] = 234221;
ans[89] = 173682;
ans[90] = 278720;
ans[91] = 206848;
ans[92] = 331143;
ans[93] = 245920;
ans[94] = 392722;
ans[95] = 291874;
ans[96] = 465061;
ans[97] = 345856;
ans[98] = 549781;
ans[99] = 409174;
ans[100] = 649019;
ans[101] = 483330;
ans[102] = 764959;
ans[103] = 570078;
ans[104] = 900373;
ans[105] = 671418;
ans[106] = 1058191;
ans[107] = 789640;
ans[108] = 1242061;
ans[109] = 927406;
ans[110] = 1455820;
ans[111] = 1087744;
ans[112] = 1704261;
ans[113] = 1274118;
ans[114] = 1992458;
ans[115] = 1490528;
ans[116] = 2326608;
ans[117] = 1741521;
ans[118] = 2713398;
ans[119] = 2032290;
ans[120] = 3160899;
ans[121] = 2368800;
ans[122] = 3677789;
ans[123] = 2757826;
ans[124] = 4274556;
ans[125] = 3207086;
ans[126] = 4962526;
ans[127] = 3725410;
ans[128] = 5755174;
ans[129] = 4322816;
ans[130] = 6667228;
ans[131] = 5010688;
ans[132] = 7716070;
ans[133] = 5802008;
ans[134] = 8920663;
ans[135] = 6711480;
ans[136] = 10303379;
ans[137] = 7755776;
ans[138] = 11888671;
ans[139] = 8953856;
ans[140] = 13705118;
ans[141] = 10327156;
ans[142] = 15784173;
ans[143] = 11899934;
ans[144] = 18162385;
ans[145] = 13699699;
ans[146] = 20879933;
ans[147] = 15757502;
ans[148] = 23983452;
ans[149] = 18108418;
ans[150] = 27524280;
ans[151] = 20792120;
ans[152] = 31561603;
ans[153] = 23853318;
ans[154] = 36160845;
ans[155] = 27342421;
ans[156] = 41397124;
ans[157] = 31316314;
ans[158] = 47353396;
ans[159] = 35839008;
ans[160] = 54124796;
ans[161] = 40982540;
ans[162] = 61816437;
ans[163] = 46828032;
ans[164] = 70548311;
ans[165] = 53466624;
ans[166] = 80453313;
ans[167] = 61000704;
ans[168] = 91682668;
ans[169] = 69545358;
ans[170] = 104403741;
ans[171] = 79229676;
ans[172] = 118806744;
ans[173] = 90198446;
ans[174] = 135102223;
ans[175] = 102614114;
ans[176] = 153528658;
ans[177] = 116658616;
ans[178] = 174350347;
ans[179] = 132535702;
ans[180] = 197865953;
ans[181] = 150473568;
ans[182] = 224406247;
ans[183] = 170727424;
ans[184] = 254344551;
ans[185] = 193582642;
ans[186] = 288094273;
ans[187] = 219358315;
ans[188] = 326120818;
ans[189] = 248410816;
ans[190] = 368939881;
ans[191] = 281138048;
ans[192] = 417130912;
ans[193] = 317984256;
ans[194] = 471335560;
ans[195] = 359444904;
ans[196] = 532274004;
ans[197] = 406072422;
ans[198] = 600743477;
ans[199] = 458482688;
ans[200] = 677637038;
ans[201] = 517361670;
ans[202] = 763943462;
ans[203] = 583473184;
ans[204] = 860768675;
ans[205] = 657667584;
ans[206] = 969336374;
ans[207] = 740890786;
ans[208] = 1091013811;
ans[209] = 834194700;
ans[210] = 1227313238;
ans[211] = 938748852;
ans[212] = 1379921672;
ans[213] = 1055852590;
ans[214] = 1550704877;
ans[215] = 1186949056;
ans[216] = 1741741564;
ans[217] = 1333640710;
ans[218] = 1955329266;
ans[219] = 1497705768;
ans[220] = 2194025352;
ans[221] = 1681116852;
ans[222] = 2460655086;
ans[223] = 1886061684;
ans[224] = 2758359212;
ans[225] = 2114965120;
ans[226] = 3090606588;
ans[227] = 2370513986;
ans[228] = 3461249193;
ans[229] = 2655684608;
ans[230] = 3874538905;
ans[231] = 2973772212;
ans[232] = 4335193118;
ans[233] = 3328423936;
ans[234] = 4848416380;
ans[235] = 3723675326;
ans[236] = 5419976831;
ans[237] = 4163989458;
ans[238] = 6056235989;
ans[239] = 4654300706;
ans[240] = 6764237552;
ans[241] = 5200062976;
ans[242] = 7551745299;
ans[243] = 5807301632;
ans[244] = 8427348786;
ans[245] = 6482671322;
ans[246] = 9400510845;
ans[247] = 7233519619;
ans[248] = 10481691022;
ans[249] = 8067955712;
ans[250] = 11682407480;
    int n;
    while(scanf("%d", &n)){
        if(n == 0) break;
        printf("%I64dn", ans[n]);
    }

    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx