ABC395D/E/F简要题解

D - Pigeon Swap (atcoder.jp)

题面：

数据范围：

直接模拟，复杂度为$O(nq)$，发现复杂度瓶颈在操作2，考虑优化操作2。

考虑固定住所有鸽巢，交换两个巢中的鸽子当作更换两个鸽巢的编号，记录每个位置的鸽巢编号，每个编号的鸽巢位于哪个位置，每个鸽子位于哪个位置，即可$O(1)$实现三个操作。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1000005,inf = 2e18,mod=1000000007;
int n;
int q;
int bel[N];
int id[N];
int invid[N];
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        bel[i]=id[i]=invid[i]=i;
    }
    while(q--){
        int op;cin>>op;
        if(op==1){
            int a,b;cin>>a>>b;
            bel[a]=invid[b];
        }
        else if(op==2){
            int a,b;
            cin>>a>>b;
            int x=invid[a],y=invid[b];
            id[y]=a;
            id[x]=b;
            invid[a]=y;
            invid[b]=x;
        }
        else if(op==3){
            int a;cin>>a;
            cout<<id[bel[a]]<<"\n";
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
}

E - Flip Edge (atcoder.jp)

给定$n$个点$m$条边的有向图，你每次可以花费$1$的代价经过一条边，或者花费$x$的代价使所有边反向，求从起点$1$到终点$n$的最短路。

反转反转所有边$1、3、5$次都是一样的，所以设立状态$di{s}_{u,0/1}$表示反转偶数次/奇数次到$u$点的最短路。

二维数组压一维：令$2\ast u-1$表示反转偶数次到达$u$点的最短路，$2\ast u$表示反转了奇数次到达$u$点的最短路

对于一条边$(u,v)$，我们可以在$2\ast u-1$与$2\ast v-1$之间建一条长度为$1$的有向边，在$2\ast v$与$2\ast u$之间建一条长度为$1$的有向边。

对于所有点我们可以在$2\ast u-1$与$2\ast u$之间建一条长度为$x$的双向边。

求出$1$到$2\ast n-1$和$2\ast n$的最短路之间的最小值即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii pair<int,int>
using namespace std;
const int N = 1000005,inf = 2e18,mod=1000000007;
int n,m,x;
int dis[400005];
vector<pii>p[400005];
void solve(){
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        p[2*i-1].push_back({2*i,x});
        p[2*i].push_back({2*i-1,x});
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        p[2*u-1].push_back({2*v-1,1});
        p[2*v].push_back({2*u,1});
    }
    memset(dis,0x3f,sizeof dis);
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push({0,1});dis[1]=0;
    while(q.size()){
        auto [d,u]=q.top();q.pop();
        for(auto [v,w]:p[u]){
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
    cout<<min(dis[2*n-1],dis[2*n]);
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    solve();
}

F - Smooth Occlusion (atcoder.jp)

先放代码

tag:二分、DP

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define lowbit(x) (x&(-x))
#define ull unsigned long long 
#define pii pair<int,int>
using namespace std;
const string yes="Yes\n",no="No\n";
const int N = 1000005,inf = 2e18,mod=1000000007;
int qpow(int x,int y=mod-2,int mo=mod,int res=1){
    for(;y;(x*=x)%=mo,y>>=1)if(y&1)(res*=x)%=mo;
    return res;
}
int jie[N],invjie[N];
int C(int n,int m){return n>=m&&m>=0?jie[n]*invjie[m]%mod*invjie[n-m]%mod:0;}
void main_init(){
    int n=N-1;jie[0]=1;for(int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mod;
    invjie[n]=qpow(jie[n]);for(int i=n-1;~i;i--)invjie[i]=invjie[i+1]*(i+1)%mod;
}
int n,k;
int u[N],d[N];
int l[N],r[N];
bool ck(int x){
    l[0]=0;
    r[0]=1e9;
    for(int i=1;i<=n;i++){
        if(u[i]+d[i]<x)return false;
        l[i]=max({x-d[i],0ll,l[i-1]-k});
        r[i]=min({u[i],x,r[i-1]+k});
        if(l[i]>r[i])return false;
    }
    return true;
}
void solve(){
    cin>>n>>k;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>u[i]>>d[i];
        sum+=u[i]+d[i];
    }
    int l=0,r=2e9;
    while(l<=r){
        int mid=l+r>>1;
        if(ck(mid))l=mid+1;
        else r=mid-1;
    }
    cout<<sum-r*n;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cout<<fixed<<setprecision(12);main_init();
    int t=1;
    //cin>>t;
    while (t--)solve();
}