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

2020杭电多校（第三场）

比赛链接

收获

  • 括号匹配不一定要用栈，也可以用队列——特别是要求字典序最小时。

1004 Tokitsukaze and Multiple

问题其实就是把序列给切分成若干段，问和为 $p$ 的倍数的最多有多少段。

贪心：作前缀和，从左往右扫，扫到模 $p$ 相同的数就形成一段。证明：如果这里不形成一段，那么右端点会右移，占掉了更多的数，答案不会更优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>

using namespace std;

const int N = 100005;

int T, n, p;

int main(){
	for(scanf("%d", &T); T; T--){
		scanf("%d%d", &n, &p);
		map<int, int> m; m[0] = 1;
		int ans = 0, s = 0;
		for(int i = 1; i <= n; i++){
			int a; scanf("%d", &a); (s += a) %= p;
			if(m[s])	ans++, m.clear(), m[s] = 1;
			else	m[s] = 1;
		}
		printf("%d\n", ans);
	}
	return 0;
}

1005 Little W and Contest

并查集维护关系，记录每一个连通块里 $1,2$ 的数量。

先把初始答案算出来，考虑合并操作导致答案减少的量：合并两个集合，那么减少了从这两个集合里拿出两个 $2$ 与其他的 $1$ 或 $2$ 匹配的数量，以及从这两个集合里拿出一个 $1$、一个 $2$ 与其他的 $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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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;
const LL inv2 = 500000004;
const LL inv3 = 333333336;

int T, n;
LL sum[3];

int fa[N];
LL cnt[N][3];
int findfa(int x){ return x == fa[x] ? x : fa[x] = findfa(fa[x]); }
inline void unionn(int x, int y){
	cnt[findfa(x)][1] += cnt[findfa(y)][1];
	cnt[findfa(x)][2] += cnt[findfa(y)][2];
	fa[findfa(y)] = findfa(x);
}

int main(){
	for(read(T); T; T--){
		read(n);
		sum[1] = sum[2] = 0;
		for(int i = 1; i <= n; i++)	cnt[i][1] = cnt[i][2] = 0, fa[i] = i;
		for(int i = 1; i <= n; i++){
			int x; read(x);
			cnt[i][x] = 1;
			sum[x]++;
		}
		LL ans = 0;
		if(sum[2] >= 3)	ans += sum[2] * (sum[2]-1) / 2 % MOD * (sum[2]-2) % MOD * inv3 % MOD;
		if(sum[2] >= 2)	(ans += sum[2] * (sum[2] - 1) / 2 % MOD * sum[1] % MOD) %= MOD;
		printf("%lld\n", ans);
		for(int i = 1; i < n; i++){
			int u, v; read(u, v); u = findfa(u), v = findfa(v);
			ans -= cnt[u][2] * cnt[v][2] * (sum[2] - cnt[u][2] - cnt[v][2] + sum[1] - cnt[u][1] - cnt[v][1]);
			ans -= (cnt[u][2] * cnt[v][1] + cnt[u][1] * cnt[v][2]) * (sum[2] - cnt[u][2] - cnt[v][2]);
			((ans %= MOD) += MOD) %= MOD;
			unionn(u, v);
			printf("%lld\n", ans);
		}
	}
	return 0;
}

1007 Tokitsukaze and Rescue

真就硬搜……算出最短路，枚举删掉其中的一条边，然后再算最短路……

看了题解，暴搜可行的原因是随机边权下，最短路边数很少。

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 = 55;
const int INF = 1e9;

int T, n, k, g[N][N], ans;

int dis[N], pre[N];
bool vis[N];
bool tag[N][N];
void dijkstra(){
	for(int i = 1; i <= n; i++)
		dis[i] = INF, vis[i] = false, pre[i] = 0;
	dis[1] = 0;
	for(int i = 1; i <= n; i++){
		int mndis = INF, mark = 0;
		for(int j = 1; j <= n; j++)
			if(dis[j] < mndis && !vis[j])
				mndis = dis[j], mark = j;
		vis[mark] = true;
		for(int j = 1; j <= n; j++){
			if(tag[mark][j])	continue;
			if(dis[j] > dis[mark] + g[mark][j]){
				dis[j] = dis[mark] + g[mark][j];
				pre[j] = mark;
			}
		}
	}
}

void dfs(int x){
	dijkstra();
	if(x == k){
		ans = max(ans, dis[n]);
		return;
	}
	int now = n;
	vector<pii> v;
	while(pre[now]){
		v.pb(mp(now, pre[now]));
		now = pre[now];
	}
	for(auto &k : v){
		tag[k.first][k.second] = tag[k.second][k.first] = true;
		dfs(x+1);
		tag[k.first][k.second] = tag[k.second][k.first] = false;
	}
}

int main(){
	for(read(T); T; T--){
		read(n, k);
		ans = 0;
		for(int i = n * (n - 1) / 2; i; i--){
			int u, v, w; read(u, v, w);
			g[u][v] = g[v][u] = w;
		}
		dfs(0);
		printf("%d\n", ans);
	}
	return 0;
}

1008 Triangle Collision

完全弹性碰撞的处理方法就是把图形关于碰撞边做对称，然后小球路径不变保持直线即可。换句话说，就是在无限大密铺等边三角形上走一条直线路径。

只考虑小球与三角形最下面的边碰撞情形，其他情形变换一下坐标。如图做平行线（蓝色虚线），有两种情况：
图一 图二
  • 红色路径（两条平行线之间）：每个碰撞点都和一个三角形有关，如图编号，发现奇数号的碰撞点很好求（红圈圈出），是一条平行于 $x$ 轴的直线与轨迹的交点；至于偶数号碰撞点，设为 $k$，我们把 $k+1$ 号碰撞点求出来，就可以确定出 $k$ 号三角形的位置，于是可以求得 $k$ 号碰撞点。
  • 绿色路径（两条平行线之外）：只考虑右边（左边对称一下）。为了方便转一下坐标系，得到上图二。类似于第一种情况编号求解即可。
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-8;
const double PI = 4 * atan2(1, 1);
const double INF = 1e16;
inline int sgn(double x){
	if(fabs(x) < eps)	return 0;
	else if(x > 0)	return 1;
	else	return -1;
}
inline int cmp(double x, double y){ return sgn(x-y); }

struct Vector{
	double x, y;
	Vector() {}
	Vector(double x, double y):x(x), y(y){}
	void read(){ scanf("%lf%lf", &x, &y); }
};
typedef Vector Point;
Vector operator + (Vector A, Vector B){ return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Vector A, Vector B){ return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (double k, Vector A){ return Vector(k * A.x, k * A.y); }
Vector operator * (Vector A, double k){ return k * A; }
Vector operator / (Vector A, double k){ return Vector(A.x / k, A.y / k); }
bool operator < (const Vector &A, const Vector &B){
	return cmp(A.x, B.x) == 0 ? cmp(A.y, B.y) < 0 : cmp(A.x, B.x) < 0;
}
bool operator == (const Vector &A, const Vector &B){ return (cmp(A.x, B.x) == 0) && (cmp(A.y, B.y) == 0); }
// dot product
double operator * (Vector A, Vector B){ return A.x * B.x + A.y * B.y; }
// cross product
double operator ^ (Vector A, Vector B){ return A.x * B.y - A.y * B.x; }
double Length(Vector A){ return sqrt(A * A); }
// rotate rad counterclockwise
Vector Rotate(Vector A, double rad){
	double co = cos(rad), si = sin(rad);
	return Vector(A.x * co - A.y * si, A.x * si + A.y * co);
}
// test if vector B is to the left of vector A
bool ToTheLeft(Vector A, Vector B){ return sgn(A ^ B) > 0; }

struct Line{
	Point p;
	Vector v;
	double ang; // angle of inclination (-PI, PI]
	Line() {}
	Line(Point p, Vector v):p(p), v(v){ ang = atan2(v.y, v.x); }
	Line(double a, double b, double c){ // ax + by + c = 0
		if(sgn(a) == 0)         p = Point(0, -c/b), v = Vector(1, 0);
		else if(sgn(b) == 0)    p = Point(-c/a, 0), v = Vector(0, 1);
		else                    p = Point(0, -c/b), v = Vector(-b, a);
	}
	Point getPoint(double t){ return p + v * t; }
	bool operator < (const Line &L) const{ return ang < L.ang; }
};
bool PointOnLine(Point p, Line l){ return sgn(l.v ^ (p-l.p)) == 0; }
bool PointOnRight(Point p, Line l){ return sgn(l.v ^ (p-l.p)) < 0; }
Point GetLineIntersection(Line l1, Line l2){
	Vector u = l1.p - l2.p;
	double t = (l2.v ^ u) / (l1.v ^ l2.v);
	return l1.p + l1.v * t;
}

//------------------------------------------------------------------------//

Point P;
Vector v;
double L;
int k;

inline void solve1(){
	double y = -(k/2) * (sqrt(3)/2) * L;
	Line l(Point(0, y), Vector(1, 0));
	Line route(P, v);
	Point inter = GetLineIntersection(l, route);
	if(k & 1){
		printf("%.8f\n", Length(inter - P) / Length(v));
		return;
	}
	else{
		int kl = 0, kr = 0;
		Line ll, lr;
		if(k % 4 == 0){
			kl = floor(inter.x / L - 0.5), kr = ceil(inter.x / L - 0.5);
			while(cmp((kl+1)*L+L/2, inter.x) < 0)	kl++;
			while(cmp((kr-1)*L+L/2, inter.x) > 0)	kr--;
			if(kl != kr-1)	puts("Something wrong1!");
			ll = Line(Point(kl*L+L/2, y), Vector(1, sqrt(3)));
			lr = Line(Point(kr*L+L/2, y), Vector(-1, sqrt(3)));
		}
		else{
			kl = floor(inter.x / L), kr = ceil(inter.x / L);
			while(cmp((kl+1)*L, inter.x) < 0)	kl++;
			while(cmp((kr-1)*L, inter.x) > 0)	kr--;
			if(kl != kr-1)	puts("Something wrong2!");
			ll = Line(Point(kl*L, y), Vector(1, sqrt(3)));
			lr = Line(Point(kr*L, y), Vector(-1, sqrt(3)));
		}

		Point interl = GetLineIntersection(ll, route), interr = GetLineIntersection(lr, route);
		if(cmp(interl.y, y) >= 0 && cmp(interl.y, y+sqrt(3)/2*L) <= 0){
			printf("%.8f\n", Length(interl - P) / Length(v));
			return;
		}
		else if(cmp(interr.y, y) >= 0 && cmp(interr.y, y+sqrt(3)/2*L) <= 0){
			printf("%.8f\n", Length(interr - P) / Length(v));
			return;
		}
		else	puts("Something wrong3!");
	}
}

inline void solve2(){
	P.x += L/2;
	P = Rotate(P, -PI/3), v = Rotate(v, -PI/3);

	double y = -((k+1)/2) * (sqrt(3)/2) * L;
	Line l(Point(0, y), Vector(1, 0));
	Line route(P, v);
	Point inter = GetLineIntersection(l, route);
	if(!(k & 1)){
		printf("%.8f\n", Length(inter - P) / Length(v));
		return;
	}
	else{
		int kl = 0, kr = 0;
		Line ll, lr;
		if((k+1) % 4){
			kl = floor(inter.x / L - 0.5), kr = ceil(inter.x / L - 0.5);
			while(cmp((kl+1)*L+L/2, inter.x) < 0)	kl++;
			while(cmp((kr-1)*L+L/2, inter.x) > 0)	kr--;
			if(kl != kr-1)	puts("Something wrong4!");
			ll = Line(Point(kl*L+L/2, y), Vector(1, sqrt(3)));
			lr = Line(Point(kr*L+L/2, y), Vector(-1, sqrt(3)));
		}
		else{
			kl = floor(inter.x / L), kr = ceil(inter.x / L);
			while(cmp((kl+1)*L, inter.x) < 0)	kl++;
			while(cmp((kr-1)*L, inter.x) > 0)	kr--;
			if(kl != kr-1)	puts("Something wrong5!");
			ll = Line(Point(kl*L, y), Vector(1, sqrt(3)));
			lr = Line(Point(kr*L, y), Vector(-1, sqrt(3)));
		}

		Point interl = GetLineIntersection(ll, route), interr = GetLineIntersection(lr, route);
		if(cmp(interl.y, y) >= 0 && cmp(interl.y, y+sqrt(3)/2*L) <= 0){
			printf("%.8f\n", Length(interl - P) / Length(v));
			return;
		}
		else if(cmp(interr.y, y) >= 0 && cmp(interr.y, y+sqrt(3)/2*L) <= 0){
			printf("%.8f\n", Length(interr - P) / Length(v));
			return;
		}
		else	puts("Something wrong6!");
	}
}

int main(){
	int T; for(scanf("%d", &T); T; T--){
		scanf("%lf%lf%lf%lf%lf%d", &L, &P.x, &P.y, &v.x, &v.y, &k);
		Point O(0, sqrt(3)/6*L);
		Vector PA = Point(-L/2, 0) - P, PB = Point(L/2, 0) - P, PC = Point(0, sqrt(3)/2*L) - P;
		Vector CA(-1, -sqrt(3)), CB(1, -sqrt(3));
		if(ToTheLeft(PB, v) && ToTheLeft(v, PC)){
			v = Rotate(v, -2*PI/3);
			P = O + Rotate(P - O, -2*PI/3);
		}
		else if(ToTheLeft(PC, v) && ToTheLeft(v, PA)){
			v = Rotate(v, 2*PI/3);
			P = O + Rotate(P - O, 2*PI/3);
		}
// cerr << "!" << P.x << " " << P.y << " " << v.x << " " << v.y << endl;
		if(sgn(CA ^ v) < 0)	P.x = -P.x, v.x = -v.x;
		if(sgn(CA ^ v) >= 0 && sgn(v ^ CB) >= 0)	solve1();
		else	solve2();
	}
	return 0;
}

看到 std 之后：我果然又又又又做复杂了……二分答案，问题转化成已知时间内发生了多少次碰撞，与水平边有 $\left\lfloor\frac{y}{\frac{\sqrt3}{2}L}\right\rfloor$ 个交点，与斜着的边的交点数旋转一下就好。

不过我的复杂度更优（这是我最后的倔强，哼！）

1009 Parentheses Matching

首先把它本身已经匹配好的左右括号去掉——每一个右括号与尽可能靠右的左括号匹配，保证多出来的左括号尽可能靠前，原因稍后解释，实现用栈就好。

然后我们得到的序列一定长这样：一连串的右括号接上一连串的左括号，中间插入一些星。由于左括号前面的星对左括号没有影响，所以正如刚才所说，要让多出来的这些左括号靠前，更有可能匹配。

于是分段：一连串的右括号为一段，一连串的左括号为段，二者相互独立，分别求解。

对于右括号段，让尽可能前面的星变成左括号去匹配，这样保证字典序最小，用队列实现；对于左括号段，让尽可能后面的星变成右括号，反过来加队列就行了。

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
#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;
char s[N], t[N];
bool del[N];

inline bool solve1(int l, int r){
	queue<int> q;
	for(int i = l; i <= r; i++){
		if(del[i])	continue;
		if(s[i] == ')'){
			if(q.empty())	return false;
			t[q.front()] = '(';
			q.pop();
		}
		else if(s[i] == '*')	q.push(i);
		else	puts("Something wrong!");
	}
	return true;
}

inline bool solve2(int l, int r){
	queue<int> q;
	for(int i = r; i >= l; i--){
		if(del[i])	continue;
		if(s[i] == '('){
			if(q.empty())	return false;
			t[q.front()] = ')';
			q.pop();
		}
		else if(s[i] == '*')	q.push(i);
		else	puts("Something wrong!");
	}
	return true;
}

inline void initCASES(){
	for(int i = 1; i <= n; i++){
		t[i] = '$';
		del[i] = false;
	}
}

int main(){
	for(read(T); T; T--){
		scanf("%s", s+1);
		n = strlen(s+1);
		initCASES();

		stack<int> stk;
		for(int i = 1; i <= n; i++){
			if(s[i] == '*')	continue;
			else if(s[i] == '(')	stk.push(i);
			else{
				if(!stk.empty()){
					del[stk.top()] = del[i] = true;
					stk.pop();
				}
			}
		}
		int lst = 0, fst = n+1;
		for(int i = 1; i <= n; i++){
			if(del[i])	continue;
			if(s[i] == ')')	lst = max(lst, i);
			if(s[i] == '(')	fst = min(fst, i);
		}
		bool ok = true;
		if(lst >= 1){
			ok = solve1(1, lst);
			if(!ok){ puts("No solution!"); continue; }
		}
		if(fst <= n){
			ok = solve2(fst, n);
			if(!ok){ puts("No solution!"); continue; }
		}

		for(int i = 1; i <= n; i++){
			if(del[i]){ putchar(s[i]); continue; }
			if(s[i] == '*'){
				if(t[i] != '$')	putchar(t[i]);
			}
			else	putchar(s[i]);
		}
		puts("");
	}
	return 0;
}

2020杭电多校（第三场）

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

作者

xyfJASON

发布于

2020-07-28

更新于

2021-08-28

许可协议

#

评论

关注我

分类

最新文章

标签

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