Atcoder ABC 395

compaq · 2025-03-03 14:05:25 · 个人记录

D - Pigeon Swap

思路：

维护三个值：

维护过程：

对于操作1：把鸟a的位置移到位置b,那么鸟a的所在巢穴就变成了g_b , 即pos_a = g_b。
对于操作2：交换位置a和位置b的巢穴时，实际上就是swap(g_a,g_b), 因为g_a, g_b就是2个位置代表的巢穴。
对于操作3：当询问鸟a所在的位置时，如果我们知道鸟a所在的巢穴p = pos_a，又知道p号巢穴的位置id_p，那么就可以得到鸟的真实位置id[pos_a]。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10; 
int pos[N], id[N], g[N];

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) g[i] = i, pos[i] = i, id[i] = i;
    int q;
    cin >> q;
    while(q--){
        int op, a, b;
        cin >> op;
        if(op == 1){//改变鸟a所在的位置
            cin >> a >> b;
            pos[a] = g[b];//巢穴b的位置在g[b]  所以鸟a的位置就会变为g[b]
        }else if(op == 2){
            cin >> a >> b;//交换a位置和b位置的巢穴  那么g[a]和id[a]就会改变，b同理
            id[g[a]] = b;
            id[g[b]] = a; 
            swap(g[a], g[b]);//交换a号位置和b号位置的巢穴
        }else {
            cin >> a;
            cout << id[pos[a]] << endl;
        }
    }

    return 0;
}

E - Flip Edge

思路：

建分层路，第一层图是原图，第二图图是反边

在同一层内的图的直接边权为1
如果要跨层的话，那么两层同个点的之间边权为x
答案min(dis_n, dis_{n+n})
最短路算法可选Dijkstra或者SPFA

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;

vector<pair<int, ll>>g[N];

ll dis[N];
int vis[N];

void dijkstra(){

    priority_queue<pair<ll, int> >q;
    memset(dis, 0x3f, sizeof dis);

    q.push({1ll * 0, 1});
    dis[1] = 0;
    while(!q.empty()){
        int u = q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(auto cur: g[u]){
            int v = cur.first;
            ll w = cur.second;
            if(dis[u] + w < dis[v]){
                dis[v] = dis[u] + w;
                q.push({-dis[v], v});
            }
        }
    }
}

signed main() {
    int n, m, x;
    cin >> n >> m >> x;

    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, 1ll});
        g[v + n].push_back({u + n, 1ll});
    }
    for(int i = 1; i <= n; i++){
        g[i].push_back({i + n, 1ll * x});
        g[i + n].push_back({i, 1ll * x});
    }

    dijkstra(); 
    cout << min(dis[n], dis[2 * n]) << endl;
    return 0;
}

F - Smooth Occlusion

思路：

条件1： u_i + d_i = h

条件2：|u_{i-1} - u_i| \leq X

二分h, 然后check

从条件1看，对于每个上牙来说，必须满足：

u \leq h$, $u$ 肯定小于等于$h$, 否则$u + d > h$, 也不满足条件$1
由此，得到u的范围：h - d \leq u \leq h

假设第i个上牙，条件1的限制范围为[l_i, r_i]

从条件2看，

第一个上牙可以认为不受限制，从第二个牙齿开始限制。那么第二个上牙的真实范围应该是[l_1-X, r_1 + X]和[l_2,r_2]的交集
后面的上牙做法以此类推，每次用前i-1个上牙得到的范围和第i个上牙本身的范围取交集
如果最后交集为空，则无解，否则存在解

最后算出的高度为h，则答案为\sum(u_i+d_i-h) \rightarrow \sum(u_i + v_i) - n \times h

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 5;
LL n,f,t,a[N],b[N],cut[N],mid,m,ans,L[N],R[N];
bool check(LL x){
    for(int i = 1;i <= n;i ++)
        L[i] = max(x - b[i],(LL)0),R[i] = a[i];
    LL l = -1e12,r = 1e12;
    for(int i = 1;i <= n;i ++){
        l = max(l,L[i]);r = min(R[i],r);
        if(l > r) return false;
        l -= m;r += m;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    LL l = 0,r = 1e12;
    for(int i = 1;i <= n;i ++){
        cin >> a[i] >> b[i];
        r = min(r, a[i] + b[i]);
    }
    //r ++;//左闭右开区间 
    LL ans;
    while(l <= r){
        mid = l + r >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    LL res = 0;
    for(int i = 1; i <= n;i ++)
        res += (a[i] + b[i] - ans);
    cout<<res;
    return 0;
}