CF934 题解

A

范围很小，可以直接 枚举。

复杂度较低的做法是枚举 的决策，然后通过求出最大的正乘积以及最大负乘积来更新答案。用 multiset 来维护 操作后的序列也许实现上较为简单。

B

简单贪心，尽可能选 8，奇数情况额外选个 9 （或其他贡献为 的数码）。

C

发现答案由 [1s] [2s, 1s] [2s] 组成，考虑用 的 DP 预处理出中间区间 [2s, 1s] 的贡献。

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
// Problem: C. A Twisty Movement
// Contest: Codeforces - Codeforces Round 462 (Div. 2)
// URL: https://codeforces.com/contest/934/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define SZ(a) ((int) (a).size())
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=2020;

int n, w[N];
int f[N][N][2];
int c[N][2];

void solve(){
	cin>>n;
	rep(i, 1, n) read(w[i]);
	rep(i, 1, n){
		rep(j, 0, 1) c[i][j]=c[i-1][j];
		c[i][w[i]&1]++;
	}
	
	rep(len, 1, n){
		rep(l, 1, n-len+1){
			int r=l+len-1;
			if(l==r){
				f[l][l][w[l]&1]=1;
			}
			else{
				rep(k, 0, 1) f[l][r][k]=f[l][r-1][k];
				if(w[r]&1){
					f[l][r][1]=max(f[l][r][1], f[l][r-1][0]+1);
					f[l][r][1]=max(f[l][r][1], f[l][r-1][1]+1);
				}
				else{
					f[l][r][0]=max(f[l][r][0], f[l][r-1][0]+1);
				}
			}
		}
	}
	
	int res=0;
	rep(l, 1, n) rep(r, l, n){
		int c0=c[r][0]-c[l-1][0];
		int c1=c[r][1]-c[l-1][1];
		int x=(c[l-1][1]+max(f[l][r][0], f[l][r][1])+c[n][0]-c[r][0]);
		int y=(c[l-1][1]+c0+c[n][0]-c[r][0]);
		int z=(c[l-1][1]+c1+c[n][0]-c[r][0]);
		res=max({res, x, y, z});
	}
	cout<<res<<"\n";
}

signed main(){
	solve();
	return 0;
}

但其实有更简单的线性 DP 做法：

由于答案的结构为 [1s] [2s] [1s] [2s]，所以可以使用 刻画这个结构（状态）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N=2020;

int w[N];
int f[N][4];

void solve(){
	int n; cin>>n;
	rep(i, 1, n) read(w[i]);
	rep(i, 1, n){
		rep(j, 0, 3) f[i][j]=f[i-1][j];
		if(w[i]==1){
			f[i][0]=max(f[i][0], f[i-1][0]+1);
			f[i][2]=max({f[i][2], f[i-1][1]+1, f[i-1][2]+1});
		}
		else{
			f[i][1]=max({f[i][1], f[i-1][0]+1, f[i-1][1]+1});
			f[i][3]=max({f[i][3], f[i-1][2]+1, f[i-1][3]+1});
		}
	}
	cout<<*max_element(f[n], f[n]+4)<<"\n";
}

D

分析

提供一个简洁易懂的做法：

注意到 ，也就是说 ，那本质上就是在求以 为基的 的表出。

故做法类似于十进制，只不过是把基底 换成 。考虑除式 ，可以发现 对应着 ，所以做除法的时候注意把 调整到 即可。

代码

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
// Problem: D. A Determined Cleanup
// Contest: Codeforces - Codeforces Round 462 (Div. 2)
// URL: https://codeforces.com/contest/934/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define SZ(a) ((int) (a).size())
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
#define int long long
using pii = pair<int, int>;
using ll = long long;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

void solve(){
	int p, k; cin>>p>>k;
	const int b=-k;
	// p = qb + r (r>=0)
	vector<int> a;
	while(p){
		int r=p%b, q=(p-r)/b;
		if(r<0) r+=-b, ++q;
		p=q;
		a.pb(r);
	}
	cout<<a.size()<<"\n";
	for(auto e: a) cout<<e<<" ";
	puts("");
}

signed main(){
	solve();
	return 0;
}

补充

我 VP 的时候没有想到上面的做法，用了一种比较麻烦的做法，这里简单说一下供参考：

记 。

那根据题目约束，我们有 。

故可以考虑解上面的不等式组得到 ，然后将 还原出来。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(){
	int p, k; cin>>p>>k;
	vector<int> b={p};
	while(b.back()<0 || b.back()>=k){
		int nb=(b.back()>=0? -(b.back()/k): -b.back()/k+(-b.back()%k!=0? 1: 0));
		b.pb(nb);
	}
	vector<int> a;
	rep(i, 1, SZ(b)-1) a.pb(b[i]*k+b[i-1]);
	a.pb(b.back());
	cout<<a.size()<<"\n";
	for(auto e: a) cout<<e<<" ";
	puts("");
}
 
signed main(){
	solve();
	return 0;
}

E

分析

本质上是求平面图的面数 。

根据欧拉公式，，其中 是点数， 是边数， 是面数， 是连通块数。

可以用并查集维护。

通过求出圆之间所有交点并去重得到。

对于 ，考虑对于每个圆，有多少个交点落在这个圆上，把这些交点数求和即可（因为注意到一段弧不可能被多个圆共有，不需要去重）。

代码

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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
// Problem: E. A Colourful Prospect
// Contest: Codeforces - Codeforces Round 462 (Div. 2)
// URL: https://codeforces.com/contest/934/problem/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define SZ(a) ((int) (a).size())
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

// V - E + F = C + 1

using db = double;

const int N=10;
const db eps=1e-10;

int sign(db a){
	return a<-eps? -1: a>eps;
}

int cmp(db x, db y){
	return sign(x-y);
}

struct P{
	db x, y;
	
	P(){}
	
	P(db x, db y): x(x), y(y){}
	
	P operator + (P p){
		return {x+p.x, y+p.y};
	}
	
	P operator - (P p){
		return {x-p.x, y-p.y};
	}
	
	P operator * (db d){
		return {x*d, y*d};
	}
	
	P operator / (db d){
		return {x/d, y/d};
	}
	
	db abs(){
		return sqrt(abs2());
	}
	
	db abs2(){
		return x*x+y*y;
	}
	
	P rot90(){
		return P(-y, x);
	}
	
	P unit(){
		return *this/abs();
	}
	
	db dis(P p){
		return (*this-p).abs();
	}
	
	bool operator < (const P &o){
		return cmp(x, o.x)? x<o.x: y<o.y;
	}
};

struct C{
	P o;
	db r;
	
	void read(){
		cin>>o.x>>o.y>>r;
	}
};

vector<P> isCC(C c1, C c2){
	db d=c1.o.dis(c2.o);
	db r1=c1.r, r2=c2.r;
	if(cmp(d, r1+r2)==1) return {};
	if(cmp(d, abs(r1-r2))==-1) return {};
	d=min(d, r1+r2);
	db y=(r1*r1 + d*d - r2*r2) / (d*2);
	db x=sqrt(r1*r1-y*y);
	P dr=(c2.o-c1.o).unit();
	P q1=c1.o+dr*y, q2=dr.rot90()*x;
	return {q1-q2, q1+q2};
}

bool PonC(P p, C c){
	return cmp(c.r, p.dis(c.o))? 0: 1;
}

struct DSU{
	int n;
	int f[N];
	
	// 记得 init
	void init(int _n){
		n=_n;
		rep(i, 1, n){
			f[i]=i;
		}
	}
	
	int find(int x){
		return x==f[x]? x: f[x]=find(f[x]);
	}
	
	void merge(int u, int v){
		u=find(u), v=find(v);
		if(u==v) return;
		f[u]=v;
	}
	
	int total(){
		int cnt=0;
		rep(i, 1, n) cnt+=(i==find(i));
		return cnt;
	}
}dsu;

int n;
C c[N];

void solve(){
	cin>>n;
	rep(i, 1, n) c[i].read();
	vector<P> b;
	dsu.init(n);
	rep(i, 1, n) rep(j, i+1, n){
		auto tmp=isCC(c[i], c[j]);
		for(auto e: tmp) b.pb(e);
		if(tmp.size()){
			dsu.merge(i, j);
		}
	}
	
	{
		// unique b
		sort(all(b));
		vector<P> nb;
		rep(i, 0, SZ(b)-1){
			bool dup=false;
			if(i && !cmp(b[i].x, b[i-1].x) && !cmp(b[i].y, b[i-1].y)){
				dup=true;
			}
			if(!dup) nb.pb(b[i]);
		}
		b=nb;
	}
	
	int C=dsu.total();
	int V=SZ(b);
	int E=0;
	rep(i, 1, n){
		for(auto e: b){
			if(PonC(e, c[i])) ++E;
		}
	}
	cout<<C+1+E-V<<"\n";
}

signed main(){
	solve();
	return 0;
}
CP > CF 题解
#DP #计算几何
CF934 题解
https://tenshi0x0.github.io/2025/08/24/CP/CF_sols/CF934/
作者
Tenshi
发布于
2025年8月24日
许可协议