26.11.19 比赛记录

更新于 2026年11月20日约 4 分钟阅读

T1 history

结论:

  1. 初始向右的人一定会被打败。
  2. 一个向左的人被称为可能胜利的人当且仅当存在 ll 使得 l∼i−1l\sim i-1 均向右且 ∑li>∑1l−1\sum_l^i>\sum_1^{l-1}。
  3. 一个向左的人一定会胜利当且仅当他是可能胜利的人并且他右边没有可能胜利的人。

因此我们预处理出前缀和 sum\text{sum} 和 ll 数组,还有一个 rir_i 表示max⁡ri\max r_i 使得 lri≤il_{r_i}\le i。因此 rir_i 后面的人只能向右走,否则就会成为 ii 右边的可能胜利的人。

fif_i 表示 ii 后面部分的方案数,fi=∑j=i+1rifjf_i=\sum_{j=i+1}^{r_i}f_j。fn=2f_n=2 因为不管 nn 初始是往左还是往右,本质都是往左走。对于 [1,l−1][1,l-1] 的数,可以随便排,方案为 2l−12^{l-1}。最终答案 2l−1fi2^{l-1}f_i。双指针维护一下可以 O(n)O(n)。

T2 sociology

每次行走,都是执行一次 x←x+⌈ai−x2⌉x\gets x+\lceil \frac{a_i-x}{2}\rceil。

发现这个向上取整很烦,不妨假设它没有。

以下 a1a_1 指 xx 和第一个地位大于自己的人的地位之差,a2a_2 指第一个和第二个之差,以此类推。

模拟一下走 33 次的过程:a1/2+(a2−a1/2)/2+(a3−(a1/2+(a2−a1/2)/2))/2=a1/8+a2/4+a3/2a_1/2+(a_2-a_1/2)/2+(a_3-(a_1/2+(a_2-a_1/2)/2))/2=a_1/8+a_2/4+a_3/2。

发现这个 a1a_1 会越变越小,不超过 log⁡2109\log_2 10^9 次,就会缩小到 00。而且 a2,a3,…a_2,a_3,\dots 都是不会变的,每次查询只有 a1a_1 是会改动的,a2,a3,…a_2,a_3,\dots 可以预计算好不会变,说明走出足够多步后 a1a_1 的影响就会消掉,然后我们就可以利用预计算好的信息求出答案。

这就是我的赛时代码,如果走到预计算好答案的位置那么就可以直接出答案。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,q,a[N],p[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>t>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    mp[0]=1;
    for(int i=1,x=0;i<=n;i++){
        x+=(a[i]-x+1)/2;
        p[i]=x,mp[x]=1;
    }
    for(int i=1,x,y;i<=q;i++){
        cin>>x>>y;
        y=n-y+1;
        int l=1,r=n;
        while(l<r){
            int mid=(l+r)/2;
            if(a[mid]<=x)l=mid+1;
            else r=mid;
        }
        if(a[l]<=x||l>y){
            cout<<"0\n";
            continue;
        }
        int ans=0,xx=x;
        for(;l<=y;l++){
            if(x==p[l-1]){
                ans=p[y]-xx;
                break;
            }
            x+=(a[l]-x+1)/2;
            if(l==y)ans=x-xx;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

随机数据下已经完全没问题了,在非随机数据下会退化至 O(nq)O(nq) 导致 TLE。

其原因就是这个向上取整,导致并不能走到预计算好答案的地方,而是永远会比这个位置多 11。

注意到 ai−xa_i-x 为偶数时,向上取整相当于没有执行,这时我们就可以走到预计算好答案的地方。因此使本代码退化的构造方式为构造 ai−xa_i-x 始终为奇数。

因此预处理 nxti\text{nxt}_i 表示 ii 后面第一个 ai−xa_i-x 为偶数的位置(不存在则为 n+1n+1)。之后就可以愉快地通过本题了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n,q,a[N],p[N],nxt[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>t>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1,x=0;i<=n;i++){
        x+=(a[i]-x+1)/2;
        p[i]=x;
    }
    nxt[n+1]=n+1;
    for(int i=n;i>=1;i--){
        if((a[i]+p[i-1])&1)nxt[i]=i;
        else nxt[i]=nxt[i+1];
    }
    for(int i=1,x,y;i<=q;i++){
        cin>>x>>y;
        y=n-y+1;
        int l=1,r=n;
        while(l<r){
            int mid=(l+r)/2;
            if(a[mid]<=x)l=mid+1;
            else r=mid;
        }
        if(a[l]<=x||l>y){
            cout<<"0\n";
            continue;
        }
        int xx=x;
        for(;l<=y;l++){
            if(x==p[l-1]){
                x=p[y];
                break;
            }
            if(x==p[l-1]+1){
                x=p[y]+(nxt[l]>y);
                break;
            }
            x+=(a[l]-x+1)/2;
        }
        cout<<x-xx<<'\n';
    }
    return 0;
}

T3 geography

没做,听说是一道很烦的题。

T4 linguistics

O(n3)O(n^3) 做法可以通过,因此讲一下 O(n3)O(n^3) 做法。

fi,jf_{i,j} 表示考虑 AA 的前 ii 段以及 BB 的前 jj 段的 LCS。

首先 fi,j←max⁡(fi−1,j,fi,j−1)f_{i,j}\gets\max(f_{i-1,j},f_{i,j-1})。

然后如果 ai=bja_i=b_j 的话,还可以继续转移。

设 ai=bj=ca_i=b_j=c,用两个指针 k,lk,l 往前找,Ak…iA_{k\dots i} 和 Bl…jB_{l\dots j} 有多少个 cc 字符(分别设为 x,yx,y)。

因此转移为 fi,j←fk−1,l−1+min⁡(x,y)f_{i,j}\gets f_{k-1,l-1}+\min(x,y)。

试想一下如果 x>yx>y 那么继续移动 kk 指针往前是没有意义的,因为 min⁡(x,y)\min(x,y) 不会改变。因此比较 x,yx,y 的大小来决定移动哪个指针。

时间复杂度 O(n3)O(n^3),数据水可以通过。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int T,t,n,m,a[N],b[N],p[N],q[N],f[N][N],pre[2][N],lst[N<<1];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i]>>p[i];
    for(int i=1;i<=m;i++)cin>>b[i]>>q[i];
    for(int i=1;i<=n+m;i++)lst[i]=0;
    for(int i=1;i<=n;i++){
        pre[0][i]=lst[a[i]];
        lst[a[i]]=i;
    }
    for(int i=1;i<=n+m;i++)lst[i]=0;
    for(int i=1;i<=m;i++){
        pre[1][i]=lst[b[i]];
        lst[b[i]]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]!=b[j])continue;
            int k=i,l=j,x=p[i],y=q[j];
            while(k>0&&l>0){
                f[i][j]=max(f[i][j],f[k-1][l-1]+min(x,y));
                if(x<y)x+=p[k=pre[0][k]];
                else y+=q[l=pre[1][l]]; 
            }
        }
    }
    cout<<f[n][m]<<'\n';
}
int main(){
    cin>>t>>T;
    while(T--)solve();
    return 0;
}

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC