Codeforces Round #529 (Div. 3)（全部题解）

87 阅读 0 评论 58 点赞

我是靠谱客的博主风趣石头，这篇文章主要介绍Codeforces Round #529 (Div. 3)（全部题解），现在分享给大家，希望可以做个参考。

A. Repeating Cipher

题意：

将一个字符串S的第一个字符写一次，第二个写两次，第三个写三次......得到字符串t，给你t，求S

分析：

根据规则，t的第一个，第二个，第四个，第七个，第十一个......便是S的组成

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
string s;
int n;
cin>>n>>s;
int k = 0;
for(int i=0;i<n;k++)
{
cout<<s[i];
i += k;
}
return 0;
}

B. Array Stabilization

题意：

从数组中删除一个值，求数组中（最大-最小的值）最小是多少

分析：

要么删最大，要么删最小

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+55;
int a[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;++i)
cin>>a[i];
sort(a,a+n);
int b = a[n-1]-a[1];
int c = a[n-2]-a[0];
cout<<min(b,c);
return 0;
}

C. Powers Of Two

题意：

问一个数 n 能否分成k个2^x形式的数的和

分析：

观察n的二进制下有m个1，那么最少就需要m个，最多无非是n个1相加，k>m时就需要拆分，2^x = 2^(x-1)+2^(x-1)，多了一个，所以只要k属于[m，n]，就一定可以拆分成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
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+55;
int a[N];
vector<int> v;
int main()
{
int n,k;
cin>>n>>k;
int sum1 = 0;
for(int i=0; i<31; ++i)
{
if(n&(1<<i))
{
sum1++;
v.push_back((1<<i));
}
}
if(k>=sum1&&k<=n)
{
cout<<"YES"<<endl;
int i = 0;
while(v.size()<k)
{
if(v[i]>1)
{
v[i] = v[i]/2;
v.push_back(v[i]);
}
else i++;
}
for(int i=0; i<v.size(); ++i)
printf("%d ",v[i]);
}
else cout<<"NO";
return 0;
}

D. Circular Dance

题意：

n个人围成一圈，每个人记得他的后面两个人是谁，输出每个人站的位置

分析：

注意：不确定后面两个人顺序，ai_1不一定就挨着第i个人

代码：

复制代码

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

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+55;
int p[N][2];
int vis[N];
void dfs(int x)
{
if(!vis[x])
{
cout<<x<<" ";
vis[x] = 1;
int f = p[x][0];
int s = p[x][1];
if(vis[f]) dfs(s);
else if(vis[s]) dfs(f);
else
{
if(p[f][0]==s||p[f][1]==s) //f后面有s,那s一定挨着x
dfs(f);
else dfs(s);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int a,b,n;
cin>>n;
for(int i=1; i<=n; ++i)
cin>>p[i][0]>>p[i][1];
dfs(1);
return 0;
}

E. Almost Regular Bracket Sequence

题意：

给你一串括号序列，你可以改变一个位置的括号使得序列合法，求有多少个这样的位置

分析：

用栈来去掉合法的序列，讨论最后栈里剩下的情况

代码：

复制代码

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
#include <stack>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+66;
char ss[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
stack<int> s;
int n;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>ss[i];
if(ss[i]==')')
{
if(!s.empty()&&ss[s.top()]=='(') s.pop();
else s.push(i);
}
else s.push(i);
}
if(s.size()==0||n%2||s.size()>2) cout<<0;//很显然
else
{
int a = s.top();s.pop();
int b = s.top();
if(ss[b]==')')
{
if(ss[a]==')')
//b位置左边的)都可以改变
{
int ans = 0;
for(int i=1;i<=b;++i)
if(ss[i]==')') ans++;
cout<<ans;
}
else cout<<0;// )( 这种无论改变哪一个都不行
}
else
{
int ans = 0;
for(int i=a;i<=n;++i) //a位置右边的都可以改变
if(ss[i]=='(') ans++;
cout<<ans;
}
}
return 0;
}

F. Make It Connected

题意：

有n个点，每个点有一个权值，在两个点之间连一条边的花费为两点权值之和，还有m条特殊边，加入这条边的花费为w，问使图联通最少花费多少

分析：

使图联通且花费最少，无非是建一颗最小生成树，除了已知的m条边，我们还可以建n*(n-1)/2条边(每两个点一条边)，但n很大，建了也存不下，考虑一个点和图联通，它的最小花费一定是和最小权值的点连一条边，于是我们就缩减到了n-1条边，克鲁斯卡尔跑一遍最小生成树就OK了

代码

复制代码

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define mk make_pair
#define f first
#define s second
using namespace std;
typedef long long ll;
const int MAXN = 2e5+255;
struct node
{
int u,v;
ll w;
};
node e[MAXN<<1];
pair<int,ll> p[MAXN];
bool cmp(pair<int,ll> p1,pair<int,ll> p2)
{
return p1.s<p2.s;
}
bool cmp2(node e1,node e2)
{
return e1.w<e2.w;
}
int pre[MAXN];
void init(int n)
{
for(int i=0;i<=n;++i)
pre[i] = i;
}
int Find(int x)
//并查集
{
int t = x;
while(pre[t]!=t) t = pre[t];
while(x!=pre[x])
{
int tep = pre[x];
pre[x] = t;
x = tep;
}
return t;
}
bool Mix(int x,int y)
{
int Fx = Find(x);
int Fy = Find(y);
if(Fx!=Fy)
{
pre[Fy] = Fx;
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
ll v;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
cin>>v;
p[i-1] = mk(i,v);
}
int len = 0;
while(m--)
{
cin>>e[len].v>>e[len].u;
cin>>e[len++].w;
}
sort(p,p+n,cmp);
for(int i=1;i<n;++i)
//创建n-1条边
{
e[len].u = p[0].f;
e[len].v = p[i].f;
e[len++].w = p[0].s+p[i].s;
}
sort(e,e+len,cmp2);
init(n);
int num = n-1;ll ans = 0;
for(int i=0;i<len&#++i)
//Kruskal算法
{
if(Mix(e[i].v,e[i].u))
{
ans += e[i].w;
num--;
}
}
cout<<ans;
return 0;
}

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
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define mk make_pair
#define f first
#define s second
using namespace std;
typedef long long ll;
const int MAXN = 2e5+255;
struct node
{
int u,v;
ll w;
};
node e[MAXN<<1];
pair<int,ll> p[MAXN];
bool cmp(pair<int,ll> p1,pair<int,ll> p2)
{
return p1.s<p2.s;
}
bool cmp2(node e1,node e2)
{
return e1.w<e2.w;
}
int pre[MAXN];
void init(int n)
{
for(int i=0;i<=n;++i)
pre[i] = i;
}
int Find(int x)
//并查集
{
int t = x;
while(pre[t]!=t) t = pre[t];
while(x!=pre[x])
{
int tep = pre[x];
pre[x] = t;
x = tep;
}
return t;
}
bool Mix(int x,int y)
{
int Fx = Find(x);
int Fy = Find(y);
if(Fx!=Fy)
{
pre[Fy] = Fx;
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
ll v;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
cin>>v;
p[i-1] = mk(i,v);
}
int len = 0;
while(m--)
{
cin>>e[len].v>>e[len].u;
cin>>e[len++].w;
}
sort(p,p+n,cmp);
for(int i=1;i<n;++i)
//创建n-1条边
{
e[len].u = p[0].f;
e[len].v = p[i].f;
e[len++].w = p[0].s+p[i].s;
}
sort(e,e+len,cmp2);
init(n);
int num = n-1;ll ans = 0;
for(int i=0;i<len&&num;++i)
//Kruskal算法
{
if(Mix(e[i].v,e[i].u))
{
ans += e[i].w;
num--;
}
}
cout<<ans;
return 0;
}