牛客小白月赛17小结

素颜马尾好姑娘i 2024-04-19 08:20 0阅读 0赞

# 牛客小白月赛17小结 #

哭了，本想着都大二了，像小白月赛应该会疯狂A题吧，但是由于前面十几分钟一直卡A，导致放弃A了时候，刚把B过，别人就AK了。。。，虽然中途有点事，但是也不至于只A了两题把，似乎题目都没看完。。  
不禁让我怀疑起，选择ACM到底是不是正确的选择。。。。

[A题：小sum的假期][A_sum]

**题解**：在这只能内心抱怨抱怨出题人，这个数据简单让我很无语，明明能A的代码wa，连样例都过不了的代码居然A了。。。。

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    using namespace std;
    struct node
    {
        
        int l,r;
    }a[100010];
    int cmp(node x,node y)
    {
        
        if(x.l!=y.l)
            return x.l<y.l;
        else
            return x.r<y.r;
    }
    int main()
    {
        
        int n,m;
        int ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
        
            scanf("%d%d",&a[i].l,&a[i].r);
        }
        sort(a+1,a+m+1,cmp);
        ans=max(ans,a[1].l-1);
        int cnt=0;
        for(int i=2;i<=m;i++)
        {
        
            if(a[i].l>a[i-1].r&&a[i].l>cnt)
                ans=max(ans,a[i].l-a[i-1].r);
            cnt=max(cnt,a[i].r);
        }
        ans=max(ans,n-cnt);
        printf("%d\n",ans);
        return 0;
    }

[B：扫雷][B]

**题解** ：无脑送分题,直接按照规则遍历，速度还是慢了，敲了十多分钟

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int n,m;
    char mp[1010][1010];
    int main()
    {
        
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
        
            scanf("%s",mp[i]+1);
        }
        for(int i=1; i<=n; i++)
        {
        
            for(int j=1; j<=m; j++)
            {
        
                int cnt=0;
                if(mp[i][j]=='.')
                {
        
                    if(i==1)
                    {
        
                        if(j==1)
                        {
        
                            if(mp[i][j+1]=='*')
                                cnt++;
                            if(mp[i+1][j]=='*')
                                cnt++;
                            if(mp[i+1][j+1]=='*')
                                cnt++;
                            mp[i][j]=cnt+'0';
                        }
                        else if(j==m)
                        {
        
                            if(mp[i][j-1]=='*')
                                cnt++;
                            if(mp[i+1][j]=='*')
                                cnt++;
                            if(mp[i+1][j-1]=='*')
                                cnt++;
                            mp[i][j]=cnt+'0';
                        }
                        else
                        {
        
                            if(mp[i][j-1]=='*')
                                cnt++;
                            if(mp[i][j+1]=='*')
                                cnt++;
                            if(mp[i+1][j-1]=='*')
                                cnt++;
                            if(mp[i+1][j]=='*')
                                cnt++;
                            if(mp[i+1][j+1]=='*')
                                cnt++;
                            mp[i][j]=cnt+'0';
                        }
    
                    }
                    else if(i==n)
                    {
        
                        if(j==1)
                        {
        
                            if(mp[i-1][j]=='*')
                                cnt++;
                            if(mp[i][j+1]=='*')
                                cnt++;
                            if(mp[i-1][j+1]=='*')
                                cnt++;
                            mp[i][j]=cnt+'0';
                        }
                        else if(j==m)
                        {
        
                            if(mp[i][j-1]=='*')
                                cnt++;
                            if(mp[i-1][j]=='*')
                                cnt++;
                            if(mp[i-1][j-1]=='*')
                                cnt++;
                            mp[i][j]=cnt+'0';
                        }
                        else
                        {
        
                            if(mp[i][j-1]=='*')
                                cnt++;
                            if(mp[i][j+1]=='*')
                                cnt++;
                            if(mp[i-1][j]=='*')
                                cnt++;
                            if(mp[i-1][j-1]=='*')
                                cnt++;
                            if(mp[i-1][j+1]=='*')
                                cnt++;
                            mp[i][j]=cnt+'0';
                        }
                    }
                    else
                    {
        
                        if(j==1)
                        {
        
                            if(mp[i-1][j]=='*')
                                cnt++;
                            if(mp[i+1][j]=='*')
                                cnt++;
                            if(mp[i-1][j+1]=='*')
                                cnt++;
                            if(mp[i][j+1]=='*')
                                cnt++;
                            if(mp[i+1][j+1]=='*')
                                cnt++;
                            mp[i][j]=cnt+'0';
                        }
                        else if(j==m)
                        {
        
                            if(mp[i-1][j]=='*')
                                cnt++;
                            if(mp[i+1][j]=='*')
                                cnt++;
                            if(mp[i][j-1]=='*')
                                cnt++;
                            if(mp[i-1][j-1]=='*')
                                cnt++;
                            if(mp[i+1][j-1]=='*')
                                cnt++;
                            mp[i][j]=cnt+'0';
                        }
                        else
                        {
        
                            if(mp[i-1][j]=='*')
                                cnt++;
                            if(mp[i+1][j]=='*')
                                cnt++;
                            if(mp[i-1][j-1]=='*')
                                cnt++;
                            if(mp[i-1][j+1]=='*')
                                cnt++;
                            if(mp[i][j+1]=='*')
                                cnt++;
                            if(mp[i][j-1]=='*')
                                cnt++;
                            if(mp[i+1][j+1]=='*')
                                cnt++;
                            if(mp[i+1][j-1]=='*')
                                cnt++;
                            mp[i][j]=cnt+'0';
                        }
                    }
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
        
            printf("%s\n",mp[i]+1);
        }
        return 0;
    }

[C：异或和][C]

**题解**：麻了，这么简单的题，居然完全没想到那去，关键对于异或不熟（究其根本，还是做少了题，不然感觉最多三分钟就能拿下这题）  
虽然题目说只要出现奇数的情况，但是出现偶数的话，由于异或直接就为0了

于是：

#include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int main()
    {
        
        int n;
        int sum,num;
        scanf("%d",&n);
        n--;
        scanf("%d",&sum);
        while(n--)
        {
        
            scanf("%d",&num);
            sum^=num;           //偶数的话，异或直接为0了，所以无需特判
        }
        printf("%d\n",sum);
        return 0;
    }

[D：解密][D]

模线性方程，哎，其实感觉核心还是拓展欧几里得算法，关键数学这做的题太少了，导致不知道怎么下手。

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int a,b=26,c,x,y;
    char s[1010];           //s表示明文和密文
    int num;          //起中间桥梁作用
    int extgcd(int a,int b,int &x,int &y)
    {
        
        if(b==0)
        {
        
            x=1;
            y=0;
            return a;
        }
        int r=extgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-(a/b)*y;
        return r;
    }
    int main()
    {
        
        scanf("%d%d%s",&a,&c,s);          //其中a表示k1，c表示k2
        extgcd(a,b,x,y);
        x=(x%26+26)%26;
        c=(26-c%26)%26;
        int len=strlen(s);
        for(int i=0;i<len;i++)
        {
        
            if(s[i]>='a')
                num=s[i]-'a';
            else
                num=s[i]-'A';
            num=(num+c)*x%26;
            if(s[i]>='a')
                s[i]=num+'a';
            else
                s[i]=num+'A';
        }
        printf("%s\n",s);
        return 0;
    }

[E：图的遍历][E]

官方题解看的一脸懵逼

考察这个遍历的性质，发现如果图存在奇环，那么跟当前奇环联通的所有点全部可以遍历到。  
首先讨论图有多少个联通块，在这些联通块中，若存在一个包含奇环的联通块，那么将当前的联通块与所有的不包含奇环的联通块相连就行了，答案个数为不包含奇环的联通块个数。  
若所有的联通块都不包含奇环，那么可以用若干条边在k个（k为奇数）联通块之间构造一条奇环，然后再把其他的联通块跟当前的奇环相连，答案为联通块的个数。

[F：小黄鸭][F]

官方题解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]  
这有点。。。。。  
感觉就是虐我啊，虽然想到是数学题，但是的确没想到建系积分

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    using namespace std;
    const double eps=1e-6;               //允许的精度范围
    const double pi=acos(-1.0);           //圆周率
    int  main()
    {
        
        double m,R;
        scanf("%lf%lf",&R,&m);
        double l=0,r=R+R;
        while(fabs(r-l)>eps)
        {
        
            double mid=(l+r)/2.0;
            double v=pi*(mid*mid*R-mid*mid*mid/3.0);
            if(v>m)
                r=mid;
            else
                l=mid;
        }
        double h=R+R-(l+r)/2.0;
        printf("%.2f\n",h);
        return 0;
    }

[G：区间求和][G]

看到官方题解中的**莫队**就让我慌了。。。。

先放到这，以后补。。。。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 1]  
迟来很久的补题（最近太懒了，周末一定要好好补补题，但愿flag别真香。。。）  
仔细学了学莫队，其实可以说为优化的暴力

主要分为分块和排序，然后板子觉得太挺短的，但是看博客大牛写有些地方很玄学，但是目前还没遇到吧

代码参考了别人的才敲出来。。。

/**莫队优化的核心是分块和排序*/
    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #define ll long long
    using namespace std;
    const int maxn=1e5+10;
    const int block=1300;            //分的块的大小
    struct node
    {
        
        int l,r,id;
    }q[maxn];
    int a[maxn];              //每个位置对应的值
    ll num[maxn],ans[maxn];
    ll res=0;
    int cmp(node x,node y)
    {
        
        if(x.l/block==y.l/block)
            return x.r<y.r;
        else
            return x.l/block<y.l/block;
    }
    /**添加一个数*/
    void add(int pos)
    {
        
        res-=num[a[pos]]*num[a[pos]]*a[pos];
        num[a[pos]]++;
        res+=num[a[pos]]*num[a[pos]]*a[pos];
    }
    /**删除一个数*/
    void del(int pos)
    {
        
        res-=num[a[pos]]*num[a[pos]]*a[pos];
        num[a[pos]]--;
        res+=num[a[pos]]*num[a[pos]]*a[pos];
    }
    int main()
    {
        
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<m;i++)
        {
        
            scanf("%d%d",&q[i].l,&q[i].r);
            q[i].id=i;
        }
        sort(q,q+m,cmp);
        int nowl=0,nowr=0;             //左右指针
        for(int i=0;i<m;i++)
        {
        
            while(nowr<q[i].r)
            {
        
                add(nowr+1);
                nowr++;
            }
            while(nowl>q[i].l)
            {
        
                add(nowl-1);
                nowl--;
            }
            while(nowr>q[i].r)
            {
        
                del(nowr);
                nowr--;
            }
            while(nowl<q[i].l)
            {
        
                del(nowl);
                nowl++;
            }
            ans[q[i].id]=res;
        }
        for(int i=0;i<m;i++)
            printf("%lld\n",ans[i]);
        return 0;
    }

[H：取球游戏][H]

感觉自己想不到。。。。。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 2]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define ll long long
    using namespace std;
    double dp[100010][110];
    int main()
    {
        
        ll c,n,m;
        scanf("%lld%lld%lld",&c,&n,&m);
        if(n>1e5)
            n=1e5+(n&1);
        dp[0][0]=1.0;
        for(int i=1;i<=n;i++)
        {
        
            for(int j=0;j<=c;j++)
            {
        
                if(j)
                    dp[i][j]+=dp[i-1][j-1]*(c-j+1)/(c*1.0);
                dp[i][j]+=dp[i-1][j+1]*(j+1)/(c*1.0);
            }
        }
        printf("%.3f\n",dp[n][m]);
        return 0;
    }

[J：计数][J]

现在补题都觉得小白赛似乎不是我想象的小白赛

[A_sum]: https://ac.nowcoder.com/acm/contest/1085/A
[B]: https://ac.nowcoder.com/acm/contest/1085/B
[C]: https://ac.nowcoder.com/acm/contest/1085/C
[D]: https://ac.nowcoder.com/acm/contest/1085/D
[E]: https://ac.nowcoder.com/acm/contest/1085/E
[F]: https://ac.nowcoder.com/acm/contest/1085/F
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ed2db741e8884826a329d6c897350c52.png
[G]: https://ac.nowcoder.com/acm/contest/1085/G
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c39d3e063d7848bb89e6b2bb4051b771.png
[H]: https://ac.nowcoder.com/acm/contest/1085/H
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/a60167e999644731918ee27867a1d068.png
[J]: https://ac.nowcoder.com/acm/contest/1085/J