UVALive 6770 - Baggage （构造）

UVALive6770 ACM ICPC 2014 world finals problem A 构造。题解传送门： problem a ACM ICPC 2014 solution to problem A - baggage here (需要科学上网) 这题的构造方法。首先要手算出n=3,4,5,6,7 的解。然后由n的解，可以推出n+4的解，然后递推一发。比如 __BABA (BA)^n BABA ABBABA (BA)^n B__A ABBA__ (BA)^n BBAA -> ABBA A^n B^n BBAA AA A^n B^n BBBBAA AAAA A^n B^n BBBB 这样就可以由n的解放，推广到n+2的解放。除了n=3外，其余的都是往左移动了两格的。

/* ***
Author :kuangbin
Created Time :2015/4/21 16:31:24
File Name :UVALive6770.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;

vector<pair<int,int> >vec[110];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
vec[3].push_back(make_pair(2,-1));
vec[3].push_back(make_pair(5,2));
vec[3].push_back(make_pair(3,-3));

vec\[4\].push\_back(make\_pair(6,-1));
vec\[4\].push\_back(make\_pair(3,6));
vec\[4\].push\_back(make\_pair(0,3));
vec\[4\].push\_back(make\_pair(7,0));

vec\[5\].push\_back(make\_pair(8,-1));
vec\[5\].push\_back(make\_pair(3,8));
vec\[5\].push\_back(make\_pair(6,3));
vec\[5\].push\_back(make\_pair(0,6));
vec\[5\].push\_back(make\_pair(9,0));

vec\[6\].push\_back(make\_pair(10,-1));
vec\[6\].push\_back(make\_pair(7,10));
vec\[6\].push\_back(make\_pair(2,7));
vec\[6\].push\_back(make\_pair(6,2));
vec\[6\].push\_back(make\_pair(0,6));
vec\[6\].push\_back(make\_pair(11,0));

vec\[7\].push\_back(make\_pair(12,-1));
vec\[7\].push\_back(make\_pair(5,12));
vec\[7\].push\_back(make\_pair(8,5));
vec\[7\].push\_back(make\_pair(3,8));
vec\[7\].push\_back(make\_pair(9,3));
vec\[7\].push\_back(make\_pair(0,9));
vec\[7\].push\_back(make\_pair(13,0));

for(int i = 8;i <= 100;i++){
    vec\[i\].push\_back(make\_pair(2*i-2,-1));
    vec\[i\].push\_back(make\_pair(3,2*i-2));
    for(int j = 0;j < i-4;j++)
        vec\[i\].push\_back(make\_pair(vec\[i-4\]\[j\].first+4,vec\[i-4\]\[j\].second+4));
    vec\[i\].push\_back(make\_pair(0,2*i-5));
    vec\[i\].push\_back(make\_pair(2*i-1,0));
}
int n;
bool first = true;
while(scanf("%d",&n) == 1){
    if(first)first = false;
    else printf("\\n");
    for(int i = 0;i < n;i++)
        printf("%d to %d\\n",vec\[n\]\[i\].first,vec\[n\]\[i\].second);
}
return 0;

}