刷题记（ACM-ICPC 2018 沈阳赛区网络预赛 - II）

CONTENT: ACM-ICPC 2018 沈阳赛区网络预赛 II
PROBLEMS:
Ka Chang - J
Convex Hull - C
The cake is a lie - E

BB

Today OTZ 廖神！

Introduction

本文主要涉及2018年沈阳网络赛的通过人数10~99的题目
剩下两题1、2人通过的日后再战 QAQ

Ka Chang - J
Convex Hull - C
The cake is a lie - E

另外附个貌似是出题人的题解 orz
https://www.cnblogs.com/Asm-Definer/p/9610262.html

Ka Chang - J

Link
https://nanti.jisuanke.com/t/A1998
Description
给定一棵树，节点从1到N，根为1，初始时节点权值均为0，现在有两种操作
1 L X: 将深度为L的节点权值加上X
2 X: 询问节点为X的子树的权值和
其中，N <= 1e5，X <= 1e8
Sample Input

Sample Output

1
0

Solution：树状数组（线段树） + DFS序 + 分块
没有显然做法，考虑分块，设置阈值block，设跑dfs序时的时间戳分别为st和ed，
当size(deep[L]) < block时，用树状数组维护节点u的st[u]对应的权值，更新时暴力更新，查询时暴力查询
当size(deep[L]) > block时，用数组deepVal[L]记录第L层对应的答案累计值，以及vectordeep_node[L]记录节点的st[u]，更新时直接更新，查询时遍历+根据st[root]与ed[root]二分查询节点数量cnt，那么其对答案的共享为deepVal[L] * cnt，累加即是这一部分的答案
对应两个部分，相加即是查询值

#include <bits/stdc++.h>
//#define __DEBUG
using namespace std;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;

struct edge {
    int v, nxt;
};
ll tree[N], deep_val[N];
vector<int> deep[N], vec_deep;
int dfstot, st[N], ed[N];

edge e[N << 1];
int head[N], tot;

inline void init() {
    memset(tree, 0, sizeof(tree));
    memset(head, -1, sizeof(head));
    memset(deep_val, 0, sizeof(deep_val));
    for(int i = 0; i < N; i++) {
        deep[i].clear();
    }
    vec_deep.clear();
    dfstot = tot = 0;
}

inline void addEdge(int u, int v) {
    e[tot] = edge{v, head[u]};
    head[u] = tot++;
}

inline int lowbit(int x) {
    return x & -x;
}

inline void update(int x, int val) {
    for(; x < N; x += lowbit(x)) {
        tree[x] += val;
    }
}

inline ll getSum(int x) {
    ll ret = 0;
    for(; x > 0; x -= lowbit(x)) {
        ret += tree[x];
    }
    return ret;
}

void dfs(int u, int pre, int d) {
    st[u] = ++dfstot;
    deep[d].emplace_back(st[u]);
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(v == pre) {
            continue;
        }

        dfs(v, u, d + 1);
    }
    ed[u] = dfstot;
}

int main() {
    int n, q;
    while(~scanf("%d%d", &n, &q)) {
        init();
        int block = sqrt(n);
        for(int i = 1; i <= n - 1; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }
        dfs(1, -1, 0);

        for(int i = 0; i < N; i++) {
            if(deep[i].size() > block) {
                vec_deep.emplace_back(i);
            }
        }

        while(q--) {
            int op;
            scanf("%d", &op);
            if(op == 1) {
                int dpt, val;
                scanf("%d%d", &dpt, &val);

                if(deep[dpt].size() > block) {
                    deep_val[dpt] += val;
                } else {
                    for(int idx : deep[dpt]) {
                        update(idx, val);
                    }
                }
            } else {
                int x;
                scanf("%d", &x);
                ll ans = getSum(ed[x]) - getSum(st[x] - 1);
                for(int dpt : vec_deep) {
                    ans += deep_val[dpt] * (upper_bound(deep[dpt].begin(), deep[dpt].end(), ed[x]) -
                                            lower_bound(deep[dpt].begin(), deep[dpt].end(), st[x]));
                }
                printf("%lld\n", ans);
            }
        }
    }
}

Convex Hull - C

Link
https://nanti.jisuanke.com/t/A1991
Description
已知

\[gay(i)=\left\{ \begin{array}{rcl} & 0, \quad& if \quad i = k*x*x, x > 1, k \geq 1 \\ & i * i ,\quad& else \end{array} \right.\]

求

\[\sum_{num=1}^n (\sum_{i=1}^{num} gay(i)) \mod p\]

其中 n <= 1e10， p <= 1e11
Sample Input

1 10
8 19230817

Sample Output

1
396

Solution：容斥原理 + 快速乘
显然，

\[\begin{aligned} ans &= \sum_{i=1}^{n}(n-i+1) \mu(i)^2 i^2 \\ &= (n+1)\sum_{i=1}^{n} \mu(i)^2 i^2 - \sum_{i=1}^{n} \mu(i)^2 i^3 \end{aligned}\]

然后发现线性还不够而且还套不进杜教筛 GG QAQ
其实只需要容斥一下就好了
考虑\mu(i) = 0的情况，用全部情况减去这种情况即是答案
当\mu(i) = 0时，说明该数有平方因子，因此考虑容斥，用DFS法组合质因子的平方，便于剪枝，现有一质因子平方组合出来的数k，其对答案的贡献为

\[ans_k = f(k) \cdot \left[(n+1)k^2 \sum_{i=1}^{n/k} i^2 - k^3\sum_{i=1}^{n/k} i^3\right]\]

其中，当k为奇数个质因子平方组合出来时值为-1，否则值为1
将1也视为由偶数个质因子平方组合出来的值后，累加ans_x即是答案

#include <bits/stdc++.h>
//#define NDEBUG
using namespace std;
typedef long long ll;
typedef pair<ll, int> pr;
const int N = 1e5 + 15;
const ll M = 1e10 + 5;

ll prime[N];
bool isprime[N];
int tot;
ll mod;
vector<pr> fac;

inline ll multi(ll x, ll y) {
    ll tmp = (x * y - (ll)((long double)x / mod * y + 1e-8) * mod);
    return tmp < 0 ? tmp + mod : tmp;
}

inline ll multi(vector<ll>& vec) {
    ll ans = vec[0];
    for(int i = 1, sz = vec.size(); i < sz; i++) {
        ans = multi(ans, vec[i]);
    }
    return ans;
}

void dfs(int idx, int tag, bool ok, ll val) {
    if(ok) {
        fac.emplace_back(make_pair(val, tag));
    }

    if(idx + 1 < tot && val < (double)M / prime[idx + 1]) {
        dfs(idx + 1, tag ^ 1, true, val * prime[idx + 1]);
        dfs(idx + 1, tag, false, val);
    }
}

inline void init() {
    memset(isprime, true, sizeof(isprime));
    tot = 0;

    prime[tot++] = 1;
    for(int i = 2; i < N; i++) {
        if(isprime[i]) {
            prime[tot++] = i;
        }
        for(int j = 1; prime[j] * i < N && j < tot; j++) {
            isprime[prime[j] * i] = false;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }

    for(int i = 0; i < tot; i++) {
        prime[i] = prime[i] * prime[i];
    }

    fac.emplace_back(make_pair(1, 0));
    dfs(0, 0, false, 1);
    sort(fac.begin(), fac.end());
}

ll solve(ll n) {
    ll ans = 0;
    vector<ll> vec;
    for(int i = 0, sz = fac.size(); i < sz && fac[i].first <= n; i++) {
        ll val = fac[i].first;
        int tag = fac[i].second & 1;

        vec.clear();

        ll div = n / val;
        vec = {div, div + 1, 2 * div + 1, n + 1, val, val};

        bool dt1 = false, dt2 = false;
        for(int i = 0; i < 3; i++) {
            ll& ele = vec[i];
            if(dt1 == false && (ele & 1) == 0) {
                ele >>= 1LL;
                dt1 = true;
            }
            if(dt2 == false && ele % 3 == 0) {
                ele /= 3;
                dt2 = true;
            }
            if(dt1 && dt2) {
                break;
            }
        }

        ll t1 = multi(vec);

        vec = {div, div, div + 1, div + 1, val, val, val};
        if(div & 1) {
            vec[2] >>= 1LL;
            vec[3] >>= 1LL;
        } else {
            vec[0] >>= 1LL;
            vec[1] >>= 1LL;
        }

        ll t2 = multi(vec);

        if(tag & 1) {
            ans = ((ans + t2 - t1) % mod + mod) % mod;
        } else {
            ans = ((ans + t1 - t2) % mod + mod) % mod;
        }
    }
    return ans;
}

int main() {
    init();
    ll n;
    while(~scanf("%lld%lld", &n, &mod)) {
        printf("%lld\n", solve(n));
    }
}

The cake is a lie - E

Link
https://nanti.jisuanke.com/t/A1993
Description
给定n个半径为R的圆的坐标，求至少包含m个圆的最小圆半径
其中 n <= 300，如果不能则输出The cake is a lie.
Sample Input

Sample Output

1.7071
The cake is a lie.

Solution：单位圆覆盖问题变形
翻Solution的时候看到神犇说本题的前身应是POJ 1981，然后就去A掉果然这题就会做了
首先不管条件s与圆的半径R，那么本题应与POJ 1981题一样
现在考虑条件s，可以二分半径，求出套住做多的圆是否满足s，极小化处理
现在再考虑半径R，实际上二分完之后，大家都要加上R，所以最后答案加R即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define OJ
using namespace std;
const int N = 300 + 15;
const double eps = 1e-6;
const double PI = acos(-1);
const int inf = 0x3f3f3f3f;

struct Point {
    double x, y;
};

struct Segment {
    double x;
    int tag;
    bool operator < (const Segment& b) const {
        return x < b.x;
    }
};

Point pt[N];
Segment seg[N << 2];

inline int dcmp(double x) {
    if(x > -eps && x < eps) {
        return 0;
    }
    return x > eps ? 1 : -1;
}

inline double sqr(double x) {
    return x * x;
}

inline double getDis(Point& a, Point& b) {
    return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

int solve(int n, double r) {
    int ans = 1;
    for(int i = 0; i < n; i++) {
        int tot = 0;
        for(int j = 0; j < n; j++) {
            double d = getDis(pt[i], pt[j]);
            if(i == j || dcmp(d - 2 * r) > 0) {
                continue;
            }

            double ang = atan2(pt[j].y - pt[i].y, pt[j].x - pt[i].x);
            double phi = acos(d / 2 / r);
            seg[tot].x = ang - phi, seg[tot++].tag = 1;
            seg[tot].x = ang + phi, seg[tot++].tag = -1;
            //seg[tot].x = ang - phi + 2 * PI, seg[tot++].tag = 1;
            //seg[tot].x = ang + phi + 2 * PI, seg[tot++].tag = -1;
        }

        sort(seg, seg + tot);
        for(int i = 0, sum = 1; i < tot; i++) {
            sum += seg[i].tag;
            ans = max(ans, sum);
        }
    }
    return ans;
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        int n, s;
        double sr;
        scanf("%d%d", &n, &s);
        for(int i = 0; i < n; i++) {
            scanf("%lf%lf", &pt[i].x, &pt[i].y);
        }
        scanf("%lf", &sr);

        if(s > n) {
            puts("The cake is a lie.");
            continue;
        }

        double l = 0, r = inf;
        while(r - l > eps) {
            double m = (l + r) / 2;
            if(solve(n, m) >= s) {
                r = m;
            } else {
                l = m;
            }
        }
        printf("%.4f\n", l + sr);
    }
}