2019杭电多校第九场2019杭电多校第九场

2019杭电多校第九场

熟悉的后半场挂机节奏，又苟进首页了，很快乐

1001. Rikka with Quicksort

upsolved

不是我做的,1e9调和级数分段打表

1002. Rikka with Cake

solved at 01:11

有一个矩形，给你很多射线（射线只有横平竖直的四个方向），问把矩形切成了多少块

队友说答案是交点数加一，作为一个合格的工具人，当然是把队友的想法实现啦

二维坐标离散化枚举纵坐标维护横坐标，常规套路，树状数组也可以做（我是线段树写习惯了根本没想起来还有树状数组）

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

struct P {
    int x, y;
    char op[3];
}a[N];

long long ans;
int b[N], totx, toty;
int T, n, m, K;
vector<int> in[N], out[N], le[N], ri[N];
int sum[N << 2];
void pushup(int rt) {
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void build(int rt, int l, int r) {
    if(l == r) {
        sum[rt] = 0;
        return;
    }
    int mid = l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    pushup(rt);
}

void update(int rt, int l, int r, int pos, int val) {
    if(l == r) {
        sum[rt] += val;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) update(rt << 1, l, mid, pos, val);
    else update(rt << 1 | 1, mid + 1, r, pos, val);
    pushup(rt);
}

int query(int rt, int l, int r, int L, int R) {
    if(L <= l && r <= R) 
        return sum[rt];
    int mid = l + r >> 1, ans = 0;
    if(L <= mid) ans += query(rt << 1, l, mid, L, R);
    if(R > mid) ans += query(rt << 1 | 1, mid + 1, r, L, R);
    return ans;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        ans = 0;
        scanf("%d%d%d", &n, &m, &K);
        for(int i = 1; i <= K; ++i) {
            scanf("%d%d%s", &a[i].x, &a[i].y, a[i].op);
            b[i] = a[i].x;
        }
        sort(b + 1, b + K + 1);
        totx = unique(b + 1, b + K + 1) - b - 1;
        for(int i = 1; i <= K; ++i) 
            a[i].x = lower_bound(b + 1, b + totx + 1, a[i].x) - b;
        for(int i = 1; i <= K; ++i) 
            b[i] = a[i].y;
        sort(b + 1, b + K + 1);
        toty = unique(b + 1, b + K + 1) - b - 1;
        for(int i = 1; i <= K; ++i) 
            a[i].y = lower_bound(b + 1, b + toty + 1, a[i].y) - b;
        build(1, 1, totx);
        for(int i = 1; i <= K; ++i) 
            in[i].clear(), out[i].clear(), le[i].clear(), ri[i].clear();
        for(int i = 1; i <= K; ++i) {
            if(a[i].op[0] == 'U')
                in[a[i].y].push_back(a[i].x);
            else if(a[i].op[0] == 'D') {
                out[a[i].y].push_back(a[i].x);
                update(1, 1, totx, a[i].x, 1);
            }
            else if(a[i].op[0] == 'L') 
                le[a[i].y].push_back(a[i].x);
            else
                ri[a[i].y].push_back(a[i].x);
        }
        for(int i = 1; i <= toty; ++i) {
            for(auto f: in[i])
                update(1, 1, totx, f, 1);
            int l = 0, r = 1e9;
            for(auto f: le[i])
                l = max(l, f);
            for(auto f: ri[i])
                r = min(r, f);
            if(l >= r) 
                ans += sum[1];
            else {
                if(l != 0)
                    ans += query(1, 1, totx, 1, l);
                if(r != 1e9)
                    ans += query(1, 1, totx, r, totx);
            }
            //cout << "ans = " << ans << endl;
            for(auto f: out[i])
                update(1, 1, totx, f, -1);
        }
        printf("%lldn", ans + 1);
    }
    return 0;
}

1003. Rikka with Mista

upsolved

至多40个数，对每一个子集求其所有数的和的十进制表示里(4)的个数，对所有子集求和

先折半，然后按十进制位考虑，双指针查询（不用多次排序，只要在一次完整的基数排序的过程中计算就好了）

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

struct num {
    LL l, r;
};

LL ans, base;
vector<num> x, y, A[10], B[10];
int T, n, p, q, w[50];

void dfs(int now, int step, LL tmp, vector<num> &x) {
    if(now == step) {
        x.push_back({tmp, 0});
        return;
    }
    dfs(now + 1, step, tmp, x);
    dfs(now + 1, step, tmp + w[now], x);
}

LL get0(vector<num> &A, vector<num> &B, LL limit) {
    LL res = 0;
    int j = B.size() - 1;
    for(int i = 0; i < A.size(); ++i) {
        while(j >= 0 && A[i].r + B[j].r >= limit) j--;
        res += j + 1;
    }
    return res;
}

LL get1(vector<num> &A, vector<num> &B, LL limit) {
    LL res = 0;
    int j = 0;
    for(int i = (int)A.size() - 1; ~i; --i) {
        while(j < B.size() && A[i].r + B[j].r < limit) j++;
        res += (int)B.size() - j;
    }
    return res;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        ans = 0; base = 1;
        x.clear(); y.clear();
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) 
            scanf("%d", &w[i]);
        p = n / 2;
        dfs(0, p, 0, x);
        dfs(p, n, 0, y);
        for(int bit = 1; bit <= 9; ++bit) {
            for(int i = 0; i <= 9; ++i)
                A[i].clear(), B[i].clear();
            for(auto f: x) 
                A[f.l % 10].push_back({f.l / 10, f.r});
            for(auto f: y)
                B[f.l % 10].push_back({f.l / 10, f.r});
            for(int i = 0; i <= 9; ++i) {
                int j1 = (14 - i) % 10, j2 = (13 - i) % 10;
                ans += get0(A[i], B[j1], base) + get1(A[i], B[j2], base);
            }
            int nowx = 0, nowy = 0;
            for(int i = 0; i <= 9; ++i) {
                for(auto f: A[i])
                    x[nowx++] = (num){f.l, f.r + i * base};
                for(auto f: B[i])
                    y[nowy++] = (num){f.l, f.r + i * base};
            }
            base *= 10;
        }
        printf("%lldn", ans);
    }
    return 0;
}

1005. Rikka with Game

solved at 00:16

一个字符串，两个人轮流操作，每个人有两种操作，一是立即终止游戏，二是将一个位置的字符变成下一个字符((a->b, b->c, ..., z->a))

第一个人想最小化字典序，第二个人想最大化字典序，求最后的字符串

想一想，发现是不考虑前缀(y),　如果首个字母是(z)则变成(b)，否则不变

1006. Rikka with Coin

solved at 00:51(+7)

有10,20,50,100四种面额的硬币，有(n)种商品，每种价格已知，求最少的硬币数使得硬币面额能恰好组成任意一种商品

设最贵的为(w)，面额100的要么是(w/100)个要么少一个，前三种暴力枚举

一开始max写成min了一直TLE...

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

int T, n, w[N];
int ans, tmp;

int vis[22];

bool judge(int x, int y, int z, int d) {
    memset(vis, 0, sizeof(vis));
    vis[0] = 1;
    for(int i = 1; i <= x; ++i) {
        for(int j = 20; j >= 1; --j)
            vis[j] |= vis[j - 1];
    }
    for(int i = 1; i <= y; ++i) {
        for(int j = 20; j >= 2; --j)
            vis[j] |= vis[j - 2];
    }
    for(int i = 1; i <= z; ++i) {
        for(int j = 20; j >= 5; --j)
            vis[j] |= vis[j - 5];
    }
    for(int i = 1; i <= n; ++i) {
        bool flag = 0;
        int t = w[i] % 10;
        while(t <= 20) {
            if(t + d * 10 >= w[i] && vis[t]) {flag = true; break;}
            t += 10;
        }
        if(!flag) return false;
    }
    return true;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        bool flag = true;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &w[i]);
            if(w[i] % 10)
                flag = false;
            w[i] /= 10;
        }
        if(!flag) {
            puts("-1");
            continue;
        }
        sort(w + 1, w + n + 1);
        tmp = w[n] / 10;
        ans = 1e9;
        for(int a = 0; a <= 10; ++a) {
            for(int b = 0; b <= 5; ++b) {
                for(int c = 0; c <= 2; ++c) {
                    for(int d = max(0, tmp - 1); d <= tmp; ++d) {
                        if(judge(a, b, c, d)) {
                            ans = min(ans, a + b + c + d);
                        }
                    }
                }
            }
        }
        printf("%dn", ans);
    }
    return 0;
}

1007. Rikka with Travel

solved at 02:13

给定一颗树，求满足存在一条点数为(i)的路径和一条点数为(j)的路径且两条路径不相交的点对((i, j))的数量((1<=n<=1e5))

我又是个工具人

树形dp

枚举一条边把树切成两半，然后两边分别求直径，假设为a, b, 那么((1<=i<=a&&1<=j<=b))的点对都满足条件((i, j)可以互换)

考虑两遍dfs, 第一遍处理出这个点的子树的直径，这个点往下延伸的最远的三个儿子以及长度，这个点的最大以及次大儿子直径

第二遍dfs处理出挖掉这个点的子树之后树的直径，可以用之前处理出的信息维护出来

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

long long answer;
int v[N];
int T, n, x, y;
vector<int> G[N];
int mx[N][3], p[N][3], ans[N][2];
int mxson[N][2], ps[N][2];

void dfs(int rt, int fa) {
    mx[rt][0] = 1; mx[rt][1] = -1e9; mx[rt][2] = -1e9;
    p[rt][0] = rt; p[rt][1] = -1; mx[rt][2] = -1;
    ans[rt][0] = 1;
    mxson[rt][0] = mxson[rt][1] = -1e9;
    ps[rt][0] = ps[rt][1] = -1;
    for(int v: G[rt]) {
        if(v == fa) continue;
        dfs(v, rt);
        if(mx[rt][2] < mx[v][0] + 1) {
            mx[rt][2] = mx[v][0] + 1;
            p[rt][2] = v;
        }
        if(mx[rt][2] > mx[rt][1]) {
            swap(mx[rt][2], mx[rt][1]);
            swap(p[rt][2], p[rt][1]);
        }
        if(mx[rt][1] > mx[rt][0]) {
            swap(mx[rt][1], mx[rt][0]);
            swap(p[rt][1], p[rt][0]);
        }
        if(ans[v][0] > mxson[rt][1]) {
            mxson[rt][1] = ans[v][0];
            ps[rt][1] = v;
        }
        if(mxson[rt][1] > mxson[rt][0]) {
            swap(mxson[rt][1], mxson[rt][0]);
            swap(ps[rt][1], ps[rt][0]);
        }
        ans[rt][0] = max(ans[rt][0], ans[v][0]);
    }
    ans[rt][0] = max(mx[rt][0] + mx[rt][1] - 1, ans[rt][0]);
}

void dfs2(int rt, int fa, int tmp, int len) {
    ans[rt][1] = tmp;
    for(int v: G[rt]) {
        if(v == fa) continue;
        int new_tmp = tmp;
        int new_len = len + 1;
        if(p[rt][0] != v) {
            new_len = max(new_len, mx[rt][0]);
        }
        if(p[rt][1] != v) {
            new_len = max(new_len, mx[rt][1]);
        }
        vector<int> vv;
        vv.push_back(len + 1);
        if(p[rt][0] != v)
            vv.push_back(mx[rt][0]);
        if(p[rt][1] != v)
            vv.push_back(mx[rt][1]);
        if(p[rt][2] != v)
            vv.push_back(mx[rt][2]);
        sort(vv.begin(), vv.end(), greater<int>());
        new_tmp = max(new_tmp, vv[0] + vv[1] - 1);
        if(ps[rt][0] != v)
            new_tmp = max(new_tmp, mxson[rt][0]);
        if(ps[rt][1] != v)
            new_tmp = max(new_tmp, mxson[rt][1]);
        dfs2(v, rt, new_tmp, new_len);
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        answer = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) G[i].clear();
        for(int i = 1; i < n; ++i) {
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(1, 0);
        dfs2(1, 0, 0, 0);
        memset(v, 0, sizeof(int) * (n + 3));
        for(int i = 1; i <= n; ++i) {
            int a = ans[i][0], b = ans[i][1];
            v[a] = max(v[a], b);
            v[b] = max(v[b], a);
        }
        for(int i = n; i; --i)
            v[i] = max(v[i], v[i + 1]);
        for(int i = 1; i <= n; ++i) {
            answer += v[i];
        }
        printf("%lldn", answer);
    }
    return 0;
}