CodeForces 723(#375-Div2)解题报告

大致题意

Problem A

一条$x$轴上有三个坐标$x1$,$x2$,$x3$,求出一坐标使得其到三坐标距离之和最小,输出最小距离。

Problem B

给定一个字符串,由大小写字母,下划线以及小括号组成

单词的定义为连续的字母,要求输出括号外的单词最长长度,即括号内的单词个数

Problem C

给定$n$,$m$,再给$n$个数,每次改变可将任意一个数改为另一个数

要求用最少的变动次数使得$1$~$m$这$m$个数里,出现次数最少的数的出现次数尽可能多。

Problem D

给定$n$$m$的字符矩阵表示地图,”$*$”表示陆地,”$.$”表示水。

不与边界连通的水的极大连通分量定义为湖,现在要求把最少的水变为陆地,使得湖的数目减少为K。

Problem E

不一定连通的无向图的每条边定向,使得入度等于出度的点数最多。(度数为$0$也可)

Problem F

给定一个无向图,问是否存在一个生成树使得$s$,$t$两点的度数不超过$ds$,$dt$

思路

A

取三个数的中位数作为汇合点,计算一下距离即可。

B

线性扫一遍字符串,遇到分隔符即对刚刚发现的单词进行相应处理。

注意字符串扫完后仍需进行一次判断(a_aa)

以及存在括号嵌套的情况(可以自己想一想怎么解决,或见AC代码)

C

只要保证$1$~$m$的每个数出现至少$n/m$次即可

判断一下,若存在数出现次数小于$n/m$,将其作为目标数,先将大于$m$的数变为目标数

若还不够,将$1$~$m$中出现次数较多的数变为目标数

此题可用$map$离散化

D

$BFS$跑连通分量确定所有的湖,注意区别

然后将所有的湖从小往大填即可

E

先明确这样两个信息:

  1. 对于任意无向图,度数为奇数的点必有偶数个

  2. 对于任意仅含偶度数点的连通图,均存在欧拉回路

现在我们将原图所有的奇度数点两两配对并连边,图就变成了只有偶度数点的图

然后对于每一个连通分量都跑欧拉回路,跑的时候给所有的边定向

输出时最大点数即原图中偶度数点的个数

不输出新加入的边即可

F

一个有两个点的度数限制的生成树问题

先将两个点及其邻边删去,然后对于剩下的所有连通分量先求出生成树。

然后对于一连通分量,其具有三种情况

  1. 其与$s$,$t$均不相连,此种情况下原图不连通,无解
  2. 其与$s$,$t$之一相连,此种情况下将其与两点之一连上,并且对应点度数$+1$
  3. 其与$s$,$t$均相连,此种情况下将其与两点中剩余度数较大的相连

若这样的情况下$s$,$t$仍不连通,酌情连$s-t$的边(假如有),或选择第三种情况下的连通分量连边使得$s$,$t$连通

这之中若度数超过限制,则无解,否则输出解即可

AC代码

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
#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[5];

int abss(int x)
{
if(x<0)return -x;else return x;
}

int main()
{
scan3(a[1],a[2],a[3]);
sort(a+1,a+4);
int d=a[2];
printf("%d",abss(a[1]-d)+abss(a[2]-d)+abss(a[3]-d));
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
56
#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 i,j,k,l,m,n;
char s[500];

int main()
{
scanf("%d\n",&n);
gets(s);
int m1=0,m2=0;
m=0;l=0;
for(i=0;i<n;i++)
{
if((s[i]>='A' && s[i]<='Z')||(s[i]>='a' && s[i]<='z')){m++;continue;}
if(l>0 && m>0)m2++;
if(l==0)m1=max(m1,m);
if(s[i]=='(')l++;
if(s[i]==')')l--;
m=0;
}
m1=max(m1,m);
printf("%d %d",m1,m2);
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
#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))

map<int,int> mp;
vector<int> q;
int i,j,k,l,m,n;
int a[2005];

int main()
{
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)mp[i]=1;
for(i=1;i<=n;i++)
{
scanf("%d",&k);
a[i]=k;
int t=mp.count(k);
if(t>0)mp[k]++;else mp[k]=2;
}
l=0;q.clear();
int ans=n/m+1;
for(i=1;i<=m;i++)
if(mp[i]<ans)q.push_back(i);
j=0;
while(j<q.size())
{
for(i=1;i<=n;i++)
{
if(a[i]>m)
{
l++;
mp[a[i]]--;
a[i]=q[j];
mp[q[j]]++;
if(mp[q[j]]>=ans)j++;
if(j==q.size())break;
}
}
if(j==q.size())break;
for(i=1;i<=n;i++)
{
if(mp[a[i]]>ans)
{
l++;
mp[a[i]]--;
a[i]=q[j];
mp[q[j]]++;
if(mp[q[j]]>=ans)j++;
if(j==q.size())break;
}
}
}
printf("%d %d\n",ans-1,l);
for(i=1;i<=n;i++)
{
if(i>1)printf(" ");
printf("%d",a[i]);
}
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#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[55][55];
int a[55][55];
struct squ
{
int num;
int square;
bool operator < (const struct squ p)const
{return square<p.square;}
}sq[2600];

struct point
{
int x,y;
point(int x=0,int y=0):x(x),y(y){}
};

int i,j,k,l,n,m,t;

int d[4][2]={0,1,1,0,0,-1,-1,0};

bool law(int x,int y)
{
if(x<1 || x>n)return false;
if(y<1 || y>m)return false;
return a[x][y]==0;
}

int bfs(int x,int y)
{
int tot=0;
point t=point(x,y);
a[x][y]=k;
queue<point> q;
while(!q.empty())q.pop();
q.push(t);
while(!q.empty())
{
point u=q.front();
tot++;q.pop();
for(int i=0;i<=3;i++)
if(law(u.x+d[i][0],u.y+d[i][1]))
{
point v=point(u.x+d[i][0],u.y+d[i][1]);
q.push(v);
a[v.x][v.y]=k;
}
}
return tot;
}

int main()
{
scanf("%d %d %d\n",&n,&m,&t);
for(i=1;i<=n;i++)
{
gets(s[i]+1);
for(j=1;j<=m;j++)
if(s[i][j]=='*')a[i][j]=-1;
}
k=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]==0)
{
k++;
sq[k].num=k;
sq[k].square=bfs(i,j);
}
for(i=1;i<=n;i++)
{
j=a[i][1];
if(j>0)sq[j].square=100000;
j=a[i][m];
if(j>0)sq[j].square=100000;
}
for(i=1;i<=m;i++)
{
j=a[1][i];
if(j>0)sq[j].square=100000;
j=a[n][i];
if(j>0)sq[j].square=100000;
}
sort(sq+1,sq+1+k);
k=1;
while(sq[k].square>0 && sq[k].square<3000)k++;
k--;
k-=t;l=0;
for(int p=1;p<=k;p++)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]==sq[p].num)
{
l++;
a[i][j]=-1;
}
}
printf("%d\n",l);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)if(a[i][j]>=0)printf(".");else printf("*");
printf("\n");
}
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
#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 edge
{
int from,to,flag;
edge(int from=0,int to=0,int flag=0):from(from),to(to),flag(flag){}
}edg[50005];
bool used[50005];
int du[205];
int stac[50005];
vector<int> odd;
vector<int> g[205];
queue<int> q;
bool vis[205];

int i,j,k,l,m,n,m1,T,sta;

int other(int e,int u)
{
if(edg[e].from==u)return edg[e].to;else return edg[e].from;
}

void dfs(int x)
{
stac[++sta]=x;
for(unsigned int i=0;i<g[x].size();i++)
{
if(used[g[x][i]])continue;
used[g[x][i]]=true;
dfs(other(g[x][i],x));
break;
}
}

void Fleury(int x)
{
sta=1;stac[sta]=x;
while(sta>=1)
{
x=stac[sta];
vis[x]=true;
bool f=false;
for(unsigned int i=0;i<g[x].size();i++)
{
if(!used[g[x][i]]){f=true;break;}
}
if(!f)q.push(stac[sta--]);
else
{
sta--;
dfs(stac[sta+1]);
}
}
}

int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
odd.clear();
while(!q.empty())q.pop();
memset(du,0,sizeof(du));
memset(edg,0,sizeof(edg));
memset(used,0,sizeof(used));
memset(vis,0,sizeof(vis));
for(i=0;i<=n;i++)g[i].clear();
for(i=1;i<=m;i++)
{
scan2(j,k);
du[j]++;du[k]++;
edg[i]=edge(j,k,0);
g[j].push_back(i);
g[k].push_back(i);
}
for(i=1;i<=n;i++)
if(du[i]%2!=0)odd.push_back(i);
printf("%d\n",n-odd.size());
m1=m;
unsigned int t=0;
while(t<odd.size())
{
edg[++m1]=edge(odd[t],odd[t+1],0);
g[odd[t]].push_back(m1);
g[odd[t+1]].push_back(m1);
t+=2;
}
for(i=1;i<=n;i++)if(!vis[i])Fleury(i);
while(!q.empty())
{
int x=q.front();q.pop();
if(q.empty())break;
int y=q.front();
for(i=0;i<g[x].size();i++)
{
k=g[x][i];
if(other(k,x)==y && edg[k].flag==0)
{
if(edg[k].from==x)edg[k].flag=1;else edg[k].flag=-1;
break;
}
}
}
for(i=1;i<=m;i++)
if(edg[i].flag>0)printf("%d %d\n",edg[i].from,edg[i].to);else printf("%d %d\n",edg[i].to,edg[i].from);
}
return 0;
}

F(By nike0good)

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<vector>
#include<set>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (1000000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
#define SI(a) ((a).size())
#define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans);
#define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl;
#define PRi2D(a,n,m) For(i,n) { \
For(j,m-1) cout<<a[i][j]<<' ';\
cout<<a[i][m]<<endl; \
}
#pragma comment(linker, "/STACK:102400000,102400000")
#define ALL(x) (x).begin(),(x).end()
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
typedef long long ll;
#define MAXN (500000+10)
class bingchaji
{
public:
int father[MAXN],n;
void mem(int _n)
{
n=_n;
For(i,n) father[i]=i;
}
int getfather(int x)
{
if (father[x]==x) return x;

return father[x]=getfather(father[x]);
}
void unite(int x,int y)
{
x=getfather(x);
y=getfather(y);
if (x^y) {
father[x]=y;
}
}
bool same(int x,int y)
{
return getfather(x)==getfather(y);
}
}S;
int n,m,s,t,ds,dt;
struct edge{
int u,v,w;
}e[MAXN*2+10];
vector<edge> ans;
bool operator<(edge a,edge b) {
return a.w<b.w;
}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}

int b[MAXN][2]={0};
vi ri;
int find(int x) {
return lower_bound(ALL(ri),x)-ri.begin();
}

int main()
{
// freopen("F.in","r",stdin);
// freopen(".out","w",stdout);

cin>>n>>m;
For(i,m) {
int u=read(),v=read();
e[i].u=u,e[i].v=v;
}
cin>>s>>t>>ds>>dt;

swap(s,t);swap(ds,dt);

For(i,m) {
e[i].w=0;
if (e[i].u==s||e[i].v==s) ++e[i].w;
if (e[i].u==t||e[i].v==t) ++e[i].w;
}
sort(e+1,e+1+m);

S.mem(n);
For(i,m) if (!e[i].w) {
if (!S.same(e[i].u,e[i].v)) {
S.unite(e[i].u,e[i].v);
ans.pb(e[i]);
}
}
For(i,n) S.getfather(i);

ri;
For(i,n) ri.pb(S.father[i]);
sort(ALL(ri));
ri.erase(unique(ri.begin(),ri.end()),ri.end());
int cnt=SI(ri);

For(i,m) if (e[i].w==1) {
int p=S.father[e[i].u],p2=S.father[e[i].v];
if (p2==s||p2==t) swap(p,p2);
int now=find(p2);
if (p==s) b[now][0]=i;
else b[now][1]=i;
}

vi oer;

bool fl=0;
Rep(i,cnt) if (ri[i]!=s&&ri[i]!=t){
if (b[i][0]==0&&b[i][1]==0) {
puts("No"); return 0;
}
else if(b[i][0]==0&&b[i][1]!=0) {
ans.pb(e[b[i][1]]); dt--;
}else if(b[i][0]!=0&&b[i][1]==0) {
ans.pb(e[b[i][0]]); ds--;
} else {
if (!fl) {
ans.pb(e[b[i][0]]);
ans.pb(e[b[i][1]]);
ds--;dt--;
fl=1;
} else oer.pb(i);
}
}
if (!fl&&e[m].w==2) {
ans.pb(e[m]);
ds--;dt--;
fl=1;
}

Rep(i,SI(oer)) {
int now=oer[i];
if (ds<=dt) {
ans.pb(e[b[now][1]]); dt--;
} else {
ans.pb(e[b[now][0]]); ds--;
}
}




if (ds<0||dt<0|| !fl || ans.size()<n-1 ) {
puts("No"); return 0;
}
puts("Yes");
Rep(i,SI(ans)) {
printf("%d %d\n",ans[i].u,ans[i].v);
}


return 0;
}