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

比赛总结

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

A：牛牛排队

题目链接

题意：

下课了，牛牛要去食堂吃饭，他们学校的食堂有很多个门，而且整个建筑物是圆形的。只不过要去吃饭的人很多，在里面吃饭的人也很多，所以大家都在门口外面排队等待吃饭。
所以牛牛采取了这样的一个策略：刚开始时，牛牛在第一个门口，如果这个门口有人在排队，那么他选择花费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

题目链接

题意

牛牛每赢一局会+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：寻宝

题目链接

题意

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

题解

一道比较裸的dp题.
$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];
    }
};

本文地址：https://blog.csdn.net/boliu147258/article/details/107887016