HDU-6862 Hexagon (2020HDU 多校 D8 H)

1008

题意：半径为n的六边形（由半径为1的小六边形组成），从某一个小六边形出发有六个方向，找到一条转向次数最多的路径（用方向表示）遍历所有的六边形（一个六边形只访问一次）。

题解：先画出n=3/4满足条件的路径，发现走每一条边的转弯方式（由两个方向表示）一致，n增加2，转弯次数也增加2

下图为n = 4的情况：

中间一圈是245612
615 衔接之后进入第二圈的左上边的连续转弯处46
3衔接， 24连续转弯
2衔接， 13连续转弯
1衔接， 62连续转弯
6衔接， 51连续转弯

下图是n = 5的情况：

路径同n = 4的2~6步

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5+50;

ll n, k;

ll imax,sum;

string s;

void get(int x) {

    s += "615";

    for(int i = 1; i <= x-2; i++) s += "46";

    s += '4';

    for(int i = 1; i <= x-1; i++) s += "35";

    s += '3';

    for(int i = 1; i <= x-1; i++) s += "24";

    s += '2';

    for(int i = 1; i <= x-1; i++) s += "13";

    s += '1';

    for(int i = 1; i <= x-1; i++) s += "62";

    s += '6';

    for(int i = 1; i <= x-1; i++) s += "51";

}

int main() {

    int T;scanf("%d",&T);

    while(T--) {

        scanf("%d",&n);

        if( n%2 == 0) {

            s = "245612";

            for(int i = 3; i <= n; i += 2) get(i);

            cout << s << endl;

        }

        else {

            s = "";

            for(int i = 2; i <= n; i += 2) get(i);

            cout << s <<endl;

        }

    }

}

巴特西

HDU-6862 Hexagon (2020HDU 多校 D8 H)

1008

最新文章

热门文章