牛客编程巅峰赛S1第10场 - 黄金&钻石（总结）

布满荆棘的人生 2022-11-25 11:57 123阅读 0赞

## 比赛总结 ##

这场感觉是最简单的，但是居然都做的这么慢。  
看完A，直接开干，样例一过，造了几个数据，立马交，结果超时…  
静下心来仔细看题，发现模拟的话肯定超时啊，于是想思维，不知道是休息了几天的原因还是啥，完全想不到什么思路。看了看时间，居然过了二十多分钟了，立马换题。期间看了看榜，都100+的人过A了，当然心急，看完B，想着能赢先赢、再能平局尽量平局，最后剩下的就是输的情况，但是居然是用循环写的，不出意外的又超时了，当场爆炸。再换题，看到C，发现就是个dp裸题啊，于是也是直接开始干，造了几个数据之后，立马交，终于过了，但是排名还是一百老几了；再回来看B，发现自己智障了，立马把循环变了，过了。但是由于前面浪费了太多时间，只剩下7分钟了，最后几十秒交A，第一次AK…  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]

## A：牛牛排队 ##

[题目链接][Link 1]

#### 题意： ####

下课了，牛牛要去食堂吃饭，他们学校的食堂有很多个门，而且整个建筑物是圆形的。只不过要去吃饭的人很多，在里面吃饭的人也很多，所以大家都在门口外面排队等待吃饭。  
所以牛牛采取了这样的一个策略：刚开始时，牛牛在第一个门口，如果这个门口有人在排队，那么他选择花费1分钟时间走到下一个门口，如果没有人的话，牛牛就可以直接进去吃饭啦。食堂的每一个门，每1分钟排队的人数都会减少一个。  
现在给你门的数量n，和每个门外排队的人的数量，如果按照牛牛的策略，那么牛牛最终会在哪个门进去吃饭呢？请你进行编程求解，返回牛牛最终是从第几个门进入食堂吃饭的。

#### 题解 ####

模拟肯定是不行了，首先考虑能不能不要绕圈，如果不能的话，就考虑每个位置最少需要绕几圈，取最小值。

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

class Solution {
        
    public:
        /**
         * 返回牛牛最终是从第几个门进入食堂吃饭的
         * @param n int整型 代表门的数量
         * @param a int整型vector 代表每个门外等待的人数
         * @return int整型
         */
        int solve(int n, vector<int>& a) {
        
            // write code here
            int pos=0;
            int ans=0;
            for(int i=0;i<a.size();i++){
        
                if(a[i]<=i){
        
                    pos=i;break;
                }
            }
            if(pos!=0){
        
                return pos+1;
            }
            int num=n/a[0];
            for(int i=1;i<a.size();i++){
        
                int x=n/a[i];
                
                if(x<num){
        
                    pos=i;num=x;
                }
            }
            return pos+1;
        }
    };

## B：石头、剪刀、布II ##

[题目链接][Link 2]

#### 题意 ####

牛牛每赢一局会+1分，每输一局会-1分，每平局一局不加分也不减分。  
牛牛这个游戏已经玩到了出神入化的地步，以至于他能猜到每一次牛妹会出什么牌。请问在知道牛妹每一轮出什么牌的情况下，牛牛最终的分数最高多少分？  
开始发给牛牛的n张牌里，有p1张石头牌，q1张剪刀牌，m1张布牌。  
开始发给牛妹的n张牌里，有p2张石头牌，q2张剪刀牌，m2张布牌。  
请返回牛牛的最高得分

#### 题解 ####

首先能赢的情况尽量赢，然后尽量平局，最后剩下的就是输的情况。

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

class Solution {
        
    public:
        /**
         * 
         * @param n int整型 
         * @param p1 int整型 
         * @param q1 int整型 
         * @param m1 int整型 
         * @param p2 int整型 
         * @param q2 int整型 
         * @param m2 int整型 
         * @return int整型
         */
        int Highestscore(int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        
            // write code here
            int num=min(p1,q2);
            int ans=0;
            if(num>0){
        
                ans+=num;
                p1-=num,q2-=num;
            }
            num=min(q1,m2);
            if(num>0){
        
                ans+=num;q1-=num,m2-=num;
            }
            num=min(m1,p2);
            if(num>0){
        
                ans+=num,m1-=num,p2-=num;
            }
            num=min(p1,p2);p1-=num,p2-=num;
            num=min(q1,q2);q1-=num,q2-=num;
            num=min(m1,m2);m1-=num,m2-=num;
            num=p1+q1+m1;
            ans-=num;
            return ans;
        }
    };

## C：寻宝 ##

[题目链接][Link 3]

#### 题意 ####

牛牛得到了一份寻宝图，根据寻宝图的指示，牛牛在一个nxm的网格中，牛牛的位置在(1,1)，宝藏的位置在(n,m)，由于寻宝需要按照特定规则，所以牛牛只能往上走或者往右走。藏宝人为了让故意为难牛牛，在地图中设置了一块长方形的陷阱区域，牛牛要是碰到了陷阱可能会有生命危险，陷阱左下坐标为(x0,y0)，右上坐标为(x1,y1)。为了牛牛能顺利找到宝藏你能告诉他有多少种不同的寻宝路径吗。

#### 题解 ####

一道比较裸的dp题.  
 d p \[ i \] \[ j \] = ( d p \[ i − 1 \] \[ j \] + d p \[ i \] \[ j − 1 \] ) % m o d （ ( i − 1 , j ) ， ( i , j − 1 ) 不 在 陷 阱 区 域 ） dp\[i\]\[j\]=(dp\[i-1\]\[j\]+dp\[i\]\[j-1\])\\%mod（(i-1,j)，(i,j-1)不在陷阱区域） dp\[i\]\[j\]=(dp\[i−1\]\[j\]\+dp\[i\]\[j−1\])%mod（(i−1,j)，(i,j−1)不在陷阱区域）

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

class Solution {
        
    public:
        long long dp[1010][1010];
        long long mod=1000000007;
        /**
         * 
         * @param n int整型 
         * @param m int整型 
         * @param x0 int整型 
         * @param y0 int整型 
         * @param x1 int整型 
         * @param y1 int整型 
         * @return int整型
         */
        int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        
            // write code here
            memset(dp,0,sizeof(dp));
            dp[1][1]=1;
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=m;j++){
        
                    int flag1=0,flag2=0;
                    if((i-1)>=x0&&(i-1)<=x1&&j>=y0&&j<=y1) flag1=1;
                    if((j-1)>=y0&&(j-1)<=y1&&i>=x0&&i<=x1) flag2=1;
                    if(!flag1) dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
                    if(!flag2) dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
                }
            }
            /*for(int i=1;i<=n;i++){
                for(int j=1;j<=m;j++) printf("%d ",dp[i][j]);
                printf("\n");
            }*/
            return dp[n][m];
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]: /images/20221124/52ddc9f5b01f4eb5a85ddd4e9efc8b02.png
[Link 1]: https://ac.nowcoder.com/acm/contest/6909/A
[Link 2]: https://ac.nowcoder.com/acm/contest/6909/B
[Link 3]: https://ac.nowcoder.com/acm/contest/6909/C