个人排位赛9补题记录

Wow! Such Sequence! (HDU 4893)

HDU的防火墙开的有点过分了，今天比赛的提交全部Network Failed。赛后发现是因为代码里有关键字update~

BTW，检查代码时发现pushdown操作下放lazy标记部分写错了：下放了lazy标记但是没有去更新子节点的值

Caravans (URAL 2034)

必须要吐槽一下这个题面：一开始我理解为，求出所有商队的所有必经点$p$，求$r$到$p$的最小距离。

结果题目的意思是：强盗知道商队会怎么走，但只能从$r$出发，问所有走法中，距离最大为多少。因此，强盗不需要埋伏在必经点！

思路：先求出从$s$到$f$的最短路长度$l$，再求从$r$到每一个点的距离$dr[i]=dist(r,i)$。建一张新图$G'$，每次从$\{x\not\in G'\mid x\in G\}$中选取一个$dr[p]$最大的点加入$G'$中，检查$dG[f]$是否为$l$（$dG[i]$代表新图中，从$s$出发到$i$的最短路，若$s$不在新图中，则$dG[i]=inf$），若是，则$dr[p]$为答案。

剩下唯一需要动点脑子的地方，就是加点以后如何计算$dG$，显然$dijkstra$即可。

---

其实上述思路可以再优化一下，二分搜索一个值$mid$，令新图包含所有$dr[x]\le mid$的点$x$，再检测新图中$dist(s,f)$是否等于$l$即可。

PS. 说实话，我看了下别人二分的做法，在105ms左右，实现的差的甚至要上170ms。因此这题的二分优化可有可无。

---

另外，本题有DP（但我更愿意称之为记忆化搜索）的解法，代码更短

定义$dfs(u)$，返回强盗在$u$所在的最短路上拦截商队的最小代价，对所有满足$dist[x]=dist[u]+1$的点，$dfs(u)=min(dr[u], max(dfs(x)))$。特别的，$dfs(s)=dr[s]$

AC代码（动态加点）--140ms

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + 100;

int n, m, s, f, r, opt;
int ds[maxn], dr[maxn], dG[maxn];
bool inG[maxn];
vector<int> G[maxn];

void bfs(int src, int * dist){
    memset(dist, 0x3f, sizeof ds);
    dist[src] = 0;
    queue<int> que;
    que.push(src);
    while(!que.empty()){
        int u = que.front(); que.pop();
        for(int v:G[u]) if(dist[v] > dist[u] + 1){
            dist[v] = dist[u] + 1;
            que.push(v);
        }
    }
}

void dijkstra(int nw_point){
    inG[nw_point] = true;
    if(nw_point != s){
        for(int v:G[nw_point]){
        if(inG[nw_point] && dG[nw_point] > dG[v] + 1) 
            dG[nw_point] = dG[v] + 1;
        }
    }else{
        dG[nw_point] = 0;
    }
    if(dG[nw_point] == inf) return;

    priority_queue<pii, vector<pii>, greater<pii> > que;
    que.push({dG[nw_point], nw_point});
    while(!que.empty()){
        pii pt = que.top(); que.pop();
        if(pt.first != dG[pt.second]) continue;

        for(int v:G[pt.second]){
            if(inG[v] && dG[v] > dG[pt.second] + 1){
                dG[v] = dG[pt.second] + 1;
                que.push({dG[v], v});
            }
        }
    }
}

void solve(){
    cin >> n >> m;
    for(int i=0, u, v; i<m; i++){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin >> s >> f >> r;
    bfs(s, ds);
    opt = ds[f];
    bfs(r, dr);
    memset(dG, 0x3f, sizeof dG);

    vector<int> pts(n);
    for(int i=0; i<n; i++) pts[i] = i + 1;
    sort(pts.begin(), pts.end(), [&](int x, int y){
        return dr[x] > dr[y];
    });

    for(int i=0; i<n; i++){
        dijkstra(pts[i]);
        if(dG[f] == opt){
            cout << dr[pts[i]] << '\n';
            break;
        }
    }
}

signed main(){
    Android;
    solve();
}

AC代码（记忆化搜索）--125ms

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + 100;

int n, m, s, f, r;
int ds[maxn], dr[maxn];
vector<int> G[maxn];

void bfs(int src, int * dist){
    // 同动态加点
}

int dp[maxn];
int dfs(int u){
    if(dp[u] != -1) return dp[u];
    int ans = dr[u], par = (u==s)?inf:0;
    for(int v:G[u]){
        if(ds[v] == ds[u] - 1){
            par = max(par, dfs(v));
        }
    }
    return dp[u] = min(ans, par);
}

void solve(){
    memset(dp, -1, sizeof dp);
    cin >> n >> m;
    for(int i=0, u, v; i<m; i++){
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin >> s >> f >> r;
    bfs(s, ds);
    bfs(r, dr);
    cout << dfs(f) << '\n';  
} 

signed main(){
    Android;
    solve();
}