2019 ICPC Asia Nanjing Regional 题解

124 阅读 0 评论 82 点赞

我是靠谱客的博主尊敬糖豆，最近开发中收集的这篇文章主要介绍2019 ICPC Asia Nanjing Regional 题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2019 ICPC Asia Nanjing Regional

A. A Hard Problem

题意：给定一个正整数n，你需要找到最小整数k，对于大小为k的集合{1,2,3…n}的任何子集里，都存在两个不同的整数u，v，u是v的因子。
思路：因子最小是2，所以从大到小找两倍。

#include <iostream>
using namespace std;
int main() {
    int T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        cout << ((n + 1) / 2 + 1) << endl;
    }
    return 0;
}

C. Digital Path

题意：寻找路径，路径上的点满足从一端到一端是严格递增1的。求总共有多少条这样的路径。
思路：可以连边建图，然后在拓扑序dp。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e3 + 10;
const ll mod = 1e9 + 7;
int n, m;
int a[N][N];
vector<pii> G[N][N];
int indeg[N][N], outdeg[N][N];
ll f[N][N][5];

void toposort() {
    queue<pii> q;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (indeg[i][j] == 0) {
                q.push(make_pair(i, j));
                f[i][j][1] = 1;
            }
        }
    }
    while (!q.empty()) {
        pii now = q.front();
        q.pop();
        for (auto i : G[now.first][now.second]) {
            f[i.first][i.second][2] = (f[i.first][i.second][2] + f[now.first][now.second][1]) % mod;
            f[i.first][i.second][3] = (f[i.first][i.second][3] + f[now.first][now.second][2]) % mod;
            f[i.first][i.second][4] =
                    (f[i.first][i.second][4] + f[now.first][now.second][3] + f[now.first][now.second][4]) % mod;
            indeg[i.first][i.second]--;
            if (indeg[i.first][i.second] == 0) {
                q.push(i);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int tx, ty;
            tx = i + 1;
            ty = j;
            if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) {
                if (a[i][j] - a[tx][ty] == 1) {
                    G[i][j].emplace_back(tx, ty);
                    indeg[tx][ty]++;
                    outdeg[i][j]++;
                }
                if (a[tx][ty] - a[i][j] == 1) {
                    G[tx][ty].emplace_back(i, j);
                    indeg[i][j]++;
                    outdeg[tx][ty]++;
                }
            }
            tx = i;
            ty = j + 1;
            if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) {
                if (a[i][j] - a[tx][ty] == 1) {
                    G[i][j].emplace_back(tx, ty);
                    indeg[tx][ty]++;
                    outdeg[i][j]++;
                }
                if (a[tx][ty] - a[i][j] == 1) {
                    G[tx][ty].emplace_back(i, j);
                    indeg[i][j]++;
                    outdeg[tx][ty]++;
                }
            }
        }
    }
    toposort();
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (outdeg[i][j] == 0) {
                ans = (ans + f[i][j][4]) % mod;
            }
        }
    }
    printf("%lldn", ans);
    return 0;
}

H. Prince and Princess

题意：一共有a+b+c个人，每个人在一个房子里，其中包括公主，你可以询问他们每个人一个问题，这些问题可以是：你是谁？谁在那个房间里？公主在哪个房间里？其中a个人支持你找到公主，会回答正确的问题，b个人反对你找到公主，会给你错误的答案，c个人吃瓜，他会给你捣乱，回答的正确或错误不确定。求最少问几个人能找到公主，如果不能找到输出NO。
思路：问每个人的问题都是公主在哪里，支持你的都是相同的正确答案，反对你的都不是正确的答案，吃瓜的不确定，那么只要出现半数以上的同一个数就能确定公主的位置。另外，如果只有一个人，那么不用问就知道这个人一定是公主……别被这个点坑了。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b + c == 1) {
        cout << "YES" << endl << 0 << endl;
        return 0;
    }
    if (a > b + c) {
        cout << "YES" << endl << 2 * (b + c) + 1 << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

K. Triangle

题意：给一个三角形的三个顶点a，b，c和一个点p，如果p点不在三角形上，输出-1。在三角形上找到另一个点q与p的连线把三角形切割成面积等大的两半，输出q的坐标。
思路：用叉积计算三角形的面积，分情况看，能得到q点一定在哪条边上，假设q点是使三角形平分的另一个点， $S_{pqc}$ 就是三角形面积一半，那么边qc与ac的比就是 $S_{pqc}$ 与 $S_{apc}$ 的比值。

#include <bits/stdc++.h>

using namespace std;
const double eps = 1e-8;
const double inf = 1e20;

struct Point {
    double x, y;

    Point() {};

    Point(double x, double y) : x(x), y(y) {}
};

bool zero(double x) {
    return (fabs(x) < eps); // x==0 返回 true
}

double cross(Point a, Point b, Point c) {
    return fabs((a.x - b.x) * (a.y - c.y) - (a.x - c.x) * (a.y - b.y)); // x1y2-y1x2
}

void solve(Point a, Point b, Point c, double s) {
    double k = s / cross(a, b, c);
    printf("%.12lf %.12lfn", (c.x - a.x) * k + a.x, (c.y - a.y) * k + a.y);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        Point a, b, c, d;
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y, &d.x, &d.y);
        double S = cross(a, b, c), sab = cross(a, b, d), sbc = cross(b, c, d), sac = cross(a, c, d);
        // p点不在三角形上：p与三条边组成的小三角形面积和不等于大三角形面积（在三角形外），或者三个小三角形面积都不等于0（在三角形内）
        if (!zero(S - sab - sbc - sac) || (!zero(sab) && !zero(sbc) && !zero(sac))) {
            cout << -1 << endl;
            continue;
        }
        // 8种情况
        if (zero(sab)) { // p在ab上
            if (sbc > sac) {
                solve(b, d, c, S / 2);
            } else {
                solve(a, d, c, S / 2);
            }
        } else if (zero(sbc)) { // p在bc上
            if (sab > sac) {
                solve(a, d, b, S / 2);
            } else {
                solve(a, d, c, S / 2);
            }
        } else if (zero(sac)) { // p在ac上
            if (sab > sbc) {
                solve(a, d, b, S / 2);
            } else {
                solve(b, d, c, S / 2);
            }
        }
    }
    return 0;
}