首页 > 其他分享 >省选互测1

省选互测1

时间：2022-12-09 22:12:54浏览次数：57  
标签：val 省选 互测 int cost maxn include dis

A. Delov 的 npy 们

题目来源 AGC031E

本来想直接用洛谷题面，但是 \(Delov\) 整了活，于是我也整了

整活题面 
# Delov 的 npy 们

> 你有喜欢的女孩子嘛 有温柔的女孩子在等你吗


## 题目描述

众所周知 $Delov$ 有很多 $npy$，但是他的时间有限，所以需要精准的时间管理

$Delov$ 的时间表可以抽象成一个二维平面

他的 $n$ 个 $npy$ 在特定时刻 $(x_i,y_i)$ 想和 $Delov$ $wan$ 游戏 , 如果 $Delov$ 在该时刻和 $npy$ $wan$, 那么会收获 $v_i$ 的好感度

$npy$ 们很懂事，所以不会有两个 $npy$ 选择的时刻相同

但是 $Delov$ 还需要码代码，不能满足所有 $npy$， 具体来讲

有 $m$ 个限制，限制以下四种：

+ 横坐标小于等于 $a_i$ 的特定时刻最多选 $b_i$ 个。
+ 横坐标大于等于 $a_i$ 的特定时刻最多选 $b_i$ 个。
+ 纵坐标小于等于 $a_i$ 的特定时刻最多选 $b_i$ 个。
+ 纵坐标大于等于 $a_i$ 的特定时刻最多选 $b_i$ 个。

这四个限制输入的时候分别用 $LRDU$ 四个字母来区分。

现在问你在满足这些约束的条件下， $Delov$ 收获的最大好感度是多少


## 输入格式

$ N $  

$ x_1 $ $ y_1 $ $ v_1 $  

$ x_2 $ $ y_2 $ $ v_2 $  

$ ... $  

$ x_N $ $ y_N $ $ v_N $ 

$ M $  

$ t_1 $ $ a_1 $ $ b_1 $ 

$ t_2 $ $ a_2 $ $ b_2 $ 

$ ... $ 

$ t_M $ $ a_M $ $ b_M $

## 输出格式

一行一个整数，最大好感度

## 样例 #1

### 样例输入 #1

7
1 3 6
1 5 9
3 1 8
4 3 8
6 2 9
5 4 11
5 7 10
4
L 3 1
R 2 3
D 5 3
U 4 2


### 样例输出 #1

36


## 样例 #2

### 样例输入 #2

3
1 2 3
4 5 6
7 8 9
1
L 100 0


### 样例输出 #2

0


## 样例 #3

### 样例输入 #3

4
1 1 10
1 2 11
2 1 12
2 2 13
3
L 8 3
L 9 2
L 10 1


### 样例输出 #3

13


## 样例 #4

### 样例输入 #4

10
66 47 71040136000
65 77 74799603000
80 53 91192869000
24 34 24931901000
91 78 49867703000
68 71 46108236000
46 73 74799603000
56 63 93122668000
32 51 71030136000
51 26 70912345000
21
L 51 1
L 7 0
U 47 4
R 92 0
R 91 1
D 53 2
R 65 3
D 13 0
U 63 3
L 68 3
D 47 1
L 91 5
R 32 4
L 66 2
L 80 4
D 77 4
U 73 1
D 78 5
U 26 5
R 80 2
R 24 5


### 样例输出 #4

305223377000


## 数据范围

- $ 1\ \leq\ N\ \leq\ 80 $~~（当然 $Delov$ 的 $npy$ 不止这么多）~~
- $ 1\ \leq\ x_i,\ y_i\ \leq\ 100 $
- $ 1\ \leq\ v_i\ \leq\ 10^{15} $
- $ 1\ \leq\ M\ \leq\ 320 $
- $ t_i $ 为 `L`, `R`, `U`, `D` 中一种
- $ 1\ \leq\ a_i\ \leq\ 100 $
- $ 0\ \leq\ b_i\ \leq\ N\ -\ 1 $

- $ (x_i,\ y_i) $ 互不相同
- $ (t_i,\ a_i) $ 互不相同

数据范围较小，限制诡异，不难想到网络流

第一印象尝试用最大流去搞，但是建不出图

我们先考虑一维。

我们转化一下限制：假设最终选择了 \(k\) 个

  • 横坐标小于等于 \(a_i\) 的最多选 \(b_i\) ​个可以转化成如果$k > b_i $​， 那么选择的编号 \(> b_i\) 的其横坐标 \(x_i > a_i\)

  • 横坐标大于等于 \(a_i\) ​的最多选 \(b_i\) 个可以转化为如果\(k > b_i\)​， 那么选择的编号 \(≤ k−b_i\) 的​其横纵标$ < a_i$

我们可以的得到每一个选择的时刻的取值范围，那么把在范围内的时刻拿出来跑最大费用流即可

两维情况，简单拓展一下即可

建图是

从源点向左边的 \(k\) 个点连 \((1,0)\) 的边，从左边的 \(k\) 个点往它们右边相邻的 \(n\) 个点按照算出来的横坐标取值范围连 \((1,0)\) 的边（处理横坐标限制）

再从这 \(n\) 个点往右边的 \(n\) 个点一一对应连 \((1,v_i)\) 的边（拆点保证每个时刻只选一次）

然后再从这 \(n\) 个点向右边的 \(k\) 个点按照算出来的取值范围连 \((1,0)\) 的边，最后再从这 \(k\)个 点往汇点连 \((1,0)\) 的边。（处理纵坐标限制）

code 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<cassert>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll read(){
	ll x = 0; char c = getchar();
	while(!isdigit(c))c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return x;
}
const int maxn = 505;
const int inf = 0x3f3f3f3f;
const ll Inf = 4e18;
int n, m;
struct node{int x, y; ll v;}d[maxn];
struct limit{char opt; int a, b;}l[maxn];
int al[maxn], ar[maxn], bl[maxn], br[maxn];
char c[3];

ll ans;

struct MCMF{
	int head[maxn], s, t, tot = 1;
	struct edge{int to, net, val; ll cost;}e[maxn * maxn];
	ll dis[maxn], flow, cost;
	queue<int>q;
	bool vis[maxn];
	void add(int u, int v, int w, ll c){
		e[++tot].net = head[u];
		head[u] = tot;
		e[tot].to = v;
		e[tot].val = w;
		e[tot].cost = c;
	}
	void link(int u, int v, int w, ll c){
		add(u, v, w, c); add(v, u, 0, -c);
	}
	bool spfa(){
		for(int i = 1; i <= t; ++i)vis[i] = false, dis[i] = -Inf;
		dis[s] = 0; q.push(s);
		while(!q.empty()){
			int x = q.front(); q.pop(); vis[x] = false;
			for(int i = head[x]; i; i = e[i].net){
				int v = e[i].to;
				if(e[i].val > 0 && dis[v] < dis[x] + e[i].cost){
					dis[v] = dis[x] + e[i].cost;
					if(!vis[v])q.push(v), vis[v] = true;
				}
			}
		}
		return dis[t] != -Inf;
	}
	int dfs(int x, int from){
		if(x == t || from <= 0)return from;
		int res = from; vis[x] = true;
		for(int i = head[x]; i; i = e[i].net){
			int v = e[i].to;
			if(!vis[v] && e[i].val > 0 && dis[v] == dis[x] + e[i].cost){
				int k = dfs(v, min(res, e[i].val));
				e[i].val -= k;
				e[i ^ 1].val += k;
				res -= k;
				if(res <= 0)break;
			}
		}
		return from - res;
	}
	void mcmf(){
		flow = cost = 0;
		while(spfa()){
			ll k = dfs(s, inf);
			flow += k;
			cost += k * dis[t];
		}
	}
	void clear(){
		for(int i = 1; i <= t; ++i)head[i] = 0;
		tot = 1;
	}
	void init(int k){
		s = k + k + n + n + 1; t = s + 1;
		for(int i = 1; i <= k; ++i)link(s, i, 1, 0);
		for(int i = 1; i <= k; ++i)link(i + k, t, 1, 0);
		for(int i = 1; i <= n; ++i)link(k + k + i, k + k + n + i, 1, d[i].v);
		for(int i = 1; i <= k; ++i)al[i] = bl[i] = 0, ar[i] = br[i] = inf;
		for(int i = 1; i <= m; ++i){
			if(l[i].opt == 'L'){for(int j = l[i].b + 1; j <= k; ++j)al[j] = max(al[j], l[i].a + 1);}
			if(l[i].opt == 'R'){for(int j = 1; j <= k - l[i].b; ++j)ar[j] = min(ar[j], l[i].a - 1);}
			if(l[i].opt == 'D'){for(int j = l[i].b + 1; j <= k; ++j)bl[j] = max(bl[j], l[i].a + 1);}
			if(l[i].opt == 'U'){for(int j = 1; j <= k - l[i].b; ++j)br[j] = min(br[j], l[i].a - 1);}
		}
		for(int i = 1; i <= k; ++i)
			for(int j = 1; j <= n; ++j)
				if(al[i] <= d[j].x && d[j].x <= ar[i])
					link(i, j + k + k, 1, 0);
		for(int i = 1; i <= k; ++i)
			for(int j = 1; j <= n; ++j)
				if(bl[i] <= d[j].y && d[j].y <= br[i])
					link(k + k + n + j, i + k, 1, 0);
		mcmf();
		if(flow == k)ans = max(ans, cost);
		clear();
	}
}W;

int main(){
	n = read();
	for(int i = 1; i <= n; ++i)d[i].x = read(), d[i].y = read(), d[i].v = read();
	m = read();
	for(int i = 1; i <= m; ++i){scanf("%s",c); l[i].opt = c[0]; l[i].a = read(), l[i].b = read();}
	for(int i = 1; i <= n; ++i)W.init(i);
	printf("%lld\n",ans);
	return 0;
}
rand 
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
mt19937 seed((ull)(new char) * (ull) (new char));
ll sint(ll l, ll r){return uniform_int_distribution<ll>(l, r)(seed);}

int n = 10, m = 20;
// int n = 80, m = 320;

map<pii, bool>mp;
map<int, bool>rl, rr, ru, rd;
void pl(){
	int x = sint(1, 100);
	while(rl[x])x = sint(1, 100);
	rl[x] = true;
	int y = sint(1, x + 1);
	cout << "L " << x << " " <<  y;
}
void pd(){
	int x = sint(1, 100);
	while(rd[x])x = sint(1, 100);
	rd[x] = true;
	int y = sint(1, x + 1);
	cout << "D " << x << " " <<  y;
}
void pu(){
	int x = sint(1, 100);
	while(ru[x])x = sint(1, 100);
	ru[x] = true;
	int y = sint(1, 100 - x + 1);
	cout << "U " << x << " " <<  y;
}
void pr(){
	int x = sint(1, 100);
	while(rr[x])x = sint(1, 100);
	rr[x] = true;
	int y = sint(1, 100 - x + 1);
	cout << "R " << x << " " <<  y;
}
int main(){
	cout << n << endl;
	for(int i = 1; i <= n; ++i){
		int x = sint(1, 100), y = sint(1, 100);
		while(mp[pii(x, y)]){
			x = sint(1, 100);
			y = sint(1, 100);
		}
		mp[pii(x, y)] = true;
		cout << x << " " << y << " " << sint(1, 1e15) << endl;
	}
	printf("%d\n",m);
	for(int i = 1; i <= m; ++i){
		int opt = sint(1, 4);
		switch(opt){
			case 1:pl(); break;
			case 2:pr(); break;
			case 3:pu(); break;
			case 4:pd(); break;
		}
		cout << endl;
	}
	return 0;
}
sys 
#include<bits/stdc++.h>

using namespace std;

int main(){

	for(int i = 1; i <= 5; ++i){
		stringstream ss;
		string s;
		ss <<"./rand>" << i <<".in" << endl;
		// string s = "./rand >";
		// s += i + '0';
		// s += ".in";
		ss >> s;
		ss.clear();
		system(s.c_str());
		ss <<"./a<" << i <<".in" <<">" << i <<".out" << endl;
		ss >> s;
		ss.clear();
		/*
		s = "./c < ";
		s += i + '0';
		s += ".in > ";
		s += i + '0';
		s += ".out";*/
		system(s.c_str());
	}
	return 0;
}

B. 皮胚

https://www.luogu.com.cn/problem/CF1572D

容易发现是二分图（popcount奇偶性）

直接连边显然会炸

发现 \(k\) 很小，那么对于某个二进制位，有可能取到的一定是前 \(k\) 大的组合

于是优化了点数

code 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<cassert>

using namespace std;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int read(){
	int x = 0; char c = getchar();
	while(!isdigit(c))c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return x;
}
const int inf = 0x3f3f3f3f;
const int mx = (1 << 20) + 55;
const int maxn = 30005;
int n, k, a[mx], cnt, pop[mx];
map<int, int>mp;

struct Mcmf{
	int s, t, head[maxn], tot = 1;
	struct edge{int to, net, val, cost;}e[maxn << 2 | 1];
	void add(int u, int v, int w, int c){
		e[++tot].net = head[u];
		head[u] = tot;
		e[tot].to = v;
		e[tot].val = w;
		e[tot].cost = c;
	}
	void link(int u, int v, int w, int c){
		// printf("%d - > %d flow = %d cost = %d\n", u, v, w, c);
		add(u, v, w, c);
		add(v, u, 0, -c);
	}
	bool vis[maxn]; 
	int dis[maxn];
	bool spfa(){
		for(int i = 1; i <= cnt; ++i)dis[i] = -inf;
		for(int i = 1; i <= cnt; ++i)vis[i] = 0;
		queue<int>q; q.push(s); dis[s] = 0; vis[s] = 1;
		while(!q.empty()){
			int x = q.front(); q.pop(); vis[x] = false;
			for(int i = head[x]; i; i = e[i].net){
				int v = e[i].to;
				if(e[i].val && dis[v] < dis[x] + e[i].cost){
					dis[v] = dis[x] + e[i].cost;
					if(!vis[v])q.push(v), vis[v] = 1;
				}
			}
		}
		// for(int i = 1; i <= cnt; ++i)printf("%d ",dis[i]);printf("\n");
		return dis[t] != -inf;
	}
	int dfs(int x, int from){
		if(x == t || from <= 0)return from;
		int res = from; vis[x] = true;
		for(int i = head[x]; i; i = e[i].net){
			int v = e[i].to;
			if(!vis[v] && e[i].val > 0 &&  dis[v] == dis[x] + e[i].cost){
				int k = dfs(v, min(res, e[i].val));
				e[i].val -= k;
				e[i ^ 1].val += k;
				res -= k;
				if(res <= 0)break;
			}
		}
		return from - res;
	}
	int flow, cost;
	void mcmf(){
		while(spfa()){
			int k = dfs(s, inf);
			flow += k;
			cost += k * dis[t];
		}
	}
	struct node{
		int val, a, b;
		friend bool operator < (const node &x, const node &y){
			return x.val > y.val;
		}
	};
	int ss;
	priority_queue<node>Q;
	void get_new(int x){
		mp[x] = ++cnt;
		if(pop[x] & 1)link(ss, cnt, 1, 0);
		else link(cnt, t, 1, 0);
	}
	void init(){
		s = 1, t = 2, ss = 3; cnt = 3;
		link(s, ss, k, 0);
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < (1 << n); ++j)if(j & (1 << i)){
				Q.push({a[j] + a[j ^ (1 << i)], j, j ^ (1 << i)});
				while(Q.size() > k)Q.pop();
			}
			while(!Q.empty()){
				int x = Q.top().a, y = Q.top().b;
				if(!mp[x])get_new(x);
				if(!mp[y])get_new(y);
				if(pop[y] & 1)swap(x, y);
				link(mp[x], mp[y], 1, Q.top().val);
				Q.pop();
			}
		}
		mcmf();
		printf("%d\n",cost);
	}
}W;


int main(){
	freopen("pp.in","r",stdin);
	freopen("pp.out","w",stdout);
	n = read(), k = read();
	for(int i = 0; i < (1 << n); ++i)a[i] = read();
	for(int i = 1; i < (1 << n); ++i)pop[i] = pop[i >> 1] + (i & 1);
	W.init();
	return 0;
}

C. 流

分段计费，有源汇上下界网络流

https://www.luogu.com.cn/problem/solution/CF708D

code 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<cassert>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read(){
	int x = 0; char c = getchar();
	while(!isdigit(c))c = getchar();
	do{x = x * 10 + (c ^ 48); c = getchar();}while(isdigit(c));
	return x;
}
const int maxn = 505;
const int inf = 0x3f3f3f3f;
int n, m, ans;
int fl[maxn];

struct MCMF{
	int head[maxn], s, t, tot = 1;
	struct edge{int to, net, val, cost;}e[maxn * maxn];
	int dis[maxn], flow, cost;
	queue<int>q;
	bool vis[maxn];
	void add(int u, int v, int w, int c){
		e[++tot].net = head[u];
		head[u] = tot;
		e[tot].to = v;
		e[tot].val = w;
		e[tot].cost = c;
	}
	void link(int u, int v, int w, int c){
		add(u, v, w, c); add(v, u, 0, -c);
	}
	bool spfa(){
		for(int i = 1; i <= t; ++i)vis[i] = false, dis[i] = inf;
		dis[s] = 0; q.push(s);
		while(!q.empty()){
			int x = q.front(); q.pop(); vis[x] = false;
			for(int i = head[x]; i; i = e[i].net){
				int v = e[i].to;
				if(e[i].val > 0 && dis[v] > dis[x] + e[i].cost){
					dis[v] = dis[x] + e[i].cost;
					if(!vis[v])q.push(v), vis[v] = true;
				}
			}
		}
		return dis[t] != inf;
	}
	int dfs(int x, int from){
		if(x == t || from <= 0)return from;
		int res = from; vis[x] = true;
		for(int i = head[x]; i; i = e[i].net){
			int v = e[i].to;
			if(!vis[v] && e[i].val > 0 && dis[v] == dis[x] + e[i].cost){
				int k = dfs(v, min(res, e[i].val));
				e[i].val -= k;
				e[i ^ 1].val += k;
				res -= k;
				if(res <= 0)break;
			}
		}
		return from - res;
	}
	void mcmf(){
		while(spfa()){
			int k = dfs(s, inf);
			flow += k;
			cost += k * dis[t];
		}
	}
	
	void init(){
		n = read(), m = read();
		s = n + 1, t = s + 1;
		for(int i = 1; i <= m; ++i){
			int u = read(), v = read(), c = read(), f = read();
			if(f <= c){
				link(u, v, c - f, 1);
				link(v, u, f, 1);
			}else{
				ans += f - c;
				link(v, u, f - c, 0);
				link(v, u, c, 1);
			}
			link(u, v, inf, 2);
			fl[u] -= f; fl[v] += f;
		}
		for(int i = 1; i <= n; ++i)if(fl[i] > 0)link(s, i, fl[i], 0);
		else if(fl[i] < 0)link(i, t, -fl[i], 0);
		link(n, 1, inf, 0);
		mcmf();
		printf("%d\n", ans + cost);
	}
}W;

int main(){
	// freopen("flow.in","r",stdin);
	// freopen("flow.out","w",stdout);
	W.init();
	return 0;
}

标签：val,省选,互测,int,cost,maxn,include,dis
From： https://www.cnblogs.com/Chencgy/p/16970117.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99