牛客编程巅峰赛S1第3场 - 青铜&白银（题解&总结）

左手的ㄟ右手 2023-02-27 10:35 13阅读 0赞

#  牛客编程巅峰赛S1第3场 - 青铜&白银（题解&总结） #

## [A：位数求和][A] ##

#### 题意 ####

给定n、m两个整数，求位数为n的数每位数相加的和等于m的数的个数  
看数据范围n<=6，即最多也就是100000-999999，于是直接暴力枚举即可。数据比较大的话则考虑用dp（雨巨直播有讲到，但是没怎么听明白…）

#### AC代码（cpp）： ####

class Solution {
        
    public:
        /**
         * 返回这样的数之和
         * @param n int整型 数的长度
         * @param m int整型 各个为之和
         * @return long长整型
         */
        long long sum(int n, int m) {
        
            // write code here
            int num=1;
            long long ans=0;
            for(int i=1;i<=n;i++){
        
                num=num*10;
            }
            for(int i=num/10;i<num;i++){
        
                int x=i,sumx=0;
                while(x){
        
                    sumx+=x%10;
                    x/=10;
                }
                if(sumx==m){
        
                    ans+=i;
                }
            }
            return ans;
        }
    };

## [B：不可思议][B] ##

#### 题意： ####

被题目给吓到了，给的随机种子生成的数据，导致看了好久都没看懂题目，再加上又把题目看错了，浪费了将近比赛的一半的时间…

其实直接按照题目的意思来写代码即可，没什么多说的，进行了一点小处理在于题目的u\[i\],v\[i\]表示一条边的两个顶点，这样构成了两个顶点集合。这里直接优化成了一个集合，即par\[i\]：表示i的父节点为par\[i\]，这样也构成了一条边。

#### AC代码（cpp）： ####

class Solution {
        
    public:
        int par[100010];
        //这里是找x到根的所有结点，居然开始看错题目了....
        long long ans(int x,int y){
        
            long long ans=0;
            while(x!=0){
        
                ans+=(y+2*x)^(y+x);
                x=par[x];
            }
            return ans;
        }
        /**
         * 
         * @param n int整型 
         * @param seed1 long长整型 
         * @param seed2 long长整型 
         * @param seed3 long长整型 
         * @param x int整型 
         * @return long长整型
         */
        long long work(int n, long long seed1, long long seed2, long long seed3, int x) {
        
            // write code here
            long long seed4;
            for(int i=1;i<n;i++){
        
                seed4=(seed1+seed2)%998244353*seed3%998244353;
                par[i+1]=(seed4%i)+1;
                seed3=seed2;seed2=seed1;seed1=seed4;
            }
            long long lastans=0,ret=0,y=0;
            for(int i=1;i<=n;i++){
        
                long long z=ans(x,y);
                ret=(ret+z)%998244353;
                lastans=z;
                x=((x+lastans)^ret)%n+1;
                y=lastans;
            }
            //printf("%lld %lld %lld %lld\n",ret,lastans,x,y);
            return ret;
        }
    };

## [C：牛牛晾衣服][C] ##

#### 题意 ####

n件带水的衣服，需要全都晾干，现在有两种方式可供选择：  
1.烘干机（一次只能烘一件衣服）：一秒可以烘干k滴水  
2.自然晾干（所有衣服）：一秒烘干1滴水  
问最少需要多少时间，可以使所有衣服都晾干

#### 题解 ####

首先，第一眼是不是容易想到贪心，但是得每次排个序，然后选最大的烘干，但是烘干时间又不好确定，如果只一秒的话，那时间复杂度得爆炸了，于是pass

接下来，优先队列。比赛的时候我就是用的c++ STL的大根堆（也就是从大到小的优先队列），但是wa了，由于这次出题人数据比较水，所有很多用大根堆的都过了，如果改成1e9,1e9-1…这样的数组的话，很明显是过不了的，于是再次pass。

最后，再怎么样也得想到二分了吧（然而比赛中并没有想到，自闭了…）。直接二分答案，最少的时间肯定是在衣服水分最少的和最多的中间，很明显结果肯定是一个单调的序列。  
如果mid所在时间不能完全晾干，则在右区间找，即：l=mid+1；  
否则在左区间找，r=mid-1；

#### AC代码（cpp）： ####

class Solution {
        
    public:
        int check(int n,int k,vector<int>& a,int mid){
        
            int sum=0;
            for(int i=0;i<n;i++){
        
                if(a[i]>mid){
        
                    if((a[i]-mid)%(k-1)==0){
        
                        sum+=(a[i]-mid)/(k-1);
                    }else{
        
                        sum+=(a[i]-mid)/(k-1)+1;
                    }
                }
            }
            if(sum>mid) return 0;
            return 1;
        }
        /**
         * 计算最少要多少时间可以把所有的衣服全烘干
         * @param n int整型 n件衣服
         * @param a int整型vector n件衣服所含水量数组
         * @param k int整型 烘干机1分钟可以烘干的水量
         * @return int整型
         */
        int solve(int n, vector<int>& a, int k) {
        
            int l=1,r=a[0];
            for(int i=1;i<n;i++){
        
                r=max(r,a[i]);
            }
            //二分答案
            while(l<=r){
        
                int mid=(l+r)/2;
                if(check(n,k,a,mid)){
        
                    r=mid-1;
                }else{
        
                    l=mid+1;
                }
            }
            return r+1;  //return r+1是因为需要保证所有衣服都烘干，即超过零点
        }
    };

后序：居然没想到这都上黄金了

[A]: https://ac.nowcoder.com/acm/contest/6220/A
[B]: https://ac.nowcoder.com/acm/contest/6220/B
[C]: https://ac.nowcoder.com/acm/contest/6220/C