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;}写在最初
大家好，我是往西汪，一位保持原创的新人博主。
如果本文对你有帮忙，请动动小手指点个赞????。你的反对是我创作路上的最大能源。谢谢大家！
也欢送来公众号【往西汪】找我游玩～