传送门

A.Berland Poker

首先算一下最多的那个人能拿多少 Joker，应该是 x=minn/k,m)) 张。那么剩下 m-x) 张 joker 均分给剩下的 n-1) 个人，这样可以保证第 2) 多的人尽量少，所以剩下的人最多能有 other=m-x)/n-1)+bool)m-x)%n-1))) 张 joker，答案就是 x-other)。

include <bits/stdc++.h>
using namespace std;
int n,m,k;

void solve){
    n=read),m=read),k=read);
    int maxv=minn/k,m);
    int other=m-maxv)/k-1)+m-maxv)%k-1)?1:0);
    printf"%d
",maxv-other);
}

int main){
    int T=read);
    whileT--) solve);
    return 0;
}

B. New Theatre Square【贪心】

题意

给一个 n imes m) 矩阵，有”.”或”*”，有两种地砖，尺寸分别为 1 imes 1) 和 1 imes 2)，价格分别为 x) 和 y)。要求将所有 “.” 覆盖，问最少需要多少钱。

思路

如果 x*2le y)，那么直接用 1 imes 1) 的地砖铺满就好。
否则先用 1 imes 2) 的地砖铺，然后再用 1 imes 1) 的地砖将漏补上。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,x,y;
char g[110][1010];

void solve){
    n=read),m=read),x=read),y=read);
    forint i=1;i<=n;i++) scanf"%s",g[i]+1);
    int ans=0;
    ifx*2<=y){
        forint i=1;i<=n;i++)forint j=1;j<=m;j++)ans+=g[i][j]=='.')*x;
        return void)printf"%d
",ans);
    }
    forint i=1;i<=n;i++)forint j=1;j<=m;j++)
        ifj<m&&g[i][j]=='.'&&g[i][j+1]=='.')
            ans+=y,g[i][j]=g[i][j+1]='*';
    forint i=1;i<=n;i++)forint j=1;j<=m;j++)ans+=g[i][j]=='.')*x;
    printf"%d
",ans);
}

int main){
    int T=read);
    whileT--) solve);
    return 0;
}

C. Mixing Water【数学？】

题意

给你两种温度的水，一种温度为 h)，一种温度为 c)。你依照 h,c,h,c,…) 的顺序向容器里倒水，问最少多少杯水可以使得容器中水的温度最接近 t)，h,c,t) 满足 cle tle h)。

思路

可以发现以这个顺序，无论倒多少杯水，最后的温度一定大于等于 h+c)/2)，所以如果 2*tle h+c)，答案直接为 2)。
否则，设要倒 x) 杯 c)，x+1) 杯 h)，那么当前温度为：frac{x+1)h+xc}{2x+1}=>frac{h+c}{2}+frac{h-c}{4x+2})。
解方程

[h+c+frac{h-c}{2x+1}=2t
]

得出来 x) 大概是个分数，取整之后，比较 x) 和 x+1) 哪个对应最接近 t) 的温度。然后计算答案。

代码

#include <bits/stdc++.h>
using namespace std;
int h,c,t;

void solve){
    scanf"%d%d%d",&h,&c,&t);
    ifh+c>=2*t) return void)printf"2
");
    double x=1.0*h-c)/2*t-h-c)-1)/2;
    int x1=int)x,x2=x1+1,ans;
    double t1=h+c+1.0*h-c)/2*x1+1))/2;
    double t2=h+c+1.0*h-c)/2*x2+1))/2;
    iffabst1-t)<=fabst2-t)) ans=x1*2+1;
    else ans=x2*2+1;
    printf"%d
",ans);
}

int main){
    int T=read);
    whileT--) solve);
    return 0;
}

D. Yet Another Yet Another Task【ST+二分】

题意

给数列 a_1,a_2,…,a_n)，计算一段连续区间之和减去该区间最大值的最大值。

思路

因为 a_i) 的值域限制，可以用最大字段和的思路来做。但本菜鸡没想到，所以用了 ST+二分 的笨办法，比赛的时候还写疵了。
对于每个 a_i) 找到以它为最大值的最长区间，这个显然可以用 ST表+二分 找到。假设为 L,R。那么此时要从中选出和最大且包含 a[i]) 的一段的和值，用 s[i]) 表示前缀和，那么这个最大的和值，就是 s[i],…,s[R]) 的最大值，减去 s[L-1],…,s[i-1]) 的最小值。所以这里同样可以用ST表实现。

代码

#include <bits/stdc++.h>
using namespace std;
int n,a[N],st[N][21],minv[N][21],maxv[N][21],s[N];

int smaxint l,int r){
    ifl==r) return a[l];
    int k=log2r-l);
    return maxst[l][k],st[r-1<<k)][k]);
}
int maxsumint l,int r){
    ifl==r) return s[l];
    int k=log2r-l);
    return maxmaxv[l][k],maxv[r-1<<k)][k]);
}
int minsumint l,int r){
    ifl==r) return s[l];
    int k=log2r-l);
    return minminv[l][k],minv[r-1<<k)][k]);
}

int main){
    n=read);
    forint i=1;i<=n;i++) a[i]=read),s[i]=s[i-1]+a[i];
    forint i=0;i<=n;i++) 
        st[i][0]=maxa[i],a[i+1]),
        maxv[i][0]=maxs[i],s[i+1]),
        minv[i][0]=mins[i],s[i+1]);
    forint j=1;j<=20;j++)
        forint i=0;i+1<<j)<=n;i++)
            st[i][j]=maxst[i][j-1],st[i+1<<j-1)][j-1]),
            maxv[i][j]=maxmaxv[i][j-1],maxv[i+1<<j-1)][j-1]),
            minv[i][j]=minminv[i][j-1],minv[i+1<<j-1)][j-1]);
    int ans=0;
    forint i=1,l,r,L,R;i<=n;i++){
        l=1,r=i;
        whilel<r){
            int mid=l+r)/2;
            ifsmaxmid,i)<=a[i]) r=mid;
            else l=mid+1;
        }
        L=l,l=i,r=n;
        whilel<r){
            int mid=l+r+1)/2;
            ifsmaxi,mid)<=a[i]) l=mid;
            else r=mid-1;
        }
        R=l;
        int temp=maxsumi,R)-minsumL-1,i-1)-a[i];
        ans=maxans,temp);
    }
    printf"%d
",ans);
    return 0;
}

E. Modular Stability

题意

问从 1,…,n) 中抽 k) 个数，对任意排列 p)，使得 x%a_{p_1}%a_{p_2}%…%a_{p_3}) 相同，问这个 k) 个数由多少种选择。

思路

补题的时候看到这道题，就这？比 D 题简单啊。
显然要满足条件，这 k) 个数中，有 1) 个数肯定是其他 k-1) 个数的约数。
那么做法就很简单了，首先枚举这 1) 个数，然后算出它倍数的个数 m)，那么就要从这这 m) 个数中选出 k-1) 个数，所以这 1) 个数对于答案的贡献为 C_m^{k-1})。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+10;
const int MOD=998244353;
inline LL qpowLL x,LL k=MOD-2,LL mod=MOD){LL res=1;whilek){ifk&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res;}
LL n,k,fac[N]={1};

LL Cint n,int m){
    ifm>n) return 0;
    return fac[n]*qpowfac[m])%MOD*qpowfac[n-m])%MOD;
}

int main){
    n=read),k=read);
    forint i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;
    ifn<k) return printf"0
"),0;
    LL ans=0;
    forint i=1;i<=n;i++){
        int num=n/i;
        ifnum<k) break;
        ans=ans+Cnum-1,k-1))%MOD;
    }
    printf"%lld
",ans);
    return 0;
}