10.4 代码源 2024 CSP-S 模拟赛 Day 9

省流：\(100+0+0+0=100\)

简称：唐诗

T1

先写了个暴力，然后在想怎么优化，然后想了个区间 DP 但是写的时候又不会了……

然后发现如果这一块数的二进制每一位都有一个数的这一位为 \(0\) 或者都相同，那么这些数合并起来一定最优，然后双指针搞，复杂度 \(O(30n)\)。（这么绕口）

赛后听别人说有规律：

所有数的与的和就是答案要求的数；

然后比一下就行了，复杂度 \(O(n)\)。

想想发现很对，跟我的有异曲同工之妙。

T2

一眼暴力，因为 \(n,m\le 100\)，然后懒得写看 T3 了。

T3

二次省流：\(2n\) 个输入但是 fd(i,1,n)，唐

赛时怎么调都不过，但是发现一个规律，就是被两个数中间那一段区间完全包含的数不能选，然后想了一个结论但是就过了第一个样例。

正解是按左端点排序+树状数组。

核心代码：

sort(p+1,p+n+1,my);fd(i,1,n)
{(f[i]+=ask(a[p[i]].l)+ask(a[p[i]].r)+2)%=mod;add(a[p[i]].r,f[i]);(ans+=f[i])%=mod;
}

然后树状数组要开 \(4\) 倍空间……

T4

第一眼只会暴力，但是写 T3 了就没写……

\(\LARGE{唐}\)