滴滴笔试
public class 组合问题 {
/**
* 小昱家的桃园丰收了！小昱采摘下来n个桃子，并对这些桃子称重，其中第i个桃子的重量为ai。
小昱想选择一些桃子装成一箱后送给朋友，但是小昱不希望一箱桃子中有一些太大的桃子而影响整体美观。
于是他给装箱工人提出了一个要求：一箱桃子中最重的桃子重量不能超过平均重量的k倍。
装箱工人想知道在满足小昱要求的情况下，一箱最多能装多少个桃子。
*
*
*
* 输入描述
* 第一行输入两个正整数 n, k，表示桃子个数、倍数系数。
*
* 接下来一行输入n个正整数a1, a2,...... an，其中ai表示第 i 个桃子的重量。
*
*
* 1 ≤ n, k ≤ 100000, 1≤ ai ≤ 109
*
* 输出描述
* 输出一个整数，表示一箱最多能装桃子数量。
*
*
* 样例输入
* 5 2
* 3 10 5 4 2
* 样例输出
* 4
*
* 提示
* 可以将第1、3、4、5个桃子装成一箱，桃子平均重量为(3 + 5 + 4 + 2) / 4 = 3.5，最重的桃子重量为5，不超过平均重量的两倍，是一种可行方案。
*
* 如果将所有桃子装成一箱，桃子平均重量为(3 + 10 + 5 + 4 + 2) / 5 = 4.8，最重桃子的重量为10，超过平均重量的两倍了，故一箱不能装5个桃子。
*/
public static void main(String[] args) {
// write your code here
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
long sum = 0;
int x = 0;
for (int j = 0, i = 0; j < n; j++) {
sum += a[j];
while (i <= j && a[j] * (long) (j - i + 1) > sum * k) {
sum -= a[i];
i++;
}
x = Math.max(x, j - i + 1);
}
System.out.println(x);
}
} 这题在考的时候出了点问题，没有跑通
自己复盘了思路....数位dp问题
public class 美丽值 {
/**
* 老张教授开了一堂美数课！
* <p>
* 老张认为每个非负整数x都有一个美丽值b(x)。
* <p>
* 一个非负整数的美丽值定义为这个数十进制下每个数位的异或和。即，对于123来说，美丽值为1^2^3=0，
* 对于654815424美丽值为6^5^4^8^1^5^4^2^4=9 （在C/C++中^运算符表示异或）
* <p>
* 现在老张想考考同学，对于[L,R]这个闭区间内的所有整数，美丽值恰好为t的数有多少个。
* <p>
* <p>
* <p>
* 输入描述
* 第一行一个正整数，表示有次询问。
* <p>
* 接下来有三行：
* <p>
* 第一行个非负整数 L1,L2,...,Li,...,LT(1≤i≤T)
* <p>
* 第二行个非负整数 R1,R2,...,Ri,...,RT(1≤i≤T)
* <p>
* 第三行个非负整数 t1,t2,...,ti,...,tT(1≤i≤T)
* <p>
* 每个询问是对于 [Li, Ri] (Li≤Ri)这个闭区间内的所有整数，美丽值恰好为的数有多少个。
* <p>
* <p>
* <p>
* 输出描述
* 每个询问输出T个整数，每两个数之间用空格隔开，表示答案。
* <p>
* <p>
* 样例输入
* 2
* 0 1
* 0 10
* 0 1
* 样例输出
* 1 2
* <p>
* 提示
* <p>
* <p>
* 一共两次询问。
* <p>
* 第1次询问 [0, 0] 这个区间中美丽值为0的有多少个，0的美丽值为0，答案为1。
* <p>
* 第2次询问 [1, 10] 这个区间中美丽值为1的有多少个，1和10的美丽值为1，答案为2。
*/
static int N = 5;
static int T = 15;
//dp[i,j,k] 表示一共i位，最高位是j，异或和为k
private static final long[][][] dp = new long[N + 1][10][T + 1];
static void init() {
for (int j = 0; j <= 9; j++) {
dp[1][j][j] = 1;
}
// 很容易疏忽的位置，容易把第三维度开太大导致超时，要对2进制加强敏感程度
// 每一位都是[1,9] 最大的异或和不超过4位全1=> (1111)2 => 15
// j x _ _ _ _ _
// 从x到最后一位一共i-1位，从j到最后一位共i位
// dp[i,j,k] += dp[i-1,x,k^j]
for (int i = 2; i <= N; i++) {
for (int j = 0; j <= 9; j++) {
for (int x = 0; x <= 9; x++) {
for (int k = 0; k <= T; k++) {
dp[i][j][k] += dp[i - 1][x][k ^ j];
}
}
}
}
}
static {
init();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] l = new int[n];
int[] r = new int[n];
int[] t = new int[n];
for (int i = 0; i < n; i++) {
l[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
r[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
t[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
System.out.print(f(r[i], t[i]) - f(l[i] - 1, t[i]) + " ");
}
}
/**
* f(n,t): [0,n] 所有的数的美丽值为t的个数
* 因为所有测试用例可以共享dp，dp初始化全局共享
* 技巧1：依赖于java底层：在类加载的时机jvm会对static属性就完成显式赋值，执行static代码块 这个过程只会发生一次且按照代码顺序执行
* 技巧2：我所知道OJ平台测试时都是类加载一次，然后每个用例会new一个对象，调用测评方法 这样可以利用构造代码块的特性 每次 new对象 先执行构造块 最后执行构造方法
* leetcode acwing 蓝桥系统 acmcoder皆适用
* 复杂度分析：
* 初始化dp: 10*10*16*4*logN
* f(n,t): log(n)
* 总复杂度为: log(n) ~ 6400*logN
*/
private static long f(int n, int t) {
if (n < 0)
return 0;
if (n == 0) {
return dp[1][n][t];
}
ArrayList<Integer> nums = new ArrayList<>();
while (n != 0) {
nums.add(n % 10);
n /= 10;
}
long res = 0;
int mask = 0;
for (int i = nums.size() - 1; i >= 0; i--) {
int x = nums.get(i);
for (int j = 0; j < x; j++) {
res += dp[i + 1][j][t ^ mask];
}
mask ^= x;
// 特判顺利到达最后一位 并且所有的位异或和正好为 t
if (i == 0 && mask == t)
res++;
}
return res;
}
} 
