Preface

最后一天~

Content

[CF1175E]Minimal Segment Cover

给定形如 /([l,r]/) 的 /(n/) 条线段。/(m/) 次询问，询问每次至少选几条线段才能使它们的并集包含线段 /([x,y]/)。无解输出 /(-1/)。

/(1/le n,m/le 2/times 10^5,0 /le l/lt r/le 5/times 10^5,0/le x/lt y /le 5/times 10^5/)。

简单题。先从一组询问 /([x,y]/) 的情况找思路。

根据贪心的思想，发现我们首先肯定是找一条线段 /([l,r]/)，使得 /(l /le x/) 且 /(r/) 最大化，这样就覆盖上了 /([x,r]/)，转化为 /([r,y]/) 的子问题。

不难发现，这个问题其实相当于从 /(x/) 跳到某条线段 /([l,r](l/le x/le r)/) 的右端点 /(r/)，再从 /(r/) 继续往右跳，直到 /(x/ge y/)。

这个问题显然可以用倍增处理。时间复杂度 /(O((n+m)/log V)/)。

Code

写代码的时候智力下线，WA 了好几发 QAQ。

// Problem: CF1175E Minimal Segment Cover
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1175E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxm = 6e5 + 5;
int n,m,cnt,f[maxm][22];
int main() {
    cnt = 0;
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;++ i) {
        int l,r;
        scanf("%d %d",&l,&r);
        f[l][0] = max(f[l][0] , r);
        cnt = max(cnt , r);
    }
    for(int i = 1;i <= cnt;++ i)f[i][0] = max(f[i][0] , f[i - 1][0]);
    for(int k = 1;k <= 20;++ k) {
        for(int i = 0;i <= cnt;++ i) {
            f[i][k] = f[f[i][k - 1]][k - 1];
        }
    }
    while(m --) {
        int x,y,ans = 0;
        scanf("%d %d",&x,&y);
        for(int k = 20;~ k;-- k) {
            if(f[x][k] < y)ans += 1 << k,x = f[x][k];
        }
        if(f[x][0] >= y)printf("%d/n",ans + 1);
        else puts("-1");
    }
    return 0;
}

[CF1009F]Dominant Indices

题解放在了长链剖分入门这篇文章里。

[CF1051F]The Shortest Statement

/(n/) 个点，/(m/) 条边的无向连通图。/(q/) 次询问，每次询问 /(x,y/) 间的最短路。

/(1/le n,m,q /le 10^5,m-n/le 20/)。

注意到 /(m-n/le 20/) 这个条件非常奇怪，它其实是在告诉我们，至多有 /(21/) 条非树边。

这样的话，至多会产生 /(42/) 个特殊节点。

/(x/to y/) 的路径只有两种可能：不经过任何一个特殊节点，或经过某个特殊节点。

那么我们把这些特殊节点选出来，跑 Dijkstra 得出最短路。

每次询问中，枚举得出 /(x/to y/) 经过每个特殊节点的最短路，和 /(x/to y/) 在树上的距离取最小值即可。

时间复杂度 /(O(n/log n+(m-n+1)/times n/log n)/)。

Code

// Problem: CF1051F The Shortest Statement
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1051F
// Memory Limit: 250 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
typedef pair<ll,int> pii;
const ll INF = 1e14;
int head[maxn],from[maxn << 1],ver[maxn << 1],nxt[maxn << 1],dis[maxn << 1],cnt;
void add(int u,int v,int t) {
    ver[++ cnt] = v;
    from[cnt] = u;
    nxt[cnt] = head[u];
    head[u] = cnt;
    dis[cnt] = t;
    return ;
}
bool vis[maxn << 1],ins[maxn];
int n,m,f[maxn][20],lg[maxn],d[maxn];
ll dp[maxn][20],dist[45][maxn];
void dfs(int u) {
    ins[u] = true;
    for(int i = head[u];~ i;i = nxt[i]) {
        int v = ver[i],w = dis[i];
        if(ins[v])continue ;
        vis[i] = vis[i ^ 1] = true;
        f[v][0] = u;
        dp[v][0] = w;
        d[v] = d[u] + 1;
        for(int k = 1;(1 << k) <= d[v];++ k) {
            f[v][k] = f[f[v][k - 1]][k - 1];
            dp[v][k] = dp[v][k - 1] + dp[f[v][k - 1]][k - 1];
        }
        dfs(v);
    }
    return ;
}
ll calcdis(int u,int v) {
    if(d[u] < d[v])swap(u , v);
    ll ans = 0;
    for(int k = lg[d[u]];~ k;-- k) {
        if(d[u] - (1 << k) >= d[v]) {
            ans += dp[u][k];
            u = f[u][k];
        }
        if(u == v)return ans;
    }
    for(int k = lg[d[u]];~ k;-- k) {
        if(f[u][k] != f[v][k]) {
            ans += dp[u][k] + dp[v][k];
            u = f[u][k];
            v = f[v][k];
        }
    }
    return ans + dp[u][0] + dp[v][0];
}
priority_queue<pii,vector<pii>,greater<pii> > q;
void dijkstra(int k,int s) {
    memset(vis , false , sizeof(vis));
    for(int i = 1;i <= n;++ i)dist[k][i] = INF;
    q.emplace(dist[k][s] = 0 , s);
    while(!q.empty()) {
        auto [p , u] = q.top();
        q.pop();
        if(vis[u])continue ;
        vis[u] = true;
        for(int i = head[u];~ i;i = nxt[i]) {
            int v = ver[i],w = dis[i];
            if(dist[k][v] > dist[k][u] + w) {
                dist[k][v] = dist[k][u] + w;
                q.emplace(dist[k][v] , v);
            }
        }
    }
    return ;
}
int main() {
    scanf("%d %d",&n,&m);
    memset(head , -1 , sizeof(head));
    cnt = -1;
    for(int i = 2;i <= n;++ i)lg[i] = lg[i >> 1] + 1;
    for(int i = 1;i <= m;++ i) {
        int u,v,t;
        scanf("%d %d %d",&u,&v,&t);
        add(u , v , t);
        add(v , u , t);
    }
    dfs(1);
    memset(ins , false , sizeof(ins));
    for(int i = 0;i <= cnt;++ i) {
        if(vis[i]||vis[i ^ 1])continue ;
        ins[from[i]] = ins[ver[i]] = vis[i] = vis[i ^ 1] = true;
    }
    int cur = 0;
    for(int i = 1;i <= n;++ i) {
        if(ins[i])dijkstra(cur ++ , i);
    }
    int Q;
    scanf("%d",&Q);
    while(Q --) {
        int x,y;
        scanf("%d %d",&x,&y);
        ll t = calcdis(x , y);
        for(int i = 0;i < cur;++ i)t = min(t , dist[i][x] + dist[i][y]);
        printf("%lld/n",t);
    }
    return 0;
}

这是暑假的最后一天了，后面准备打一场 ABC，然后用小号玩玩 CF。

upd：ABC F 题不会摆烂，CF D 不会摆烂，哈哈，反正最后一天了。

趁着还能碰电子产品赶紧再看一会末日三问（