CodeForces 733 解题报告

思路

Problem A

最左端加一个A,最右端加一个A,求相邻两个元音字母$(A,E,I,O,U,Y)$的距离最大值即可

Problem B

枚举翻转哪一对即可

Problem C

通过观察注意到一个性质,即b数组中相邻的数对应着a数组中的连续一段数

而且b数组中的相邻数,在a数组中对应的区间也相邻

故可用$O(n)$的复杂度扫一遍,其中对于每个区间找一个符合要求的最大值把剩下的怪兽吃掉就好

P.S. 注意判断怪兽不够或多余的情况QAQ

Problem D

显然球的半径为长方体三边长的最小值

标准做法:

将每个长方体的三边长从大到小排序,然后分别作为第1.2.3关键字对长方体排序

计算相邻两个是否比单个更优即可

(因为对于两个能合并的长方体,显然将第一长和地热场的边组成的面贴合才会对最终结果可能有贡献)

我的SB做法:

跑了三遍排序,每次对于长方体的不同边顺序做三关键字排序,然后二分最可能的合并项尝试合并

Problem E–By zbh2047

首先,由于移动路线是往返的,故某一次从一端不改变方向的走到最头后,经过路径的箭头方向是一致的,且与移动方向相反,这就表明返回时可以走更大的长度。因而,最终一定会走出来

接下来,考虑最终从哪个方向出来。设某一位置右侧有$a$个向左的箭头,左侧有$b$个向右的箭头,那么$a>b$时将从左侧出来,$a<b$时将从右侧出来。$a=b$时出来方向和初始方向一致。而初始点越靠右,$b$就越大,$a$就越小,故最终从左侧出来的所有初始点集合组成一个区间,最左端为$1$;从右侧出来的所有初始点集合也组成一个区间,最右端为$n$。

故下面只考虑从左侧出来的情况,右侧出来的情况只需把字符串反转过来即可类似处理。

假设我们求出了以第($i-1$)格为初始时的答案,目标为在常数时间求出第i格为初始时的答案。我们引入$pos_i$表示从左往右第$i$个方向向左的箭头位置。那么,有一个有趣的性质:

当从第i格进入时,最终经过该箭头调转方向即可从最左端出来。根据该性质,考虑以i格进入比第(i-1)格进入多走的路径,不难得到:
$ansi = ans{i-1} + (pos_i - i) * 2 + 1$

时间复杂度$O(n)$

Problem F

我们首先看一个显然的性质,那就是我们只需要对于一条边进行操作即可

然后先求出原图的最小生成树,那么对于操作的边存在两种情况

  1. 操作的是树边,直接算一下比较一下就可以了

  2. 操作的是非树边,设这条边为$V$,我们将$V$加入$MST$后得到了一个环

    我们需要找到环上除了$V$以外的最大的边,将其换成$V$,从而保证结果依然为树

对于找到树上两点间最大边,我使用了倍增的LCA做法

总复杂度$O(mlogm+mlogn)$

代码

A

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
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

char s[105];

int i,n,m,ans;
char c;

int main()
{
n=0;
while(scanf("%c",&c)==1 && c>='A' && c<='Z')
{
s[++n]=c;
}
s[0]='A';
s[++n]='A';
i=m=0;ans=0;
while(i<n)
{
i++;
if(s[i]=='A' || s[i]=='E' || s[i]=='O' || s[i]=='U' || s[i]=='Y' || s[i]=='I')
{
if(i-m>ans)ans=i-m;
m=i;
}
}
printf("%d",ans);
return 0;
}

B

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
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

int a[100005],b[100005];
int i,j,l,m,n,r,ans;

int main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d %d",&a[i],&b[i]);
l+=a[i];
r+=b[i];
}
ans=abs(l-r),m=0;
for(i=1;i<=n;i++)
{
j=abs((l-a[i]+b[i])-(r-b[i]+a[i]));
if(j>ans){ans=j;m=i;}
}
printf("%d",m);
return 0;
}

C

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
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

int a[505],b[505];
int cz[505][2];
int i,j,k,l,m,n;
int last,now,sum;

bool cl(int x,int y)
{
if(x==y)return true;
int js=(x-i);
int ma=0,p=0;
for(int i=x;i<=y;i++)if(a[i]>ma)ma=a[i];
for(int i=x;i<=y;i++)
{
if(a[i]<ma)continue;
if(i>x && a[i]>a[i-1]){p=i;break;}
if(i<y && a[i]>a[i+1]){p=i;break;}
}
if(p==0)return false;
int le=p-1,ri=p+1;
if(le<x && ri>y)return true;
if(ri<=y && a[p]>a[ri])
{
for(int i=p+1;i<=y;i++)
{
cz[++sum][0]=p-js;
cz[sum][1]=1;
}
for(int i=p-1;i>=x;i--)
{
cz[++sum][0]=p-js;
cz[sum][1]=0;
p--;
}
}else
{
int lll=p;
for(int i=p-1;i>=x;i--)
{
cz[++sum][0]=p-js;
cz[sum][1]=0;
p--;
}
for(int i=lll+1;i<=y;i++)
{
cz[++sum][0]=p-js;
cz[sum][1]=1;
}
}
return true;
}

int main()
{
scan(n);
for(i=1;i<=n;i++)scan(a[i]);
scan(m);
for(i=1;i<=m;i++)scan(b[i]);
last=1;sum=0;
for(i=1;i<=m;i++)
{
int tot=0;
j=last;
if(j>n){printf("NO");return 0;}
while(j<=n && tot<b[i])
{
tot+=a[j];
if(tot==b[i]){now=j+1;break;}
j++;
}
if(tot>b[i]){printf("NO");return 0;}
bool f=cl(last,j);
if(!f){printf("NO");return 0;}
last=now;
}
if(now<=n){printf("NO");return 0;}
printf("YES\n");
for(i=1;i<=sum;i++)
{
printf("%d ",cz[i][0]);
if(cz[i][1]==0)printf("L\n");
if(cz[i][1]==1)printf("R\n");
}
return 0;
}

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
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
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

struct stone
{
LL a,b,c;
int pos;
stone(LL a=0,LL b=0,LL c=0,int pos=0):a(a),b(b),c(c),pos(pos){}
bool operator < (const struct stone p)const
{
if(a>p.a)return true;
if(a<p.a)return false;
if(b>p.b)return true;
if(b<p.b)return false;
return c>p.c;
}
}st[100005];

LL a[5];
LL store[100005][3];
int an[3];
int i,j,k,l,m,n;
LL ans=0;

LL mini(LL x,LL y,LL z)
{
LL t=x;
t=min(t,y);
t=min(t,z);
return t;
}

int find(int now)
{
int l=now+1,r=n;
while(r-l>1)
{
int mid=(l+r)>>1;
if(st[mid].a<st[now].a){r=mid;continue;}
if(st[mid].b>st[now].b){l=mid;continue;}
if(st[mid].b<st[now].b){r=mid;continue;}
if(mini(st[now].a,st[now].b,st[now].c+st[mid].c)>ans){ans=mini(st[now].a,st[now].b,st[now].c+st[mid].c);m=2;an[1]=st[now].pos;an[2]=st[mid].pos;}
r=mid;
}
if(st[now].a!=st[l].a || st[now].b!=st[l].b)l++;
if(st[now].a==st[l].a && st[now].b==st[l].b)return l;
return 0;
}

int main()
{
scan(n);m=1;
for(i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&a[1],&a[2],&a[3]);
sort(a+1,a+4);
store[i][0]=a[1];store[i][1]=a[2];store[i][2]=a[3];
if(a[1]>ans){ans=a[1];an[1]=i;}
st[i]=stone(a[3],a[2],a[1],i);
}
sort(st+1,st+n+1);
for(i=1;i<=n;i++)
{
int p=find(i);
if(mini(st[i].a,st[i].b,st[i].c+st[p].c)>ans)
{ans=mini(st[i].a,st[i].b,st[i].c+st[p].c);m=2;an[1]=st[i].pos;an[2]=st[p].pos;}
}
for(i=1;i<=n;i++)st[i]=stone(st[i].b,st[i].c,st[i].a,st[i].pos);
sort(st+1,st+n+1);
for(i=1;i<=n;i++)
{
int p=find(i);
if(mini(st[i].a,st[i].b,st[i].c+st[p].c)>ans)
{ans=mini(st[i].a,st[i].b,st[i].c+st[p].c);m=2;an[1]=st[i].pos;an[2]=st[p].pos;}
}
for(i=1;i<=n;i++)st[i]=stone(st[i].b,st[i].c,st[i].a,st[i].pos);
sort(st+1,st+n+1);
for(i=1;i<=n;i++)
{
int p=find(i);
if(mini(st[i].a,st[i].b,st[i].c+st[p].c)>ans)
{ans=mini(st[i].a,st[i].b,st[i].c+st[p].c);m=2;an[1]=st[i].pos;an[2]=st[p].pos;}
}
printf("%d\n",m);
for(i=1;i<=m;i++)
{
if(i>1)printf(" ");
printf("%d",an[i]);
}
return 0;
}

E–By zbh2047

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<cstdio>
int n;
char s[2][1000002];
long long ans[1000002];
int pos[1000002];
int solve(char s[])
{
int left = 0;
s[0] = 'D';
for (int i = 0; i <= n + 1; i++){
if (s[i] == 'D')pos[left++] = i;
}
for (int i = 1; i < left; i++)
ans[i] = ans[i - 1] + (pos[i] - i) * 2 + 1;
return left;
}
int main()
{
int len;
scanf("%d%s", &n, s[0] + 1);
len = solve(s[0]);
for (int i = 1; i < len; i++)
printf("%I64d\n", ans[i]);
for (int i = 1; i <= n; i++)
s[1][i] = s[0][n + 1 - i] == 'D' ? 'U' : 'D';
len = solve(s[1]);
for (int i = len - 1; i > 0; i--)
printf("%I64d\n", ans[i]);
return 0;
}

F

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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

const int maxn=200005;
const int maxm=200005;

struct edge
{
int u,v,pos;
LL disa,cost;
edge(int u=0,int v=0,int pos=0,LL disa=0,LL cost=0):u(u),v(v),pos(pos),disa(disa),cost(cost){}
bool operator < (const struct edge p)const
{return disa<p.disa;}
}edg[maxn];

struct tree
{
int fat,dep;
vector<int> son;
}tr[maxn];

int i,j,k,l,m,n,bj,maxd,ans1,wow;
LL sum,tot,sum1;
int ans[maxn];
int a[maxn];
bool b[maxm];
bool ff=false;

LL dou[maxn][20];
int fat[maxn][20];
vector<int> g[maxn];

int find(int x)
{
if(a[x]==x)return x;
else return a[x]=find(a[x]);
}

inline int other(int now,int num)
{
if(num==0)return 0;
if(edg[num].u==now)return edg[num].v;else return edg[num].u;
}

void dfs(int now)
{
if(a[now]>0)return;
a[now]=1;
tr[now].dep=tr[other(now,tr[now].fat)].dep+1;
maxd=max(tr[now].dep,maxd);
for(unsigned int i=0;i<g[now].size();i++)
{
int v=other(now,g[now][i]);
if(a[v]>0)continue;
tr[now].son.push_back(g[now][i]);
tr[v].fat=g[now][i];
}
for(unsigned int i=0;i<tr[now].son.size();i++)
dfs(other(now,tr[now].son[i]));
}

void mkd()
{
for(int i=1;i<=n;i++)dou[i][0]=edg[tr[i].fat].disa,fat[i][0]=other(i,tr[i].fat);
for(int step=1;(1<<(step))<=maxd;step++)
for(int i=1;i<=n;i++)
{
dou[i][step]=max(dou[i][step-1],dou[fat[i][step-1]][step-1]);
fat[i][step]=fat[fat[i][step-1]][step-1];
}
}

LL search(int x,int y)
{
if(tr[x].dep<tr[y].dep)
{int o=x;x=y;y=o;}
LL ma=0;int t;
if(tr[x].dep>tr[y].dep)
{
while(tr[x].dep>tr[y].dep)
{
t=0;
while(tr[fat[x][t]].dep>tr[y].dep)t++;
if(tr[fat[x][t]].dep==tr[y].dep)
{
ma=max(ma,dou[x][t]);
x=fat[x][t];
break;
}
t--;
ma=max(ma,dou[x][t]);
x=fat[x][t];
}
}
while(x!=y)
{
t=0;
while(fat[x][t]!=fat[y][t])t++;
if(t==0)
{
ma=max(ma,dou[x][t]);
ma=max(ma,dou[y][t]);
break;
}
t--;
ma=max(ma,dou[x][t]);
ma=max(ma,dou[y][t]);
x=fat[x][t];
y=fat[y][t];
}
if(x==y)wow=x;else wow=fat[x][0];
return ma;
}

int main()
{
scan2(n,m);
for(i=1;i<=m;i++)scanf("%lld",&edg[i].disa);
for(i=1;i<=m;i++)scanf("%lld",&edg[i].cost);
for(i=1;i<=m;i++)
{
scan2(j,k);
edg[i]=edge(min(j,k),max(j,k),i,edg[i].disa,edg[i].cost);
}
scanf("%lld",&tot);
sort(edg+1,edg+m+1);
memset(b,0,sizeof(b));
for(i=1;i<=n;i++)a[i]=i;
l=1;sum=0;
for(i=1;i<=m;i++)
{
if(l>=n)break;
j=find(edg[i].u);
k=find(edg[i].v);
if(j==k || a[j]==a[k])continue;
sum+=edg[i].disa;
a[k]=a[j];l++;
g[edg[i].u].push_back(i);
g[edg[i].v].push_back(i);
ans[++ans1]=i;
b[i]=true;
}
sum1=sum;bj=0;maxd=0;
for(int t=1;t<=ans1;t++)
{
if(sum1-tot/edg[ans[t]].cost<sum){sum=sum1-tot/edg[ans[t]].cost;bj=ans[t];}
}
memset(a,0,sizeof(a));
tr[1].fat=0;tr[0].dep=0;dfs(1);
mkd();bool f=false;
for(i=1;i<=m;i++)
{
if(b[i])continue;
LL temp=edg[i].disa-tot/edg[i].cost;
LL fuck=search(edg[i].u,edg[i].v);
//if(n==50 && edg[i].disa==683)printf("%lld\n",fuck);
if(sum1-fuck+temp<sum){f=true;sum=sum1-fuck+temp;l=i;}
}
if(!f)
{
printf("%lld\n",sum);
for(i=1;i<=ans1;i++)
{
edge e=edg[ans[i]];
if(bj==ans[i])
{
printf("%d %lld\n",e.pos,e.disa-tot/e.cost);
}else
{
printf("%d %lld\n",e.pos,e.disa);
}
}
return 0;
}
search(edg[l].u,edg[l].v);
LL mm=0;int bbb;
int x=edg[l].u,y=edg[l].v;
while(x!=wow)
{
if(edg[tr[x].fat].disa>mm){mm=edg[tr[x].fat].disa;bbb=tr[x].fat;}
x=fat[x][0];
}
while(y!=wow)
{
if(edg[tr[y].fat].disa>mm){mm=edg[tr[y].fat].disa;bbb=tr[y].fat;}
y=fat[y][0];
}
for(i=1;i<=ans1;i++)if(ans[i]==bbb)ans[i]=l;
printf("%lld\n",sum);
for(i=1;i<=ans1;i++)
{
edge e=edg[ans[i]];
if(l==ans[i])
{
printf("%d %lld\n",e.pos,e.disa-tot/e.cost);
}else
{
printf("%d %lld\n",e.pos,e.disa);
}
}
return 0;
}