nowcoder_第一场

比赛总结

考试总结：
打的不行，没有全力去想每一个部分分，没有拼命去打。T2思路没有扩展开。
T2想到了f[i][j]为第i位，乘积为j的dp，然后发现空间会炸，之后发现所有乘积是2,3,5,7的幂相乘，然后感觉可以枚举，于是想枚举一个乘积，看有多少数在LR之间。其实发现乘积很少，直接压一下状态就行了，甚至可以写20个map的。。。。
T1没想出正解，然后就几乎放弃了，想写60分，然后写了$n^3$...还以为是$n^2$

T1

二分一个中位数并不具有单调性。可能1可以是中位数，2就不行了，3又可以了。
二分一个区间[x,+oo)，这是具有单调性的。
比如：
第一个是 101000100
第二个是 111111100
位置代表这个数字，1代表是与否。

二分很奇妙！！！

对于数字的不同的个数很少的情况：枚举一个中位数，小于的设为-1，大于等于的设为1，如果存在一个长度大于等于m的区间，那么说明存在一个中位数大于等于x。
于是可以二分这个x。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 100100;
int a[N], b[N], n, L;
bool check(int x) {
    for (int i=1; i<=n; ++i) b[i] = a[i] >= x ? 1 : -1;
    for (int i=1,Mi= 1e9; i<=n; ++i) {
        if (i > L) Mi = min(Mi, b[i - L]);
        b[i] += b[i - 1];
        if (i > L && b[i] - Mi > 0) return true;
    }
    return false;
}
int main() {
    n = read(), L = read();
    for (int i=1; i<=n; ++i) a[i] = read();
    int l = 0, r = 1e9, ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    cout << ans;
    return 0;
}

T2

乘积（第二维）状态都是$2^a+3^b+5^c+7^d$的形式，于是状态数并不多，对每个状态编一个号，然后dp。
或者直接 map< LL, LL >dp[22]。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 500100;
map<LL,int> mp;
LL f[22][N];
int num[22];
LL L, R, L1, R1;
int Index;
LL dfs(int p,LL sum,bool Head,bool lim) {
    if (p == 0) {
        if (sum >= L1 && sum <= R1) return 1;
        return 0;
    }
    int id = mp[sum];
    if (Head && !lim && f[p][id] != -1) return f[p][id];
    int u = lim ? num[p] : 9;
    LL res = 0;
    for (int i=0; i<=u; ++i) {
        if (i == 0) res += dfs(p - 1, Head?0:1, Head, lim&&i==num[p]);
        else res += dfs(p - 1, sum * i, 1, lim&&i==num[p]);
        // 如果sum * i大于R1了，不能直接跳过，因为后面还可能有0 
    }
    if (Head && !lim) f[p][id] = res;
    return res;
}
LL solve(LL x) {
    if (x < 0) return 0;
    if (x == 0 && x >= L1 && x <= R1) return 1;
    int p = 0;
    while (x) {
        num[++p] = x % 10;
        x /= 10;
    }
    return dfs(p, 1, 0, 1);
}
int pri[] = {2, 3, 5, 7};
void getsta(int x, LL sum) {
    if (x == 4) {
        mp[sum] = ++Index;
        return ;
    }
    getsta(x + 1, sum);
    for (int i=1; (sum*=pri[x])<=R1; ++i) 
        getsta(x + 1, sum);
}
int main() {
    memset(f, -1, sizeof(f));
    cin >> L >> R >> L1 >> R1;
    mp[0] = ++Index;
    getsta(0, 1ll);
    cout << solve(R) - solve(L - 1);
    return 0;
}

T3

题意：一棵树，很多条路径，每次询问(v,k)为：在v到1的路径上，寻找距离1最近的一个点u，使得这个v->u的路径被k条给出的路径完全覆盖。
一条路径覆盖另一条路径必须是被覆盖的，完全在另一条中。

暴力就是，枚举一个在v->1的路径上枚举一个u，然后判断所有的路径是否能覆盖v->u。
优化：对于查询的一条路径(u,p)，相当于查询有多少条给定的路径(x,y)，满足x在u子树，y在p子树外部，反过来也可以。
那么可以讲一条给定的路径(x,y)拆成(x,lca),(y,lca)，就是说，x,y的子树中有一条路径的一个端点在子树内，另一个端点在LCA，那么这条路径的贡献就是deth[lca]，于是在x,y出打上一个标记为deth[lca]。

现在查询v，就是在v的子树内查询第k小的数。

对每个点建立主席树，然后可以快速插叙。由于有些父节点是有子节点的信息的，于是启发式合并维护。

然后发现如果转化为dfs序上，就是查询一段区间的k小值。又出现了一个问题：就是每个点不止插入一个标记，那么就暴力插入吧，依次在主席树的序列上排开，Root[i]就是i的所有标记插入完后的位置。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 200005;
int L[N], R[N], pos[N], deth[N], f[N][21];
int ls[N * 40], rs[N * 40], sum[N * 40], Root[N];
int Time_Index, CntNode;
vector<int> T[N];
vector<int> tag[N];
void dfs(int u,int fa) {
    f[u][0] = fa;
    deth[u] = deth[fa] + 1;
    L[u] = ++Time_Index;
    pos[Time_Index] = u;
    for (int sz=T[u].size(),i=0; i<sz; ++i) {
        int v = T[u][i];
        if (v == fa) continue;
        dfs(v, u);
    }
    R[u] = Time_Index;
}
int LCA(int u,int v) {
    if (deth[u] < deth[v]) swap(u, v);
    int d = deth[u] - deth[v];
    for (int j=20; j>=0; --j) 
        if ((1 << j) & d) u = f[u][j];
    if (u == v) return u;
    for (int j=20; j>=0; --j) 
        if (f[u][j] != f[v][j]) 
            u = f[u][j], v = f[v][j];
    return f[u][0];
}
void update(int l,int r,int &rt,int last,int p) {
    rt = ++CntNode;
    ls[rt] = ls[last], rs[rt] = rs[last], sum[rt] = sum[last] + 1;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (p <= mid) update(l, mid, ls[rt], ls[last], p);
    else update(mid + 1, r, rs[rt], rs[last], p);
}
int query(int l,int r,int Head,int Tail,int k) {
    if (sum[Tail] - sum[Head] < k) return -1;
    if (l == r) return l;
    int cnt = sum[ls[Tail]] - sum[ls[Head]];
    int mid = (l + r) >> 1;
    if (k <= cnt) return query(l, mid, ls[Head], ls[Tail], k);
    else return query(mid + 1, r, rs[Head], rs[Tail], k - cnt);
}
int main() {
    int n = read(), m = read();
    for (int i=1; i<n; ++i) {
        int u = read(), v = read();
        T[u].push_back(v), T[v].push_back(u);
    }
    dfs(1, 0);
    for (int j=1; j<=20; ++j) 
        for (int i=1; i<=n; ++i) 
            f[i][j] = f[f[i][j - 1]][j - 1];
    for (int i=1; i<=m; ++i) {
        int u = read(), v = read(), lca = LCA(u, v);
        tag[u].push_back(deth[lca]), tag[v].push_back(deth[lca]);
    }
    for (int i=1; i<=n; ++i) {
        Root[i] = Root[i - 1]; // 没有也要赋一个值！！！ 
        int last = Root[i - 1];
        for (int sz=tag[pos[i]].size(),j=0; j<sz; ++j) {
            update(1, n, Root[i], last, tag[pos[i]][j]);
            last = Root[i];
        }
    }
    int Q = read();
    while (Q--) {
        int v = read(), k = read();
        int t = query(1, n, Root[L[v] - 1], Root[R[v]], k);
        if (t == -1 || t >= deth[v]) puts("0");
        else printf("%d\n", deth[v] - t);
    }
    return 0;
}