【XJTU 2020暑期集训】Day15 - 2019 Multi-University Training Contest 7

A - A + B = C

首先去除 a,b,c 的后导零并记录个数,最后在答案中算上即可,所以下面讨论的均为 a,b,c 个位不为0的情况。显然 x,y,z 均不为0的解一定可以转化为其中至少有一个为0的解,所以我们只讨论 x,y,z 中至少有一个为0的情况。当 x=y=z=0 时,只需判断 a+b=c 是否成立即可;当只有 x=y=0 时,只需解方程 a+b=c\cdot 10^z,求出 a+b 并去除其后导零并判断是否与 c 相等即可,对于 x=z=0,y=z=0 的情况同理可得;当只有 x=0 时,显然 a+b\cdot 10^y=c\cdot 10^z 无解,对于 y=0,z=0 的情况同样无解,至此讨论完毕,用大整数实现即可。

B - Bracket Sequences on Tree

C - Cuber Occurrence

D - Data Structure Problem

有结论:点积为最值的点对一定在凸包上,通过移动两端点的方法即可证明。由于数据随机,凸包的期望大小为 \log n。当加入点时,如果落在了凸包上则加入并重新计算凸包,则期望总重构次数为 \log n,该操作期望总复杂度 O(n\log n+\log^2 n\cdot \log\log n)。当删除点时,由于要删除的是当前剩下的第 r 个点,用pbds中的平衡树维护即可,如果删除的点是凸包上的点,则暴力重构凸包,该操作总复杂度 O(n\log n+\log^2 n)。查找点积最小值点对时,在凸包上暴力枚举即可,该操作总复杂度 O(n\log^2 n)

E - Equation

F - Halt Hater

由于向右转代价为0,所以如果当前处在某一条边上,则相当于你已经占据了不断向右转所围成的这个格子。所以将每一个格子视为一个点,从一个格子到一个边相连的格子,代价为一次直走的代价 b;从一个格子到一个点相连的格子,代价为一次左转的代价 a。若要从格子 (x_0,y_0) 到格子 (x_t,y_t),则有三种情况:两次直走、先直着走再斜着走、斜着走两次;分类讨论即可。答案即为从初始格子走到终点相邻的四个格子中答案的最小值。

G - Intersection of Prisms

H - Just Repeat

对于颜色为 c 的牌,若Cuber QQ有 x_c 张,Quber CC有 y_c 张。如果 y_c=0,则这 x_c 张牌一定是Cuber QQ留在最后出的,对于 x_c=0 的情况同理。对于每一方来说,都想让自己得分与对手得分的差值最大化,当 x_c\neq 0,y_c\neq 0 时,如果一方出了这张颜色为 c 的牌,相当于让差值增加了 x_c+y_c。所以将这些颜色按照 x_c+y_c 降序排序,然后双方轮流出 x_c+y_c 最大的颜色即可。

I - Kejin Player

f[i] 表示从第 i 级升到第 i+1 级的期望花费,则有等式 f[i]=a_i+(1-p_i)\sum_{k=x_i}^{i}f[k],移项可得 f[i]=\frac{a_i+(1-p_i)\sum_{k=x_i}^{i-1}f[k]}{p_i},递推求解即可。对于询问 l,r,答案即为 \sum_{k=l}^{r-1}f[k]

J - Final Exam

对于最坏的情况,如果出题老师想要卡掉他,一定是挑他复习时间最少的 n-k+1 道题,将其全部卡掉。所以只需要在最小的 n-k+1 道题中过其中一道题,即可满足在最坏情况下也能答对至少 k 题。对于最小的 n-k+1 道题,如果它们的复习总时长 t\le m,则老师总有办法能卡掉所有题;而当 t=m+1 时,一定至少能过其中一道题。此外要让所有题的复习总时长最小,即要在 t=m+1 的情况下让第 n-k+1 小的题目复习时长最小,即为 \left\lceil\frac{m+1}{n-k+1}\right\rceil,所以最终答案为 \left\lceil\frac{m+1}{n-k+1}\right\rceil\cdot(k-1)+m-1

Code

A - A + B = C

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_L 100005

using namespace std;

struct Bign {
    int len, sgn, w[MAX_L];
    void clear() {
        len = sgn = 1;
        memset(w, 0, sizeof(w));
    }
    Bign operator=(int x) {
        clear();
        if (x != 0) {
            if (x < 0) {
                sgn = -1, x = -x;
            }
            len = 0;
            while (x) {
                w[len++] = x % 10;
                x /= 10;
            }
        }
        return *this;
    }
    Bign operator=(string s) {
        clear();
        reverse(s.begin(), s.end());
        if (s.back() == '-') {
            sgn = -1, s.pop_back();
        }
        for (int i = 0; i < s.size(); i++) {
            w[i] = s[i] - '0';
        }
        len = s.size();
        return *this;
    }
    Bign() {
        clear();
    }
    Bign(int x) {
        *this = x;
    }
    friend istream& operator>>(istream& in, Bign& a) {
        string s;
        in >> s;
        a = s;
        return in;
    }
    friend ostream& operator<<(ostream& out, const Bign& a) {
        if (a.sgn < 0) {
            out << "-";
        }
        for (int i = a.len - 1; i >= 0; i--) {
            out << a.w[i];
        }
        return out;
    }
    friend int cmp(const Bign& a, const Bign& b) {
        if (a.sgn != b.sgn) {
            return a.sgn > b.sgn ? 1 : -1;
        }
        int res = a.sgn;
        if (a.len != b.len) {
            return a.len > b.len ? res : -res;
        }
        for (int i = a.len - 1; i >= 0; i--) {
            if (a.w[i] != b.w[i]) {
                return a.w[i] > b.w[i] ? res : -res;
            }
        }
        return 0;
    }
    friend bool eq(const Bign& a, const Bign& b) {
        return cmp(a, b) == 0;
    }
    friend Bign add(const Bign& a, const Bign& b) {
        Bign c;
        c.len = max(a.len, b.len);
        for (int i = 0; i < c.len; i++) {
            if (i < a.len) {
                c.w[i] += a.w[i];
            }
            if (i < b.len) {
                c.w[i] += b.w[i];
            }
            c.w[i + 1] += c.w[i] / 10;
            c.w[i] %= 10;
        }
        if (c.w[c.len] > 0) {
            c.len++;
        }
        return c;
    }
    friend Bign sub(Bign a, Bign b) {
        Bign c;
        if (a < b) {
            swap(a, b), c.sgn = -1;
        }
        c.len = a.len;
        for (int i = 0; i < c.len; i++) {
            c.w[i] += a.w[i];
            if (i < b.len) {
                c.w[i] -= b.w[i];
            }
            if (c.w[i] < 0) {
                c.w[i] += 10, c.w[i + 1]--;
            }
        }
        while (c.w[c.len - 1] == 0) {
            c.len--;
        }
        return c;
    }
    friend Bign operator+(const Bign& a, const Bign& b) {
        return add(a, b);
    }
    friend Bign operator-(const Bign& a, const Bign& b) {
        return sub(a, b);
    }
    friend bool operator<(const Bign& a, const Bign& b) {
        return cmp(a, b) < 0;
    }
    friend bool operator>(const Bign& a, const Bign& b) {
        return cmp(a, b) > 0;
    }
    friend bool operator==(const Bign& a, const Bign& b) {
        return eq(a, b);
    }
    int remove() {
        int cnt = 0;
        while (cnt < len && w[cnt] == 0) {
            cnt++;
        }
        for (int i = cnt, j = 0; i < len; i++, j++) {
            w[j] = w[i];
        }
        for (int i = 0, j = len - 1; i < cnt; i++, j--) {
            w[j] = 0;
        }
        len -= cnt;
        return cnt;
    }
};

int T;
Bign a, b, c;

void print(int x, int y, int z) {
    int mn = min(x, min(y, z));
    int d = max(0, -mn);
    cout << x + d << " " << y + d << " " << z + d << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> a >> b >> c;
        int ta = a.remove();
        int tb = b.remove();
        int tc = c.remove();
        if (a + b == c) {
            print(-ta, -tb, -tc);
            continue;
        }
        Bign t = c - b;
        if (t > 0) {
            int cnt = t.remove();
            if (t == a) {
                print(cnt - ta, -tb, -tc);
                continue;
            }
        }
        t = c - a;
        if (t > 0) {
            int cnt = t.remove();
            if (t == b) {
                print(-ta, cnt - tb, -tc);
                continue;
            }
        }
        t = a + b;
        if (t > 0) {
            int cnt = t.remove();
            if (t == c) {
                print(-ta, -tb, cnt - tc);
                continue;
            }
        }
        cout << -1 << endl;
    }
}

B - Bracket Sequences on Tree


C - Cuber Occurrence


D - Data Structure Problem

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define MAX_N 100005
#define EPS 1e-8
#define eq(x, y) (fabs((x) - (y)) < EPS)

using namespace std;

const unsigned mul = 20190812;

class Magic {
public:
    Magic(unsigned state) : state(state), ans(0) {}
    unsigned long long retrieve() {
        unsigned modulo = 0x7fffffff;
        state = ((unsigned long long)state * mul + ans) % modulo;
        unsigned high = state;
        state = ((unsigned long long)state * mul + ans) % modulo;
        return high * modulo + state;
    }
    int retrieve(int a, int b) {
        assert(a <= b);
        return (int)(retrieve() % (b - a + 1)) + a;
    }
    void submit(unsigned k) {
        ans = ans * mul + k;
    }
    unsigned retrieveAns() {
        return ans;
    }

private:
    unsigned state, ans;
};

#define int long long

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 int sqr(const Point &p) {
        return p.x * p.x + p.y * p.y;
    }
    friend int dot(const Point &a, const Point &b) {
        return a.x * b.x + a.y * b.y;
    }
    friend int cross(const Point &a, const Point &b) {
        return a.x * b.y - b.x * a.y;
    }
};

using namespace __gnu_pbds;
#define pii pair<int, int>
#define pip pair<int, Point>
#define ti tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define tp tree<Point, null_type, less<Point>, rb_tree_tag, tree_order_statistics_node_update>
#define tpip tree<pip, null_type, less<pip>, rb_tree_tag, tree_order_statistics_node_update>

namespace Graham {

pip p[MAX_N];
pip con[MAX_N];

bool cmp(const pip &a, const pip &b) {
    int c = cross(a.second - p[1].second, b.second - p[1].second);
    return c ? c > 0 : sqr(a.second - p[1].second) < sqr(b.second - p[1].second);
}

void graham(vector<pip> &vc) {
    if (vc.size() <= 2) {
        return;
    }
    int n = 0;
    for (int i = 0; i < vc.size(); i++) {
        p[++n] = vc[i];
    }
    for (int i = 2; i <= n; i++) {
        if (p[i].second < p[1].second) {
            swap(p[i], p[1]);
        }
    }
    sort(p + 2, p + 1 + n, cmp);
    int tot = 0;
    con[++tot] = p[1], con[++tot] = p[2];
    for (int i = 3; i <= n; i++) {
        while (tot >= 2 && cross(con[tot].second - con[tot - 1].second, p[i].second - con[tot].second) <= 0) {
            tot--;
        }
        con[++tot] = p[i];
    }
    vc.clear();
    for (int i = 1; i <= tot; i++) {
        vc.push_back(con[i]);
    }
}

}  // namespace Graham

class DataStructure {
public:
    int sz, cnt;
    tpip tr;
    vector<pip> vc;
    DataStructure() {
        sz = cnt = 0;
    }
    void add(int x, int y) {
        sz++, cnt++;
        tr.insert(pip(cnt, Point(x, y)));
        vc.push_back(pip(cnt, Point(x, y)));
        Graham::graham(vc);
    }
    void erase(int r) {
        sz--;
        pip res = *tr.find_by_order(r - 1);
        tr.erase(res);
        for (int i = 0; i < vc.size(); i++) {
            if (vc[i].first == res.first) {
                vc.clear();
                for (auto tt = tr.begin(); tt != tr.end(); tt++) {
                    vc.push_back(*tt);
                }
                Graham::graham(vc);
                return;
            }
        }
    }
    int size() {
        return sz;
    }
    pii query() {
        if (sz == 0) {
            return pii(0, 0);
        }
        int dt = dot(vc[0].second, vc[0].second);
        pii res(vc[0].first, vc[0].first);
        for (int i = 0; i < vc.size(); i++) {
            for (int j = 0; j < vc.size(); j++) {
                if (vc[i].first <= vc[j].first) {
                    int ndt = dot(vc[i].second, vc[j].second);
                    if (ndt < dt) {
                        dt = ndt, res = pii(vc[i].first, vc[j].first);
                    } else if (ndt == dt) {
                        res = min(res, pii(vc[i].first, vc[j].first));
                    }
                }
            }
        }
        return res;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    const int lim = 1e9;
    int q;
    cin >> q;
    for (int k = 0; k < q; k++) {
        unsigned state;
        cin >> state;
        string s;
        cin >> s;
        DataStructure ds;
        Magic magic(state);
        for (char c : s) {
            if (c == 'a') {
                int x = magic.retrieve(-lim, lim);
                int y = magic.retrieve(-lim, lim);
                ds.add(x, y);
            } else if (c == 'e') {
                unsigned pos = magic.retrieve(1, ds.size());
                ds.erase(pos);
            } else if (c == 'q') {
                auto best = ds.query();
                magic.submit(best.first);
                magic.submit(best.second);
            }
        }
        cout << magic.retrieveAns() << endl;
    }
}

E - Equation


F - Halt Hater

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

using namespace std;

int T, a, b, x, y;

int solve(int x, int y) {
    x = abs(x), y = abs(y);
    int ans = (x + y) * b;
    int mn = min(x, y), mx = max(x, y);
    ans = min(ans, (mx - mn) * b + mn * a);
    if ((x + y) & 1) {
        ans = min(ans, (mx - 1) * a + b);
    } else {
        ans = min(ans, mx * a);
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> a >> b >> x >> y;
        int ans = solve(x, y);
        ans = min(ans, solve(x - 1, y));
        ans = min(ans, solve(x, y + 1));
        ans = min(ans, solve(x - 1, y + 1));
        cout << ans << endl;
    }
}

G - Intersection of Prisms


H - Just Repeat

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

using namespace std;

int T, n, m, p;
int a[MAX_N];
int b[MAX_N];

namespace Gen {
unsigned long long k1, k2, mod;
unsigned long long rng() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}
void gen() {
    cin >> k1 >> k2 >> mod;
    for (int i = 1; i <= n; i++) {
        a[i] = rng() % mod;
    }
    cin >> k1 >> k2 >> mod;
    for (int i = 1; i <= m; i++) {
        b[i] = rng() % mod;
    }
}
}  // namespace Gen

struct cmp {
    bool operator()(const pii &a, const pii &b) {
        return a.first + a.second < b.first + b.second;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> m >> p;
        if (p == 1) {
            for (int i = 1; i <= n; i++) {
                cin >> a[i];
            }
            for (int i = 1; i <= m; i++) {
                cin >> b[i];
            }
        } else {
            Gen::gen();
        }
        map<int, pii> mp;
        for (int i = 1; i <= n; i++) {
            mp[a[i]].first++;
        }
        for (int i = 1; i <= m; i++) {
            mp[b[i]].second++;
        }
        int ra = 0, rb = 0;
        priority_queue<pii, vector<pii>, cmp> q;
        for (auto it = mp.begin(); it != mp.end(); it++) {
            pii tp = it->second;
            if (!tp.first || !tp.second) {
                ra += tp.first, rb += tp.second;
            } else {
                q.push(tp);
            }
        }
        int sd = 0, sa = 0, sb = 0;
        while (!q.empty()) {
            pii tp = q.top();
            q.pop();
            if (sd == 0) {
                sa += tp.first;
            } else {
                sb += tp.second;
            }
            sd = 1 - sd;
        }
        int ta = ra + sa, tb = rb + sb;
        if (ta > tb) {
            cout << "Cuber QQ" << endl;
        } else {
            cout << "Quber CC" << endl;
        }
    }
}

I - Kejin Player

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 500005
#define MOD 1000000007
#define inv(x) (fpow((x), MOD - 2))
#define int long long

using namespace std;

int T, n, q;
int p[MAX_N];
int x[MAX_N];
int a[MAX_N];
int f[MAX_N];
int s[MAX_N];

int fpow(int x, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) {
            ans = ans * x % MOD;
        }
        x = x * x % MOD, k >>= 1;
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> q;
        int u, d;
        for (int i = 1; i <= n; i++) {
            cin >> u >> d >> x[i] >> a[i];
            p[i] = u * inv(d) % MOD;
        }
        for (int i = 1; i <= n; i++) {
            f[i] = (a[i] + (1 - p[i] + MOD) * (s[i - 1] - s[x[i] - 1] + MOD)) % MOD * inv(p[i]) % MOD;
            s[i] = (s[i - 1] + f[i]) % MOD;
        }
        int l, r;
        while (q--) {
            cin >> l >> r;
            cout << (s[r - 1] - s[l - 1] + MOD) % MOD << endl;
        }
    }
}

J - Final Exam

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

using namespace std;

int T, n, m, K;

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> m >> K;
        cout << (int)ceil((m + 1.0) / (n - K + 1.0)) * (K - 1) + m + 1 << endl;
    }
}
点赞

发表评论

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