8-2作业/重写ren_gao_zu

· · 个人记录

作业

P1890 gcd区间

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e3+5,M=2e6+5;
int n,m,lg[N],f[N][15],a[N];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)f[i][0]=a[i];
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(int j=1;j<=12;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=__gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        int len=r-l+1;
        int j=lg[len],ans;
        ans=__gcd(f[l][j],f[r-(1<<j)+1][j]);
        cout<<ans<<endl;
    }
    return 0;
}

P1714 切蛋糕

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5,M=2e6+5;
int n,m,lg[N],f[N][25],a[N],ma=-1e18,s[N];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)f[i][0]=a[i]+f[i-1][0];
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(int j=1;j<=21;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            //ma=max(ma,f[i][j]);
        }
    }
    int j=lg[m],ans=0;
    for(int i=m;i<=n;i++){
        ans=max(ans,f[i][0]-min(f[i-m][j],f[i-(1<<j)+1][j]));
    }cout<<ans;
    return 0;
}

重写

P2698 [USACO12MAR] Flowerpot S

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5,M=2e6+5;
int n,m,lg[N],f[N][30],D,ans=1e18,g[N][30];
struct node{
    int x,y;
}a[N];
bool cmp(node a,node b){
    return a.x<b.x;
}
bool check(int l,int r){
    int j=lg[r-l+1],ma=max(f[l][j],f[r-(1<<j)+1][j]),mi=min(g[l][j],g[r-(1<<j)+1][j]);
    if(ma-mi>=D)return 1;
    return 0;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>D;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)f[i][0]=a[i].y,g[i][0]=a[i].y;
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=n;i++){
        int l=i-1,r=n+1,mid;
        while(l+1<r){
            mid=l+r>>1;
            if(check(i,mid)){
                r=mid;

            }
            else l=mid;
        }
        if(r<=n)ans=min(ans,a[r].x-a[i].x);
    }
    if(ans==1e18)cout<<-1;
    else cout<<ans;
    return 0;
}

P2866 [USACO06NOV] Bad Hair Day S

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5,M=2e6+5;
int n,lg[1000005],f[N][25],a[N];
int sum;
bool check(int l,int r){
    int j=lg[r-l+1];
    int ans=max(f[l][j],f[r-(1<<j)+1][j]);
    if(a[l-1]>ans)return 1;
    return 0;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)f[i][0]=a[i];
    for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
    for(int j=1;j<=20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=n;i++){
        int mid,l=i,r=n+1;
        while(l+1<r){
            mid=(l+r)>>1;
            if(check(i+1,mid)){
                l=mid;
            }
            else r=mid;
        }
        sum+=l-i;
    }cout<<sum;
    return 0;
}