涵盖知识点:数学、三分

比赛链接:传送门

A - Berland Poker

题意:有nn张牌,其中mm张王牌,将这nn张牌平均分给kk个人(n%k==0)(n%k==0),询问拿到王牌数最多和剩下的所有人中拿到王牌数最多的之差最大为多少
题解:一个人全拿王牌(足够的话) 剩下的人均分。
Accept Code:

#include <bits/stdc++.h>using namespace std;int main(){    int t;cin>>t;    while(t--){        int n,m,k;        cin>>n>>m>>k;        int mx=min(n/k,m);        m-=mx;        int ot=(m+k-2)/(k-1);        cout<<mx-ot<<"\n";    }    return 0;}

B - New Theatre Square

题意:给出一个只由黑白组成的n×mn×m的矩阵,现在要填冲所有的白块,可以选择花费xx1个1个填,也可以选择横向的1×21×2一次填,花费yy。问最少花费。
题解:判断2x2x和yy的大小,然后贪心。
Accept Code:

#include <bits/stdc++.h>using namespace std;const int maxn=1010;string mp[maxn];int main(){    int t;cin>>t;    while(t--){        int n,m,x,y;        cin>>n>>m>>x>>y;        for(int i=0;i<n;i++)cin>>mp[i];        int cost=0;        if(2*x<=y){            for(int i=0;i<n;i++){                for(int j=0;j<m;j++){                    if(mp[i][j]=='.')cost+=x;                }            }        }        else{            for(int i=0;i<n;i++){                for(int j=0;j<m;j++){                    if(mp[i][j]=='.'){                        if(j!=m-1&&mp[i][j+1]=='.'){                            j++;                            cost+=y;                        }                        else cost+=x;                    }                }            }        }        cout<<cost<<"\n";    }    return 0;}

C - Mixing Water

题意:热水和冷水的温度分别为h,ch,c。
以 一杯热水->一杯冷水->一杯热水->一杯冷水->…的顺序加入一个容器内,
询问最少加多少杯,可以最接近温度tt
题解:在偶数次的时候温度位h+c2h+c2别的时候都会大于这个值。所以若2t≤h+c2t≤h+c答案就是22。其余情况显然这个绝对值具有单调递减后递增的趋势,三分即可。
Accept Code:

#include <bits/stdc++.h>using namespace std;const int maxn=1010;const int inf=0x3f3f3f3f;typedef long long ll ;int h,c,t;double f(ll x,ll y){    return fabs((double)t-1.0*(x*h+y*c)/(x+y));}int main(){    int _;cin>>_;    while(_--){        cin>>h>>c>>t;        if(t*2<=h+c){            cout<<"2\n";            continue;        }        ll l=0,r=inf;        while(l<r){            ll ml=l+(r-l)/3,mr=r-(r-l)/3;            if(f(ml+1,ml)<=f(mr+1,mr))r=mr-1;            else l=ml+1;        }        cout<<2*l+1<<"\n";    }    return 0;}

D - Yet Another Yet Another Task

题意:给定nn个数anan,求一段区间之和-区间内最大值的最大值
题解:枚举最大值在线处理最长子段和。
Accept Code:

#include <bits/stdc++.h>using namespace std;const int maxn=1e5+10;int a[maxn];int main(){    int n;    cin>>n;    for(int i=1;i<=n;i++)cin>>a[i];    int ans=0;    for(int mx=1;mx<=30;mx++){        int res=0;        for(int i=1;i<=n;i++){            if(a[i]>mx)res=0;            else{                res+=a[i];                if(res<0)res=0;                else ans=max(res-mx,ans);            }        }    }    cout<<ans<<"\n";    return 0;}

E - Modular Stability

题意:给定nn和kk,要求在[1,n][1,n]中找出不同的kk个数组成递增序列aa,使得(((xmoda1)moda2)…modak−1)modak=(((xmodap1)modap2)…modapk−1)modapk(((xmoda1)moda2)…modak−1)modak=(((xmodap1)modap2)…modapk−1)modapk,pp是aa的任意排列。
题解:从[1,n][1,n]中选取一个基数pp,再从[1,n][1,n]中找k−1k−1的这个基数pp的倍数即可,最终结果都为x%px%p。
Accept Code:(鬼知道为什么cout就WA了QAQ)

#include <bits/stdc++.h>using namespace std;const int maxn=500010,mod=998244353;typedef long long ll;int fac[maxn],inv[maxn],n,k,ans;int qpow (int a,int b) {    int res=1;    while (b) {        if (b&1)res=(1ll*res*a)%mod;        a=(1ll*a*a)%mod;        b>>=1;    }    return res;}int c (int n,int m) {    if (n<m) return 0;    return (1ll*fac[n]*((1ll*inv[m]*inv[n-m])%mod))%mod;}int main () {    cin>>n>>k;    fac[0]=inv[0]=1;    for (int i=1;i<=n;i++)fac[i]=(1ll*fac[i-1]*i)%mod;    inv[n]=qpow(fac[n],mod-2);    for (int i=n-1;i>=1;i--) inv[i]=(1ll*inv[i+1]*(i+1))%mod;    for (int i=1;i<=n;i++) {        int tmp=n/i-1;        ans=(ans+c(tmp,k-1))%mod;    }    printf("%d\n",ans);    return 0;}