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

Codeforces Round #637 (Div.2)

比赛链接 / 官方题解链接

A. Nastya and Rice

Solution

只要 $[n(a-b),n(a+b)]$ 和 $[c-d,c+d]$ 有交即可。

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

int T, n, a, b, c, d;

int main(){
	for(read(T); T; T--){
		read(n, a, b, c, d);
		int l = n * (a - b), r = n * (a + b);
		if(c + d >= l && c - d <= r)	puts("Yes");
		else	puts("No");
	}
	return 0;
}

B. Nastya and Door

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
#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, n, k;
LL a[N], p[N], s[N];

int main(){
	for(read(T); T; T--){
		read(n, k);
		a[0] = a[n+1] = 1e16;
		for(int i = 1; i <= n; i++){
			read(a[i]);
			p[i] = s[i] = 0;
		}
		for(int i = 1; i <= n; i++){
			if(a[i] > a[i-1] && a[i] > a[i+1])
				p[i] = 1;
			s[i] = p[i] + s[i-1];
		}
		LL mx = -1, mark = 0;
		for(int i = 1; i <= n; i++){
			int j = i + k - 1;
			if(j > n)	break;
			LL cnt = s[j] - s[i-1];
			if(p[i])	cnt--;
			if(p[j])	cnt--;
			if(cnt > mx)	mx = cnt, mark = i;
		}
		printf("%lld %lld\n", mx + 1, mark);
	}
	return 0;
}

C. Nastya and Strange Generator

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

int T, n, p[N];

int main(){
	for(read(T); T; T--){
		read(n);
		for(int i = 1; i <= n; i++)	read(p[i]);
		bool ok = true;
		for(int i = 2; i <= n; i++){
			if(p[i] < p[i-1])	continue;
			else if(p[i] > p[i-1] + 1){
				ok = false;
				break;
			}
		}
		puts(ok ? "Yes" : "No");
	}
	return 0;
}

D. Nastya and Scoreboard

Solution

容易想到的一个 $dp$ 是：$dp[i][j]$ 表示前 $i$ 个数点亮了 $j$ 根管子的最大数值，但是这样做的话，$dp$ 数组需要开成字符串类型，而字符串的比较是 $O(n)$ 的，会 $TLE$.

正解是结合一下贪心和 $dp$：设 $dp[i][j]$ 表示从后往前的 $i$ 个数能否在点亮 $j$ 根管子后形成数字，这样 $dp$ 就是 $O(n^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
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
#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 n, k;
string digits[20], a[N];
int dis[N][10];
bool can[N][N];

inline int dist(int x, string s){
	string sx = digits[x];
	int res = 0;
	for(int i = 0; i < 7; i++){
		if(sx[i] == s[i])	continue;
		if(sx[i] == '0' && s[i] == '1')	return 1e9;
		else if(sx[i] == '1' && s[i] == '0')	res++;
	}
	return res;
}

int main(){
	read(n, k);
	digits[0] = "1110111";
	digits[1] = "0010010";
	digits[2] = "1011101";
	digits[3] = "1011011";
	digits[4] = "0111010";
	digits[5] = "1101011";
	digits[6] = "1101111";
	digits[7] = "1010010";
	digits[8] = "1111111";
	digits[9] = "1111011";
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		for(int j = 0; j <= 9; j++)
			dis[i][j] = dist(j, a[i]);
	}
	can[n+1][0] = true;
	for(int i = n; i >= 1; i--)
		for(int num = 0; num <= 9; num++)
			for(int j = dis[i][num]; j <= k; j++)
				can[i][j] |= can[i+1][j-dis[i][num]];
	if(can[1][k] == false)	puts("-1");
	else{
		for(int i = 1; i < n; i++){
			for(int num = 9; num >= 0; num--){
				if(k >= dis[i][num] && can[i+1][k-dis[i][num]]){
					k -= dis[i][num];
					putchar(num + '0');
					break;
				}
			}
		}
		for(int num = 9; num >= 0; num--){
			if(dis[n][num] == k){
				printf("%d\n", num);
				break;
			}
		}
	}
	return 0;
}

E. Nastya and Unexpected Guest

Solution

【参考官方题解】我们把“在模 $g$ 余 $j$ 的时刻到达第 $i$ 个安全岛”看做一个状态，那么不同状态之间就可以连上不同边权的边（边权即花费的时间），最短路就是答案。但是这样做复杂度太高。

重新定义边权为：到达当前状态经过的“绿灯-红灯”轮数。那么边权只是 $0$ 或者 $1$，要求得最短路，我们只需要进行 $01bfs$，即使用双端队列代替 dijkstra 的优先队列，边权是 $0$ 就从前插入，边权是 $1$ 就从后插入，仍然维护了队列的单调性，且复杂度降低到 $O(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
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 M = 10005;

int n, m, d[M], g, r;
LL dp[M][1005], ans = 1e16;
bool vis[M][1005];

void bfs(){
	deque<pii> q; // first: pos; second: time
	q.push_front(mp(1, 0));
	vis[1][0] = 1;
	while(!q.empty()){
		pii cur = q.front(); q.pop_front();
		if(cur.second == 0)
			if(n - d[cur.first] <= g)
				ans = min(ans, dp[cur.first][cur.second] * (g + r) + n - d[cur.first]);
		if(cur.second == g){
			if(!vis[cur.first][0]){
				dp[cur.first][0] = dp[cur.first][cur.second] + 1;
				vis[cur.first][0] = 1;
				q.push_back(mp(cur.first, 0));
			}
			continue;
		}
		if(cur.first > 1){
			int v = d[cur.first] - d[cur.first-1] + cur.second;
			if(v <= g && !vis[cur.first-1][v]){
				dp[cur.first-1][v] = dp[cur.first][cur.second];
				vis[cur.first-1][v] = 1;
				q.push_front(mp(cur.first-1, v));
			}
		}
		if(cur.first < m){
			int v = d[cur.first+1] - d[cur.first] + cur.second;
			if(v <= g && !vis[cur.first+1][v]){
				dp[cur.first+1][v] = dp[cur.first][cur.second];
				vis[cur.first+1][v] = 1;
				q.push_front(mp(cur.first+1, v));
			}
		}
	}
}

int main(){
	read(n, m);
	for(int i = 1; i <= m; i++)	read(d[i]);
	sort(d+1, d+m+1);
	read(g, r);
	bfs();
	if(ans == 1e16)	puts("-1");
	else	printf("%lld\n", ans);
	return 0;
}

F. Nastya and Time Machine

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

int n, mxdeg, deg[N];
vi edge[N];
vector<pii> ans;

void dfs(int x, int f, int t){
	ans.pb(mp(x, t));
	if(t == mxdeg){
		t = mxdeg - deg[x];
		ans.pb(mp(x, t));
	}
	for(auto to: edge[x]){
		if(to == f)	continue;
		dfs(to, x, t + 1);
		t++;
		if(ans.back().second != t - 1)
			ans.pb(mp(to, t - 1));
		ans.pb(mp(x, t));
		if(f && t == mxdeg){
			t = mxdeg - deg[x];
			ans.pb(mp(x, t));
		}
	}
}

int main(){
	read(n);
	if(n == 1){
		puts("1");
		puts("1 0");
		return 0;
	}
	for(int i = 1; i < n; i++){
		int u, v; read(u, v);
		edge[u].pb(v), edge[v].pb(u);
		deg[u]++, deg[v]++;
		mxdeg = max(mxdeg, deg[u]);
		mxdeg = max(mxdeg, deg[v]);
	}
	dfs(1, 0, 0);
	printf("%d\n", (int)ans.size());
	for(auto k: ans)
		printf("%d %d\n", k.first, k.second);
	return 0;
}

Codeforces Round #637 (Div.2)

http://xyfjason.github.io/blog-xcpc/2020/04/24/Codeforces-Round-637-Div-2/

作者

xyfJASON

发布于

2020-04-24

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

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