赛后——2.12 寒假模拟8
\(\text{T1}\) 吃
题意
小 \(S\) 面前有 \(n\) 个桌子，每个桌子上有两样吃的，它们的种类分别用 \(A_i,B_i\) 表示。
小 \(S\) 想要选出连续的一段桌子，然后从每个桌子上挑出一个食物吃下去。特别地，他想要他吃的所有食物种类都一样。
现在小 \(S\) 想要知道，他最多能吃多少个食物？以及在这样的前提下，食物的最小标号是多少。
思路
直接扫一遍，每次不连续就更新答案。
代码
点击查看代码
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read(),b[i]=read();
}
for(int i=1;i<=n;i++){
for(int j=1;j<=5;j++){
if(a[i]==j||b[i]==j){
cnt[j]++;
}
else{
tot[j]=max(tot[j],cnt[j]);
cnt[j]=0;
}
}
}
for(int i=1;i<=5;i++){
tot[i]=max(tot[i],cnt[i]);
}
for(int i=1;i<=5;i++){
if(tot[i]>maxval){
maxval=tot[i];
maxpos=i;
}
}
printf("%d %d\n",maxval,maxpos);
return 0;
}
\(\text{T2}\) 糖
题意
小 \(S\) 有 \(m\) 颗糖，想把它分给 \(n\) 个小朋友。
第 \(i\) 个小朋友对于分到糖果的预期值是 \(A_i\)。
现在，假设第 \(i\) 个小朋友分到了小于 \(A_i\) 的糖果，设其为 \(B_i\)，那么这个小朋友的怒气值就是 \((A_i-B_i)^2\)。
请最小化它们的怒气值之和。
思路
显然 \(m-\sum A_i\) 的值均摊到每个小朋友身上，就能使这个怒气值最小（由平方公式 \((\alpha+\beta)^2=\alpha^2+2\alpha\beta+\beta^2\) 得）。于是我们考虑如何去均摊。
显然直接求 \((m-\sum A_i)/n\) 以及其余数是错的，拿 \(n=4,m=6,A=\{1,5,3,5\}\) 来举例，这个均摊的值为 \(2\)，可对于 \(A_1\) 而言，最多差值也就是 \(1\)，因此这个均摊需要我们动态维护。
于是将 \(A\) 升序排序，对每个 \(A_i\)，使其答案为 \(\min(num,A_i)\)，其中 \(num\) 为目前的均摊值。不断更新这个 \(num\)，并将最后的余数也均摊。
输出平方和即可。
代码
点击查看代码
int n;
ll m,a[maxn],sum,ans[maxn];
ll lft;
int main(){
m=read(),n=read();
for(int i=1;i<=n;i++){
a[i]=read();
sum+=a[i];
}
if(sum<=m) return printf("0\n"),0;
lft=sum-m;
sort(a+1,a+1+n);
int tmp=n;
for(int i=1;i<=n;i++){
int num=lft/tmp;
if(num>a[i]){
lft-=a[i];
ans[i]=a[i];
}
else{
lft-=num;
ans[i]=num;
}
tmp--;
}
while(lft){
for(int i=n;i>=1;i--){
if(ans[i]\(\text{T3}\) 数
题意
小 \(S\) 有个序列。
对于一个连续子序列，它的权值被定义为这个序列的最大值减去这个序列的最小值。
现在，小 \(S\) 有一个长度为 \(n\) 的序列，请你求出这个序列连续子序列的权值之和。
思路
发现答案为 \(\sum_{i=1}^n\sum_{j=i}^n (\max_{k=i}^j\{a_k\}-\min_{k=i}^j\{a_k\})\)。
我们不直接拆这个式子，考虑每个 \(a_i\) 对答案的贡献，其贡献为 \(a_i\times \text{作为区间最大值方案数}-\text{作为区间最小值的方案数}\)，其实我们找到一个 \(l_i\)，\(r_i\) 分别表示使 \(a_i\) 为最大值的最大区间的左右端点到 \(i\) 的距离，方案数就是 \(l_i\times r_i\)，当然这里一个要算上 \(i\)，另一个则不能（为了去重）。最小值同理。
枚举左右端点容易想到单调栈（与其相似的单调队列是维护一个定长区间最值），每次都找到最左与最右端点，期间不断弹栈，再把 \(i\) 入栈即可。
代码
点击查看代码
stack s;
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
a[0]=a[n+1]=0x3f3f3f3f;
s.push(0);
for(int i=1;i<=n;i++){
while(a[s.top()]=1;i--){
while(a[s.top()]<=a[i]) s.pop();
r[i]=s.top()-i;
s.push(i);
}
while(!s.empty()) s.pop();
for(int i=1;i<=n;i++){
ans+=a[i]*l[i]*r[i];
}
a[0]=a[n+1]=0;
s.push(0);
for(int i=1;i<=n;i++){
while(a[s.top()]>a[i]) s.pop();
l[i]=i-s.top();
s.push(i);
}
while(!s.empty()) s.pop();
s.push(n+1);
for(int i=n;i>=1;i--){
while(a[s.top()]>=a[i]) s.pop();
r[i]=s.top()-i;
s.push(i);
}
//while(!s.empty()) s.pop();
for(int i=1;i<=n;i++){
ans-=a[i]*l[i]*r[i];
}
printf("%lld\n",ans);
return 0;
}
\(\text{T4}\) 膜
题意
（原题面政治敏感）
在区间 \([1,n]\) 中，\([1,x]\) 是合法的，反之 \([x+1,n]\) 是不合法的。
现在有 \(k\) 个点用于测试，每个点在进入不合法区间后会失效（无法继续使用），求找出这个 \(x\) 在最坏情况下需要的次数。
思路
我们设 \(f_{i,j}\) 为 \(i\) 个点，\(j\) 次测试能测到的最多点数。发现进入合法区间和非法区间的方案唯一区别是测试点会减少一个。
于是，转移方程 \(f_{i,j}=f_{i,j-1}+f{i-1,j-1}+1\)。
我们设 \(g_{i,j}=f_{i,j+1}-f{i,j}\)，于是瞎推一波就有：
\[\begin{aligned} g_{i,j}&=f{i+1,j}-f_{i,j}\\ &=(f_{i+1,j-1}+f_{i,j-1}+1)-(f_{i,j-1}+f_{i-1,j-1}+1)\\ &=(f_{i+1,j-1}-f_{i,j-1})-(f_{i,j-1}-f_{i-1,j-1})\\ &=g_{i,j-1}+g_{i-1,j-1} \end{aligned}\]发现这个 \(g\) 的递推式形如组合数（边界值也是一样的），且 \(g\) 本质为 \(f\) 的差分数组，于是 \(f_{i,j}\) 可以由 \(g\) 得到：
\[f_{i,j}=\sum_{l=1}^i g_{l,j}=\sum_{l=1}^i \dbinom{j}{l} \]二分去找这个最小的 \(j\) 即可。
代码
点击查看代码
inline bool check(ll x){
ll num=1,sum=0;
for(int i=1;i<=k;i++){
db tmp=1.0*num*(x-i+1)/i;
if(tmp>1e18) return true;
num=num*(x-i+1)/i;
sum+=num;
if(sum>=n) return true;
}
return sum>=n;
}
int main(){
t=read();
while(t--){
n=read(),k=read();
ll l=1,r=n;
ans=-1;
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
printf("%lld\n",ans);
}
return 0;
}