2025多校冲刺CSP模拟赛5

T1：小 Z 爱计数（count）

思路：

一道挂大分的签到题。

显然，我们要根据 \(a_i-a_{i-1}\) 值对输入数据进行排序，然后通过 \(a_i-a_{i-1}\) 与\(b_i-b_{i-1}\) 之间的值的比较来判断操作是否合法。这里我们根据 （题解） 是否使用 \(reset\) 键将操作划分为两种：

1. 使用 \(reset\) 键。那么显然当 \(b_i ≤ a_i-a_{i-1}-1\) 时成立

2. 不使用 \(reset\) 键。那么当 \(b_i-b_{i-1} ≤ a_i-a_{i-1}\) 为成立的充分条件。为什么是充分条件呢？因为我们不难发现：一个 \(+1\) 操作和一个 \(-1\) 操作合起来对值无影响。所以不等号两旁必须奇偶性相同才合法。

代码：

$code$

#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
const int N=1e6+5;
int T,c,n;
struct node{int a,b;bool operator<(const node &css)const{return a<css.a;}
}e[N];
signed main(){
//	freopen("count.in","r",stdin);
//	freopen("count.out","w",stdout);ios::sync_with_stdio(false);cin>>T;while(T--){cin>>c>>n;for(int i=1;i<=n;i++){cin>>e[i].a>>e[i].b;}sort(e+1,e+1+n);bool f=0;for(int i=1;i<=n;i++){if(abs(e[i].b-e[i-1].b)<=(e[i].a-e[i-1].a)&&((abs(e[i].b-e[i-1].b)%2)==((e[i].a-e[i-1].a)%2)));else if(e[i].a-e[i-1].a-1>=abs(e[i].b));else f=1;}if(f) cout<<"No"<<'\n';else cout<<"Yes"<<'\n';}return 0;
}

T2：小 Z 爱划分（partition）

思路：

确认过眼神，是我赛时想不出的式子转化。

首先暴力 \(dp\) 肯定不难想：

\[dp_i=\sum_{j=0}^{i-1}dp_j×(a_i⊕a_j)^2 \]

这玩意一眼不是正解，但是你说这又是异或又是平方的不太好优化。那我们就先把平方去掉找找思路。

那么式子就变为了

\[dp_i=\sum_{j=0}^{i-1}dp_j×(a_i⊕a_j) \]

然后我们得想想办法把异或变个样子，那我们不妨考虑 违拆 拆位，单独考虑每个二进制位，于是就有了下式：

\[dp_i=\sum_t \sum_{j=0}^{i-1} dp_j×2^t[ ~ a_i(t)_2 ≠ a_j(t)_2 ~ ] \]

其中 \(x(k)_2\) 表示 \(x\) 在二进制下的第 \(k\) 位 （ 此为不正规设定，并无科学依据，请勿模仿 ）

接下来，我们不妨令 \(sum_{x,y}\) 表示所有满足 \(a_k(x)=y\) 的 \(dp_k\) 之和。这时我们就成功的解决了不带平方的问题。

那么接下来我们烧烤如何把平方加上。众所周知，平方的展开式为

\[(a_1+a_2+...a_n)^2=\sum_{i=1}^n\sum_{j=1}^n a_i a_j \]

那我们何不直接将这式子代入 \(dp\) 式中。这样，我们就得到了

\[dp_i=\sum_{t_1,t_2} \sum_{j=0}^{i-1} dp_j×2^{t_1+t_2}[ ~ a_i(t_1)_2 ≠ a_j(t_1)_2∧a_i(t_2)_2 ≠ a_j(t_2)_2 ~ ] \]

同理，我们设 \(sum_{x_1,x_2,y_1,y_2}\) 表示所有满足 \(a_k(x_1)=y_1∧a_k(x_2)=y_2\)

然后我们就可以以 \(O(log^2 ~ a_i)\) 的时间复杂度完成这道题啦~~

代码：

$code$

#include<iostream>
#define int long long 
using namespace std;
const int N=2e5+5,M=31,mod=1e9+7;
int T,n,ans,a[N],s[N],sum[M][M][2][2];
signed main(){
//	freopen("partition.in","r",stdin);
//	freopen("partition.out","w",stdout);ios::sync_with_stdio(false);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]^a[i];for(int i=0;i<M;i++) for(int j=0;j<M;j++) sum[i][j][0][0]=1,sum[i][j][0][1]=sum[i][j][1][0]=sum[i][j][1][1]=0;for(int i=1;i<=n;i++){ans=0;for(int j=0;j<M;j++)for(int k=0;k<M;k++)ans=(ans+(1ll<<(j+k))%mod*sum[j][k][(((s[i]>>j)&1)^1)][(((s[i]>>k)&1)^1)]%mod)%mod;for(int j=0;j<M;j++)for(int k=0;k<M;k++)sum[j][k][((s[i]>>j)&1)][((s[i]>>k)&1)]=(sum[j][k][((s[i]>>j)&1)][((s[i]>>k)&1)]+ans)%mod;}cout<<ans<<'\n';}return 0;
}

注意： 第19行的 \(1ll\) 决定着你是 \(100 ~ pts\) 还是 \(20 ~ pts\)

T3：小 Z 爱优化（opti）

思路：

我们可以将题面转化为：

我们有 \(2n-1\) 块位置不能变的多米诺骨牌，这些多米诺骨牌的长度为 \(a_i\) 或 \(a_i + a_{i-1}\)，我们需要用这些多米诺骨牌平铺整个区间，求多米诺骨牌的长度值差最小为多少.

由于最小值和最大值都是在变化的所以我们很难进行一些操作。那我们不妨枚举最小值，然后一心一意地最小化最大值就好了。

然后我们就可以愉快地考虑 \(dp\) 了。我们设 \(dp_i\) 表示前 \(i\) 个多米诺骨牌最小化的最大值。 \(dp\) 式子也不难想

\[dp_i=min\{max\{dp_{i-1},a_i\},max\{dp_{i-2},a_i+a_{i-1}\}\} \]

但是显然，我们现在是无法 \(AC\) 的，所以我们要考虑如何优化。

我们可以仿照矩阵乘法抽象出一个以 \((min,max)\) 为运算的广义矩阵乘法：

\[\left[ \begin{matrix} dp_i\\ dp_{i-1} \\ \end{matrix} \right] = \left[ \begin{matrix} a_i & a_i + a_{i-1}\\ -∞ & ∞\\ \end{matrix} \right] \left[ \begin{matrix} dp_{i-1}\\ dp_{i-2}\\ \end{matrix} \right] \]

说个人话点的理解，就是把原来矩阵乘法中的乘法变成取 \(max\) ，把原来的加法变成取 \(min\) 。

正当我们由于如何计算时，线段树维护矩阵乘就闪亮登场啦~~ （其实就是线段树上的每一个节点存一个矩阵啦）

然后我们就可以以 \(O(\sum n ~ log ~ n)\) 的时间复杂度 \(AC\) 啦~~

还有另一种做法，咱就不写了，不过还是粘一下题解叭~~ 请看VCR：

代码：

$code$

#include<iostream>
#include<algorithm>
#define int long long
#define lid (id<<1)
#define rid (id<<1|1)
using namespace std;
const int N=2e5+5,inf=1e18;
int T,n,a[N],cnt,ans;
struct wutong{int x,y,z;bool operator<(const wutong &css)const{return z<css.z;}
}w[N<<1]; 
struct jade{int a,b,c,d;jade operator*(const jade &css)const{return {max(min(a,css.a),min(b,css.c)),max(min(a,css.b),min(b,css.d)),max(min(c,css.a),min(d,css.c)),max(min(c,css.b),min(d,css.d))};}//可以类比正常的来理解矩阵乘法 
}t[N<<2];
inline void build(int id,int l,int r){if(l==r){t[id]={-inf,inf,-inf,-inf};return ;}int mid=(l+r)>>1;build(lid,l,mid);build(rid,mid+1,r);t[id]=t[lid]*t[rid];
}
inline void update(int id,int l,int r,int x,int flag,int val){if(l==r){if(flag) t[id].c=val;else t[id].a=val;return ;}int mid=(l+r)>>1;if(x<=mid) update(lid,l,mid,x,flag,val);else update(rid,mid+1,r,x,flag,val);t[id]=t[lid]*t[rid];
}
signed main(){
//	freopen("opti.in","r",stdin);
//	freopen("opti.out","w",stdout);ios::sync_with_stdio(false);cin>>T;while(T--){cin>>n;cnt=0,ans=inf;for(int i=1;i<=n;i++) cin>>a[i],w[++cnt]={i,0,a[i]},w[++cnt]={i,1,a[i-1]+a[i]};sort(w+1,w+1+cnt);build(1,1,n);for(int i=1;i<=cnt;i++){update(1,1,n,w[i].x,w[i].y,w[i].z);ans=min(ans,w[i].z-max(t[1].a,t[1].c));}cout<<ans<<'\n';}return 0;
}

T4：小 Z 爱考试（exam）

嘿嘿，一如既往地不会啦~~

后言

像在说梦话，乱七八糟，并且莫名其妙地开始煽情而且疑似有病句。

总之，别骂太狠。【拜托🙏】

🌹鲜花🌹

就像那句歌词所言，
“我希望你被爱着，我希望你要快乐”
无论你是谁
同班同学也好，学哥学姐也好，学弟学妹也好
还是素未谋面的人也罢
即使我们之间可能并未有过深的交情
但我还是想给予你最真挚地祝愿
或许我们之间有过一些小矛盾，也可能你有过某些时刻单方面的看我不爽
这些都没有关系
它们只能证明我们或许在某些事情上的观念，喜好和处理方式不同
但这并不意味着我或你不值得人间美好
如今山河无恙、万家灯火
同为华夏儿女
我希望你健康快乐，积极乐观、永远对未来、生活和自己充满希望
就像鲁迅说的那样
“愿中国青年都能摆脱冷气，只是向上走”