ooliver

2026-10-22 比赛总结

ooliver OI

NOIP 二十连测 day4

温度

很显然的是我们可以先把所有的 ai 都对 k 取模一下，然后排个序，此时的答案就应该是最大值和最小值的平均值（向上取整）

最优解是要考虑有些 ai 多减去了一个 k 变成负数，这些 ai 肯定是排序后数列的一个后缀，枚举这个后缀，每次计算是 O(1) 的。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,ans,a[500005];
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]%=k;
    sort(a+1,a+1+n);
    ans=(a[n]-a[1]+1)/2;
    for(int i=1;i<n;i++) ans=min(ans,(a[i]+k-a[i+1]+1)/2);
    cout<<ans;
    return 0;
}

小恐龙

考虑这是一个最短路问题，障碍是不能连边的。如果是添加障碍的话很难处理，但如果我们倒着处理，每次减少了一个障碍，由于 k 的大小限制，最短路更新的复杂度是可行的，这样就做完了。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5,inf=1e9;
int n,q,k,f[N],ans[N],cnt;
bool ob[N],iq[N];

struct node{
    int op,x;
}op[N];

void push(int s){
    queue<int> q0,q1;
    q0.push(s),iq[s]=1;
    while(q0.size()||q1.size()){
        int u;
        if(q0.empty()) u=q1.front(),q1.pop();
        else if(q1.empty()) u=q0.front(),q0.pop();
        else if(q0.front()<=q1.front()) u=q0.front(),q0.pop();
        else u=q1.front(),q1.pop();
        iq[u]=0;
        int v0=u+1;
        if(v0<=n&&!ob[v0]&&f[u]<f[v0]){
            f[v0]=f[u];
            if(!iq[v0]) q0.push(v0),iq[v0]=1;
        }
        int v1=u+k;
        if(v1<=n&&!ob[v1]&&f[u]+1<f[v1]){
            f[v1]=f[u]+1;
            if(!iq[v1]) q1.push(v1),iq[v1]=1;
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q>>k;
    for(int i=1;i<=q;i++){
        cin>>op[i].op>>op[i].x;
        if(op[i].op==1) ob[op[i].x]=1;
    }
    for(int i=1;i<=n;i++) f[i]=inf;
    if(!ob[1]) f[1]=0,push(1);
    for(int i=q;i>=1;i--){
        if(op[i].op==2){
            int x=op[i].x;
            ans[++cnt]=f[x]>=inf?-1:f[x];
        }
        else{
            int x=op[i].x;
            ob[x]=0;
            int nd=inf;
            if(x==1) nd=0;
            else{
                if(x-1>=1&&!ob[x-1]) nd=min(nd,f[x-1]);
                if(x-k>=1&&!ob[x-k]) nd=min(nd,f[x-k]+1);
            }
            if(nd<f[x]){
                f[x]=nd;
                push(x);
            }
        }
    }
    for(int i=cnt;i>=1;i--) cout<<ans[i]<<"\n";
    return 0;
}

铁路

很显然的是最优路径上停靠的车站等级一定是单峰的，所以直接考虑从两端往最高等级的车站爬，爬的过程中一步能跳的最远位置要么是左边第一个等级不小于它的点，要么是右边第一个等级不小于它的点。

那每个点走 2j 步能覆盖的范围显然就是一个区间，直接用单调栈求出一跳的端点，然后倍增维护一下区间极值。询问的时候让两边像求 LCA 一样贪心往上倍增跳，直到区间能接起来为止，单次查询是 O(logn) 的。

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=5e5+5,M=20;
int n,q,k,l[N],st[N],tp;
int dl[M][N],dr[M][N];

int gl(int j,int x,int y){
    return min(dl[j][x],dl[j][y]);
}

int gr(int j,int x,int y){
    return max(dr[j][x],dr[j][y]);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q>>k;
    for(int i=1;i<=n;i++) cin>>l[i];
    tp=0;
    for(int i=1;i<=n;i++){
        while(tp&&l[st[tp]]<l[i]) tp--;
        dl[0][i]=tp?st[tp]:i;
        st[++tp]=i;
    }
    tp=0;
    for(int i=n;i>=1;i--){
        while(tp&&l[st[tp]]<l[i]) tp--;
        dr[0][i]=tp?st[tp]:i;
        st[++tp]=i;
    }
    for(int j=1;j<M;j++) for(int i=1;i<=n;i++){
        int a=dl[j-1][i],b=dr[j-1][i];
        dl[j][i]=gl(j-1,a,b);
        dr[j][i]=gr(j-1,a,b);
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        if(x>y) swap(x,y);
        int ans=0,lx=x,rx=x;
        for(int j=M-1;j>=0;j--){
            int a=gl(j,lx,rx),b=gr(j,lx,rx);
            if(b<y) ans+=1<<j,lx=a,rx=b;
        }
        int ly=y,ry=y;
        for(int j=M-1;j>=0;j--){
            int a=gl(j,ly,ry),b=gr(j,ly,ry);
            if(a>rx) ans+=1<<j,ly=a,ry=b;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

故障机器

简化题意：两种机器，一种说真话，一种乱说，并且乱说的机器对相同的机器得到的答案总是一样的。现在最多进行 8 轮相互询问，试找出每个机器是真是假。

考虑只有机器两两互相询问得到的信息才方便处理。不难发现，当两个机器两两询问得到的结果都是 1，说明这两个机器肯定要么都是真，要么都是假，那我们就把这两个机器归为同一个等价类。

显然两个等价类是可以合并的，当且仅当其中的机器相互询问得到的结果都是 1；如果两个类不能合并，我们标记一下。我们考虑循环八次，每次把可合并的两个等价类成对加到一个数组里。顺次遍历从大到小排序后的数组，对能合并的两个类合并。

由于真的机器数量是大于总的数量的一半的，这么进行若干次后，理想状态下所有的 1 都合并到一起了，此时最大的一个等价类就包含了所有的 1，其余等价类都是 0，就得到答案了。

代码：

#include<bits/stdc++.h>
#include"check.h"
using namespace std;

const int N=105;
int n;
int in[N],tag[N][N],siz[N],m[N];

vector<int> query(vector<int> a);

vector<int> check(int c,int n){
    vector<int> p(n),ans(n);
    for(int i=0;i<n;i++){
        in[i]=i;
        for(int j=0;j<n;j++) tag[i][j]=0;
    }
    int t=8;
    while(t--){
        for(int i=0;i<n;i++) siz[i]=0;
        for(int i=0;i<n;i++) siz[in[i]]++;
        vector<pair<int,int>> v;
        for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(in[i]!=in[j]) v.push_back({i,j});
        sort(v.begin(),v.end(),[&](pair<int,int> a,pair<int,int> b){
            return max(siz[in[a.first]],siz[in[a.second]])>max(siz[in[b.first]],siz[in[b.second]]);
        });
        for(int i=0;i<n;i++) m[i]=-1;
        for(auto it:v){
            int x=it.first,y=it.second;
            if(tag[in[x]][in[y]]) continue;
            if(m[x]==-1&&m[y]==-1) m[x]=y,m[y]=x;
        }
        for(int i=0;i<n;i++) p[i]=i;
        for(int i=0;i<n;i++) if(m[i]>i) swap(p[i],p[m[i]]);
        vector<int> s=query(p);
        for(int i=0;i<n;i++) if(i<p[i]){
            if(s[i]==1&&s[p[i]]==1){
                int u=in[i],v=in[p[i]];
                for(int j=0;j<n;j++) if(in[j]==u) in[j]=v;
            }
            else tag[in[i]][in[p[i]]]=tag[in[p[i]]][in[i]]=1;
        }
    }
    for(int i=0;i<n;i++) siz[i]=0;
    for(int i=0;i<n;i++) siz[in[i]]++;
    int mx=0,x=-1;
    for(int i=0;i<n;i++) if(siz[i]>mx) mx=siz[i],x=i;
    for(int i=0;i<n;i++) ans[i]=(in[i]==x);
    return ans;
}