牛客CSP-J入门组赛前集训营2
A-昂贵的字符串
30分
由于约束，字符串同类都是相等的，所以直接按要求计算即可。
100分
我们按以下顺序进行操作即可:
- 将S中所有大写字母全部转换成小写，如果A，B是大写，将A，B也转换为小写
- 遍历字符串S，如果字符s[i]==A，则使s[i]=B。
- 统计不同种类的字符计算答案
B-最小差
10分
由于所有ai值相等，所以最大值和最小值相等，直接输出0即可。
40分
由于是一个排列，最开始差一定为n-1，考虑每次去掉一个最大或最小的数，那么差就会减一，因此对于一个排列，答案是n-1-k。
100分
考虑最优的方法一定是去掉了一些比较小的值，去掉了一些比较大的值，因此分别枚举最小和最大值分别去掉了多少个，由于尽可能多的去掉元素不会导致答案更大，具有单调性，所以可以O(n)枚举比较小的元素去掉了多少个，假如最小元素去掉了i个，最大元素区间k-i个即是最优的。如果把数组从大到小排序，就可以O(k+nlog2(n))解决此题。
C-价值不小于k的区间
如何计算一个区间的价值：
我们可以想到一个经典的问题：
X轴上有N个点，求X轴上一点使它到这N个点的距离之和最小，输出这个最小的距离之和。
这个点就是中位数
那么我们使整个区间的数都修改成中位数操作的次数就最小了
于是我们要维护中位数，小于中位数的数的和，大于中位数的和
30分
乱搞，直接枚举区间，然后排序(使用辅助更快)统计即可
60分
枚举区间，然后对顶堆统计即可.
对顶堆：
开一个大根堆和一个小根堆
我们可以以小根堆的堆顶为“分界线”
如果大于它，就加入小根堆
反之加入大根堆
如果两个堆的个数相差超过
，就把多的那个堆的堆顶弹出来，加入另一个堆的堆顶
如果要求中位数的话，显然是两个堆中个数多的那一个的堆顶
100分
尺取法(双指针) + 数据结构()
我们假设区间的价值
这样的话的价值也
,左端点可以选
可以使用尺取法,枚举右端点，统计答案
动态维护区间价值我们可以选用各种平衡树，也可以巧用,
pb_ds
()
D-函数
首先，根据组合数公式得出f(n,r)=p(n)/p(n-r)/p(r)*p(n-r)=p(n)/p(r)
设g(l,r)=l*(l+1)*…*(r-1)*r，因此f(n,r)=g(r+1,n)，特别的r==n是f(n,r)=1。
10分
因为100%100==0，因此当mod>100时，直接输出0即可，否则暴力即可，时间复杂度O(q*mod)
40分
由于模数为质数，我们可以直接与处理阶乘和阶乘的逆元，每次查询O(1)得出答案，时间复杂度O(q+n)
100分
由于模数可能不为质数，所以我们不要用到除法即可，我们用线段树维护区间连乘的值，时间复杂度O(q*log2(n))
注意此题要用到__int128或者用10000进制慢速乘
标程：
A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41554265
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41554322
C:出题人暂时失踪
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41554373
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41554409
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41554458
查看16道真题和解析