Atcoder ABC 395

思路：

维护三个值：

$pos_i \rightarrow i$ 号鸟在的巢穴
$g_i \rightarrow i$ 号位置放的巢穴
$id_i \rightarrow i$ 号巢穴所在的位置

维护过程：

对于操作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]$ 。

CPP

#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$

CPP

#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 + d \geq h \rightarrow u \geq h - d$ ， $u + d$ 必须大于等于 $h$ ，否则不满足条件 $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

CPP

#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;
}

文章操作

相关推荐

评论

Atcoder ABC 395