共计 3431 个字符，预计需要花费 9 分钟才能阅读完成。
A. 位数求和
题目形容
牛牛想晓得所有的长度为 n 的数中，各个位上的数字之和为 m 的这些数的和是多少呢。给定 n 和 m，求这些数的和。
备注:
1 ≤ n ≤ 6,1 ≤ m ≤ 9 ∗ n示例 1
输出
2, 3输入
63阐明
12 + 21 + 30 = 63解法一：暴力枚举
思路剖析
因为范畴很小，所以能够暴力枚举每一个长度为 n 的数，看其是否符合条件。
工夫复杂度：$O(10^n)$。总共枚举 $10^n – 10^{n-1}$ 个数字。
空间复杂度：$O(1)$。
代码实现
public long sum (int n, int m) {
long res = 0;
int max = (int)Math.pow(10, n);
for(int i = (int)Math.pow(10, n - 1); i < max; i++){
int j = i, sum = 0;
while(j > 0) {sum += j % 10; j /= 10;}
if(sum == m) res += i;
}
return res;
}解法二：DFS
思路剖析
从前到后顺次枚举每一位上的数字，到第 $n$ 位时进行，若此时的数满足条件，则计入总和中。
能够退出剪枝操作，记后面的位上数字之和为 a，若 $a + b = m (b \in [1,9])$ 则只需枚举 $[1, b]$ 即可。
工夫复杂度：$O(10^n)$。递归 $n$ 层，每层循环 10 次。但退出了剪枝策略，因而工夫开销比解法一要小一些。
空间复杂度：$O(n)$。须要递归 $n$ 层。
代码实现
long res = 0;
public long sum(int n, int m) {for (int i = 1; i <= 9 && i <= m; i++) dfs(n - 1, m - i, i);
return res;
}
public void dfs(int n, int m, int num) {if(n == 0 && m == 0) res += num;
if(n == 0) return;
for (int i = 0; i <= 9 && i <= m; i++) dfs(n - 1, m - i, num * 10 + i);
}B. 不堪设想
题目形容
给定一颗节点编号为 1 ~ n 的，且以 1 为根的树，给出 n 组询问，每次询问给定一个数对 (x, y)，求 i 为 x 到根门路上的点(包含 x 和根) $∑_i(y+2i)xor(y+i)$.
对于这 n 组询问的答案，不须要顺次输入 n 个数，你只须要输入他们的和对 998244353 的取模即可。
树的信息以及询问不会间接给出，输出数据只蕴含随机种子，具体生成形式请仔细阅读备注内容。
备注:
输出数据蕴含 5 个整数，n,seed1,seed2,seed3,x.
树的信息生成伪代码如下
//////////////////////1/////////////////////
定义边集数组 u[],v[] //u[i],v[i]示意第 i 条边的两个端点
定义变量 seed4
定义循环变量 i 从 1 到 n -1
循环体开始
seed4=(seed1+seed2)%998244353*seed3%998244353;
u[i]=i+1;
v[i]=(seed4%i)+1;
seed3=seed2;
seed2=seed1;
seed1=seed4;
循环体完结
//////////////////////1/////////////////////
询问信息生成伪代码如下，顺带一提，第一次询问的 x 会在输出中给出
//////////////////////2/////////////////////
定义变量 lastans，初始值为 0
定义变量 ret，初始值为 0
定义变量 y，初始值为 0 // 含意见题干
定义函数 ans(x,y)，返回值为对数对 (x,y) 这组询问的答案 // 这里“询问”的含意见题干
定义变量 z
定义循环变量 i 从 1 到 n
循环体开始
z=ans(x,y);
ret=(ret+z)%998244353;
lastans=z;
x=((x+lastans)^ret)%n+1;
y=lastans;
循环体完结
//////////////////////2/////////////////////
输入一个整数，示意答案。n<=10^5,seed1,seed2,seed3<=10^9,x<=n
保障结构出的数据非法。示例 1
输出
3,1,1,1,1输入
7示例 2
输出
4,2,2,3,1输入
119解法：直观解法
思路剖析
这题和它的名字一样，题目是 “ 不堪设想 ” 的长，乍看会认为很难。看完题目后发现，只须要实现函数 ans 即可，“不堪设想”的简略……
就是从 x 一直的往上找父亲节点 i 直到根节点，返回门路上 $(y+2*i) xor (y+i)$ 的总和。
能够用数学归纳法证实 $u[i]$ 的父节点是 $v[i]$。这个证实比较简单，就不多赘述了。
工夫复杂度：$O(n*k)$。$k$ 是树的深度，总共 $n$ 组询问，每次询问最多循环计算 $k$ 次。
空间复杂度：$O(n)$。须要存储 $n – 1$ 个节点的父节点。
代码实现
int[] p; // p[i] 是 i 的父节点
public long work(int n, long seed1, long seed2, long seed3, int x) {
// 生成树
p = new int[n + 1];
for (int i = 1; i < n; i++) {long seed4 = (seed1 + seed2) % 998244353 * seed3 % 998244353;
p[i + 1] = (int) (seed4 % i) + 1;
seed3 = seed2;
seed2 = seed1;
seed1 = seed4;
}
// 询问信息生成
long lastans = 0, ret = 0, y = 0;
for (int i = 1; i <= n; i++) {long z = ans(x, y);
ret = (ret + z) % 998244353;
lastans = z;
x = (int) ((x + lastans) ^ ret) % n + 1;
y = lastans;
}
return ret;
}
public long ans(int x, long y) {
long ans = 0;
while (x != 1) {ans += (y + 2 * x) ^ (y + x);
x = p[x];
}
ans += (y + 2) ^ (y + 1);
return ans;
}C. 牛牛晾衣服
题目形容
牛牛有 n 件带水的衣服，干燥衣服有两种形式。
一、是用烘干机，能够每分钟烤干衣服的 k 滴水。
二、是天然烘干，每分钟衣服会天然烘干 1 滴水。
烘干机比拟小，每次只能放进一件衣服。
留神，应用烘干机的时候，其余衣服依然能够放弃天然烘干状态，当初牛牛想晓得起码要多少工夫能够把衣服全烘干。
备注:
第一个参数 n(1 ≤ n ≤ 105)，代表一共有多少件衣服。第二个参数为 n 个数 (1 ≤ an ≤ 109) 组成的数组，代表 n 件衣服别离有多少水滴水。第三个参数 k(1 ≤ k ≤ 109)，代表烘干机每分钟能烘干 k 滴水。程序应返回：一个整数，代表使 n 件衣服全副干燥所须要的起码的工夫。示例 1
输出
3,[2,3,9],5输入
3阐明
前两分钟对第三件衣服进行烘干机烘干，使得衣服的水份别离为 0，1，0，所以最快三分钟能够烘干。解法：二分法
思路剖析
先不思考怎么用程序实现，如果让你本人算起码烘干工夫，你会怎么算？
是不是对间接算烘干工夫毫无脉络？那如果给你个工夫 t，让你判断 t 分钟后衣服是否全副烘干。这个问题是不是就简略很多了？
因而咱们能够暴力遍历每一个时刻，看是否能烘干，最小的时刻就是题目要求的答案了。
然而暴力匹配耗时太多了啊，怎么办呢？
咱们发现这是在线性间断区域内进行遍历的，显然应用二分法能够大大降低工夫复杂度。
工夫复杂度：$O(nlogn)$。二分搜寻的复杂度是 $O(logn)$, 每次搜寻时判断是否全副烘干须要 $O(n)$。
空间复杂度：$O(1)$。
代码实现
public int solve (int n, int[] a, int k) {Arrays.sort(a);
int l = a[0], r= a[a.length - 1];
while(l < r){int mid = (l + r) >> 1;
if(check(mid, k, a)) r = mid;
else l = mid + 1;
}
return r;
}
public boolean check(int t, int k, int[] a){
int cnt = 0; // 记录烘干机用时
for(int i = a.length - 1; i >= 0 && cnt <= t; i--){if(a[i] <= t) break;
cnt += (a[i] - t) / (k - 1);
if(((a[i] - t) % (k - 1)) != 0) cnt++;
}
return cnt <= t;
}写在最初
大家好，我是往西汪，一位保持原创的新人博主。
如果本文对你有帮忙，请动动小手指点个赞????。你的反对是我创作路上的最大能源。谢谢大家！
也欢送来公众号【往西汪】找我游玩～
