牛客编程巅峰赛S1第3场 - 青铜&白银

A.位数求和

解题思路

这道题没有什么算法可言，因为的范围很小，所以可以直接打暴力，唯一的优化就是不需要从1到指定位数的数字，而只需要从比这个数字的位数小一位的数字开始。

参考代码

import java.util.*;


public class Solution {
    /**
     * 返回这样的数之和
     * @param n int整型 数的长度
     * @param m int整型 各个为之和
     * @return long长整型
     */
    public long sum (int n, int m) {
        // write code here
        int mul = 1;
        for(int i=1; i<=n; i++) mul *= 10;

        long res = 0;

        for(int i=mul/10; i<=mul; i++) {
            int tmp = i;
            int sum = 0;
            while(tmp != 0) {
                sum += tmp % 10;
                tmp /= 10;
            }

            if(sum == m) res += i;
        }

        return res;
    }
}

A题扩展: 当题目中最大为100，这道题该如何解决呢?

解题思路

有了状态转移方程之后，我们还要考虑一个问题就是求出来的结果中是含有前导0的，可能有1个，2个或者n个，而这些数字的和正是f[n-1][0-9][m]表示n-1位，且第n-1位为0-9，和为m的所有数字的和。
参考代码

import java.util.*;


public class Solution {
    /**
     * 返回这样的数之和
     * @param n int整型 数的长度
     * @param m int整型 各个为之和
     * @return long长整型
     */
    int N = 110, M = 1010;
    long[][][] f = new long[N][10][N]; // f[i, j, k]表示i位数字，最高位为j，前i位数字的和为k的所有数字的和
    long[][][] cnt = new long[N][10][N]; // cnt[i, j, k]表示i位数字，最高位为j，前i位数字的和为k的数字的个数
    public long sum (int n, int m) {
        // write code here
        for(int i=0; i<=9; i++){
            f[1][i][i] = i;
            cnt[1][i][i] = 1;
        }

        for(int i=2; i<=n; i++){
            for(int j=0; j<=9; j++){
                for(int k=j; k<=9*i; k++){

                    // 进行状态转移
                    for(int u=0; u<=9; u++){
                        f[i][j][k] += f[i-1][u][k-j] * 10 + cnt[i-1][u][k-j] * j;
                        cnt[i][j][k] += cnt[i-1][u][k-j];
                    }
                }
            }
        }

        long res = 0;
        for(int i=0; i<=9; i++) {
            res += f[n][i][m] - f[n-1][i][m];
        }

        return res;
    }
}

还有另一种方式实现不含前导0，就是我们可以发现，除了第一位不能填0之外，剩下的所有位置都可以填0，所以在枚举2位的情况时，要保证前一位的数字不为0就好了。

参考代码

import java.util.*;


public class Solution {
    /**
     * 返回这样的数之和
     * @param n int整型 数的长度
     * @param m int整型 各个为之和
     * @return long长整型
     */
    int N = 110, M = 1010;
    long[][][] f = new long[N][10][N]; // f[i, j, k]表示i位数字，最高位为j，前i位数字的和为k的所有数字的和
    long[][][] cnt = new long[N][10][N]; // cnt[i, j, k]表示i位数字，最高位为j，前i位数字的和为k的数字的个数
    public long sum (int n, int m) {
        // write code here
        for(int i=0; i<=9; i++){
            f[1][i][i] = i;
            cnt[1][i][i] = 1;
        }

        for(int i=2; i<=n; i++){
            for(int j=0; j<=9; j++){
                for(int k=j; k<=9*i; k++){

                    // 进行状态转移
                    for(int u=(i == 2? 1 : 0); u<=9; u++){
                        f[i][j][k] += f[i-1][u][k-j] * 10 + cnt[i-1][u][k-j] * j;
                        cnt[i][j][k] += cnt[i-1][u][k-j];
                    }
                }
            }
        }

        long res = 0;
        for(int i=0; i<=9; i++) res += f[n][i][m];

        return res;
    }
}

B.不可思议

解题思路
这道题首先分析u[i]和v[i], 发现在构造的过程中，v[i]的值总是小于u[i]的，由于1号节点是根节点，所以最终的边一定是u[i] - > v[i]的，所以这里我们使用一个pre数组记录每一个点的前驱节点，然后对于每一次的询问，从当前节点出发，通过pre数组一直走到根节点，求出对应的结果即可

参考代码

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param seed1 long长整型 
     * @param seed2 long长整型 
     * @param seed3 long长整型 
     * @param x int整型 
     * @return long长整型
     */
    int MOD = 998244353, N = 100010, M = 2 * N;
    int[] u = new int[N];
    int[] v = new int[N];
    int[] pre = new int[N]; // 存储每一个点的前驱节点

    long ans(long x, long y){
        long res = 0;
        while(x != 1){
            res += ((y + 2 * x) ^ (y + x));
            x = pre[(int) x];
        }

        res += ((y + 2 * x) ^ (y + x));
        return res;
    }

    public long work (int n, long seed1, long seed2, long seed3, int x) {
        // write code here
        long seed4 = 0;
        for(int i=1; i<=n-1; i++){
            seed4=(seed1+seed2)%MOD*seed3%MOD;
            u[i]=i+1;
            v[i]=(int)((seed4%i)+1);

            pre[u[i]] = v[i];
//            pre[v[i]] = u[i];

            seed3=seed2;
            seed2=seed1;
            seed1=seed4;
        }

        long lastans = 0;
        long ret = 0;
        long y = 0;

        long z = 0;
        for(int i=1; i<=n; i++){
            z=ans(x,y);
            ret=(ret+z)%998244353;
            lastans=z;
            x=(int) (((x+lastans)^ret)%n+1);
            y=lastans;
        }

        return ret;
    }
}

C. 牛牛晾衣服

解题思路
这道题首先我们可以通过分析得到，它具有二段性，所谓的二段性就指的是，当确定了答案为某一个值之后，在答案左边的都是不满足的，而答案右边的都是可以满足的，很明显，这道题是有的，之后我们考虑check函数怎么写，对于每一次二分出的限定时间lim,首先在这lim的时间内，所有的衣服都会自然的风干lim的水量，但是其中肯定会有一些衣服晾不干，因此需要烘***来烘干，而由于使用烘***其实是浪费了一次自然烘干的机会，所以对于当前的这一分钟，使用烘***烘干的水量实际上是k-1, 遍历整个数组，求出所需时间，如果大于lim,则返回0，否则返回1

参考代码

import java.util.*;


public class Solution {
    /**
     * 计算最少要多少时间可以把所有的衣服全烘干
     * @param n int整型 n件衣服
     * @param a int整型一维数组 n件衣服所含水量数组
     * @param k int整型 烘***1分钟可以烘干的水量
     * @return int整型
     */
    boolean check(int lim, int[] a, int n, int k) {
        int sum = 0;

        for(int i=0; i<n; i++) {
            if(a[i] <= lim) continue;

            sum += Math.ceil((double)(a[i] - lim) / (k - 1));
            if(sum > lim) return false;
        }

        return true;
    }

    public int solve (int n, int[] a, int k) {
        // write code here
        int max = a[0];
        for(int i=0; i<n; i++) max = Math.max(max, a[i]);

        if(k == 1) return max;

        int l = 0; int r = max;
        while(l < r) {
            int mid = l + r >> 1;
            if(!check(mid, a, n, k)) l = mid + 1;
            else r = mid;
        }

        return l;
    }
}