CSP2025模拟赛1（2025.7.23）

From nfls

T1（easy,100%）

link
简单贪心+模拟。

T2 （mid,90%）

题意
给定两个长度为 $n$ 的数组 $A$ 和 $B$，对于所有的 $a_i+b_j$ 从小到大排序，并输出第 $L$ 个到第 $R$ 个数。   $1\le n\le 10^5,1\le L\le R\le n^2,R-L<10^5,1\le A_i,B_i\le 10^9$

思路
首先会想到一个弱化版：输出序列中前 $n$ 个数。
这就直接小根堆堆优化模拟即可，堆中维护 $n$ 个数。这启示我们如果知道排第 $L$ 的数那么 $O(nlogn)$ 就可以知道答案。
由于单调性，考虑二分第 $L$ 个数的值。只需要知道当前这个二分值有多少个数小于等于它即可。将 $A,B$ 从小到大排序，遍历每个 $A_i$ ，发现 $B$ 中合法的数的个数是单调不升的，可以不必二分查找，（本人因为没发现这一性质 -> TLE 90pts） ，复杂度为 $O(n)$ 的。

反思
优化代码时注意发现性质以减少不必要的运算。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;

int n;
ll a[maxn],b[maxn];
ll Calc(ll x){
	int j=0;
	while(j<n&&a[1]+b[j+1]<=x) j++;
	ll s=0;
	for(int i=1;i<=n&&j>0;i++){
		while(j>0&&a[i]+b[j]>x) j--;
		s+=j;
	}
	return s;
}

int Get_(ll x,ll y){
	int l=0,r=n+1,mid;
	while(l+1<r){
		mid=(l+r)>>1;
		if(x+b[mid]>=y) r=mid;
		else l=mid;
	}
	return r;
}

struct NODE{ ll w,pt,pt2; };

struct CMP{
	bool operator () (const NODE &u,const NODE &v){
		return u.w>v.w;
	}
};
priority_queue<NODE,vector<NODE>,CMP>q;
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout); 
	ll tl,tr; scanf("%d%lld%lld",&n,&tl,&tr);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%lld",&b[i]);
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	ll l=0,r=a[n]+b[n]+1,mid;
	while(l+1<r){
		mid=(l+r)>>1;
		if(Calc(mid)>=tl) r=mid;
		else l=mid;
	}
	ll tmpr=Calc(r);
	if(tmpr>=tr){
		for(ll i=tl;i<=tr;i++)
			printf("%lld ",r);
		return 0;
	}
	else{
		for(ll i=tl;i<=tmpr;i++)
			printf("%lld ",r);
		r++; int j;
		for(int i=1;i<=n;i++){
			int j=Get_(a[i],r);
			if(j<=n) q.push({a[i]+b[j],i,j});
		}
		int pos,pos2;
		for(ll i=tmpr+1;i<=tr;i++){
			printf("%lld ",q.top().w);
			pos=q.top().pt,pos2=q.top().pt2+1;
			q.pop();
			if(pos2<=n) q.push({a[pos]+b[pos2],pos,pos2});
		}
	}
	return 0;
}

T3 （mid,30%）

link
题意
求两个序列 $A,B$ 的最长上升公共子序列长度。   $1\le n\le 5000$

思路
有一个 $O(n^4)$ 暴力，设 $f_{i,j}$ 表示 $A_i==B_j$ 且以他们结尾的最大长度。$f_{i,j}=max(f_{a,b}+1)$ ，注意 $A_a==B_{b}and{A}_a<A_i$ 。
发现 $i,j$ 两维没什么区别，所以优化状态空间变成 $O(n)$ 就好，改记 $f_i$ 表示以 $i$ 结尾的最大长度，转移类似，时间复杂度降为 $O(n^2)$ 。

思路
考场上没时间想了，转移的方式一定程度上影响了状态的优化。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
int a[maxn],b[maxn],f[maxn];
int main(){
	freopen("lcis.in","r",stdin);
	freopen("lcis.out","w",stdout); 
	int n; cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int m; cin>>m;
	for(int i=1;i<=m;i++)
		cin>>b[i];
	int ans=0;
	for(int i=1;i<=n;i++){
		int ma=0;
		for(int j=1;j<=m;j++){
			if(a[i]==b[j]){
				f[j]=max(f[j],ma+1);
				ans=max(ans,ma+1);
			}
			else if(a[i]>b[j]) ma=max(ma,f[j]);
		}
	}
	cout<<ans;
	return 0;
}

T4 （hard,40%）

link
题意
有 $m$ 个球排成一排，其中 $n$ 个球在游戏前已经被取走了，游戏照如下原则直到球取完为止：

1. 找到最长的一段连续的没被取走的球，如果有多段，选择最左边的一段；
2. 取这段中最中间的一个球，如果长度是偶数，那么，取较左的一个；

有 $q$ 次询问，求第 $Q_i$次拿了哪个球，$Q_i$ 是递增的。   $1\le m\le 10^{14},1\le q,m\le 10^5,n\le m,Q_q\le m$

思路
$m$ 很大啊，考虑记录连续段的信息，因为连续段的数量是 $n+q$ 级别的。我们称拿走 $n$ 个球后原序列分成的所有连续段为 主要段 。有一个性质：大小为 D 的主要段只会被分成最多 logD 种不同大小的子段。
对于某次询问 $i$ ，如果知道答案原来所在的主要段，那就直接暴力模拟拆解就好了。

对于每一个主要段，我们能够很轻松地算出它被分割的整个过程中会被分成多少种大小的子段，以及每一种大小的子段分别有多少个。对于每个主要段，我们通过一个三元组(段的长度，段的数量，所属的主要段)来描述它的子段们。
我们将每个段的每个三元组都放在一个序列 $S$ 里面，并将这个序列按照长度（降序）为第一关键字，所属段（从左到右）为第二关键字排序。得到这个序列之后，我们不仅能够确定第 $X$ 个被取出的球所在的当前段的大小 $L$，还能够确定当前段所属的主要段是哪一个。
接下来，我们只需要确定当前段在主要段的哪个位置就可以了。从大的排过序的序列中，我们能够得到当前段在当前主要段里所有长度为 $L$ 的段之中是第 $K$ 个被拆开成长度为 $L$ 的段。这个时候，我们就可以不用管别的主要段了。
让我们重新考察一下一个段被拆开的过程：当第一个球被拿走的时候，它分裂成了两个部分，所有左边长度为 $L$ 的子段都会在右边长度为 $L$ 的子段之前被拆开。所以，如果左边将会出现的长度为 $L$ 的子段的个数 $\ge K$，我们就去左边查找答案。不然，（设左边长度为的子段个数为 $P$），我们就去右边查找序数为的长度为 $(K-P)$ 的子段。就这样分治下去，直到我们当前正在查找的段长度为停止，返回答案。
题解链接（不想写了）

时间复杂度大概为 $O(nlo{g}^{2}m)$ 。

反思
有点难的一道题，听完讲解后还是觉得很难。性质发现了还要会用。

代码

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;

map<ll,ll>f;
ll Dfs(ll x,ll y){//将长度为 x 的区间拆解为 长度 y 需要多少步 
	if(x<y) return 0;
	if(x==y) return 1;
	if(f.count(x)) return f[x];
	return f[x]=Dfs((x-1)/2,y)+Dfs(x/2,y); 
}

ll Query(ll l,ll r,ll len,ll lmt){
	ll mid=(l+r)>>1;
	if(r-l+1==len) return mid;
	ll k=Dfs(mid-l,len);
	if(k>=lmt) return Query(l,mid-1,len,lmt);
	else return Query(mid+1,r,len,lmt-k);
}

ll a[maxn];
struct NODE{ ll len,id; };
bool operator <(const NODE &a,const NODE &b){ return a.len!=b.len?a.len>b.len:a.id<b.id; }
map<NODE,ll>cnt;
int main(){
	freopen("ball.in","r",stdin);
	freopen("ball.out","w",stdout); 
	ll m,n,q; cin>>m>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i-1]+1<=a[i]-1) cnt[{a[i]-a[i-1]-1,i}]++; 
	}
	a[n+1]=m+1;
	if(a[n]+1<=m) cnt[{m-a[n],n+1}]++;
	while(q--){
		ll x; cin>>x;
		if(x<=n){
			cout<<a[x]<<"\n";
			continue;
		}
		while(1){
			auto now=*cnt.begin(); ll len=now.first.len,id=now.first.id;
			if(n+now.second<x){
				n+=now.second; cnt.erase(now.first);
				if((len-1)/2>=1) cnt[{(len-1)/2,id}]+=now.second;
				if(len/2>=1) cnt[{len/2,id}]+=now.second;
			}
			else{
				f.clear();
				cout<<Query(a[id-1]+1,a[id]-1,len,x-n)<<"\n";
				break;
			}
		}
	}
	return 0;
}

总结

3.3 h 4 problems 还是很紧，应该多放时间在 $T3$ 的，毕竟 $T3$ 比 $T4$ 可做，主要是 $T4$ 的暴力打得不够优秀没拿到分。DP 还是要多多练习！