牛客CSP-J入门组赛前集训营2

A-昂贵的字符串

30分

由于约束，字符串同类都是相等的，所以直接按要求计算即可。

100分

我们按以下顺序进行操作即可:

1. 将S中所有大写字母全部转换成小写，如果A，B是大写，将A，B也转换为小写
2. 遍历字符串S，如果字符s[i]==A，则使s[i]=B。
3. 统计不同种类的字符计算答案

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