本文共 4657 字，大约阅读时间需要 15 分钟。

C. Mixing Water

题意：热水h度，冷水c度，目标t度，往桶内倒热水或者冷水得到的桶内温度是倒入的温度的平均温度，第一次一定倒的是热水

做法：本来毫无思路，然后公告提示是热水冷水交替的倒，那么就是简单的推公式了。设热水x次，冷水倒x-1次。

公式：

如果热水冷水都是到x次,化简公式：

  先特判这个就可以了。

解出x就可以了。

#include
   
    #define rep(i,a,b) for(int i=a;i<=(b);++i)#define per(i,a,b) for(int i=a;i>=(b);--i)#define mem(a,x) memset(a,x,sizeof(a))#define pb push_back#define pi pair
    
     #define mk make_pairusing namespace std;typedef long long ll;ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}inline ll read(){	ll x=0,w=1; char c=getchar();	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}	return w==1?x:-x;}double x,y,t;double f(ll a){    return abs((x*a+y*(a-1))/(2*a-1)-t);}int main(){    int _=read();while(_--)    {        cin>>x>>y>>t;        if(x==t){printf("1\n");continue;}        if((x+y)>=t*2){printf("2\n");continue;}        ll a=(y-t)/(x+y-2*t);        double mi=f(a);        int ans=2*a-1;        for(int i=a-1;i<=a+1;++i){            if(f(i)
    
   

D. Yet Another Yet Another Task

题意：给你n长度的序列a，你可以选择一个区间，这区间的权值为 区间和减去区间一个最大值，求一个权值最大的区间，输出这个最大权值。

做法：安利两个做法，1是题目 的 官方做法 dp做法  但是呢 a[i]受约束 -30<=a[i]<=30，2是去年某场网络赛剽窃许老师的做法，我觉得算是原题吧这个题，可以做大范围的a[i]，第二个做法更妙。

做法1：枚举x为最大值，需要去掉的 然后dp[i][0]代表以i右端点区间的最大子段和  并且没有去掉x，dp[i][1]代表去掉了x。

转移方程：

if(a[i]>x) continue;			dp[i][0]=max(dp[i-1][0]+a[i],0ll);//			if(a[i]==x) dp[i][1]=max(dp[i-1][0],dp[i-1][1]+a[i]);			else dp[i][1]=dp[i-1][1]+a[i];

做法2：单调栈+线段树维护前缀和的最大值和最小值。

单调栈预处理出以i为最大值时 能到覆盖的最大区间l[i] r[i]，接着枚举i  代表去掉i 然后在 l[i] r[i] 找前缀和的最小值，和前缀和的最大值。

若最小值的位置大于等于最大值的位置，那么此次查询作废，为0

否则最大权值就是mx-mi-a[i]

#include
   
    #define rep(i,a,b) for(int i=a;i<=(b);++i)#define per(i,a,b) for(int i=a;i>=(b);--i)#define mem(a,x) memset(a,x,sizeof(a))#define pb push_back#define pi pair
    
     #define mk make_pairusing namespace std;typedef long long ll;ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}inline ll read(){	ll x=0,w=1; char c=getchar();	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}	return w==1?x:-x;}const int N=1e5+10;int a[N],sum[N],n,l[N],r[N];struct node{    int v,pos;}mi[4*N];struct node1{    int v,pos;}mx[4*N];node Min(node a,node b){    if(a.v<=b.v) return a;    return b;}node1 Max(node1 a,node1 b){    if(a.v
     
      >1;    build(id<<1,l,mid);    build(id<<1|1,mid+1,r);    mi[id]=Min(mi[id<<1],mi[id<<1|1]);    mx[id]=Max(mx[id<<1],mx[id<<1|1]);}node qu(int id,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return mi[id];    int mid=l+r>>1;    node ans={1000000,0};    if(ql<=mid) ans=qu(id<<1,l,mid,ql,qr);    if(qr>mid) ans=Min(ans,qu(id<<1|1,mid+1,r,ql,qr));    return ans;}node1 qu1(int id,int l,int r,int ql,int qr){    if(ql<=l&&r<=qr) return mx[id];    int mid=l+r>>1;    node1 ans={-1000000,0};    if(ql<=mid) ans=qu1(id<<1,l,mid,ql,qr);    if(qr>mid) ans=Max(ans,qu1(id<<1|1,mid+1,r,ql,qr));    return ans;}int main(){    n=read()+1;    rep(i,2,n) a[i]=read(),sum[i]=sum[i-1]+a[i];    build(1,1,n);    rep(i,1,n) l[i]=r[i]=i;    stack
      
       sta;    rep(i,1,n)    {        while(sta.size()&&a[i]>=a[sta.top()]) sta.pop();        if(sta.size()) l[i]= sta.top()+1;        else l[i]=0;        sta.push(i);    }    while(sta.size()) sta.pop();    per(i,n,1)    {        while(sta.size()&&a[i]>=a[sta.top()]) sta.pop();        if(sta.size()) r[i]=sta.top()-1;        else r[i]=n;        sta.push(i);    }    //rep(i,1,n) printf("i:%d l:%d r:%d sum:%d\n",i,l[i],r[i],sum[i]);    int ans=0;    rep(i,1,n)    {        if(l[i]==r[i]) continue;        node mii=qu(1,1,n,l[i],i);        node1 mxx=qu1(1,1,n,i,r[i]);        if(mii.pos>=mxx.pos) continue;        //printf("i:%d l:%d r:%d mi:%d mx:%d tm:%d\n",i,l[i],r[i],mii.pos,mxx.pos,mxx.v-mii.v-a[i]);        ans=max(ans,mxx.v-mii.v-a[i]);    }    printf("%d\n",ans);}/*10-5 28 -18 -10 9 -2 11 -6 -19 30*/
      
     
    
   

E. Modular Stability

题意：给你n  k  要你构造k长度的序列 a[i]  ,范围：1<=a[i]<=a[i]<=n,  使得所有数 无论a[i] 是什么顺序 满足下面的式子

做法：我怎么这题也是做过，全是原题。设首位为i，那么后面的依次是i的倍数就可以了。

如果第一个数字是i，那么剩下的位置如果是i的倍数也是可以的，就是c(n/i-1,k-1)，第一个一定要是最小的。

#include
   
    using namespace std;typedef long long ll;const int N=5e5+10;const int mod=998244353;int n,k;ll ans;ll jc[N],inv[N];inline ll qp(ll a,ll b){	ll ans=1;	for(;b;b>>=1)	{		if(b&1) ans=ans*a%mod;		a=a*a%mod;	}	return ans;}inline void prework(){	scanf("%d%d",&n,&k);	jc[0]=1;	for(int i=1;i<=n;i++)		jc[i]=jc[i-1]*i%mod;	inv[n]=qp(jc[n],mod-2);	for(int i=n-1;i>=0;i--)		inv[i]=inv[i+1]*(i+1)%mod;}ll c(int n,int m){	if(m>n || m<0) return 0;	return jc[n]*inv[n-m]%mod*inv[m]%mod;}int main(){    prework();    if(k>n) ans=0;	else{        ans=0;        for(int i=1;i<=n;i++) ans=(ans+c(n/i-1,k-1))%mod;	}    printf("%d\n",ans);}
   

转载地址：https://ccsudeer.blog.csdn.net/article/details/106426027 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！