1111 B
题意
有 \(n\) 个人，每个人有一个属性 \(a_i\) ，现在你可以进行 \(m\) 次操作，每次你可以踢掉一个人或者将一个人的水平值+1，每个人最多加 \(k\) 次，问最大可能的平均属性值。 \((1\le n\le 10^5)\)
Examples
input
2 4 6
4 7
output
11.00000000000000000000
input
4 2 6
1 3 2 3
output
5.00000000000000000000
解
排序，预处理后缀和，枚举踢掉人的个数，计算。
1111 C
题意
有一个 \(2^n\) 的线段，上面有 \(k\) 个怪物，你首先在处理 \([1,2^n]\) ，每次你可以：
- 将当前区间分成左、右两个长度相等的区间；
- 销毁当前区间。如果区间里没有怪物，花费 \(A\) ；否则花费 \(B*N*l\) ， \(N\) 指当前区间中的怪物， \(l\) 指当前区间的长度。
问销毁整个大区间的最小花费。
\((1\le n\le 30,1\le k\le 10^5)\)
Examples
input
2 2 1 2
1 3
output
6
input
3 2 1 2
1 7
output
8
解
dfs+剪枝
如何查询一个区间里有多少个怪物？upper_bound-lower_bound
1111 D
题意
钢铁侠必须要选择类型和x，y两洞穴中类型相同的反派，把它们移动到殖民地的前半部或者后半部，并且剩余的反派，如果是同一类型，也要呆在同一边。问这样移动的方案数。
\(|s|,q\le 10^5\)
Examples
input
abba
2
1 4
1 2
output
2
0
input
AAaa
2
1 2
1 3
output
2
0
input
abcd
1
1 3
output
8
解
\(dp[i][j]\) 表示只考虑两部分中的一部分，字母 \(i,j\) 都在这一边的方案数。
对于 \(x,y\) ，答案为： \(2*dp[x][y]*\frac{(\frac{|s|}{2}!)^2}{\Pi cnt_i!}(i为所有字母)\)