gym-101667K Untangling Chain

Untangling Chain

构造

显然对于一条线段来说，走到头只有左右两边可以选择，换句话说，第一次是横着走，第二次是竖着走，因此可以构造一个走法，让他每次都突破自身走过路径的四个边（矩形），使得每次走到头的时候，他的左右两边必然不存在直线

构造的合法性：

每次只突破长度 \(1\)，因此对于横向 \(or\) 纵向来说，总共突破 \(\frac{n}{2}\) 次，因此最长的线段也就是 \(n\) 的长度

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int add[4] = {1, -1, -1, 1};
int way[4] = {0, 0, 0, 0};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int>ans(n, 0);
    int dir = 3;
    int x[2] = {0, 0};
    for(int i=0; i<n; i++)
    {
        int a, b;
        cin >> a >> b;
        ans[i] = abs(way[dir] + add[dir] - x[dir & 1]);
        x[dir & 1] = way[dir] + add[dir];
        way[dir] += add[dir];
        dir = ((dir + b) % 4 + 4) % 4;
    }
    for(int i=0; i<n; i++)
    {
        if(i) cout << " ";
        cout << ans[i];
    }
    cout << endl;
    return 0;
}