xyd 模拟赛二·题解

· · 个人记录

T1 排列

显然对于一行只能选一个点，对于第一行只能选第 [1,2] 个，第二行只能选第 [1,3] 个，……，第 \lfloor \frac{n}{2}\rfloor 行只能选第 [1,\lfloor \frac{n}{2}\rfloor+1] 个；后一半完全对称。

然后呢？不会了。打个表！

盯着表可以注意到，如果把第 0 行和第 n+1 行也考虑进去（只能选 1），发现所有选法里面没有都没有 121 这个子序列！

实际上，一个序列可以被分成若干个子序列的子问题。对于一个三个数 x<y<z 的子问题，如果想要 x 和 z 都只出现一次，那么只能是 z,y,x，此时是 111，不可能取出 121！

然后就做完了，跑个 DP，记 f_{i,p_1,p_2} 表示确定到第 i 行，这一个选第 p_1 个点，前一个选第 p_2 个点能取到的最大价值，当出现 121 的时候不更新即可。

时间复杂度 O(n)

T2 onepointfive

我要是当时会四边形不等式我就会完了

发现 dis^{1.5} 满足四边形不等式，考虑决策单调性。链上的做法是简单的。

扩展到树上，考虑 dsu on tree。对于一条重链维护一个单调队列。处理一个点时，先遍历轻子树，通过当前的队列暴力更新轻子树内的答案，不加入队列；再遍历重儿子，加入队列；再遍历轻儿子，开一个新队列维护。维护队列时使用类似双指针的东西维护一个当前可能作为决策点的区间 L,R 即可。

时间复杂度 O(n\log n)。

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

#define ll long long
#define db double
#define lb long double
#define i128 __int128
#define ull unsigned long long
#define pii pair<ll, ll>
#define fir first
#define sec second  
#define iinf (int)(2e9)
#define linf (ll)(1e18)
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define per(i, r, l) for(int i = r; i >= l; i--)

ll read(){
    ll x = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
    while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;
}

const int maxn = 1e6 + 5;

int n, a[maxn];
vector<int> G[maxn];

int dep[maxn], son[maxn], siz[maxn];

void init(int u, int ff) {
    dep[u] = dep[ff] + 1, siz[u] = 1;
    for(auto v : G[u]) {
        init(v, u); siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

db f[maxn], val[maxn];
struct Seg{int l, r, x; db y;} stk[maxn];

db w(int x, db y){return pow(x, 1.5) + y;}

void dfs2(int u, int l, int r){
    while(l <= r && stk[l].r < dep[u]) ++l;
    assert(l <= r);
    f[u] = min(f[u], w(dep[u] - stk[l].x, stk[l].y) + a[u]);
    for(auto v : G[u]){
        dfs2(v, l, r);
    }
}
void dfs1(int u, int l, int r){
    while(l <= r && stk[l].r < dep[u]) ++l;
    if(l <= r) {
        f[u] = min(f[u], w(dep[u] - stk[l].x, stk[l].y) + a[u]);
        stk[l].l = dep[u] + 1;
    }
    while(l <= r && w(stk[r].l - stk[r].x, stk[r].y) > w(stk[r].l - dep[u], f[u])) --r;
    int pos = dep[u] + 1;
    if(l <= r){
        pos = stk[r].r + 1;
        int L = stk[r].l, R = stk[r].r, mid;
        while(L <= R){
            mid = (L + R) >> 1;
            if(w(mid - stk[r].x, stk[r].y) > w(mid - dep[u], f[u])) pos = mid, R = mid - 1;
            else L = mid + 1;
        }
        stk[r].r = pos - 1;
    }
    if(pos <= n) stk[++r] = {pos, n, dep[u], f[u]};
    for(auto v : G[u]){
        if(v == son[u]) continue;
        dfs2(v, l, r);
    }
    if(son[u]) dfs1(son[u], l, r);
    for(auto v : G[u]){
        if(v == son[u]) continue;
        dfs1(v, 1, 0);
    }
}

void sol(){
    n = read();
    for(int i = 1; i <= n; i++) val[i] = sqrt(i) * i;
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 2; i <= n; i++){
        int ff = read(); G[ff].push_back(i);
    }
    init(1, 0);
    for(int i = 0; i <= n; i++) f[i] = 1e30;
    f[1] = 0;
    dfs1(1, 1, 0);
    for(int i = 1; i <= n; i++) printf("%.4f ", f[i]);
}

int main(){
    freopen("onepointfive.in", "r", stdin);
    freopen("onepointfive.out", "w", stdout);
    int _ = 1;
    while(_--) sol();
}

T3 Interesting DS Problem

暂时不会。