Codeforces Round # 703 (Div. 2)题解

Roast:

看到公告里说 I tried my best to create some good problems and clear statements, so I hope you'll enjoy the round:) 和 story 然后在做题时候感觉自己的C假了。感慨weak data。然而还好没有$FST$。

很可惜的就是F题用了time这个变量 $\textsf{CE}$ 了，不然绝杀了QwQ。。

我太菜了。

A - Shifting Stacks

Description

给定 $n$ 堆石头堆，第 $i$ 堆上面有 $h_i$ 块石头。现在可以进行多次操作，每次可以将第 $i$ 堆上面拿走一块石头放到第 $i+1$ 堆上面（别问能不能拿走最后一堆上面的），可以重复在某一堆上面拿，直到拿空。问能否在多次操作之后使得 $h_i$ 呈严格单调递增。$1\le n\le100,0\le h_i\le10^9$

Solution

观察发现：最小的且满足要求的数列，是 $0, 1, 2, \cdots, n-1 $。前缀和维护一下。

Code

int n , a[maxn];
void up(){
    cin >> n;
    // int sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        // sum += a[i];
    }
    vi sum(n+10);
    for(int i = 1; i <= n; i++){
        sum[i] = sum[i-1] + a[i];
    }
    int tt = 0;
    for(int i = 1; i <= n; i++){
        if(sum[i] >= tt){
            tt = tt+i;
            continue;
        }else{
            cout << "NO" << endl;
            return ;
        }
    }
    cout << "YES\n";
}

B - Eastern Exhibition

Description

给定 $n$ 个房子的坐标，第 $i$ 个房子的坐标为 $(x_i,y_i)$ 。（所有横纵坐标的值均为整数）

现在想要建一个剧院，该剧院到第 $i$ 个房子的曼哈顿距离为 $dist(x)$ ，请求出有多少个坐标，使得剧院建在这个坐标上面时，使得 $\sum_{i=1}^{n}dist(i)$ 最小？

$1\le n\le 1000,0\le x_i,y_i\le10^9$

Solution

每个维度不相关，中位数问题，甚至可以多维度。

Code

int x[maxn], y[maxn];
void up(){
    int n;
    cin >> n;
    for(int i = 1; i <= n;i++){
        cin >> x[i] >> y[i];
    }
    sort(x+1, x+1+n), sort(y+1,y+1+n);
    int ans = 0;
    if(n&1)ans=1;
    else{
        ans=ans+abs(x[n/2+1]-x[n/2]+1)*abs(y[n/2+1]+1-y[n/2]);
        
    }
    cout << ans << endl;
}

C2 - Guessing the Greatest (hard version)

Description

交互题。

已知一个长度为 $n$ 的数列 ${a_n}$ ，我们在一开始只知道数列的长度。

我们每次可以向系统询问一段区间 $[l,r]$ 内第二大元素的下标，现在我们需要经过多次询问，找出该数列中最大元素的下标。

询问次数不得超过 $20$ 次。

$2^{20}\ge 10^5$

Solution

观察到与值域没啥关系。

就考虑最大值区间在左边还是在右边。

trick ：第一次先询问一次中间，看最大值再左边还是右边。

接着二分区间。

$2^{20} > 10^5$ 可以通过。

Code

int32_t main()
{
    cin >> n;
    int l = 1, r = n;
    auto query = [&](int l , int r){
        cout << "? " << l << " " << r << endl;
        int x;
        cin >> x;
        return x;
    };
    int fii = query(1, n);
    #define mid ((l+r)>>1)
    if(fii != 1 and query(1,fii) == fii){
        l = 1, r = fii - 1;
        int ans = 0;
        while(l <= r){
            if(query(mid, fii) == fii) {
                ans = mid, l = mid+1;
            }else {
                r = mid - 1;
            }
        }
        cout << "! " << ans << endl;
    }else {
        l = fii + 1, r = n;
        int ans = 0;
        while(l <= r){
            if(query(fii, mid) == fii) {
                ans = mid , r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        cout << "! " << ans << endl;
    }
    return 0;
}

D - Max Median

Description

给定一个长度为 $n$ 的数列 ${a_n}$ ，尝试找出一组长度不短于 $k$ 的连续子数列，使得其中位数最大。

中位数的定义（和标准可能有所出入）：长度为 N 的数列，其升序排列后的第 $\lfloor\frac{N+1}{2}\rfloor$ 个元素，为该数列的中位数。

$1\le k\le n\le 2\times10^5,1\le a_i\le n$

Solution

官方做法很好：

如果 ${a_n}$ 中只有 $0$ 和 $1$ ，咋选？
显然，应该选择一个长度不小于 $k$ 的区间段，使得其中 $0$ 的数量少于 $1$ ，这样才能使得中位数是 $1$ 而非 $0$ 。
我们也可以将 0 改为 −1 ，问题就变成了如何使区间和为正数了。
直接求区间和的最大值，那么我们直接枚举 $r$ ，然后找 $suml$ 最小值，然后相减一下，看看能不能使得区间值大于 0 的。朴素复杂度 $O(n^2)$ ，数据结构优化 $O(n\ log_n)$ ，线性递推复杂度 $O(n)$。
然而，现在这数列里面的数也不只 0 和 1 ？
我们可以抽象一下，0 和 1 是典型的布尔值，那么对于数列里面的每个数，我们可以对其进行一个布尔表达式的运算，使得结果为 0 或者 1 即可（也就是将数分成两类）。
题目要求中位数最大，那我们的表达式应该也和大小有关系。不妨设定一个数 $x$ ，如果 $ai\ge x$ 就将其标记为 1，反之标记为 0 。显然 $min{1\le i\le n}a_i\le x\le max{1\le i\le n}a_i$

对于 $x$ 构造出来的新数列，如果我们可以找出一个中位数为 1 的子数列，说明这个子数列在原数列中的对应数列，他的中位数是不小于 $x$ 的。
对于这个 $x$，我们可以二分: 对中位数 $x$ 在值域上进行二分，每次线性判定，总复杂度 $O(nlogn)$

Code

int n , k , a[maxn], sum[maxn];
int32_t main()
{
    close;
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    auto chk = [&](int x){
        for(int i = 1; i <= n; i++){
            sum[i] = sum[i-1] + (a[i] >= x ? 1 : -1);
        }
        int mn = INF, mx = -INF;
        for(int i = k; i <= n; i++){
            umin(mn, sum[i-k]), umax(mx, sum[i] - mn);
        }
        return mx > 0;
    };
    int l = 0, r = INF;
    while(l < r){
        int mid = (l+r+1) >> 1;
        if(chk(mid)) l = mid;
        else r = mid-1;
    }
    cout << l << endl;
    return 0;
}

E - Paired Payment

Description

Solution

Code

1
2

F - Pairs of Paths

Description

Solution

有交的点对，按lca排序，先处理lca不同的（lca相同的直接C(size,2)就行了），不同的如果有交一定是lca深度大的再lca深度小的链上

时间复杂度$O(nlog^2)$

Code

int n, m;
struct Node {
    int v, w;
    Node(int v_, int w_) { v = v_, w = w_; }
};
vector<Node> g[maxn];
 
int father[maxn], sz[maxn];
int dis[maxn];
int dep[maxn];
vi anss;
int fa[maxn], dfn[maxn], pos[maxn], decr, timee, top[maxn], son[maxn];
void dfs(int u, int fa, int deep) {
    father[u] = fa;
    dep[u] = deep;
    sz[u] = 1;
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i].v;
        if (v == fa) continue;  //
 
        dis[v] = dis[u] + g[u][i].w;
        dfs(v, u, deep + 1);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) {
            son[u] = v;
        }
    }
}
 
int p[maxn][30];
void Init_LCA() {
    for (int j = 0; (1 << j) <= n; ++j)
        for (int i = 1; i <= n; ++i) p[i][j] = -1;
    for (int i = 1; i <= n; ++i) p[i][0] = father[i];
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i <= n; ++i)
            if (p[i][j - 1] != -1) p[i][j] = p[p[i][j - 1]][j - 1];
}
map<pii, int> mp;
int LCA(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int i, lg;
    for (lg = 0; (1 << lg) <= dep[x]; ++lg)
        ;
    --lg;
    /// 使x往上走直到和y在同一水平线上；
    for (i = lg; i >= 0; --i)
        if (dep[x] - (1 << i) >= dep[y]) x = p[x][i];
    if (x == y) return x;
    /// 此时x，y在同一水平线上，使x，y同时以相同的速度(2^j)往上走；
    for (i = lg; i >= 0; --i)
        if (p[x][i] != -1 && p[x][i] != p[y][i]) x = p[x][i], y = p[y][i];
    return father[x];
}
 
namespace Seg {
int sum[maxn * 4];
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid ((l + r) >> 1)
void build(int o, int l, int r) {
    sum[o] = 0;
    if (l == r) return;
    build(ls, l, mid), build(rs, mid + 1, r);
}
 
int query(int o, int l, int r, int L, int R) {
    if (L <= l && R >= r) return sum[o];
    int ret = 0;
    if (L <= mid) ret += query(ls, l, mid, L, R);
    if (R > mid) ret += query(rs, mid + 1, r, L, R);
    return ret;
}
void modify(LL o, LL l, LL r, int x) {
    sum[o]++;
    if (l == r) return;
    if (x <= mid)
        modify(ls, l, mid, x);
    else
        modify(rs, mid + 1, r, x);
}
}  // namespace Seg
using namespace Seg;
 
vector<pii> SS[maxn];
vi Q[maxn];
 
void dfs2(LL u, LL f, LL tp) {
    fa[u] = f;
    dfn[u] = ++timee;
    pos[timee] = u;
    top[u] = tp;
    if (son[u]) {
        dfs2(son[u], u, tp);
    }
    for (LL i = 0; i < g[u].size(); ++i) {
        LL v = g[u][i].v;
        if (v == f || v == son[u]) continue;
        dfs2(v, u, v);
    }
}
void dfs3(LL u, LL f) {
    static int id[maxn], cnt[maxn];
    LL tmp(0);
    for (LL i = 0; i < g[u].size(); ++i) {
        LL v = g[u][i].v;
        if (v == f) continue;
        dfs3(v, u);
        id[v] = ++tmp;
    }
    for (LL i = 0; i < SS[u].size(); ++i) {
        int x(SS[u][i].first), y(SS[u][i].second);
        if (x != u) {
            decr += cnt[x];
            cnt[x]++;
        }
        if (y != u) {
            decr += cnt[y];
            cnt[y]++;
        }
        if (x != u && y != u) {
            if (id[x] > id[y]) swap(x, y);
            decr -= mp[pii(x, y)];
            mp[pii(x, y)]++;
        }
    }
}
 
LL upp(int x, LL len) {
    for (LL i = 20; i >= 0; --i)
        if ((len >> i) & 1) x = p[x][i];
    return x;
}
int qry(int x, int y) {
    LL ret(0);
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret += Seg::query(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ret += Seg::query(1, 1, n, dfn[x], dfn[y]);
    return ret;
}
void change(int x) { Seg::modify(1, 1, n, dfn[x]); }
 
tuple<int , int , int > qy[300010];
int32_t main() {
    close;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y, w;
        cin >> x >> y;
        w = 1;
        g[x].push_back(Node(y, w));
        g[y].push_back(Node(x, w));
    }
    dis[1] = 1;
    dfs(1, -1, 1);
    Init_LCA();
    dfs2(1,0,1);
    cin >> m;
    int kp = 1;
    for(int i = 1; i <= m;i++) {
        int x, y;
        cin >> x >> y;
        LL z(LCA(x, y));
        Q[dep[z]].eb(i);
        // std::cout << "z === " << z << "  " << dep[z] << "\n";
        qy[i] = make_tuple(x,y,z);
        kp++;
    }
    cerr << "fuck" << endl;
    Seg::build(1, 1, n);
    cerr << "yy" << endl;
    ll Ans = 0;
    for (LL i = n; i >= 1; --i) {
        int sz = Q[i].size();
        if (!sz) continue;
        static int cnt[maxn];
        // cout << "sjad" << endl;
        for (LL j = 0; j < Q[i].size(); ++j) {
            LL now = (Q[i][j]);
            auto [x, y , z] = qy[now];
            Ans += cnt[z];
            cnt[z]++;
            Ans += qry(x, z) + qry(y, z);
        }
        for (LL j = 0; j < Q[i].size(); ++j) {
            LL now(Q[i][j]);
            auto [x, y , z] = qy[now];
            change(z);
        }
    }
    // cerr << "now " << endl;
    Seg::build(1, 1, n);
    decr = 0;
    // cout << "fuckk" << endl;
    for (LL i = n; i >= 1; --i) {
        for (LL j = 0; j < Q[i].size(); ++j) {
            int now = Q[i][j];
            auto [x, y , z] = qy[now];
            int ttt = (qry(x, z) + qry(y, z));
            decr += ttt;
        }
        for (LL j = 0; j < Q[i].size(); ++j) {
            LL now = Q[i][j];
            auto [x, y , z] = qy[now];
            if (x != z) {
                LL len = dep[x] - dep[z];
                len --;
                x = upp(x, len);
                change(x);
                anss.eb(x);
            }
            if (y != z) {
                int len = dep[y] - dep[z];
                len--;
                y = upp(y, len);
                change(y);
            }
            SS[z].eb(x, y);
        }
    }
    dfs3(1, 0);
    int fk =  Ans - decr;
    cout <<fk  << endl;
    // while (m--) {
    //     int x, y;
    //     scanf("%d%d", &x, &y);
    //     printf("%d\n", dis[x] + dis[y] - 2 * dis[LCA(x, y)]);
    // }
}