比赛链接
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";
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;
}
}
}
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;
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题（现在是蓝），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
|
#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])
{
t[i]=1;
}
bool flag=0;
for(long long i:e[v])
{
if(t[i])
{
cout<<i<<"\n";
xl=i;
flag=1;
break;
}
}
if(!flag)
{
cout<<0<<"\n";
xl=0;
}
}
return 0;
}
|
好吧下面是正解
使用启发式合并。如果两个点有一个共同的邻点，那么有三种可能：
- u是v的祖父
- v是u的祖父
- 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];
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)
{
return f[x];
}
if(f[f[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写完啦！！！！！
感谢观看呀
