【XJTU 2020暑期集训】Day6 - 2017 ACM-ICPC, Asia Regional 2017, Japan

A - Secret of Chocolate Poles

签到题。设 f[i][0/1] 表示堆到高度 i,顶层为黑色或白色,此时的方案数。转移方程为 f[i][0]=f[i-1][1],f[i][1]=f[i-1][0]+f[i-k][0],边界条件为 f[0][0]=1,统计答案为 \sum_{i=1}^nf[i][1]

B - Parallel Lines

搜索题。每次选择剩余点中编号最小的那个,然后枚举它和那个点配对,记录其斜率并在链表中删除后继续进行dfs。全部选择完后,对于所有点对的斜率,用map统计答案。总复杂度为总情况数乘上统计答案的复杂度,即 O(C_{16}^8\cdot8!/2^8\cdot n\log n)

C - Medical Checkup

可以计算出第 i 个人体检的开始时间为前面人的健康值之和 \sum_{k=1}^{i-1}h[k],随后他开始第一个体检并花费 h[i] 分钟,随后他每完成一项体检(包括等待时间),都需要 \max_{k=1}^{i-1}h[k] 分钟,用剩余时间计算他还能做的体检数即可。

D - Making Perimeter of the Convex Hull Shortest

E - Black or White

F - Pizza Delivery

将原问题分解成两个子问题:最短路会不会变短?会不会变长?

先考虑会不会变短。记原图为 G,当前边为 e,当前边的反向边为 e',有一个显然的结论:在 G+e' 中,一条最短路不会同时包含 ee'。所以如果在 G+e' 中存在一条最短路包含 e' 且长度小于原图中的最短路,则边反向后最短路的长度一定减小。具体实现就是,先从 s,t 分别用原图 G 和全部边反向后的图 G' 跑单源最短路,得到数组 \mathrm{dis}\mathrm{rdis}。对于边 (u,v,w),如果有 \mathrm{dis}[v]+w+\mathrm{rdis}[u]\lt \mathrm{dis}[t],则最短路会变短,否则不会。

假设最短路不会变短,现在考虑会不会变长。显然,在最短路上的所有边构成了一个DAG。如果某一条边在DAG上且被所有的最短路经过,则这条边一定为这个DAG的割边,且将其反向后最短路会变长;如果某条边不在DAG上或没有被所有最短路经过,则将其反向后最短路不会变长。需要注意的是,要用tarjan求DAG的割边,加边时应将单向边变为双向边。

G - Rendezvous on a Tetrahedron

将正四面体无限展开,发现展开后原来的不同面规律分布。用所给角度与距离确定终点在哪个三角形中即可。

H - Homework

I - Starting a Scenic Railroad Service

对于政策一(乘客自己选座位),设 s_i 表示对于第 i 个区间,有多少个区间是与它有重叠的(包括它自己),则座位的最少数量为 s_k=\max_{i=1}^n s_i,证明如下。首先证明至少需要 s_k 个座位:最坏的情况是,与 k 冲突的 s_k-1 个区间先预定,则每个区间可以占用单独的一个座位,如果座位数少于 s_k 的话,轮到 k 预定时是没有座位可选的。然后证明 s_k 个座位是足够的:对于这种最坏的情况,s_k 个座位一定可以将这 s_k 个区间安排下,那么对于剩下的其它的区间,由于其 s 均不超过 s_k,所以也都可以安排下。求 s_i 时可以用树状数组求与 i 不冲突的区间个数,用 n 减去即为 s_i

对于政策二(公司安排座位),答案为在某一站时,同时在车上的乘客的最大数量。差分即可解决。

J - String Puzzle

K - Counting Cycles

Code

A - Secret of Chocolate Poles

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 105
#define int long long

using namespace std;

int n, K;
int f[MAX_N][2];

signed main() {
    scanf("%lld%lld", &n, &K);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i][0] += f[i - 1][1];
        f[i][1] += f[i - 1][0];
        if (i - K >= 0) {
            f[i][1] += f[i - K][0];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += f[i][1];
    }
    printf("%lld\n", ans);
}

B - Parallel Lines

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#define MAX_N 20

using namespace std;

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

struct Point {
    int x, y;
    Point() {}
    Point(int _x, int _y) : x(_x), y(_y) {}
    friend Point operator+(const Point &a, const Point &b) {
        return Point(a.x + b.x, a.y + b.y);
    }
    friend Point operator-(const Point &a, const Point &b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    friend bool operator<(const Point &a, const Point &b) {
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    }
    friend Point getslope(Point a, Point b) {
        Point c = a - b;
        if (!c.x) {
            return Point(0, 1);
        }
        if (!c.y) {
            return Point(1, 0);
        }
        int sgn = 1;
        if (c.x < 0) {
            sgn *= -1, c.x *= -1;
        }
        if (c.y < 0) {
            sgn *= -1, c.y *= -1;
        }
        int g = gcd(c.x, c.y);
        return Point(c.x / g, c.y / g * sgn);
    }
};

int n, ans = 0;
int L[MAX_N];
int R[MAX_N];
Point p[MAX_N];
Point slp[MAX_N];

void del(int x) {
    L[R[x]] = L[x], R[L[x]] = R[x];
}

void rec(int x) {
    L[R[x]] = R[L[x]] = x;
}

int getans() {
    map<Point, int> mp;
    int res = 0;
    for (int i = 1; i <= (n >> 1); i++) {
        mp[slp[i]]++;
    }
    for (auto it = mp.begin(); it != mp.end(); it++) {
        res += (it->second - 1) * it->second / 2;
    }
    return res;
}

void dfs(int stp) {
    if (stp == (n >> 1) + 1) {
        ans = max(ans, getans());
        return;
    }
    int h = R[0];
    del(h);
    for (int i = R[0]; i != n + 1; i = R[i]) {
        del(i);
        slp[stp] = getslope(p[h], p[i]);
        dfs(stp + 1);
        rec(i);
    }
    rec(h);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].x, &p[i].y);
    }
    for (int i = 0; i <= n + 1; i++) {
        L[i] = i - 1, R[i] = i + 1;
    }
    L[0] = n + 1, R[n + 1] = 0;
    dfs(1);
    printf("%d\n", ans);
}

C - Medical Checkup

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100005
#define int long long

using namespace std;

int n, t;
int h[MAX_N];
int s[MAX_N];
int ans[MAX_N];

signed main() {
    scanf("%lld%lld", &n, &t);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", h + i);
    }
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + h[i];
    }
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        mx = max(mx, h[i]);
        int rest = t - s[i - 1];
        if (rest < h[i]) {
            ans[i] = 1;
        } else {
            rest -= h[i];
            int d = rest / mx + 1;
            ans[i] = 1 + d;
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", ans[i]);
    }
}

D - Making Perimeter of the Convex Hull Shortest


E - Black or White


F - Pizza Delivery

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define MAX_N 100005
#define MAX_M 100005
#define pii pair<int, int>
#define int long long

using namespace std;

struct Edge {
    int t, w;
    Edge() {}
    Edge(int _t, int _w) : t(_t), w(_w) {}
};

int n, m, tot = 0;
int u[MAX_M];
int v[MAX_M];
int w[MAX_M];
int dis[MAX_N];
int rdis[MAX_N];
bool vis[MAX_N];
int dfn[MAX_N];
int low[MAX_N];
bool tag[MAX_M];
vector<Edge> e[MAX_N];
vector<Edge> re[MAX_N];
vector<pii> se[MAX_N];

void dij(int s, int *dis, vector<Edge> *e) {
    priority_queue<pii, vector<pii>, greater<pii> > q;
    memset(dis, 0x3f, sizeof(int) * (n + 5));
    memset(vis, false, sizeof(bool) * (n + 5));
    dis[s] = 0;
    q.push(pii(0, s));
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x]) {
            continue;
        }
        vis[x] = true;
        for (int i = 0; i < e[x].size(); i++) {
            int t = e[x][i].t, w = e[x][i].w;
            if (dis[x] + w < dis[t]) {
                dis[t] = dis[x] + w;
                q.push(pii(dis[t], t));
            }
        }
    }
}

void tarjan(int x, int p) {
    dfn[x] = low[x] = ++tot;
    bool flag = false;
    for (int i = 0; i < se[x].size(); i++) {
        int t = se[x][i].first, id = se[x][i].second;
        if (!dfn[t]) {
            tarjan(t, x);
            low[x] = min(low[x], low[t]);
            if (low[t] > dfn[x]) {
                tag[id] = true;
            }
        } else if (dfn[t] < dfn[x]) {
            if (t == p && !flag) {
                flag = true;
            } else {
                low[x] = min(low[x], dfn[t]);
            }
        }
    }
}

signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld%lld", u + i, v + i, w + i);
        e[u[i]].push_back(Edge(v[i], w[i]));
        re[v[i]].push_back(Edge(u[i], w[i]));
    }
    dij(1, dis, e), dij(2, rdis, re);
    for (int i = 1; i <= m; i++) {
        if (dis[u[i]] + w[i] + rdis[v[i]] == dis[2]) {
            se[u[i]].push_back(pii(v[i], i));
            se[v[i]].push_back(pii(u[i], i));
        }
    }
    tarjan(1, 0);
    for (int i = 1; i <= m; i++) {
        if (dis[v[i]] + w[i] + rdis[u[i]] < dis[2]) {
            printf("HAPPY\n");
        } else if (tag[i]) {
            printf("SAD\n");
        } else {
            printf("SOSO\n");
        }
    }
}

G - Rendezvous on a Tetrahedron

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define rad(x) ((x)*PI / 180.0)

using namespace std;

const double PI = acos(-1);

string solve(int d, int l) {
    double l1 = l * sin(rad(d)) * 2.0 / sqrt(3.0);
    double l2 = l * sin(rad(60.0 - d)) * 2.0 / sqrt(3.0);
    int fl1 = floor(l1), fl2 = floor(l2);
    double c = l1 + l2;
    int fc = fl1 + fl2 + 1;
    bool flag = c < fc;
    if (fl1 & 1) {
        if (fl2 & 1) {
            return flag ? "ZYX" : "YAX";
        } else {
            return flag ? "YZA" : "ZXA";
        }
    } else {
        if (fl2 & 1) {
            return flag ? "XAZ" : "AYZ";
        } else {
            return flag ? "AXY" : "XZY";
        }
    }
}

void replace(string &s, char a, char b) {
    int pos = s.find(a);
    while (pos != string::npos) {
        s[pos] = b;
        pos = s.find(a);
    }
}

int main() {
    ios::sync_with_stdio(false);
    string ss, s[2];
    int d, l;
    for (int i = 0; i < 2; i++) {
        cin >> ss >> d >> l;
        s[i] = solve(d, l);
        replace(s[i], 'X', ss[0]);
        replace(s[i], 'Y', ss[1]);
        if (ss == "BC") {
            replace(s[i], 'Z', 'D');
        } else if (ss == "CD") {
            replace(s[i], 'Z', 'B');
        } else {
            replace(s[i], 'Z', 'C');
        }
        sort(s[i].begin(), s[i].end());
    }
    if (s[0] == s[1]) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
}

H - Homework


I - Starting a Scenic Railroad Service

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 200005
#define MAX_L 100005
#define pii pair<int, int>

using namespace std;

int n, mx = 0;
int cnt[MAX_L];
int wl[MAX_L];
int wr[MAX_L];
pii p[MAX_N];

int asks(int *w, int k) {
    if (k <= 0) {
        return 0;
    }
    int ans = 0;
    for (int i = k; i >= 1; i -= i & -i) {
        ans += w[i];
    }
    return ans;
}

void updx(int *w, int k, int x) {
    if (k <= 0) {
        return;
    }
    for (int i = k; i <= mx; i += i & -i) {
        w[i] += x;
    }
}

int solve1() {
    for (int i = 1; i <= n; i++) {
        updx(wl, p[i].first, 1);
        updx(wr, p[i].second, 1);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        updx(wl, p[i].first, -1);
        updx(wr, p[i].second, -1);
        int sl = asks(wr, p[i].first);
        int sr = asks(wl, mx) - asks(wl, p[i].second - 1);
        int s = n - sl - sr;
        ans = max(ans, s);
        updx(wl, p[i].first, 1);
        updx(wr, p[i].second, 1);
    }
    return ans;
}

int solve2() {
    for (int i = 1; i <= n; i++) {
        cnt[p[i].first]++;
        cnt[p[i].second]--;
    }
    for (int i = 1; i <= mx; i++) {
        cnt[i] += cnt[i - 1];
    }
    int ans = 0;
    for (int i = 1; i <= mx; i++) {
        ans = max(ans, cnt[i]);
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &p[i].first, &p[i].second);
        mx = max(mx, max(p[i].first, p[i].second));
    }
    int x = solve1(), y = solve2();
    printf("%d %d\n", x, y);
}

J - String Puzzle


K - Counting Cycles


点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注