牛客编程巅峰赛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;
}
}
查看16道真题和解析
