7-29作业/重写ren_gao_zu

ren_gao_zu · 2025-07-30 12:04:22 · 个人记录

作业

UVA11572 唯一的雪花 Unique Snowflakes

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int t,n,a[1000005];
deque<int>dq;
map<int,int>mp;
void solve(){
    mp.clear();
    while(dq.size())dq.pop_back();
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int maxn=0;
    for(int i=1;i<=n;i++){
        while(dq.size()&&mp[a[i]]==1){
            mp[a[dq.front()]]=0;
            dq.pop_front();
        }
        mp[a[i]]=1;
        dq.push_back(i);
        maxn=max(maxn,(long long)dq.size());
    }
    cout<<maxn<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

P4392 [BalticOI 2007] Sound 静音问题

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int t,n,a[1000005],m,c;
bool flag;
deque<int>d,q;
void solve(){
    cin>>n>>m>>c;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        while(d.size()&&a[d.back()]<=a[i])d.pop_back();
        while(q.size()&&a[q.back()]>=a[i])q.pop_back();
        if(d.size()&&d.front()+m<=i)d.pop_front();
        if(q.size()&&q.front()+m<=i)q.pop_front();
        d.push_back(i);
        q.push_back(i);
        if(i>=m&&a[d.front()]-a[q.front()]<=c){
            cout<<i-m+1<<endl;
            flag=1;
        }

    }
    if(!flag)cout<<"NONE";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

P11963 [GESP202503 六级] 环线

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int a[1000005],n,s[10000005];
deque<int>dq;
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];
        a[i+n]=a[i];
    }
    for(int i=1;i<=2*n;i++)s[i]=s[i-1]+a[i];
    int ma=-1e18;
    for(int i=1;i<=2*n;i++){
        while(dq.size()&&s[dq.back()]>=s[i])dq.pop_back();
        if(dq.size()&&dq.front()+n<=i)dq.pop_front();
        if(i>=n){
            ma=max(ma,s[i]-s[dq.front()]);
        }
        dq.push_back(i);
    }
    cout<<ma;
    return 0;
}

重写

Problem A. Ascending Rating HDU - 6319

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e7+5;
int t,n,m,k,q,p,r,MOD,a[N];
deque<int>dq;
void solve(){
    cin>>n>>m>>k>>p>>q>>r>>MOD;
    int A=0,B=0;
    for(int i=1;i<=n;i++){
        if(i<=k)cin>>a[i];
        else a[i]=(a[i-1]*p+i*q+r)%MOD;
    }
    while(dq.size())dq.pop_back();
    for(int i=n;i>=1;i--){
        if(!dq.empty()&&dq.front()>i+m-1){
            dq.pop_front();
        }
        while(!dq.empty()&&a[dq.back()]<=a[i])dq.pop_back();
        dq.push_back(i);
        if(i<=n-m+1){
            A+=a[dq.front()]^i;
            B+=dq.size()^i;
        }

    }
    cout<<A<<" "<<B<<endl;

}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

P1638 逛画展

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m,a[1000005];
int dal,dar;
//deque<int>dq;
int num[10005];
bool check(int x){
    //while(dq.size())dq.pop_back();
    memset(num,0,sizeof num);
    int cnt=0;
    for(int i=1;i<x;i++){
        //dq.push_back(a[i]);
        num[a[i]]++;
        if(num[a[i]]==1)cnt++;
    }
    for(int i=x;i<=n;i++){
        //dq.push_back(a[i]);
        num[a[i]]++;
        if(num[a[i]]==1)cnt++;
        //dq.pop_front();
        if(i!=x){
            num[a[i-x]]--;
            if(num[a[i-x]]==0)cnt--;
        }
        if(cnt==m){
            dar=i;
            dal=i-x+1;
            return 1;
        }
    }return 0;
}
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];
    int l=0,r=n+1;
    while(l+1<r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid;
        }
        else l=mid;
    }
    cout<<dal<<" "<<dar;
    return 0;
}

P1714 切蛋糕

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m;
int a[1000005],s[1000005];
deque<int>dq;
int ma=-0x3f3f3f3f;
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    dq.push_back(0);
    for(int r=1;r<=n;r++){
        while(dq.size()&&s[r]<=s[dq.back()]){
            dq.pop_back();
        }
        if(r-dq.front()>m){
            dq.pop_front();
        }
        ma=max(ma,s[r]-s[dq.front()]);
        dq.push_back(r);
    }
    cout<<ma;

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

P2629 好消息，坏消息

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,a[2000005],s[2000005];
deque<int>dq;
int ans;
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];
        a[i+n]=a[i];
    }
    for(int i=1;i<=2*n;i++){
        s[i]=a[i]+s[i-1];
    }
    for(int i=2*n;i>=1;i--){
        while(dq.size()&&s[i]<=s[dq.back()]){
            dq.pop_front();
        }
        dq.push_front(i);
        if(dq.back()-i>=n)dq.pop_back();
        int r=dq.back();
        if(i<=n&&s[r]>=s[i-1])ans++;
    }cout<<ans;
    return 0;
}