一起来做题~欢乐赛1

A 可以用map离散化

#include<bits/stdc++.h>
using namespace std;
int const N=2e5+7;
int t,n,m;
map<int,int>pos,cnt;  //可以用map离散化 //记录在数轴的位置并映射出它的值 
map<int,int>::iterator it; 
int main(){
    cin >> t;
    while(t--){
        cin >> n >> m;
        pos.clear();cnt.clear();
        for(int i=1;i<=n;++i){
            int a;cin >> a; 
            pos[a]=1;cnt[a]++;
        }
        for(int i=1;i<=m;++i){
            int a;cin >> a;
            pos[a]=0;cnt[a]=0;
        }
        int ans=0,sum=0;
        for(it=pos.begin();it!=pos.end();++it){
            if(it->second) sum+=cnt[it->first];
            else sum=0;
            ans=max(ans,sum);
        }
        if(ans) cout << ans << "\n";
        else cout << "Impossible\n"; 
    }
    return 0;
}

B 按灯题

尝试着分析（画一画，举例子）可以发现是按灯题的模型
第一个确定了，放法就确定了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e4+7;
int n;
int a[N],l[N];
int pan(){
    for(int i=2;i<=n;++i){
        l[i]=a[i-1]-l[i-1]-l[i-2];
        if(l[i]<0||l[i]>1) return 0;
    }
    if(l[n]+l[n-1]!=a[n]) return 0;
    return 1;
} 
int main(){
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> a[i];
    }
    int cnt=0;
    l[1]=1;
    if(pan()) cnt++;
    l[1]=0;
    if(pan()) cnt++;
    cout << cnt;
    return 0;
}

C 提前操作和反向操作

发功后对前面的无影响，对后面的有影响，所以可以让其全部发完功再操作
操作可以从后往前

看到区间修改就要反映过来（差分前缀和、线段树）
特别是看到区间相对大小的变化，要反映过来是差分

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=5e4+7;
int t,n,m;
int a[N],b[N],sex[N];
int main(){
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i=1;i<=n;++i){
            cin >> sex[i] >> a[i];
            b[i]=a[i]-a[i-1];
        }
        for(int i=1;i<=m;++i) {
            int x;cin >> x;
            b[1]+=1;b[x+1]-=1;
        }
        for(int i=1;i<=n;++i) b[i]+=b[i-1];
        int maxn[2]={0,0},cnt=0;
        for(int i=n;i>=1;--i){
            if(b[i]>=maxn[sex[i]^1]) cnt++;
            maxn[sex[i]]=max(maxn[sex[i]],b[i]);
        }
        cout << cnt << "\n";
    }
    return 0;
}

D 记搜写dp

背包也是线性dp，想到可以由前面覆盖（转移），而无背包的形，要反映过来是线性dp

求分数，f肯定表示分数，而其表示的搜索状态一般为题目所给的条件

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=357;
int n,m,op[6];
int a[N],f[47][47][47][47];
int dfs(int i,int j,int k,int l){
    if(i<0||j<0||k<0||l<0) return 0;
    if(f[i][j][k][l]!=0) return f[i][j][k][l];
    f[i][j][k][l]=max( max(dfs(i-1,j,k,l),dfs(i,j-1,k,l)),
                       max(dfs(i,j,k-1,l),dfs(i,j,k,l-1)) )
                  + a[1+i+2*j+3*k+4*l];  
    return f[i][j][k][l];
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i) cin >> a[i];
    for(int i=1;i<=m;++i) {
        int x;cin >> x;
        op[x]++;
    }
    int ans=0;
    ans=dfs(op[1],op[2],op[3],op[4]);
    cout << ans;
    return 0;
}

E 用倍增预处理

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e6+7;
int n,m,k;
ll a[N];
ll f[N][24];
int pan(int l,int r){
    int ans=0;
    for(int j=20;j>=0;--j){
        if(f[l][j]<=r){
            ans+=(1<<j);
            l=f[l][j];
        }
    }
    //if(f[l][0]==l&&a[l]>k) return 0;
    if(f[l][0]<=r) return 0;
    return ans+1;
}
int main(){
    cin >> n >> m >> k;
    for(int i=1;i<=n;++i){
        cin >> a[i];
    }
    for(int j=0;j<=20;++j){    
        for(int i=1;i<=n+1;++i){  //注意这里到n+1
            f[i][j]=n+1;    //初始化
        }
    }
    ll sum=0;
    for(int i=1,j=0;i<=n;++i){
        while(j<=n&&sum<=k) sum+=a[++j];
        f[i][0]=j;   //初始化
        sum-=a[i];
    }
    for(int j=1;j<=20;++j){
        for(int i=1;i<=n;++i){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
    int l,r;
    for(int i=1;i<=m;++i){
        cin >> l >> r;
        int ans=0;
        ans=pan(l,r);
        if(ans) cout << ans << "\n";
        else cout << "Chtholly\n";
    }
    return 0;
}