# 小白月赛30链接

https://ac.nowcoder.com/acm/contest/9667

# A 黑白边

## AC代码

```#include<bits/stdc++.h>
#define ll long long

const int N=2e5+10;
int fa1[N],fa[N],n,m,u,v,w,cnt1,cnt;

int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}

int find1(int x)
{
return fa1[x]==x?x:fa1[x]=find1(fa1[x]);
}

void join(int x,int y)
{
int rx=find(x),ry=find(y);
if(rx!=ry) fa[rx]=ry;
}

void join1(int x,int y)
{
int rx=find1(x),ry=find1(y);
if(rx!=ry) fa1[rx]=ry;
}

using namespace std;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i,fa1[i]=i;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
join(u,v);
if(!w) join1(u,v);
}
for(int i=1;i<=n;i++)
{
if(fa[i]==i) cnt++;
if(fa1[i]==i) cnt1++;
}
if(cnt>1) cout<<-1<<endl;
else cout<<cnt1-1<<endl;
}```

# C 滑板上楼梯

## AC代码

```#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n;
int main()
{
cin>>n;
int mod=n%4;
ll div=n/4;//注意开ll
if(mod==3 || mod==1) cout<<2*div+1<<endl;//注意不能改为2*n/4+1，这样先算的是2*n，会影响结果
else if(mod==2) cout<<2*div+2<<endl;
else cout<<2*div<<endl;
}```

# D GCD

## AC代码

```#include<bits/stdc++.h>
#define ll long long
const int N=1e5+10;
int n,x,prime[N];
bool vis[N];

using namespace std;
int main()
{
cin>>n;
for(int i=2;i<=n;i++)
{
if(!vis[i]) prime[++x]=i;
for(int j=1;j<=x;j++)
{
if(prime[j]*i>n) break;
vis[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}

if(x+1==n) cout<<-1<<endl;
else cout<<x+2<<endl;
}
```

# E 牛牛的加法

## AC代码

```#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
string s1,s2;
int ans[N],ts1[N],ts2[N];
int main()
{
cin>>s1>>s2;

int n=s1.size(),m=s2.size();
s1='.'+s1;s2='.'+s2;
for(int i=1;i<=n;i++) ts1[n-i+1]=s1[i]-'0';
for(int i=1;i<=m;i++) ts2[m-i+1]=s2[i]-'0';
int len=max(n,m);
for(int i=1;i<=len;i++) ans[i]=(ts1[i]+ts2[i])%10;
while(len>1 && ans[len]==0) len--;
for(int i=1;i<=len;i++) cout<<ans[len-i+1];
}```

# F 石子合并

## AC代码

```#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
ll n,mx,a[N],sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],mx=max(a[i],mx),sum+=a[i];
cout<<(n-1)*mx+sum-mx<<endl;
}```

# G滑板比赛

## AC代码

```#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,a[N],b[N];

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+m+1);

int now=1;
for(int i=1;i<=n;i++)
{
if(a[i]>b[now])
{
now++;
if(now>m) break;
}
}

cout<<now-1<<endl;
return 0;
}
```

# 个人总结

A题，最开始想不到用什么算法，居然觉得像最小生成树，好歹没一直犯傻，过了十分钟想出了并查集；之后我居然卡在bug上了，de了20min没找出来就又写了一遍“一模一样”的，过了，我就怀疑人生了，明明“一样”，第一个样例都错了，第二个直接AC了？之后，又对比俩代码，过了20min，发现find1函数中的return中的find1写成了find，我裂开……
B题，比较明显的线段树，de了有一会的bug，甚至怀疑不是线段树了，扫了一眼大佬题解标题，确实是线段树，才安下心开始debug，最后A了。
C题，wa了两发，第一发2 * n/4连写了，wa掉；第二发，div存下了n/4，但是忘开ll了，wa掉……
E题，wa了一发吧，忘了处理前导零了，之后又有bug，de了20min发现是有的n写成了m，或者len写成了n之类的XX错误……
F题，wa了一发，又傻了……居然还贪心起来了，贪错了……看到题目以为是区间dp板子来着，发现不是啊。
G题，哎，没想到是简单贪心，因为记得雨巨讲过田忌赛马，所以就认定了这题是“田忌赛马”了，好像是区间dp，就先去学了好久的“田忌赛马”。看了大佬代码才知道只是个简单贪心……
H题，不会，一直用的mutilset，发现迭代器真的难用，有时候根本不知道指向哪里，debugde了好久好久都不想放弃，因为感觉思路没什么问题。最后还是放弃了，也不知道哪里错的，最多能过80数据。
I题，被“异或和”这个词搞懵了，直接“异或”不好吗，来个“和”，我以为要全部区间还要求和，样例也不来点notes……只想出来了技巧一，之后没敢写，估计写也想不到……
J题，开始还以为选奇数或偶数权值最大的就行嘞，结果发现是错的，比如1，4，可以两个都选，并不是只能选奇数或者偶数。真的是傻……。直到看了一眼大佬题解，大标题：dp……无意扫到是通过第二维控制选还是不选，之后想了一会A了……