发表更新ICPC/CCPC / Contests / 其他15 分钟读完 (大约2310个字)

2020杭电多校（第四场）

比赛链接

收获

  • 学到了一个神奇的建图——$x$ 坐标和 $y$ 坐标分两边，连线就是 $(x,y)$ 这个点。

1002 Blow up the Enemy

暴力枚举就好。比较谁赢就比较杀死对方时间的长短。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 1005;

int T, n, a[N], d[N];

inline double calc(int i, int j){
	int t = 100 / a[i]; while(t * a[i] < 100) t++;
	int win = (t - 1) * d[i];
	t = 100 / a[j]; while(t * a[j] < 100) t++;
	int lose = (t - 1) * d[j];
	if(win > lose)	return 0;
	else if(win < lose)	return 1;
	return 0.5;
}

int main(){
	for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(a[i], d[i]);
		vector<double> p(n+5);
		double mx = 0;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++)
				p[i] += calc(i, j);
			mx = max(mx, p[i]);
		}
		printf("%.8f\n", mx / n);
	}
	return 0;
}

1003 Contest of Rope Pulling

转化问题为：$n+m$ 个物品，每个物品描述为 $(w_i,v_i)$，求 $\sum w_i=0$ 下 $\sum v_i$ 的最大值。

这是一个 $01$ 背包问题，$dp[i][j]=\max(dp[i-1][j],dp[i-1][j-w_i]+v_i)$，但是直接做是 $O(n\sum w_i)=O(10^9)$ 的，会 TLE。

由于最后我们要的答案是 $dp[n][0]$，所以 $dp$ 过程中，第二维越大，就越不大可能拉回来了。所以我们随机搞一搞，设一个上界 $T$，不考虑 $j>T$ 或 $j<T$ 的情况。这一随机处理的可行性依赖于：随机排序后，序列前缀和的最大值足够小（小于 $T$）。具体证明看题解吧，我也不会啊～

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 2005;

int T, n, m;
struct Node{
	LL w, v;
}a[N];

int main(){
	srand(time(NULL));
	for(read(T); T; T--){
		read(n, m);
		for(int i = 1; i <= n + m; i++){
			read(a[i].w, a[i].v);
			if(i > n)	a[i].w = -a[i].w;
		}
		random_shuffle(a+1, a+n+m+1);
		LL lim = sqrt(n + m) * 1000 * 2;
		vector< vector<LL> > dp(2, vector<LL>(2*lim+1, -1e14));
		dp[0][0+lim] = dp[1][0+lim] = 0;
		int now = 0;
		for(int i = 1; i <= n + m; i++, now ^= 1)
			for(int j = -lim; j <= lim; j++)
				if(j - a[i].w <= lim && j - a[i].w >= -lim)
					dp[now ^ 1][j+lim] = max(dp[now][j+lim], dp[now][j-a[i].w+lim] + a[i].v);
		printf("%lld\n", dp[now][0+lim]);
	}
	return 0;
}

另外，在 $dp$ 的过程中决定 for 的范围也能卡过去：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 2005;

int T, n, m;
struct Node{
	LL w, v;
}a[N];

int main(){
	srand(time(NULL));
	for(read(T); T; T--){
		read(n, m);
		for(int i = 1; i <= n + m; i++)
			read(a[i].w, a[i].v);
		int lim1 = 0;
		for(int i = 1; i <= n; i++)	lim1 += a[i].w;
		vector<LL> f(lim1+5, -1e14); f[0] = 0;
		lim1 = 0;
		for(int i = 1; i <= n; i++){
			lim1 += a[i].w;
			for(int j = lim1; j >= a[i].w; j--)
				f[j] = max(f[j], f[j-a[i].w] + a[i].v);
		}

		int lim2 = 0;
		for(int i = n+1; i <= n+m; i++)	lim2 += a[i].w;
		vector<LL> g(lim2+5, -1e14); g[0] = 0;
		lim2 = 0;
		for(int i = n+1; i <= n+m; i++){
			lim2 += a[i].w;
			for(int j = lim2; j >= a[i].w; j--)
				g[j] = max(g[j], g[j-a[i].w] + a[i].v);
		}
		
		LL ans = 0;
		for(int i = min(lim1, lim2); i >= 0; i--)
			ans = max(ans, f[i] + g[i]);
		printf("%lld\n", ans);
	}
	return 0;
}

1004 Deliver the Cake

每个点拆成左手、右手两个点，跑最短路即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 200500;
const int M = 800005;
const LL INF = 1e16;

struct Edge{
	int nxt, to; LL dis;
}edge[M<<1];
int head[N], edgeNum;
void addEdge(int from, int to, LL dis){
	edge[++edgeNum] = (Edge){head[from], to, dis};
	head[from] = edgeNum;
}
inline void ae(int from, int to, LL dis){
	addEdge(from, to, dis), addEdge(to, from, dis);
}

namespace SP{
	int n;
	LL dis[N];
	void dijkstra(int s){
		for(int i = 1; i <= n; i++)	dis[i] = INF;
		priority_queue< pair<LL, int> > q;
		dis[s] = 0;
		q.push(make_pair(-dis[s], s));
		while(!q.empty()){
			auto cur = q.top(); q.pop();
			if(-cur.first > dis[cur.second])	continue;
			for(int i = head[cur.second]; i; i = edge[i].nxt){
				if(dis[edge[i].to] > dis[cur.second] + edge[i].dis){
					dis[edge[i].to] = dis[cur.second] + edge[i].dis;
					q.push(make_pair(-dis[edge[i].to], edge[i].to));
				}
			}
		}
	}
}

int T, n, m, s, t, x;
char c[N];

int main(){
	for(read(T); T; T--){
		read(n, m, s, t, x);
		edgeNum = 0;
		for(int i = 1; i <= 2 * n + 2; i++)	head[i] = 0;

		scanf("%s", c+1);
		for(int i = 1; i <= m; i++){
			int u, v; LL d; read(u, v, d);
			if(c[u] == 'L'){
				if(c[v] == 'L')	ae(u, v, d);
				else if(c[v] == 'R')	ae(u, v+n, d+x);
				else	ae(u, v, d), ae(u, v+n, d+x);
			}
			else if(c[u] == 'R'){
				if(c[v] == 'R')	ae(u+n, v+n, d);
				else if(c[v] == 'L')	ae(u+n, v, d+x);
				else	ae(u+n, v, d+x), ae(u+n, v+n, d);
			}
			else if(c[u] == 'M'){
				if(c[v] == 'L')	ae(u, v, d), ae(u+n, v, d+x);
				else if(c[v] == 'R')	ae(u, v+n, d+x), ae(u+n, v+n, d);
				else	ae(u, v, d), ae(u, v+n, d+x), ae(u+n, v, d+x), ae(u+n, v+n, d);
			}
		}
		int S = 2 * n + 1, T = 2 * n + 2;
		addEdge(S, s, c[s] == 'R' ? INF : 0), addEdge(S, s+n, c[s] == 'L' ? INF : 0);
		addEdge(t, T, c[t] == 'R' ? INF : 0), addEdge(t+n, T, c[t] == 'L' ? INF : 0);
		SP::n = 2 * n + 2;
		SP::dijkstra(S);
		printf("%lld\n", SP::dis[T]);
	}
	return 0;
}

1005 Equal Sentences

为了满足题目要求，我们发现我们能做的操作只能是相邻两数进行交换。

于是设 $dp[i]$ 是前 $i$ 个数的方案数，那么：

  • 若 $s_i=s_{i-1}$，$dp[i]=dp[i-1]$；
  • 若 $s_i\neq s_{i-1}$，$dp[i]=dp[i-1]+dp[i-2]$. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 100005;
const LL MOD = 1e9+7;

int n;
string s[N];

int main(){
	int T; for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++)	cin >> s[i];
		vector<LL> dp(n+5);
		dp[0] = dp[1] = 1;
		for(int i = 2; i <= n; i++){
			if(s[i] == s[i-1])	dp[i] = dp[i-1];
			else	dp[i] = (dp[i-1] + dp[i-2]) % MOD;
		}
		printf("%lld\n", dp[n]);
	}
	return 0;
}

1007 Go Running

在一条线上跑来跑去的很混乱，我们自然想到把 $(t_i,x_i)$ 画到二维直角坐标系里，那么问题转化成：用最少的斜上/斜下 $45^\circ$ 直线穿过所有点。斜着很难受，我们转换一下坐标系 $\begin{cases}x’=x+y\\y’=y-x\end{cases}$ 就把问题变成了：用最少的平行于坐标轴的线穿过所有点。

这可以转换成二分图——横坐标和纵坐标是二分图两部分，$x$ 向 $y$ 连边表示 $(x,y)$ 这个点，而二分图的点表示平行于 $y$ 或 $x$ 轴的直线。那么问题转化成了：选出最少的点覆盖所有边，就是二分图最小点覆盖问题，根据 $\textbf{Konig}$ 定理，等价于二分图最大流问题。

注意：这道题 $\textbf{Dinic}$ 必须要用当前弧优化，否则会 TLE。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)

const int N = 500005;
const int INF = 1e9;

namespace FLOW{
	
	int s, t, n;
	struct Edge{
		int nxt, to, flow;
	}edge[N<<2];
	int head[N], edgeNum = 1, cur[N];
	void addEdge(int from, int to, int flow){
		edge[++edgeNum] = (Edge){head[from], to, flow};
		head[from] = edgeNum;
	}

	bool inq[N];
	int dep[N], curArc[N];
	bool bfs(){
		for(int i = 1; i <= n; i++)
			dep[i] = INF, inq[i] = 0, curArc[i] = head[i];
		queue<int> q;
		q.push(s);
		inq[s] = 1;
		dep[s] = 0;
		while(!q.empty()){
			int cur = q.front(); q.pop();
			inq[cur] = 0;
			for(int i = head[cur]; i; i = edge[i].nxt){
				if(dep[edge[i].to] > dep[cur] + 1 && edge[i].flow){
					dep[edge[i].to] = dep[cur] + 1;
					if(!inq[edge[i].to]){
						q.push(edge[i].to);
						inq[edge[i].to] = 1;
					}
				}
			}
		}
		if(dep[t] != INF)	return 1;
		return 0;
	}
	int dfs(int x, int minFlow){
		int flow = 0;
		if(x == t)	return minFlow;
		for(int i = curArc[x]; i; i = edge[i].nxt){
			curArc[x] = i;
			if(dep[edge[i].to] == dep[x] + 1 && edge[i].flow){
				flow = dfs(edge[i].to, min(minFlow, edge[i].flow));
				if(flow){
					edge[i].flow -= flow;
					edge[i^1].flow += flow;
					return flow;
				}
			}
		}
		return 0;
	}
	int Dinic(){
		int maxFlow = 0, flow = 0;
		while(bfs()){
			while(flow = dfs(s, INF))
				maxFlow += flow;
		}
		return maxFlow;
	}

	void init(int ss, int tt, int nn){
		s = ss, t = tt, n = nn;
		edgeNum = 1;
		for(int i = 1; i <= n; i++)	head[i] = 0;
	}
}


int T, n, l[N], r[N];

struct Point{
	int x, y;
}p[N];

int main(){
	for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++){
			int x, y; read(x, y);
			p[i].x = x + y, p[i].y = y - x;
		}

		for(int i = 1; i <= n; i++)	l[i] = p[i].x, r[i] = p[i].y;
		sort(l+1, l+n+1);
		int lenl = unique(l+1, l+n+1) - (l+1);
		sort(r+1, r+n+1);
		int lenr = unique(r+1, r+n+1) - (r+1);

		FLOW::init(1, 2, lenl + lenr + 2);
		for(int i = 1; i <= lenl; i++)
			FLOW::addEdge(1, i+2, 1), FLOW::addEdge(i+2, 1, 0);
		for(int i = 1; i <= lenr; i++)
			FLOW::addEdge(i+lenl+2, 2, 1), FLOW::addEdge(2, i+lenl+2, 0);
		for(int i = 1; i <= n; i++){
			p[i].x = lower_bound(l+1, l+lenl+1, p[i].x) - l;
			p[i].y = lower_bound(r+1, r+lenr+1, p[i].y) - r;
			FLOW::addEdge(p[i].x+2, p[i].y+lenl+2, 1), FLOW::addEdge(p[i].y+lenl+2, p[i].x+2, 0);
		}
		printf("%d\n", FLOW::Dinic());
	}
	return 0;
}

1011 Kindergarten Physics

出题人耍我们呐……在题设范围内，小球动不了多少，直接输出 $d$ 就行了……

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>

int main(){
	int T; for(scanf("%d", &T); T; T--){
		int d; scanf("%*d%*d%d%*d", &d);
		printf("%d\n", d);
	}
	return 0;
}

2020杭电多校（第四场）

http://xyfjason.github.io/blog-xcpc/2020/07/30/2020杭电多校（第四场）/

作者

xyfJASON

发布于

2020-07-30

更新于

2021-08-28

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×