Posted 题解13 minutes read (About 2020 words)

「AtCoder ExaWizards 2019」简要题解

AtCoder ExaWizards 2019

A - Regular Triangle

题意

判断三个数能否成为一个等边三角形的三条边的长度。

做法

= =

代码

1
2
3
4
5
6
7
#include<cstdio>
int a, b, c;
int main() {
	scanf("%d%d%d", &a, &b, &c);
	puts(a==b && b==c ? "Yes" : "No");
	return 0;
}

B - Red or Blue

题意

有一个仅包含 R 和 B 的字符串，判断 R 的数量是否严格比 B 多。

做法

= =

代码

1
2
3
4
5
6
7
8
#include<cstdio>
int n, ans;
char s[105];
int main() {
	scanf("%d%s", &n, s);
	for(int i=0; i<n; ++i) ans+=s[i]=='R'?1:-1;
	return puts(ans>0?"Yes":"No"), 0;
}

C - Snuke the Wizard

题意

有一排 \(n\) 个格子，第 \(i\) 个格子标有一个大写字母 \(s_i\)。

初始时每个格子上有一个傀儡，Snuke 会依次进行 \(q\) 次操作。

第 \(i\) 次操作给出 \(t_i,d_i\)，

  • 若 \(d_i\) 为 L 则把所有标了 \(t_i\) 的格子上的傀儡左移一格。
  • 若 \(d_i\) 为 R 则把所有标了 \(t_i\) 的格子上的傀儡右移一格。

若一个傀儡移出 \([1,n]\) 则立刻消失。

求最终留下的傀儡个数。

\(n,q\le 2\times 10^5\)

做法

还想了好久

显然任意两个傀儡之间的相对顺序不会改变。

于是消失的傀儡是一个前缀和一个后缀。

直接二分判断。

复杂度 \(O(n\log n)\)。

代码

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
	if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
	*ooh++=c;
}
template<class T>
inline void print(T x) {
	static int buf[30], cnt;
	if (x==0) print('0');
	else {
		if (x<0) print('-'), x=-x;
		for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
		while(cnt) print((char)buf[cnt--]);
	}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 200005;
int n, q;
char s[N], t[N], d[N];
inline int solve(int x){
	for(int i=1; i<=q; ++i) if(t[i]==s[x]) x+=(d[i]=='L'?-1:1);
	return x;
}
int main() {
	read(n), read(q);
	while(isspace(s[1]=read()));
	for(int i=2; i<=n; ++i) s[i]=read();
	for(int i=1; i<=q; ++i){
		while(isspace(t[i]=read()));
		while(isspace(d[i]=read()));
	}
	int l=1, r=n, ans1=0, ans2=n+1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(!solve(mid)) ans1=mid, l=mid+1; else r=mid-1;
	}
	l=1, r=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(solve(mid)==n+1) ans2=mid, r=mid-1; else l=mid+1;
	}
	return printf("%d", ans2-ans1-1), 0;
}

D - Modulo Operations

题意

有 \(n\) 个互不相同的数 \(s_1,s_2,\dotsc,s_n\)。

给出一个 \(x\)，求共 \(n!\) 种排列 \(p_1,p_2,\dotsc,p_n\)，初值 \(x\) 依次模 \(s_{p_1},s_{p_2},\dotsc,s_{p_n}\) 最后得到的数的和。

\(n\le 200,s_i,x\le 10^5\)。

做法

\(x\bmod y\ne x\) 当且仅当 \(y\le x\)。

令 \(f_i\) 表示当前的数为 \(i\)，忽略所有 \(s_k > i\) 后的答案。

于是枚举一个 \(s_k\le i\)，表示下一次选的数，得到的新的数为 \(i\bmod s_k\)。

于是除了 \(s_k\) 以外在 \((i\bmod s_k,i]\) 中的数可以在任何时候选，可以先乘上一个方案数。

复杂度 \(O(nx)\)。

代码

实现和上面写的不同，是从 \(x\) 出发计算成为每个值的方案数。

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

const int N = 100005, M = 205, P = 1000000007;
int n, x, ans, a[M], f[N], s[N], is[N];
inline int Pow(ll x, int y=P-2){
	int ans=1;
	for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
	return ans;
}
int main() {
	scanf("%d%d", &n, &x);
	for(int i=1; i<=n; ++i) scanf("%d", a+i);
	sort(a+1, a+n+1);
	for(int i=1; i<=x; ++i){
		s[i]=1;
		for(int j=1; j<=n; ++j) if(a[j]>i) s[i]=(ll)s[i]*j%P;
		is[i]=Pow(s[i]);
	}
	f[x]=s[x];
	for(int i=x; i>=a[1]; --i) if(f[i]){
		int cnt=1;
		for(int j=n; j; --j) if(a[j]<=i)
			f[i%a[j]]=(f[i%a[j]]+(ll)f[i]*s[i%a[j]]%P*is[a[j]-1]%P*cnt)%P, cnt=(ll)cnt*(j-1)%P;
	}
	for(int i=1; i<a[1]; ++i) ans=(ans+(ll)i*f[i])%P;
	return printf("%d", ans), 0;
}

E - Black or White

题意

有 \(b\) 个黑子和 \(w\) 个白子。

每次以相等的概率选取一个还有剩余的颜色，扔掉该颜色的一个棋子。

对于每个 \(i\in[1,b+w]\) 输出第 \(i\) 次扔黑子的概率。

\(b,w\le 10^5\)。

做法

  • 如果第 \(i\) 次两种颜色都有剩余，那么概率为 \(\frac{1}{2}\)。
  • 如果仅有黑色，概率为 \(1\)。
  • 如果仅有白色，概率为 \(0\)。

枚举 \(i\)，每种情况的概率可以轻易维护。

复杂度 \(O(b+w)\)。

代码

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
#include<cstdio>
#include<algorithm>

using namespace std;
#define ll long long

const int N = 200005, P = 1000000007, inv2 = (P+1)/2;
int b, w, fac[N], ifac[N], p[N];
inline int Pow(ll x, int y=P-2){
	int ans=1;
	for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
	return ans;
}
inline int C(int x, int y){ return x>=y?(ll)fac[x]*ifac[y]%P*ifac[x-y]%P:0;}
int main() {
	scanf("%d%d", &b, &w);
	fac[0]=p[0]=1;
	for(int i=1; i<N; ++i) fac[i]=(ll)fac[i-1]*i%P, p[i]=(ll)p[i-1]*inv2%P;
	ifac[N-1]=Pow(fac[N-1]);
	for(int i=N; --i;) ifac[i-1]=(ll)ifac[i]*i%P;
	for(int i=1; i<min(b, w); ++i) printf("%d\n", inv2);
	int x=0, y=0;
	for(int i=min(b, w); i<=b+w; ++i){
		printf("%lld\n", ((ll)(P+P+1-x-y)*inv2+y)%P);
		x=(x+(ll)C(i-1, b-1)*p[i])%P;
		y=(y+(ll)C(i-1, w-1)*p[i])%P;
	}
	return 0;
}

F - More Realistic Manhattan Distance

题意

有一个 \(n\times m\) 的网格图。

每行和每列都确定了一个方向，该行/列相邻的两个点都有一条该方向的边权为 \(1\) 的有向边。

\(q\) 次询问两点间的最短路，如果无法到达输出 \(-1\)。

\(n,m\le 10^5,q\le 2\times 10^5\)。

做法

分析一下性质

一条最短路径至多转弯 \(4\) 次

可以通过枚举证明，参考官方题解的末尾。

除了起点，每个点最多扩展 \(3\) 个新的点

考虑一个有用的点必须是拐点，于是方向只有一种，讨论和终点的位置关系：

  • 若终点在射线上，则直接走到最优。
  • 若沿方向走一步会远离终点（反终点方向），那么显然只要考虑第一个可以左拐和第一个可以右拐的点即可。
  • 若沿方向走一步会靠近终点，除了上述两种情况，还需要考虑经过射线上离终点最近的一个点之后第一个能转向终点方向的点，证明也类似。

于是暴力扩展只有 \(O(1)\) 个有用的点。

复杂度 \(O(q)\)。

代码

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
	if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
	*ooh++=c;
}
template<class T>
inline void print(T x) {
	static int buf[30], cnt;
	if (x==0) print('0');
	else {
		if (x<0) print('-'), x=-x;
		for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
		while(cnt) print((char)buf[cnt--]);
	}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 100005, M = 5;
pair<int,int> A, B, f[M][N];
int n, m, q, ans, cnt[M], tl[N][2], tr[N][2], sl[N][2], sr[N][2], dis[M][N];
bool g[M][N];
char s[N], t[N];
inline void extend(int id, pair<int,int> a, int d, bool e){
	int x=a.first, y=a.second, z;
	if(e){
		if(t[y]=='S'){
			if(sr[x][0]) f[id][cnt[id]]=make_pair(sr[x][0], y), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+sr[x][0]-x;
			if(sr[x][1]) f[id][cnt[id]]=make_pair(sr[x][1], y), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+sr[x][1]-x;
			if(B.first>x){
				if(B.second==y) ans=min(ans, d+B.first-x);
				if(z=sr[B.first-1][B.second>y]) f[id][cnt[id]]=make_pair(z, y), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+z-x;
			}
		}
		else{
			if(sl[x][0]) f[id][cnt[id]]=make_pair(sl[x][0], y), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+x-sl[x][0];
			if(sl[x][1]) f[id][cnt[id]]=make_pair(sl[x][1], y), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+x-sl[x][1];
			if(B.first<x){
				if(B.second==y) ans=min(ans, d+x-B.first);
				if(z=sl[B.first+1][B.second>y]) f[id][cnt[id]]=make_pair(z, y), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+x-z;
			}
		}
	}
	else{
		if(s[x]=='E'){
			if(tr[y][0]) f[id][cnt[id]]=make_pair(x, tr[y][0]), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+tr[y][0]-y;
			if(tr[y][1]) f[id][cnt[id]]=make_pair(x, tr[y][1]), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+tr[y][1]-y;
			if(B.second>y){
				if(B.first==x) ans=min(ans, d+B.second-y);
				if(z=tr[B.second-1][B.first>x]) f[id][cnt[id]]=make_pair(x, z), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+z-y;
			}
		}
		else{
			if(tl[y][0]) f[id][cnt[id]]=make_pair(x, tl[y][0]), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+y-tl[y][0];
			if(tl[y][1]) f[id][cnt[id]]=make_pair(x, tl[y][1]), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+y-tl[y][1];
			if(B.second<y){
				if(B.first==x) ans=min(ans, d+y-B.second);
				if(z=tl[B.second+1][B.first>x]) f[id][cnt[id]]=make_pair(x, z), g[id][cnt[id]]=e, dis[id][cnt[id]++]=d+y-z;
			}
		}
	}
}
int main() {
	read(n), read(m), read(q);
	while(isspace(s[1]=read()));
	for(int i=2; i<=n; ++i) s[i]=read();
	while(isspace(t[1]=read()));
	for(int i=2; i<=m; ++i) t[i]=read();

	for(int i=2; i<=n; ++i) sl[i][0]=sl[i-1][0], sl[i][1]=sl[i-1][1], sl[i][s[i-1]=='E']=i-1;
	for(int i=n; --i;) sr[i][0]=sr[i+1][0], sr[i][1]=sr[i+1][1], sr[i][s[i+1]=='E']=i+1;
	for(int i=2; i<=m; ++i) tl[i][0]=tl[i-1][0], tl[i][1]=tl[i-1][1], tl[i][t[i-1]=='S']=i-1;
	for(int i=m; --i;) tr[i][0]=tr[i+1][0], tr[i][1]=tr[i+1][1], tr[i][t[i+1]=='S']=i+1;
	while(q--){
		read(A.first), read(A.second), read(B.first), read(B.second);
		memset(cnt, 0, sizeof cnt), ans=1e9, extend(0, A, 0, 0), extend(0, A, 0, 1);
		for(int i=0; i<4; ++i){
			for(int j=0; j<cnt[i]; ++j) extend(i+1, f[i][j], dis[i][j], g[i][j]^1);
		}
		print(ans==1e9?-1:ans), print('\n');
	}
	return flush(), 0;
}

「AtCoder ExaWizards 2019」简要题解

https://cekavis.github.io/atcoder-exawizards2019/

Author

Cekavis

Posted on

2019-04-08

Updated on

2022-06-16

Licensed under

Comments

Follow
×