发表更新ICPC/CCPC / Contests / Codeforces18 分钟读完 (大约2770个字)

Educational Codeforces Round 87

比赛链接 / 官方题解链接

rating 大涨174！开心～～～

A. Alarm Clock

Solution

如果 $a\leq b$，那么时间就是 $b$；否则，如果定的时间内睡不着，无解；否则，答案就是 $b+\left\lceil\frac{a-b}{c-d}\right\rceil\times c$.

Code

>folded
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
#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)

LL T, a, b, c, d;

int main(){
	for(read(T); T; T--){
		read(a, b, c, d);
		if(a <= b){
			printf("%lld\n", b);
			continue;
		}
		if(c <= d){
			puts("-1");
			continue;
		}
		LL res = b + (a - b) / (c - d) * c;
		if((a - b) % (c - d))	res += c;
		printf("%lld\n", res);
	}
	return 0;
}

B. Ternary String

Solution

设 $d[i][1/2/3]$ 表示第 $i$ 个数之前（包括本身）的第一个 $0/1/2$ 的位置。这个可以很容易 dp 得到。

于是对于以 $i$ 为右端点的区间，$\min\{d[i][1],d[i][2],d[i][3]\}$ 就是最大的包含 $0,1,2$ 至少一次的左端点，用区间长度更新答案。

Code

>folded
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
#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 = 200005;

int T, d[N][10];
char s[N];

int main(){
	for(read(T); T; T--){
		scanf("%s", s+1);
		int n = strlen(s+1);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= 3; j++){
				if(s[i] == j + '0')	d[i][j] = i;
				else	d[i][j] = d[i-1][j];
			}
		}
		int ans = 1e9;
		for(int i = 3; i <= n; i++){
			int pos = min(d[i][1], min(d[i][2], d[i][3]));
			if(pos == 0)	continue;
			ans = min(ans, i - pos + 1);
		}
		if(ans == 1e9)	puts("0");
		else	printf("%d\n", ans);
	}
	return 0;
}

C1. Simple Polygon Embedding

Solution

$n$ 为偶数，最小的能框住正 $2n$ 边形的正方形长这样（$n=4$ 画了完整的图，$n=6,8$ 只画了圆圈内的部分）：

按这个规律码就行了。

P.S. 我果然做复杂了……答案就是 $\frac{1}{\tan{\frac{\pi}{2\cdot n}}}$.

Code

>folded
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
#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 double pi = acos(-1);

int T, n;

int main(){
	for(read(T); T; T--){
		read(n);
		double theta = pi / n, ans = 0;
		int m = (n - 2) / 2;
		for(int i = 1; i <= m / 2; i++)
			ans += sin(theta * i) + cos(theta * i);
		if(m & 1)	ans += 1 / sqrt(2);
		printf("%.10f\n", ans * 2 + 1);
	}
	return 0;
}

C2. Not So Simple Polygon Embedding

Solution

$n$ 为奇数，最小的能框住正 $2n$ 边形的正方形长这样（$n=4$ 画了完整的图，$n=6,8$ 只画了圆圈内的部分）：

找到正方形的边与哪个顶点触碰（该顶点是第一个倾角大于等于 45 度的顶点），就可以计算了。

P.S. 是的我又做复杂了，答案就是 $\frac{\cos(\frac{\pi}{4n})}{\sin(\frac{\pi}{2n})}$.

Code

>folded
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
#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 double pi = acos(-1);

int T, n;

int main(){
	for(read(T); T; T--){
		read(n);
		double theta = pi / n, ans = 0;
		int m = (n - 1) / 2;
		double x = 0, y = 0;
		x = 0.5;
		int k = 0;
		for(k = 1; k <= m; k++)
			if(k * theta * 4 >= pi)
				break;
		for(int i = 1; i < k; i++){
			x += cos(theta * i);
			y += sin(theta * i);
		}
		double h = 0;
		for(int i = 1; i <= m; i++)	h += sin(theta * i);
		ans = (h - y + x) * sqrt(2);
		printf("%.10f\n", ans);
	}
	return 0;
}

D. Multiset

Solution

用值域线段树模拟题目操作。

好吧，其实用树状数组就可以了。

Code

>folded
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
#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 = 1000005;

int n, q;

struct segTree{
    int size;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((l + r) >> 1)
void pushup(int id){
    tr[id].size = tr[lid].size + tr[rid].size;
}
void insert(int id, int l, int r, int val){
    if(l == r){
        tr[id].size++;
        return;
    }
    if(val <= mid)  insert(lid, l, mid, val);
    else    insert(rid, mid+1, r, val);
    pushup(id);
}
void delRank(int id, int l, int r, int rk){
    if(l == r){
        tr[id].size--;
        return;
    }
    if(tr[lid].size >= rk)  delRank(lid, l, mid, rk);
    else    delRank(rid, mid+1, r, rk - tr[lid].size);
    pushup(id);
}
int findRank(int id, int l, int r, int rk){
    if(l == r)  return l;
    if(tr[lid].size >= rk)  return findRank(lid, l, mid, rk);
    else    return findRank(rid, mid+1, r, rk - tr[lid].size);
}

int main(){
	read(n, q);
    for(int i = 1; i <= n; i++){
    	int a; read(a);
    	insert(1, 1, n, a);
    }
    while(q--){
    	int a; read(a);
    	if(a < 0)	delRank(1, 1, n, -a);
    	else	insert(1, 1, n, a);
    }
    if(tr[1].size > 0)  printf("%d\n", findRank(1, 1, n, 1));
    else	puts("0");
    return 0;
}

E. Graph Coloring

Solution

首先发现性质：如果图中存在奇环，那么一定不可行。

于是现在图中没有奇环，也即该图是若干个连通的二分图。我们只需要在每一个二分图中选择一侧填 $2$，另一侧填 $1$ 或 $3$，问是否存在一个方案使得 $2$ 的数量等于 $n2$（$1$ 和 $3$ 的数量自然就是 $n1+n3$ 了）。

这是一个简单的 dp：记 $a[i],b[i]$ 表示第 $i$ 个二分图的两侧的点数，设 $dp[i][j]$ 表示前 $i$ 个二分图能否选出 $j$ 个点填 $2$，那么，$dp[i][j]=dp[i-1][j-a[i]]\ \mathrm{OR}\ dp[i-1][j-b[i]]$.

这玩意儿其实可以用 bitset 优化，但是这道题犯不着。

至于输出方案，我们在 dp 的过程中记录一下转移的路径，就可以从末状态倒着推回去了。

Code

>folded
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
#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 = 5005;
const int M = 100005;

int n, m, n1, n2, n3, n0;
int a[N][2], id;
vi v[N][2];

bool dp[N][N], ans[N];
int which[N][N];

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

int col[N];
void dfs(int x, int c){
	col[x] = c;
	for(int i = head[x]; i; i = edge[i].nxt){
		if(col[edge[i].to] == -1)	dfs(edge[i].to, c ^ 1);
		else if(col[edge[i].to] == c){
			puts("NO");
			exit(0);
		}
	}
}

bool vis[N];
void dfs(int x){
	vis[x] = true;
	a[id][col[x]]++;
	v[id][col[x]].pb(x);
	for(int i = head[x]; i; i = edge[i].nxt){
		if(vis[edge[i].to])	continue;
		dfs(edge[i].to);
	}
}

int main(){
	memset(col, -1, sizeof col);
	memset(which, -1, sizeof which);
	read(n, m);
	read(n1, n2, n3); n0 = n1 + n3;
	for(int i = 1; i <= m; i++){
		int u, v; read(u, v);
		addEdge(u, v), addEdge(v, u);
	}
	for(int i = 1; i <= n; i++)
		if(col[i] == -1)
			dfs(i, 0);
	for(int i = 1; i <= n; i++)
		if(!vis[i])
			++id, dfs(i);
	dp[0][0] = true;
	for(int i = 1; i <= id; i++){
		for(int j = 0; j <= n2; j++){
			if(j >= a[i][0]){
				dp[i][j] |= dp[i-1][j-a[i][0]];
				if(dp[i-1][j-a[i][0]])	which[i][j] = 0;
			}
			if(j >= a[i][1]){
				dp[i][j] |= dp[i-1][j-a[i][1]];
				if(dp[i-1][j-a[i][1]])	which[i][j] = 1;
			}
		}
	}
	if(!dp[id][n2])	return puts("NO"), 0;
	puts("YES");
	int now = n2;
	for(int i = id; i >= 1; i--){
		for(auto k: v[i][which[i][now]])
			ans[k] = true;
		now -= a[i][which[i][now]];
	}
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(!ans[i]){
			if(cnt < n1)	printf("1"), cnt++;
			else	printf("3");
		}
		else	printf("2");
	}
	puts("");
	return 0;
}

F. Summoning Minions

Solution

【参考官方题解】首先我们找到一些贪心的性质：所有兵都应该被召唤（如果某兵没有被召唤，召唤它之后再删掉它不会使答案更差）；最终应该召唤满 $k$ 个兵（如果不满 $k$ 个，我们没有必要删掉某些兵）；如果一个兵会被删去，我们可以再召唤它之后立刻删掉它，对答案无影响。

基于上述性质，我们的策略是：先召唤 $k-1$ 个兵；再召唤 $n-k$ 个兵，并且一召唤出来就立刻删掉它；最后召唤 $1$ 个兵。

先召唤的 $k-1$ 个兵中，第 $j$ 个召唤的兵对答案的贡献是 $a_i+(j-1)\cdot b_i$；随后召唤的 $n-k$ 个兵对答案的贡献都是 $(k-1)\cdot b_i$；最后一个兵对答案的贡献是 $a_i+(k-1)\cdot b_i$.

于是我们可以把 $n$ 个兵到 $n$ 个位置（一共 $n^2$ 个数对）对答案的贡献算出来。我们现在需要找到一个配对方式，使得每一个位置被分配一个兵。于是可以网络流解决：以兵和位置为顶点建图，某兵到某位置的边的流量为 $1$，费用为该兵到该位置的对答案的贡献；然后源点向每个兵连流量为 $1$，费用为 $0$ 的边；每个位置向汇点连流量为 $1$，费用为 $0$ 的边。跑最小费用最大流（因为题目要求价值最大，所以上述连边中费用全部取负，跑出来的最小费用取负就是最大价值）。输出方案的话，哪条边满流了就说明那条边是一个匹配。

Code

>folded
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
122
123
124
#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 = 200;
const int INF = 1e9;

int T, n, k, a[N], b[N];

struct Edge{
    int nxt, to, flow, cost;
}edge[N*N*2];
int head[N], edgeNum = 1;
void addEdge(int from, int to, int flow, int cost){
    edge[++edgeNum].nxt = head[from];
    edge[edgeNum].to = to;
    edge[edgeNum].flow = flow;
    edge[edgeNum].cost = cost;
    head[from] = edgeNum;
}

int src, dst;
int minCost[N], minFlow[N], pre[N];
bool inq[N];
int spfa(){
    for(int i = 1; i <= n; i++){
        minCost[i] = minFlow[i] = INF;
        pre[i] = 0;
        inq[i] = 0;
    }
    queue<int> q;
    q.push(src);
    inq[src] = 1;
    minCost[src] = 0;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        inq[cur] = 0;
        for(int i = head[cur]; i; i = edge[i].nxt){
            if(edge[i].flow && minCost[edge[i].to] > minCost[cur] + edge[i].cost){
                minCost[edge[i].to] = minCost[cur] + edge[i].cost;
                minFlow[edge[i].to] = min(minFlow[cur], edge[i].flow);
                pre[edge[i].to] = i;
                if(!inq[edge[i].to]){
                    q.push(edge[i].to);
                    inq[edge[i].to] = 1;
                }
            }
        }
    }
    if(pre[dst] == 0)	return -1;
    return minFlow[dst];
}

void EK(int &maxflow, int &mincost){
    maxflow = mincost = 0;
    int flow = 0;
    while((flow = spfa()) != -1){
        int t = dst;
        while(t != src){
            edge[pre[t]].flow -= flow;
            edge[pre[t]^1].flow += flow;
            t = edge[pre[t]^1].to;
        }
        maxflow += flow;
        mincost += flow * minCost[dst];
    }
}

int main(){
	for(read(T); T; T--){
		read(n, k);
		edgeNum = 1;
		memset(head, 0, sizeof head);
		for(int i = 1; i <= n; i++){
			read(a[i], b[i]);
			for(int j = 1; j <= n; j++){
				if(j < k){
					addEdge(i, j+n, 1, - a[i] - (j - 1) * b[i]);
					addEdge(j+n, i, 0, a[i] + (j-1) * b[i]);
				}
				else if(j < n){
					addEdge(i, j+n, 1, -(k-1) * b[i]);
					addEdge(j+n, i, 0, (k-1) * b[i]);
				}
				else{
					addEdge(i, j+n, 1, - a[i] - (k-1) * b[i]);
					addEdge(j+n, i, 0, a[i] + (k-1) * b[i]);
				}
			}
		}
		int nn = n;
		n <<= 1;
		src = ++n, dst = ++n;
		for(int i = 1; i <= nn; i++){
			addEdge(src, i, 1, 0), addEdge(i, src, 0, 0);
			addEdge(i+nn, dst, 1, 0), addEdge(dst, i+nn, 0, 0);
		}
		int maxflow, mincost;
		EK(maxflow, mincost);
		printf("%d\n", k + 2 * (nn - k));
		for(int j = 1; j <= nn; j++){
			for(int i = head[j+nn]; i; i = edge[i].nxt){
				if(edge[i].to == dst)	continue;
				if(edge[i^1].flow == 0){
					if(j < k)	printf("%d ", edge[i].to);
					else if(j < nn)	printf("%d %d ", edge[i].to, -edge[i].to);
					else	printf("%d\n", edge[i].to);
					break;
				}
			}
		}
	}
	return 0;
}

Educational Codeforces Round 87

http://xyfjason.github.io/blog-xcpc/2020/05/17/Educational-Codeforces-Round-87/

作者

xyfJASON

发布于

2020-05-17

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

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