@Dmaxiya 2018-08-17T10:27:00.000000Z 字数 6110 阅读 909

Codeforces Round #488 (Div. 1)

Codeforces

Contests 链接：Codeforces Round #488 (Div. 1)
过题数：2
排名：295/715

A. Two Squares

题意

按顺时针或逆时针的顺序给出两个正方形四个顶点的坐标，第一个正方形四边都平行于坐标轴，第二个正方形的四边与坐标轴夹角都是 $45°$ ，问两个正方形是否相交（仅顶点有交点或者一个正方形包含于另一个正方形也属于相交）。

输入

输入包含两行，每行四对整数，每对整数表示正方形的其中一个顶点的坐标，每一行的四个坐标都是按照顺时针或者逆时针顺序给出的。
第一行给出边与坐标轴平行的正方形顶点坐标，第二行给出边与坐标轴夹角为 $45°$ 的正方形顶点坐标，所有整数都在 $[-100,100]$ 内。

输出

如果两个正方形相交则输出 "Yes"，否则输出 "No"，大小写任意。

样例

输入	输出
0 0 6 0 6 6 0 6 1 3 3 5 5 3 3 1	YES
0 0 6 0 6 6 0 6 7 3 9 5 11 3 9 1	NO
6 0 6 6 0 6 0 0 7 4 4 7 7 10 10 7	YES

题解

先按照顶点给出的顺序在二维数组上描出正方形的边界，接着填充两个正方形内部，再判断是否相交。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200 + 100;
int dx, dy;
int x[8], y[8];
bool vis[2][maxn][maxn];
void pull(bool vis[maxn][maxn]) {
    for(int i = 0; i < 4; ++i) {
        int ii = (i + 1) % 4;
        dx = x[ii] - x[i];
        dy = y[ii] - y[i];
        if(dx != 0) {
            dx /= abs(dx);
        }
        if(dy != 0) {
            dy /= abs(dy);
        }
        int xx = x[i];
        int yy = y[i];
        while(yy != y[ii] || xx != x[ii]) {
            vis[xx][yy] = true;
            xx += dx;
            yy += dy;
        }
        vis[xx][yy] = true;
    }
    for(int i = 0; i < maxn; ++i) {
        int Left = maxn;
        int Right = 0;
        for(int j = 0; j < maxn; ++j) {
            if(vis[i][j]) {
                Left = min(Left, j);
                Right = max(Right, j);
            }
        }
        for(int j = Left; j <= Right; ++j) {
            vis[i][j] = true;
        }
    }
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &x[0], &y[0]) != EOF) {
        memset(vis, 0, sizeof(vis));
        x[0] += 100;
        y[0] += 100;
        for(int i = 1; i < 4; ++i) {
            scanf("%d%d", &x[i], &y[i]);
            x[i] += 100;
            y[i] += 100;
        }
        pull(vis[0]);
        for(int i = 0; i < 4; ++i) {
            scanf("%d%d", &x[i], &y[i]);
            x[i] += 100;
            y[i] += 100;
        }
        pull(vis[1]);
        bool flag = false;
        for(int i = 0; i < maxn; ++i) {
            for(int j = 0; j < maxn; ++j) {
                if(vis[0][i][j] && vis[1][i][j]) {
                    flag = true;
                    break;
                }
            }
            if(flag) {
                break;
            }
        }
        if(flag) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}

B. Open Communication

题意

两个人分别被分到一对数字，每个数字都在 $[1,9]$ 内，且每对中的两个数字是不同的，两个人被分到的数字对保证只有一个数字是相同的，另一个数字不同。
现在第一个人给出 $n$ 对数字，第二个人给出 $m$ 对数字，他们给出的数字对中，必须有一个包含自己被分到的数字，其他数字对必须保证是两个不相同的在 $[1,9]$ 内的数字。你不知道他们被分到的数字对是什么，但是可以看到他们给出的数字对，问你是否能判断出他们被分到的数字对中，相同的那个数字。

输入

第一行包含 $n$ 和 $m$ $(1\leq n,m\leq12)$ ，第二行包含 $n$ 对数字，第三行包含 $m$ 对数字。数据保证合法。

输出

如果你可以猜到他们被分到的数字对中相同的那个数字，则输出这个数字，如果你猜不到，但是可以确定他们两个人都知道相同的那个数字，则输出 $0$ ，否则输出 $-1$ 。

样例

输入	输出
2 2 1 2 3 4 1 5 3 4	1
2 2 1 2 3 4 1 5 6 4	0
2 3 1 2 4 5 1 2 1 3 2 3	-1
2 3 1 2 4 5 1 3 2 3 4 6	-1

题解

按照题意模拟：先从第一个人的角度看，对于第一个人给出的每一对数字，如果对方给出的数字对中，与第一个人自己的数字对仅有一个数字相同，且相同的数字一样，则第一个人可以确定相同的数字，如：第一个人给出的是 $(1,2)$ ，对于第二个人给出的 $(1,2),(1,3),(1,4)$ ，他可以确定那个相同的数字是 $1$ ，但是对于第一个人来说，他知道自己那组数据是哪一组，从“你”的角度看，“你”不知道他给出的是哪组数据，如果假设第一个人拿到的是他展示的任一组数据，得到了多于 $1$ 个的答案（如： $(1,3),(2,3)$ 与 $(1,2)$ ，第一个人可以得到是 $1$ 或者 $2$ 中的一个答案，但是从“你”的角度看，却不知道是 $1$ 还是 $2$ ），这时候就是输出 $0$ 的情况。再用同样的逻辑从第二个人的角度看。注意只要有一个人无法唯一确定答案，就是输出 $-1$ 的情况，如样例 $4$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100;
bool flag;
int n[2];
pair<int, int> par[2][maxn];
set<int> st, stt;
int match(const pair<int, int> &a, const pair<int, int> &b, int &num) {
    int ret = 0;
    if(a.first == b.first) {
        ++ret;
        num = a.first;
    }
    if(a.second == b.second) {
        ++ret;
        num = a.second;
    }
    if(a.first == b.second) {
        ++ret;
        num = a.first;
    }
    if(a.second == b.first) {
        ++ret;
        num = b.first;
    }
    return ret;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n[0], &n[1]) != EOF) {
        flag = true;
        st.clear();
        for(int i = 0; i < 2; ++i) {
            for(int j = 0; j < n[i]; ++j) {
                scanf("%d%d", &par[i][j].first, &par[i][j].second);
            }
        }
        for(int i = 0; i < 2; ++i) {
            int ii = 1 - i;
            for(int j = 0; j < n[i]; ++j) {
                stt.clear();
                for(int k = 0; k < n[ii]; ++k) {
                    int num;
                    int cnt = match(par[i][j], par[ii][k], num);
                    if(cnt == 1) {
                        st.insert(num);
                        stt.insert(num);
                    }
                }
                if((int)stt.size() > 1) {
                    flag = false;
                }
            }
        }
        if(!flag) {
            printf("-1\n");
            continue;
        }
        if((int)st.size() != 1) {
            printf("0\n");
        } else {
            set<int>::iterator it = st.begin();
            printf("%d\n", *it);
        }
    }
    return 0;
}

C. Careful Maneuvering

题意

两个小飞船被两列大飞船包围，其中一列飞船的横坐标都是 $-100$ ，另一列飞船的横坐标都是 $100$ ，它们的纵坐标都是整数，两个小飞船的横坐标都为 $0$ 。
现在两列飞船同时向小飞船发射激光炮，小飞船拥有防护罩，激光炮无法伤害它们，但是激光会穿过他们射向对面的飞船，所有大飞船的两个激光炮都是瞄准两个小飞船发射的，问小飞船的纵坐标应该在哪个位置（不必为整数），才能使得被激光炮打中的大飞船最多，输出被打中的大飞船的最大数量。

输入

第一行为 $n$ 和 $m$ $(1\leq n,m\leq60)$ ，分别表示 $x=-100$ 和 $x=100$ 的大飞船数量，第二行包含 $n$ 个整数 $y_{1,i}$ ，表示 $x=-100$ 的飞船的纵坐标，第三行的 $m$ 个整数 $y_{2,i}$ 表示 $x=100$ 的飞船的纵坐标，其中 $0\leq|y_{1,i}|,|y_{2,i}|\leq10^4$ 。

输出

能被击中的最多的大飞船数量。

样例

输入	输出
3 9 1 2 3 1 2 3 7 8 9 11 12 13	9
5 5 1 2 3 4 5 1 2 3 4 5	10

题解

由于两边飞船是对称分布的，所以小飞船的位置一定为整数或 $x.5$ ，所以可以将所有大飞船的纵坐标 $\times2$ ，所有坐标就都为整数了。
第一步预处理，先 $O(nm)$ 计算出每个小飞船的纵坐标 $(\frac{y_{1,i}+y_{2,i}}{2})$ ，对每个小飞船的纵坐标， $O(n\log m+m\log n)$ 计算出当所有大飞船瞄准这个点时，左右两边的飞船被打中的状态（用 $long~long$ 的 $64$ 个 $01$ 位记录被打中的状态），预处理时间复杂度为 $O(n^3\log n)$ 。
接着 $O((nm)^2)$ 枚举小飞船的两个位置，对于每两个小飞船的位置，将两边的飞船击中状态按位或起来，用 $bitset$ $O(1)$ 计算总的被击落的飞船数，取最大值，总的时间复杂度为 $O(n^4)$ 。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 200 + 100;
int n, m, ans;
int *it;
int Left[maxn], Right[maxn];
LL statu_Left[40000 + 100], statu_Right[40000 + 100];
int Count(LL x) {
    int ret = 0;
    for(int i = 0; i < 62; ++i) {
        ret += ((x >> i) & 1);
    }
    return ret;
}
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("test1.out", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    while(scanf("%d%d", &n, &m) != EOF) {
        ans = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d", &Left[i]);
            Left[i] *= 2;
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d", &Right[i]);
            Right[i] *= 2;
        }
        sort(Left, Left + n);
        sort(Right, Right + m);
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                int pos = (Left[i] + Right[j]) / 2;
                int Index = pos + 20000;
                statu_Left[Index] = statu_Right[Index] = 0;
                for(int k = 0; k < n; ++k) {
                    int x = 2 * pos - Left[k];
                    it = lower_bound(Right, Right + m, x);
                    if(it - Right != m && *it == x) {
                        statu_Left[Index] |= (1LL << k);
                    }
                }
                for(int k = 0; k < m; ++k) {
                    int x = 2 * pos - Right[k];
                    it = lower_bound(Left, Left + n, x);
                    if(it - Left != n && *it == x) {
                        statu_Right[Index] |= (1LL << k);
                    }
                }
            }
        }
        for(int a = 0; a < n; ++a) {
            for(int b = 0; b < m; ++b) {
                int pos1 = (Left[a] + Right[b]) / 2 + 20000;
                for(int c = 0; c < n; ++c) {
                    for(int d = 0; d < m; ++d) {
                        int pos2 = (Left[c] + Right[d]) / 2 + 20000;
                        bitset<60> bit1(statu_Left[pos1] | statu_Left[pos2]);
                        bitset<60> bit2(statu_Right[pos1] | statu_Right[pos2]);
                        ans = max(ans, (int)(bit1.count() + bit2.count()));
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

Codeforces Round #488 (Div. 1)

A. Two Squares

题意

输入

输出

样例

题解

过题代码

B. Open Communication

题意

输入

输出

样例

题解

过题代码

C. Careful Maneuvering

题意

输入

输出

样例

题解

过题代码

内容目录