@Dmaxiya 2018-08-17T10:24:56.000000Z 字数 6466 阅读 1163

Codeforces Round #492 (Div. 1)

Codeforces

Contests 链接：Codeforces Round #492 (Div. 1)
过题数：1
排名：409/663

A. Tesla

题意

在一个 $4\times n$ 停车场上，第 $1$ 行和第 $4$ 行是停车位，第 $2$ 行和第 $3$ 行是车行道，如下图：

总共有 $k$ 辆车，分别编号为 $1$ 到 $k$ ，每辆车都要停到与车辆编号相同的停车位上。每辆车每次只能移动到相邻的坐标上，且编号为 $i$ 的车辆只允许在车行道上行驶或者进入编号为 $i$ 的停车位内，不允许进入其他编号的停车位与没有编号的停车位上。问是否能找到一种移动次数在 $20000$ 次内的车辆行驶方案，使得所有车都进入到对应的停车位，如果可以，则输出车辆行驶路线，否则输出 $-1$ 。

输入

第一行包括两个整数 $n$ 和 $k~(1\leq n\leq50,1\leq k\leq2n)$ ，接下去四行每行 $n$ 个整数，第 $1$ 行和第 $4$ 行的非零数字表示对应编号的停车位， $0$ 表示禁止进入的停车位，第 $2$ 行和第 $3$ 行非零数字表示对应编号的车的位置， $0$ 表示空地，其他车辆可以移动到该处。

输出

如果无法在 $20000$ 步内将所有车辆移动到对应的停车位，则输出 $-1$ ，否则第一行输出一个整数 $m$ 表示需要的移动次数，接下去 $m$ 行每行三个整数 $i,r,c$ ，表示第 $i$ 辆车移动到第 $r$ 行第 $c$ 列的位置上，移动的位置必须保证合法。如果有多解则输出任意一组。

样例

输入	输出	提示
4 5 1 2 0 4 1 2 0 4 5 0 0 3 0 5 0 3	6 1 1 1 2 1 2 4 1 4 3 4 4 5 3 2 5 4 2	除了车辆 $5$ ，其他车辆都在相应的停车位旁，样例输出给出的是到达相应停车位的最快的方式，其他任何一种移动次数小于 $20000$ 次的方案都是允许的。
1 2 1 2 1 2	-1	所有车辆都在一列内，且他们的相对位置导致它们无法回到自己的停车位内，所以只能输出 $-1$ 。
1 2 1 1 2 2	2 1 1 1 2 4 1

题解

可以将所有车辆按顺时针或者逆时针的顺序在第 $2$ 、 $3$ 行内移动，每次移动，检查车辆位置是否在对应停车位旁，如果是，则直接进入停车位，否则继续跟着所有车辆移动。可以计算得出，最坏情况下 $(n=50,k=99)$ 所有车辆需要的移动次数为 $100\times100+100=10100<20000$ ，如果无法顺/逆时针移动，车辆也无法进入停车位，则输出 $-1$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 500;
const int maxcnt = 20000 + 100;
struct Node {
    int x, y;
    Node() {}
    Node(int xx, int yy) {
        x = xx;
        y = yy;
    }
};
bool operator!=(const Node &a, const Node &b) {
    return a.x != b.x || a.y != b.y;
}
int n, k, anscnt, cnt;
int num[4][maxn];
Node pre[4][maxn];
bool vis[4][maxn];
int ans[maxcnt][3];
const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
bool in(int x, int y) {
    return x >= 1 && x <= 2 && y >= 0 && y < n;
}
void dfs(int x, int y) {
    for(int i = 0; i < 4; ++i) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if(in(xx, yy) && !vis[xx][yy]) {
            vis[xx][yy] = true;
            pre[xx][yy] = Node(x, y);
            dfs(xx, yy);
        }
    }
}
void get_in() {
    for(int i = 1; i <= 2; ++i) {
        for(int j = 0; j < n; ++j) {
            if(num[i][j] != 0 && num[i][j] == num[i ^ 1][j]) {
                ans[anscnt][0] = num[i][j];
                ans[anscnt][1] = (i ^ 1) + 1;
                ans[anscnt][2] = j + 1;
                anscnt++;
                num[i][j] = 0;
                --cnt;
            }
        }
    }
}
bool Go() {
    for(int i = 1; i <= 2; ++i) {
        for(int j = 0; j < n; ++j) {
            if(num[i][j] == 0) {
                Node Begin = Node(i, j);
                Node first = pre[Begin.x][Begin.y];
                Node second = Begin;
                while(first != Begin) {
                    if(num[first.x][first.y] != 0) {
                        ans[anscnt][0] = num[first.x][first.y];
                        ans[anscnt][1] = second.x + 1;
                        ans[anscnt][2] = second.y + 1;
                        ++anscnt;
                    }
                    swap(num[first.x][first.y], num[second.x][second.y]);
                    second = first;
                    first = pre[second.x][second.y];
                }
                return true;
            }
        }
    }
    return false;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &k) != EOF) {
        anscnt = 0;
        cnt = k;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < 4; ++i) {
            for(int j = 0; j < n; ++j) {
                scanf("%d", &num[i][j]);
            }
        }
        dfs(1, 0);
        bool flag;
        do {
            get_in();
            flag = Go();
        } while(flag && cnt != 0);
        if(cnt != 0) {
            printf("-1\n");
            continue;
        }
        printf("%d\n", anscnt);
        for(int i = 0; i < anscnt; ++i) {
            for(int j = 0; j < 3; ++j) {
                if(j != 0) {
                    printf(" ");
                }
                printf("%d", ans[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

B. Suit and Tie

题意

有 $n$ 对夫妻，他们坐在一排，每对夫妻之间的位置不一定是相邻的，如果每次只能将相邻位置的两个人交换位置，问最少要交换多少次才能让所有夫妻坐在相邻的位置上。

输入

第一行为一个整数 $n~(1\leq n\leq100)$ ，第二行为 $2n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq n)$ ，数据保证 $1$ 到 $n$ 的每个数字只出现 $2$ 次。

输出

输出最少的交换次数。

样例

输入	输出	提示
4 1 1 2 3 3 2 4 4	2	可以通过下面的交换达到结果： $11233244\rightarrow11232344\rightarrow11223344$ ；也可以通过下面的交换达到结果： $11233244\rightarrow11323244\rightarrow11332244$ 。
3 1 1 2 2 3 3	0	$112233$ 已经使得所有夫妻座位相邻，因此不需要进行任何交换。
3 3 1 2 3 1 2	3

题解

对于每个数字中在左边的那个，去找另一个数字，将另一个数字移动到左边的数字旁边，依次贪心下去，就能得到最短的移动步数。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 300;
int n;
int num[maxn];
int Find(int Index, int x) {
    for(int i = Index; i <= n; ++i) {
        if(num[i] == x) {
            return i;
        }
    }
    return -1;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        int ans = 0;
        n *= 2;
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
        }
        for(int i = 1; i <= n; ++i) {
            int End = Find(i + 1, num[i]);
            if(End != -1) {
                for(int j = End - 1; j > i; --j) {
                    swap(num[j], num[j + 1]);
                    ++ans;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Leaving the Bar

题意

给定 $n$ 个向量，要求对每个向量分配一个系数 $1$ 或 $-1$ ，使得所有向量乘上对应的系数后相加得到的最终的向量模长不超过 $1.5\times10^6$

输入

第一行包含一个整数 $n~(1\leq n\leq10^5)$ ，接下去 $n$ 行每行两个整数 $x_i,y_i$ ，表示第 $i$ 个向量的值 $\vec v=(x_i,y_i)$ ，数据保证每一个向量的模长 $|\vec v|\leq10^6$ 。

输出

输出一行，包含 $n$ 个整数 $c_1,c_2,\cdots,c_n$ ，每个整数必须为 $1$ 或 $-1$ ，表示每个向量对应的系数，输出必须保证 $|\sum_{i=1}^nc_i\vec v_i|\leq1.5\times10^6$ 。如果有多解输出任意一组即可。

样例

输入	输出
3 999999 0 0 999999 999999 0	1 1 -1
1 -824590 246031	1
8 -67761 603277 640586 -396671 46147 -122580 569609 -2112 400 914208 131792 309779 -850150 -486293 5272 721899	1 1 1 1 1 1 1 -1

题解

由如下断言：

对于任意三个模长小于 $r$ 的向量 $v_1,v_2,v_3$ ， $v_1,v_2,v_3,-v_1,-v_2,-v_3$ $6$ 个向量中，两两之间夹角最小的角度最大为 $60°$ ，将这两个夹角小于 $60°$ 的向量做差，则得到的新向量的长度一定不大于 $r$ 。

可知，可以将 $n$ 个向量每 $3$ 个之间选择两个求和或做差，最终得到的向量模长一定不大于 $10^6$ ，合并到只剩下两个向量时，这两个向量所在的直线夹角最大为 $90°$ ，将这两个向量求和或做差，得到的向量长度最大为 $\sqrt 2r\approx 1.4\times10^6<1.5\times10^6$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
struct Node {
    LL x, y;
    int l, r;
    Node() {}
    Node(LL xx, LL yy) {
        x = xx;
        y = yy;
    }
    double length() {
        return sqrt(x * x + y * y);
    }
    LL mult(const Node &n) {
        return x * n.x + y * n.y;
    }
    Node operator-() {
        return Node(-x, -y);
    }
};
LL operator*(const Node &a, const Node &b) {
    return a.x * b.y - a.y * b.x;
}
Node operator-(const Node &a, const Node &b) {
    return Node(a.x - b.x, a.y - b.y);
}
int n, cnt;
int ans[maxn], the_Index[3];
Node node[maxn];
bool Close(Node &a, Node &b) {
    if(a.mult(b) < 0) {
        return false;
    }
    LL tmp = abs(a * b);
    return tmp <= a.length() * b.length() / 2 * sqrt(3.0);
}
int Creat_Node(const Node &n, int l, int r) {
    ++cnt;
    node[cnt] = n;
    node[cnt].l = l;
    node[cnt].r = r;
    return cnt;
}
void Solve() {
    sort(the_Index, the_Index + 3);
    do {
        int l = the_Index[0];
        int r = the_Index[1];
        Node tmp = node[l];
        Node ntmp = node[r];
        if(Close(tmp, ntmp)) {
            ans[l] = 1;
            ans[r] = -1;
            int Index = Creat_Node(tmp - ntmp, l, r);
            ans[Index] = 1;
            the_Index[0] = Index;
            the_Index[1] = the_Index[2];
            return ;
        }
        ntmp = -node[r];
        if(Close(tmp, ntmp)) {
            ans[l] = ans[r] = 1;
            int Index = Creat_Node(tmp - ntmp, l, r);
            ans[Index] = 1;
            the_Index[0] = Index;
            the_Index[1] = the_Index[2];
            return ;
        }
    } while(next_permutation(the_Index, the_Index + 3));
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        cnt = 0;
        for(int i = 1; i <= n; ++i) {
            scanf("%I64d%I64d", &node[i].x, &node[i].y);
            node[i].l = node[i].r = 0;
            ++cnt;
        }
        if(n == 1) {
            printf("1\n");
            continue;
        }
        ans[1] = 1;
        the_Index[0] = 1;
        the_Index[1] = 2;
        for(int i = 3; i <= n; ++i) {
            the_Index[2] = i;
            Solve();
        }
        int l = the_Index[0];
        int r = the_Index[1];
        if(node[l].mult(node[r]) >= 0) {
            ans[r] = -1;
        } else {
            ans[r] = 1;
        }
        for(int i = cnt; i >= 1; --i) {
            ans[node[i].l] *= ans[i];
            ans[node[i].r] *= ans[i];
        }
        for(int i = 1; i <= n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

Codeforces Round #492 (Div. 1)

A. Tesla

题意

输入

输出

样例

题解

过题代码

B. Suit and Tie

题意

输入

输出

样例

题解

过题代码

C. Leaving the Bar

题意

输入

输出

样例

题解

过题代码

内容目录