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

这场爆0了，呜~，状态时好时坏，不过无所谓(才怪)，学到东西就好QWQ

A 牛牛排队

解题思路
这道题关键在于算出每一门口排队的人需要牛牛走多少圈人数才能为0，那么对于每一个门口的人数num,可以将其分解为i + x * n,那么所对应的圈数就是1 + (a[i] - i + n - 1) / n，找到需要圈数最小的且最靠前的那个就是最终的结果，(考试的时候我居然想的是经过a[i]时间牛牛可以恰好走到该位置那该位置就是答案，考后想反问自己一句，为什么要恰好走到呢，就不能到之前人家已经是0了吗?)
参考代码

import java.util.*;


public class Solution {
    /**
     * 返回牛牛最终是从第几个门进入食堂吃饭的
     * @param n int整型 代表门的数量
     * @param a int整型一维数组 代表每个门外等待的人数
     * @return int整型
     */
    public int solve (int n, int[] a) {
        // write code here
        int[] t = new int[n];
        int pos = -1;
        int min = 0x3f3f3f3f;

        for(int i=0; i<n; i++){
            a[i] -= i;
            if(a[i] <= 0) t[i] = 1;
            else t[i] = 1 + (a[i] + n - 1) / n;

            if(min > t[i]){
                min = t[i];
                pos = i;
            }
        }

        return pos + 1;
    }
}

B 石头、剪刀、布II

解题思路
这道题贪心的想就可以了，对于牛牛的牌的分配是这样的，先将牛牛分数可以+1的牌出掉，然后将二者平局的牌出掉，那么对于剩下的牌，就只能是牛牛-1了。
参考代码

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型
     * @param p1 int整型
     * @param q1 int整型
     * @param m1 int整型
     * @param p2 int整型
     * @param q2 int整型
     * @param m2 int整型
     * @return int整型
     */
    public int Highestscore (int n, int p1, int q1, int m1, int p2, int q2, int m2) {
        // write code here
        // 计算牛牛的得到的正分
        int a = Math.min(p1, q2);
        int b = Math.min(q1, m2);
        int c = Math.min(m1, p2);

        p1 -= a; q2 -= a;
        q1 -= b; m2 -= b;
        m1 -= c; p2 -= c;

        int d = Math.min(p1, p2);
        int e = Math.min(q1, q2);
        int f = Math.min(m1, m2);

        p1 -= d; p2 -= d;
        q1 -= e; q2 -= e;
        m1 -= f; m2 -= f;

        int res = a + b + c - p2 - q2 - m2;
        return res;
    }
}

C 寻宝

解题思路
这道题就是一道经典的动态规划的问题，定义f[i][j]表示从[1, 1]到[i, j]的路径数，那么状态转移就是f[i][j] = f[i-1][j] + f[i][j-1]
但是我考试的时候交了一份这样的代码:

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型
     * @param m int整型
     * @param x0 int整型
     * @param y0 int整型
     * @param x1 int整型
     * @param y1 int整型
     * @return int整型
     */
    int MOD = 1000000007;
    public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) {
        // write code here
        long[][] f = new long[n+1][m+1];

        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(i >= x0 && i <= x1 && j >= y0 && j <= y1) f[i][j] = 0;
                else if(i == 1) f[i][j] = 1;
                else if(j == 1) f[i][j] = 1;
                else f[i][j] = (f[i-1][j] + f[i][j-1]) % MOD;
            }
        }

        return (int)f[n][m];
    }
}

哎，愣是想了足足半个小时没想明白，后来才发现，原来是中间的两个else出锅了，因为有可能陷阱挡住了第一行/第一列之后的某些元素，但是我还是把它们的方案数设为1，这就肯定不对了。
参考代码

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型
     * @param m int整型
     * @param x0 int整型
     * @param y0 int整型
     * @param x1 int整型
     * @param y1 int整型
     * @return int整型
     */
    int MOD = 1000000007;
    public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) {
        // write code here
        long[][] f = new long[n+1][m+1];

        f[1][1] = 1;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(i == 1 && j == 1) continue;
                if(i >= x0 && i <= x1 && j >= y0 && j <= y1) f[i][j] = 0;
                else f[i][j] = (f[i-1][j] + f[i][j-1]) % MOD;
            }
        }

        return (int)f[n][m];
    }
}