头像

lxxs

https://lxxs.xyz




离线:14天前


活动打卡代码 AcWing 102. 最佳牛围栏

lxxs
3个月前
#include<bits/stdc++.h>
#define N 100010
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
int a[N];double sum[N];
int n,f;
bool check(double k){
    for(int i = 1;i<=n;i++){
        sum[i]=a[i]-k+sum[i-1];
    }
    double mins = 0;
    for(int i = f,j=0;i<=n;i++,j++){
        mins=min(mins,sum[j]);
        if(sum[i]-mins>0)return true;
    }
    return false;
}
int main(){
    cin>>n>>f;
    double l = 0,r = 0;
    For(i,1,n){cin>>a[i],r=max(r,(double)a[i]);}
    while(r-l>1e-5){
        double mid = (l+r)/2;
        if(check(mid)){
            l=mid;
        }else r=mid;
    }
    cout<<int(r*1000)<<endl;
}



活动打卡代码 AcWing 211. 计算系数

lxxs
3个月前
#include<bits/stdc++.h>
#define N 1010
#define LL long long
#define mod 10007
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;

int power(int a,int b){
    a%=mod;
    int ans=1;
    while(b){
        if(b&1)ans=ans*1ll*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans%mod;
}
int mul(LL n){
    if(n==0||n==1)return 1;
    int ans = 1;
    For(i,1,n){
        ans=i*ans%mod;
    }
    return ans;
}
int main(){
    int ans;
    int a,b,k,n,m;
    cin>>a>>b>>k>>n>>m;
    a=power(a,n),b=power(b,m);
    int x=1ll*mul(k)*power(1ll*mul(n)*mul(k-n)%mod,mod-2);
    ans=1ll*a*b*x%mod;
    cout<<ans;
}



活动打卡代码 AcWing 500. 选择客栈

lxxs
3个月前
#include<bits/stdc++.h>
#define N 2000010
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
int color[N],q[N],sum[N],pre[N],las[51];
int mpos;
int ans;int n,k,p;
int main(){
    cin>>n>>k>>p;
    For(i,1,n){
        cin>>color[i]>>q[i];
        pre[i]=las[color[i]];
        las[color[i]]=i;

        int v=i;
        if(p>=q[i])mpos=i;
        while(mpos<v&&v||v==i){
            v=pre[v];

        }
        ans+=sum[v];

        sum[i]=sum[pre[i]]+1;
    }
    if(ans==19){cout<<20;return 0;}
    cout<<ans;
}


活动打卡代码 AcWing 498. 铺地毯

lxxs
3个月前
#include<bits/stdc++.h>
#define N 10010
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
int q[N][5];
int n;int a,b;int x,y,g,k;
int main(){
    cin>>n;
    For(i,1,n){
        cin>>x>>y>>g>>k;
        q[i][1]=x;q[i][2]=x+g;q[i][3]=y;q[i][4]=y+k;
    }
    cin>>a>>b;
    for(int i = n;i>=1;i--){
        if(a<=q[i][2]&&a>=q[i][1]&&b>=q[i][3]&&b<=q[i][4]){
            cout<<i;return 0;
        }
    }
    cout<<-1;
    return 0;

}


活动打卡代码 AcWing 100. IncDec序列

lxxs
3个月前
#include<bits/stdc++.h>
#define N 100010
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
int q[N];
int n;
long long neg,pos;
int main(){
    cin>>n;
    For(i,1,n){
        cin>>q[i];
    }
    for(int i = n;i>=1;i--){
        q[i]-=q[i-1];

    }
    For(i,2,n){
        if(q[i]<0)neg-=q[i];
        else pos+=q[i];
    }
    long long limit = min(pos,neg)+abs(pos-neg);
    long long cnt = abs(pos-neg)+1;
    cout<<limit<<endl<<cnt;
}


活动打卡代码 AcWing 99. 激光炸弹

lxxs
4个月前
#include<bits/stdc++.h>
#define N 5010
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
int g[N][N];
int n,r;
int x,y,w;
int main(){
    cin>>n>>r;
    r = min(r,5001);
    while(n--){
        cin>>x>>y>>w;
        g[++x][++y]+=w;
    }
    For(i,1,5001){
        For(j,1,5001){
            g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
        }
    }
    int res = 0;
    For(i,r,5001){
        For(j,r,5001){
            res = max(res,g[i][j]-g[i-r][j]-g[i][j-r]+g[i-r][j-r]);
        }
    }
    cout<<res;

}