ICPC2020-沈阳站

题目链接

H-Hard Calculation

#include<iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    cout << n + 2020 << endl;
    return 0;
}

I-Mr. Main and Windmills

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second
const int N = 1005, INF = 1e9 + 7;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;

struct Line {
    double k, b;
};

int n, m, h, k;
PII s, t, l, r;
PII p[N];
vector<PDD> arr;

Line create(int x1, int y1, int x2, int y2) {
    int dy = y1 - y2, dx = x1 - x2;
    if (dx == 0) return {INF, x1 * 1.0};
    double k = dy * 1.0 / dx;
    return {k, y1 - k * x1};
}

//获取交点
PDD get(Line &l1, Line &l2) {
    if (l1.k == l2.k) {         //平行，无交点
        return {INF, INF};
    } else if (l1.k == INF) {  //l1垂直
        return {l1.b, l2.k * l1.b + l2.b};
    } else if (l2.k == INF) {   //l2垂直
        return {l2.b, l1.k * l2.b + l1.b};
    }

    double xx = (l2.b - l1.b) / (l1.k - l2.k);
    return {xx, l1.k * xx + l1.b};
}

int main() {
    cin >> n >> m;
    scanf("%d%d%d%d", &s.x, &s.y, &t.x, &t.y);
    for (int i = 1; i <= n; i++) scanf("%d%d", &p[i].x, &p[i].y);
    l = {s.x, s.y}, r = {t.x, t.y};
    if (l > r) swap(l, r);

    //路径向量
    PII v = {t.x - s.x, t.y - s.y};
    Line row = create(t.x, t.y, s.x, s.y);
    while (m--) {
        arr.clear();
        scanf("%d%d", &h, &k);
        for (int j = 1; j <= n; j++) {
            if (h == j) continue;
            Line line = create(p[h].x, p[h].y, p[j].x, p[j].y);
            PDD jd = get(row, line);
            if (jd.x == INF) {    //无交点
                continue;
            }

            if (row.k == INF) {   //路径垂直
                if (jd.y < l.y || jd.y > r.y) continue;
            } else {
                if (jd.x < l.x || jd.x > r.x) continue;
            }
            arr.push_back(jd);
        }

        sort(arr.begin(), arr.end());
        arr.erase(unique(arr.begin(), arr.end()), arr.end());
        int sz = arr.size();
        if (k > sz) {
            puts("-1");
            continue;
        }
        if (sz == 1) {
            printf("%.10lf %.10lf\n", arr[0].x, arr[0].y);
            continue;
        }

        PDD vv = {arr[1].x - arr[0].x, arr[1].y - arr[0].y};
        if (vv.x * v.x >= 0 && vv.y * v.y >= 0) printf("%.10lf %.10lf\n", arr[k - 1].x, arr[k - 1].y);
        else printf("%.10lf %.10lf\n", arr[sz - k].x, arr[sz - k].y);
    }

    return 0;
}

J-Parallel Sort

#include<bits/stdc++.h>

using namespace std;
#define x first
#define y second
const int N = 1e5 + 5;
typedef pair<int, int> PII;
int n, a[N], m, k;
bool v[N];
vector<int> arr;
vector<vector<PII>> ans;

//检测是否为最终结果
bool check() {
    for (int i = 1; i <= n; i++) if (a[i] != i) return false;
    return true;
}

//遍历p节点所在图
void vis(int p) {
    arr.clear();
    bool st = true;
    for (int i = p; st || i != p; i = a[i]) {
        arr.push_back(i);
        v[i] = true;
        st = false;
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    while (!check()) {
        vector<PII> an;
        k++;    //交换轮数
        memset(v, false, sizeof v);
        for (int i = 1; i <= n; i++) {
            if (a[i] != i && !v[i]) {
                vis(i);
                int l = 0, r = arr.size() - 1;
                while (l < r) {
                    swap(a[arr[l]], a[arr[r]]);
                    an.push_back({arr[l], arr[r]});
                    l++, r--;
                }
            }
        }
        ans.push_back(an);
    }

    //结果输出
    cout << k << endl;
    for (int i = 0; i < ans.size(); i++) {
        printf("%d ", ans[i].size());
        for (int j = 0; j < ans[i].size(); ++j) {
            printf("%d %d ", ans[i][j].x, ans[i][j].y);
        }
        puts("");
    }

    return 0;
}

L-Simone and graph coloring

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
int T, n, a[N], f[N], pos[N];

int main() {
    cin >> T;
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

        int len = 1;
        f[1] = a[1];
        pos[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (a[i] < f[len]) {
                f[++len] = a[i];
                pos[i] = len;
            } else {
                int id = lower_bound(f + 1, f + len + 1, a[i], greater<int>()) - f;
                f[id] = a[i];
                pos[i] = id;
            }
        }

        printf("%d\n", len);
        for (int i = 1; i <= n; i++) printf("%d ", pos[i]);
        puts("");
    }
    return 0;
}