CSP-S 2024 游记

9.22

初赛。来早了点，开雀，吃二。

天一的老同学啊！唠嗑。

进场。秒了第一页的题。没有困难的 linux 题，不慌了！接着看，哈希，不会，最小割计数，这是平面图！快排，前几天刚做过一道快排；后面不看了。

秒了所有选择题。哈希猜了个 O(n)，因为 \alpha\le 1。最小割直接暴力数了，转对偶图失败了。

阅读做的很顺。计算量好大。

完型怎么又是万恶的 Um_nik 大法。手玩了一下，发现这个二分可以简单地理解为线段树二分！那就对完了，怎么 4 个 A（伏笔）。

然后一眼看到了 0x?f。这不会啊，跳。做完了别的，这题猜一个 0xff。抄答题卡。

又做到这个题了，发现 update 里的东西我理解错了，改！然后手算 inf 的二进制形式，发现是 00011111000111110001111100011111，那就是 0x1f。这里花了十几分钟啊！

出场估满分。结果再一想发现 upper_bound() 可以找不到，那 3 分没了啊！好像没别的扣分了。

9.24

97，符合预期。

10.26

快进到进考场。

13:57：电脑屏幕好暗，尝试在设置里找亮度，突然听到“不要动电脑，两点开始试机”的指令，吓了一跳。

14:05：写完了板子和快读，写了个快速幂学习编译命令。然后睡了二十分钟。

14:30：花五分钟读了一下题，大致体感如下：t1 看上去比较水，要不然二分一下就好了；t2 看都不想看；t3 似乎不太难，有个显然的 dp 待会儿想想优化；t4 是什么一坨玩意儿。怎么要对每个前缀求答案。怎么多测 256 组？？？ccf 你又线性卡对数是吧。

14:35：胡 t1。写了这个：先排序，然后被删掉的肯定是一个前缀，我们枚举前缀长度，找到用哪个点来删它即可。14:42 通过了样例，时间复杂度 O(n\log n)。

void Main(){
    cin>>n;
    REP(i,0,n)cin>>a[i];
    sort(a,a+n);
    int ans=n,x=0;
    REP(i,0,n){
        x=max(x,i+1);
        while(x<n&&a[x]<=a[i])++x;
        if(x>=n)break;
        ++x;--ans;
    }
    cout<<ans<<endl;
}

14:42：手刃加速度公式。发现超速是一段区间，先写第一问。讨论了 delta 的正负性，推了除法的上下取整，对着很强的样例 1 改对了。这下错不了了吧！

    while(n--){
        int pos,v,delta;
        cin>>pos>>v>>delta;
        if(delta==0){
            if(v>V)a.pb({pos,L});
        }else if(delta>0){
            if(v>V)a.pb({pos,L});
            else{
                int t=pos+(V*V-v*v)/(2*delta)+1;
                if(t<=L)a.pb({t,L});
            }
        }else{
            if(v>V){
                delta=-delta;
                int R=min(L,v*v/(2*delta)+pos);
                R=min(R,pos+(v*v-V*V+2*delta-1)/(2*delta)-1);
                if(pos<=R)a.pb({pos,R});
            }
        }
    }

??:??：写第二问。考虑一个 dp，f_i 表示选的最后一个点是第 i 个的时候最少选几个点。我们在最后多加一个必须选的点即可。考虑转移，限制只有：一个区间内必须包含一个点，于是相当于对于转移到 f_i 的 f_j 必须满足不存在区间 [l,r] 使得 j<l\le r<i。相当于 j\ge \max_{r\le i}l。于是转移是这个 \max 开始的区间 \min，由于这玩意单调，直接不带删双指针维护即可。欸这不是我们单调队列板子吗，那考的不错。15:19 通过，时间复杂度 O(T(n(\log n+\log q)+q))。瓶颈在排序和 upper_bound。

    sort(all(a));
    n=q;vector<int>b(n);
    REP(i,0,n)cin>>b[i];
    int x=0;vector<pii>c;
    for(auto [i,j]:a){
        while(x<n&&b[x]<i)++x;
        if(x<n&&b[x]<=j){
            c.pb({x,upper_bound(all(b),j)-b.begin()-1});
        }
    }
    ++n;
    vector<int>dp(n,0),lmn(n),mx(n,-1);
    for(auto [i,j]:c)mx[j+1]=max(mx[j+1],i);
    int cmx=-1,r=-1,mid=0,rmn=n;
    REP(i,0,n){
        cmx=max(cmx,mx[i]);
        if(cmx==-1){
            dp[i]=1;
            continue;
        }
        while(r<i-1)rmn=min(rmn,dp[++r]);//[l,mid)[mid,r]
        if(cmx>=mid){
            mid=r;lmn[mid]=n;rmn=dp[mid];
            for(int j=mid-1;j>=cmx;--j){
                lmn[j]=min(lmn[j+1],dp[j]);
            }
        }
        dp[i]=min(lmn[cmx],rmn)+1;
    }
    cout<<c.size()<<' '<<n-dp[n-1]<<endl;

15:20 胡 t3。考虑我们 P353 的 dp 优化：设 f_i 表示 i 与 i-1 颜色不同的最大收益。注意到这个转移只能是 i 开始的连续段颜色相同，一直到 j 是第一个不同的，于是 f_i\rightarrow f_j。贡献是 [a_{i-1}=a_j]a_j+\sum_{k=i}^{j-2}[a_k=a_{k+1}]a_k。写个平方试试水。

15:25 写完，一遍过了样例 1 和样例 2 的前两个点，后面 WA 了。找不到错。于是 这 就 开 始 写 拍 子 了。拍了一下发现错了，结果是 f_i\rightarrow f_{i+2} 的转移的特判写假了。也许是不需要特判的啊啊啊啊啊。

15:30 考虑优化。我们先找 a_{i-1}\neq a_j 时的转移，把后面的转移拆成前缀和：设 p_i=\sum_{k=2}^{i}[a_k=a_{k-1}]a_k，于是上面那玩意变成 p_{j-1}-p_{i}。然后这个转移就优雅地变成 p_{j-1}+\max{(f_i-p_i)}。求一下前缀 \max 即可。考虑 a_{i-1}=a_j 时，显然对每个值分别求一下前缀 \max 即可，具体类似。时间复杂度 O(Tn)。写了一下又挂了，拍不出错，结果死因是：g++ 1.cpp -o -O2。发现了之后一遍过了样例，跑得很快，时间 15:44。

int n;
int a[200005],f[200005],g[1000005],p[200005];
void Main() {
    cin>>n;
    REP(i,0,n)cin>>a[i];
    p[0]=0;
    REP(i,1,n)p[i]=p[i-1]+(a[i]==a[i-1]? a[i]:0);
    f[1]=0;
    REP(i,2,n)f[i]=f[i-1]+(a[i-1]==a[i-2]? a[i-1]:0);
    REP(i,0,n)g[a[i]]=-1e18;
    int mx=-1e18;
    REP(i,2,n){
        f[i]=max(f[i],f[i-1]+(a[i]==a[i-2]? a[i-2]:0));
        mx=max(mx,f[i-2]-p[i-2]);
        f[i]=max(f[i],mx+p[i-1]);
        if(i>2)g[a[i-3]]=max(g[a[i-3]],f[i-2]-p[i-2]);
        f[i]=max(f[i],g[a[i]]+p[i-1]+a[i]);
    }
    int ans=f[n-1],s=0;
    for(int i=n-2;i;--i){
        s+=a[i]==a[i+1]? a[i]:0;
        ans=max(ans,f[i]+s);
    }
    cout<<max(ans,s+(a[0]==a[1]? a[0]:0))<<endl;
}

16:10 一直到这会儿都在随机思考 t4，想不到任何 O(n\ \mathrm{poly}\log) 做法。然后脑子一抽发现对于任何全已知的子树和任何全未知的子树，胜者都是确定的；而同时包含已知和未知的子树一共只有 k 个。画了个图证明了一下这个结论，很兴奋，感觉 O(n\ \mathrm{poly}\log) 不就出来了吗。然后考虑转移，全已知的子树只有一个胜者，所以维护问号的个数和坐标和之后，剩下只有 O(k) 个东西，暴力合并是 O(k) 的，就做到了 O(nk^2)！写到 16:41 通过了所有样例。小插曲：样例 5 多测每个点跑 1s，理由是编译但是不保存。最后把样例 5 的点复制几百遍，跑 T=256 用时 27s，玩你妈。

17:10 在此之前，都在随机思考啊，想到了若干种 O(nk) 的做法，但是都写到一半头晕写不下去，感觉细节太太太多了。最后一个看上去最有前途的版本是：开桶维护，再维护一个清空标记。这个清空太难均摊了吧。想到了用 vector 维护所有需要清空的东西，但是为啥没写呢？最后写了 set 维护，因为这样没啥细节，时间复杂度 O(Tnk\log k)。也是调了很久才过样例啊啊啊啊啊！时间是 17:57，T=256 跑了 9s。

#include<bits/stdc++.h>
#define ll long long
#define REP(i,a,n) for(int i=(a);i<(int)(n);++i)
#define pb push_back
#define pii pair<int,int>
using namespace std;
int n,q,k;
int a[200005],A[200005],qr[200005];
bool D[20][200005];
int op[400005],b[400005];
void build(int l,int r,int d,int p){
    b[p]=D[d][l>>d];
    if(l==r){
        op[p]=l;
        return;
    }
    int m=(l+r)>>1;
    build(l,m,d-1,p*2+1);build(m+1,r,d-1,p*2+2);
    int x=op[p*2+1],y=op[p*2+2];
    if(x==-2||y==-2)op[p]=-2;
    else if(x==-1&&y==-1)op[p]=-1;
    else if(x>=0&&y>=0){
        if(b[p])op[p]=a[y]>=d? y:x;
        else op[p]=a[x]>=d? x:y;
    }else op[p]=-2;
}
struct winners{
    set<pii>a;
    int b;ll s;
    void init(){
        a.clear();b=s=0;
    }
    void add(int l,int r){
        b+=r-l+1;s+=1ll*(r-l+1)*(l+r+2)/2;
    }
    void Add(int x){a.insert({::a[x],x});}
    void cl(int d){
        while(a.size()&&a.begin()->first<d)a.erase(a.begin());
    }
    bool check(int d){
        return b==0&&a.begin()->first>=d;
    }
    ll calc(){
        ll res=s;
        for(auto i:a)res+=i.second+1;
        return res;
    }
}res;
void solve(int l,int r,int d,int p,int N){
    if(r<=N){
        res.init();
        res.Add(op[p]);
        return;
    }
    if(l>N){
        res.init();
        res.add(l,r);
        return;
    }
    int m=(l+r)>>1;
    if(m==N){
        res.init();
        if(b[p]){
            res.add(m+1,r);
            res.Add(op[p*2+1]);
        }else if(a[op[p*2+1]]>=d)res.Add(op[p*2+1]);
        else res.add(m+1,r);
        return;
    }
    if(N<m){
        solve(l,m,d-1,p*2+1,N);
        if(b[p])res.add(m+1,r);
        else{
            if(res.check(d))return;
            res.cl(d);
            res.add(m+1,r);
        }
    }else{
        solve(m+1,r,d-1,p*2+2,N);
        if(!b[p]){
            if(a[op[p*2+1]]>=d)res.init(),res.Add(op[p*2+1]);
        }else{
            if(res.check(d))return;
            res.cl(d);
            res.Add(op[p*2+1]);
        }
    }
}
void Main(){
    int r[4];
    REP(i,0,4)cin>>r[i];
    REP(i,0,n)a[i]=min(A[i]^r[(i+1)%4],k);
    build(0,(1<<k)-1,k,0);
    ll ans=0;
    REP(_,0,q){
        int x=qr[_],p=0,d=k;
        if(!x){
            ans^=_+1;
            continue;
        }
        while(x<(1<<(d-1)))--d,p=p*2+1;
        solve(0,(1<<d)-1,d,p,x);
        ans^=1ll*(_+1)*res.calc();
    }
    cout<<ans<<endl;
}
signed main(){
    cin>>n>>q;
    REP(i,0,n)cin>>A[i];
    REP(i,0,q)cin>>qr[i],--qr[i];
    k=1;while((1<<k)<n)++k;
    REP(i,1,k+1){
        string s;cin>>s;
        REP(j,0,(1<<(k-i))){
            D[i][j]=s[j]=='1';
        }
    }
    int tc;
    cin>>tc;q=1;
    while(tc--)Main();
    return 0;
}

18:00 测试了一下，T\le 16 跑了 0.6s，T\le 64 跑了 2.3s，那就是 376。瞪了一会儿好像没啥方便的优化，开始思考出去之后咋汇报成绩，然后去拍 t1 了。然后就结束了。代码长度是 889,2472,1553,3045，按题目编号排序。

18:31 左右两位高人开始高谈阔论。

• 你 AK 了吗？
• 没有啊，你 AK 了吗？
• 没有没有。zhk 肯定 AK 了。
• （此时我害怕极了）
• 我 t2 写了 5K！
• （此时我害怕极了，因为没听见是哪题，以为过了 t4）
• 5K 得了二三十分吧。
• （？？？）
• t2 不是板子题吗？先二分端点，然后线段覆盖，就解决了啊！
• 我 t4 胡乱写了点东西，不知道多少分啊。
• t3 呢？我一点也不会啊
• 我 t3 瞎写了个 dp 式子。竟然过样例了！O(n^2) 的！都不知道为什么是对的！来我给你看看。
• （这么菜？）
• 这次考线段树了吗？
• 没有吧。
• 我觉得 noip 会考线段树！
• noip 不会考线段树板子吧，就算考也只会考一个很难的题，然后需要用到线段树。所以会线段树也没什么用。除非他出线段树板子题。
• 唉，大佬啊，我还不会打线段树。
• ……（懒得听了）

回家路上发现大家 t1 怎么都是 dilworth 变成众数出现次数。我是不是假了？？？宣传 t3 线性做法，怒喷 t4 出题人。

自测 376，问题不大。把 t4 改成 O(nk) 只花了 20 分钟啊？？？为啥我考场上不写？？？

11.4

11:00：怎么查分变今天了。

13:00：怎么没有。怎么变 16:00 了。

16:00：怎么没有。怎么变 17:30 了。

17:27：怎么就有了？还是 376 没挂哦。