小白月赛30题解或部分题解

小白月赛30链接

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

前言

简单的题我就直接写在这里了，稍微有难度的，我会通过链接的形式放在这篇博客里~

A 黑白边

解题思路

并查集
若不会并查集，有篇并查集基础讲解的博客
大致思路：
两个并查集，第一个并查集用于判断是否可以联通；第二个并查集用于计算最少白边数。
判断联通的并查集好写，直接板子就行；但是计算最少白边的并查集怎么写？
其实也是板子，只不过需要判断一下，当边为黑的时候进行“连边”，最后求出连通分支数-1就是最少白边数。
为什么这样就能求出最少白边数？
图片说明
懂了吧，把黑边连起来会出现若干连通分支，若整个图还能连通就说明必然存在白边使连通分支相连，所以最少的白边数就是连通分支数-1。

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;
}

B最好的宝石

题解链接

C 滑板上楼梯

解题思路

贪心，尽量一步3个+一步1个地跳，这样跳一步3个的次数是最多的，总的跳的步数是最少的；
最后看余数，=0说明正好跳完，答案为2 * 商；=1说明差一个，跳1个一步到终点，答案为2 * 商+1；=2说明差两步，跳2个一步到终点，答案为2 * 商+2；=3说明差3步，跳1个三步到终点，答案为2 * 商+1。

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

解题思路

欧拉筛
欧拉筛讲解
大致思路：
统计n个数的素数的个数，因为要求任意的k大小的集合存在gcd大于1的，那最“坏”的集合就是包含了所有素数的集合并且还包含了个1，这就是最大的不满足要求的集合，所以这个集合只要能再容下任意一个其他的数，必然能出现两个数gcd大于1。
问题就转化为了，统计素数个数，设为x，看是否存在比大小为x+1的集合更大的集合，若存在，说明大小为x+2的集合的大小即为答案，若不存在，输出-1。

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 石子合并

解题思路

每个石子都去和最大价值的石子合并，这样丢弃每个石子所获得的价值都是最大的，结果也是最优的。
如何实现每个石子都和最大价值的石子合并？
其实不用一步步模拟；首先我们要找到最大价值的石子吧，之后以最大价值的石子为中心向两侧扩展丢弃，这样每次丢弃的石子都能与最大价值的石子进行加权了，使得结果最优。
体现在代码上，输入的时候找到最大值，并统计所有石子的价值和；输出n-1个最大值（因为除了最大的石子外的全部石子都要和最大石子合并）+全部石子的价值-最大价值（因为除了最大的石子外的全部石子都要和最大石子合并）

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滑板比赛

解题思路

贪心；
贪心策略：用尽量小的去赢；
将两个数组排序后贪心即可。

说实话这题我没做出来，确实这题很简单，我把它想成了“田忌赛马”了，看了一眼大佬的题解，发现只需要简单贪心，根本用不到区间dp。我就开始思考，两道题如此类似，为什么这道只用简单贪心，而“田忌赛马”要用区间dp？
最终整理了一下，大致如下：
本题只考虑了赢与输，而“田忌赛马”除了要考虑赢和输，还要考虑平的情况，这导致“田忌赛马”比本题要难；
本题将平的情况也归于输一类，可以理解为，赢权值为1，输权值为0；“田忌赛马”中，赢权值为1，平权值为0，输权值为-1，这样应该明白区别了吧。
再来个例子，比如a：20 20，b：20 20，显然按照本题的贪心思想去解决“田忌赛马”问题，最终的结果为负值，其实应该为0。

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;
}

H 第 k 小

题解链接

I 区间异或

题解链接

J 小游戏

题解链接

个人总结

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了……
撒花，完结