发表更新Overall Editorials / AtCoder9 分钟读完 (大约1284个字)

AtCoder Beginner Contest 350 赛后总结

比赛链接

RT。这十分恶毒的Microsoft Defender在我使用美丽的Dev-c++和Code::Blocks时疯狂地弹弹窗让我扫描病毒威胁，又由于洛谷在线IDE的格式非常不自动化（指tab要自己tab）因此是我罚时+=5*5min，(╯▔皿▔)╯。

赛时没做出来的会全码写注释

题解

A. Past ABCs

依旧非常简单，不多说了放代码。

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
#include<bits/stdc++.h>

using namespace std;

string s; 

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	cin>>s;
	if(s[0]=='A'&&s[1]=='B'&&s[2]=='c')
	{
		int t=(s[3]-'0')*100+(s[4]-'0')*10+s[5]-'0';
		if(t>=1&&t<350&&t!=316)
		{
			cout<<"Yes\n";
			return 0;
		}
	}
	cout<<"No\n";

	return 0;
}

B. Dentist Aoki

这个题面真的好癫qwq

按题目模拟就行了没有什么思维含量，但是身为一名蒟蒻，还是交了一遍罚时，原因：没有本地运行代码导致for循环的起始写错了。其实可以用来熟悉bitset的使用（？），遂放一篇bitset的代码

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>

using namespace std;

int n,q;
bitset<1005> b;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>n>>q;
    for(int i=0;i<q;i++)
    {
        int t;
        cin>>t;
        b.flip(t);
    }
    cout<<n-b.count()<<"\n"; //如果在一开始将bitset初始化为全1，就输出b.count()
    
	return 0;
}

C. Sort

好了，就是这道令我罚时+=4的题力！（蠢蠢的很安心

四发都错在没有将swap了之后的id更改，谁能想到atcoder给的样例一个都查不出来（气

非常直白，存一下每个 $a_i$ 的索引，再遍历，如果 $a_i≠i$ 那么就把 $a_i$ 和 $a$ 中值为 $i$ 的元素交换，然后用vector存即可。

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
#include<bits/stdc++.h>

using namespace std;

int n;
int a[200005],id[200005];
vector<pair<int,int> > s;

int main()
{
	cin>>n ;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		id[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=i)
		{
			swap(a[i],a[id[i]]);
			s.push_back({i,id[i]});
			id[a[id[i]]]=id[i];
		}
	}
	cout<<s.size()<<"\n" ;
	for(int i=0;i<s.size();i++)
	{
		cout<<s[i].first<<" "<<s[i].second<<"\n";
	}
	
	return 0 ;
}

D. New Friends

某位zhy同学没有开龙龙导致WA掉，让我们恭喜他

就是让每一个连通图都变成完全图，所以使用 冰茶几 并查集维护，求出把所有图变成完全图之后的总边数，再减掉原有的变数即可。

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
#include<bits/stdc++.h>

using namespace std;

long long n,m;
long long par[200005],cnt[200005];
long long ans;

long long findf(long long x)
{
	return (par[x]==x)?x:par[x]=findf(par[x]);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(long long i=1;i<=n;i++)
	{
		par[i]=i;
	}
	for(long long i=0;i<m;i++)
	{
		long long a,b;
		cin>>a>>b;
		par[findf(a)]=findf(b);
	}
	for(long long i=1;i<=n;i++)
	{
		cnt[findf(i)]++;
	}
	
	for(long long i=1;i<=n;i++)
	{
		ans+=(cnt[i]-1)*cnt[i]/2;
	}

	cout<<ans-m<<"\n";
	
	return 0;
}

E. Toward 0

学校刚教完概率与期望，我却不会做，是__导致我这样的

看到1e18的数据范围直接被MLE劝退，愣是没有想到其实可以用map，是__导致我这样的！

骰子只有1-6的点数，所以每次到的值都是可以写作 $⌊\frac{𝑛}{2^𝑖3^𝑗5^𝑘}⌋$ （因为 $⌊\frac{⌊\frac{n}{x}⌋}{y}⌋=⌊\frac{⌊\frac{n}{y}⌋}{x}⌋=⌊\frac{n}{xy}⌋$ ）

所以我们就可以聪明地使用map数组dp，得到以下递推公式：

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
#include<bits/stdc++.h>

using namespace std;

long long n,a,x,y;
map<long long,double> dp;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>n>>a>>x>>y;
	dp[0]=0;
	for(long long i=1;i<=n;i*=2)
	{
		for(long long j=1;i*j<=n;j*=3)
		{
			for(long long k=1;i*j*k<=n;k*=5)
			{
				dp[n/(i*j*k)]=0; //先新建可能取到的dp索引对应的dp数组的位置（因为使用map）
			}
		}
	}
	
	for(map<long long,double>::iterator i=dp.begin();i!=dp.end();i++)
	{
		if(!i->first)
		{
			continue;
		}
		double p=x+dp[i->first/a],q=6.0*y; //p是选择/a的期望，q是选择抛骰子的期望
		for(int j=2;j<=6;j++)
		{
			q+=dp[i->first/j];
		}
		q/=5;
		i->second=min(p,q); //递推，最小代价
	}

	cout<<fixed<<setprecision(6)<<dp[n]<<"\n";

	return 0;
}

F. Transpose

非常经典的栈，试问Atcoder，为何E>F。

其实感觉难度不是很大，不知道为什么是绿并F题，但话说我一直都很讨厌这种 (((()))(()) 的题QAQ

同样也是直接模拟，但是首先利用栈来记录这个字符串所有括号的位置和字母是否最终被反转

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
#include<bits/stdc++.h>

using namespace std;

string s;
int p[500005]; //用于配对左括弧和右括弧的位置
stack<int> st; //用于存储左括弧

void output(int x,int y)
{
	if(x<=y)
	{
		for(int i=x;i<=y;i++)
		{
			if(s[i]=='(')
			{
				if(p[i]!=i+1) //如果括号组内不为空
				{
					output(p[i]-1,i+1); //整体翻转输出
				}
				i=p[i]; //跳到下一组
			}
			else
			{
				cout<<s[i];
			}
		}
	}
	else
	{
		for(int i=x;i>=y;i--)
		{
			if(s[i]==')')
			{
				if(p[i]!=i-1)
				{
					output(p[i]+1,i-1); //整体翻转输出
				}
				i=p[i]; //跳到下一组
			}
			else
			{
				cout<<s[i];
			}
		}
	}
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>s;
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='(')
		{
			st.push(i);
		}
		else if(s[i]==')')
		{
			p[st.top()]=i;
			p[i]=st.top();
			st.pop();
		}
		else
		{
            //如果这个字符在奇数个括号组里，就说明它会被大小写反转,偶数则会被反转回来
			if(st.size()&1)
			{
				if(s[i]>='a'&&s[i]<='z')
				{
					s[i]-='a'-'A';
				}
				else
				{
					s[i]-='A'-'a';
				}
			}
		}
	}
	output(0,s.size()-1);
	cout<<"\n";
	
	return 0;
}

G. Mediator

一道被建议评橙的G题（现在是蓝），Atcoder怎么总能水暴力（？

于是投喂一篇暴力（它甚至不需要吸氧就能过我真的

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
// Let us water a brute force ! 
#include<bits/stdc++.h>

using namespace std;

const long long mod=998244353;

long long n,q;
vector<long long> e[200005];
bool t[200005];

void geti(long long &op,long long &u,long long &v,long long xl) //如题
{
	op=1+(((op*(1+xl))%mod)%2);
	u=1+(((u*(1+xl))%mod)%n);
	v=1+(((v*(1+xl))%mod)%n);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>n>>q;
	long long xl=0;
	
	while(q--)
	{
		memset(t,0,sizeof t);
		
		long long op,u,v;
		cin>>op>>u>>v;
		
		geti(op,u,v,xl);
		
		if(op==1)
		{
			e[v].push_back(u);
			e[u].push_back(v); //存边
			continue;
		}
		
		for(long long i:e[u]) //遍历与u相邻的点
		{
			t[i]=1;
		}
		
		bool flag=0;
		for(long long i:e[v])
		{
			if(t[i]) //判断是否与v相邻
			{
				cout<<i<<"\n";
				xl=i;
				flag=1;
				break;
			}
		}
		if(!flag) //否则输出0
		{
			cout<<0<<"\n";
			xl=0;
		}
	}

	return 0;
}

好吧下面是正解

使用启发式合并。如果两个点有一个共同的邻点，那么有三种可能：

  1. u是v的祖父
  2. v是u的祖父
  3. u和v是兄弟

所以依然使用带权并查集进行维护。

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
#include<bits/stdc++.h>

using namespace std;

const long long mod=998244353;

long long n,q;
vector<long long> e[200005];
int f[200005],par[200005],siz[200005];
//分别为点i的父亲，点i的根，点i的深度

void geti(long long &op,long long &u,long long &v,long long xl)
{
	op=1+(((op*(1+xl))%mod)%2);
	u=1+(((u*(1+xl))%mod)%n);
	v=1+(((v*(1+xl))%mod)%n);
}

void dfs(int x) //遍历并确定每个点的父亲节点
{
    for(auto i:e[x])
    {
        if(i==f[x])
        {
            continue;
		}
        f[i]=x;
        dfs(i);
    }
}

int query(int x,int y)
{
    if(f[x]==f[y]&&f[x]) //如果两点为兄弟节点
    {
        return f[x];
	}
    if(f[f[x]]==y) //x的祖父为y
    {
        return f[x];
	}
    if(f[f[y]]==x) //y的祖父为x
    {
        return f[y];
	}
    return 0;
}

int find(int x) //找根
{
    return x==par[x]?x:par[x]=find(par[x]);
}

void merge(int x,int y) //合并
{
    int fx=find(x),fy=find(y);
    if(fx==fy)
    {
        return;
	}
    par[fy]=fx;
    siz[fx]+=siz[fy];
    siz[fy]=0;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>n>>q;
	for(int i=1;i<=n;i++) //初始化
	{
		par[i]=i;
		siz[i]=1;
	}
	
	long long xl=0;
	
	while(q--)
	{		
		long long op,u,v;
		cin>>op>>u>>v;
		
		geti(op,u,v,xl);
		
		if(op==1)
		{
			if(siz[find(u)]<siz[find(v)])
			{
				swap(u,v);
			}
			e[v].push_back(u);
			e[u].push_back(v);
			f[v]=u;
			merge(u,v);
			dfs(v);
			continue;
		}
		
		xl=query(u,v);
		cout<<xl<<"\n";
	}

	return 0;
}

wow写完啦！！！！！

感谢观看呀

AtCoder Beginner Contest 350 赛后总结

https://imoliviauu.github.io/2024/04/21/atcoder-beginner-contest-350/

作者

Olivia_uu

发布于

2024-04-21

更新于

2024-05-12

许可协议

You need to set install_url to use ShareThis. Please set it in _config.yml.

评论

关注我

目录

链接

分类

最新文章

归档

标签

Combinatorics1
Disjoint Set1
Dynamic Programming3
Euler's totient function1
Game Theory1
Graph Theory2
Monotonic queue1
Number theory1
Ordinary Generating Function1
Segment Tree4
Simulated Annealing1
Society1
Spanning Tree2
Teenagers1
Tree1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×