AtCoder Beginner Contest 350

A

注意特判x!=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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+5;
int a[N];
int b[N];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
string s;
cin>>s;
if(s[0]=='A'&&s[1]=='B'&&s[2]=='C')
{
int x=(s[3]-'0')*100+(s[4]-'0')*10+(s[5]-'0')*1;
if(x<350&&x!=316&&x!=0)
{
    cout<<"Yes";
    return  0;
}
}
cout<<"No";
}


B

B题直接用一个map记录一下，然后如果是奇数那么就意味着这颗牙没了，就--

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+5;
int a[N];
int b[N];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
int n,m,q;
cin>>n>>m;
map<int,int>mp;
for(int i=1;i<=m;i++)
{
    int x;
    cin>>x;
    mp[x]++;
}
int ans=n;
for(auto &[x,y]:mp)
if(y&1)
{
    n--;
}
cout<<n;

}


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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+5;
int a[N];
int b[N];
vector<pair<int,int> >q;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    b[a[i]]=i;
}
int ans=0;

for(int i=1;i<=n;i++){
if(a[i]==i)
{
    continue;
}
else
{
    ans++;
    int c=a[i];
    q.push_back({i,b[i]});
    swap(a[i],a[b[i]]);
    swap(b[c],b[i]);}
}
cout<<ans<<'\n';
for(auto y:q)
{
cout<<y.first<<' '<<y.second<<'\n';
}

}

D

本题来自Huangyu的警示:fa数组存的不是根节点啊喂，find才是，仔细一想，是这样（）。

但赛时还是用一个while水过去了，51ms跑的飞快。

本题思路就是找到并查集的所有连通块，记录每个连通块的数量，然后等差数列求和加起来

赛时版本：

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<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+5;
int f[N];
map<ll,ll>mp;
int find(int x)
{ 
    //查询 x 的帮主
	if(x == f[x]) return x; //如果找的帮主就是自己，那么自己就是帮主
	return f[x] = find(f[x]);//带路径压缩的
}
void join(int c1,int c2){ //将一个亲戚关系加入到集合中
	if(find(c1) != find(c2))  //如果关系不为同一个，那就更改关系
		f[find(c2)] = find(c1);	
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
//计算每个并查集有多少个连通块
//然后直接计算现在的好友个数
//并查集应该形成的好友个数
//直接减去即可
ll n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
    f[i]=i;
}
int cnt=0;
for(int i=1;i<=m;i++)
{
int x,y,tx,ty;
cin>>x>>y;
join(x,y);
}
for(int i=1;i<=n;i++)
{
while(find(f[i])!=f[i])
{
   f[i]=find(f[i]); 
}    
mp[f[i]]++;
}
ll sum=0;
for(auto &[x,y]:mp)
{   
sum+=(y)*(y-1)/2;
}
cout<<sum-m;
}


深入理解了并查集的Find和fa后的代码：

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<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+5;
int f[N];
map<ll,ll>mp;
int find(int x)
{ 
    //查询 x 的帮主
	if(x == f[x]) return x; //如果找的帮主就是自己，那么自己就是帮主
	return f[x] = find(f[x]);//带路径压缩的
}
void join(int c1,int c2){ //将一个亲戚关系加入到集合中
	if(find(c1) != find(c2))  //如果关系不为同一个，那就更改关系
		f[find(c2)] = find(c1);	
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
//计算每个并查集有多少个连通块
//然后直接计算现在的好友个数
//并查集应该形成的好友个数
//直接减去即可
ll n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
    f[i]=i;
}
int cnt=0;
for(int i=1;i<=m;i++)
{
int x,y,tx,ty;
cin>>x>>y;
join(x,y);
}
for(int i=1;i<=n;i++)
{  
mp[find(i)]++;
}
ll sum=0;
for(auto &[x,y]:mp)
{   
sum+=(y)*(y-1)/2;
}
cout<<sum-m;
}


警示后人......

E

非常经典的期望dp典题，由于数据范围不好直接dp，考虑直接结合进行结合map进行记忆化搜索。

注意一个地方，其是一开始是有solve(n/1)这种情况的

也就是

\(solve(n)=(solve(n/1)+(solve(n / 2) + solve(n / 3) + solve(n / 4) + solve(n / 5) + solve(n / 6)) + y * 6))*\frac{1}{6}\)再移项之后会变成下面这个式子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+5;
ll n,a,x,y;
map<ll,long double>mp;
long double solve(ll n)
{
    if (n == 0)
        return 0;
    if (mp.count(n))
        return mp[n];
    return mp[n] = min(((solve(n / 2) + solve(n / 3) + solve(n / 4) + solve(n / 5) + solve(n / 6)) + y * 6) / 5, solve(n / a) + x);
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
    cin >> n >> a >> x >> y;
    cout << setprecision(10) << fixed << solve(n) << endl;

}


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
#include<bits/stdc++.h>
using namespace std;
string s;
int match[500005],cnt;
stack<int> st;
void zhuan(int id)
//直接翻转字符串
{
	if('a'<=s[id]&&s[id]<='z') s[id]-=32;
	else s[id]+=32;
}
void f(int l,int r,int state)
{
	if(state==0)
		while(l<=r)
			if(s[l]=='(') f(l+1,match[l]-1,1),l=match[l]+1;
			else cout<<s[l++];
	else
		while(l<=r)
			if(s[r]==')') f(match[r]+1,r-1,0),r=match[r]-1;
			else cout<<s[r--];
}
signed main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
		if(s[i]=='(') cnt++,st.push(i);
		else if(s[i]==')')
		{
			int w=st.top();st.pop();
			match[i]=w,match[w]=i;
			cnt--;
		}
		else if(cnt%2) zhuan(i);
	f(0,s.size()-1,0);
	return 0;
}