CSP-J模拟赛3—总结

2025.10.3

王语曦

方法：

	方法	考场得分	考场用时
$T1$	暴力	$100pts$	$35min$
$T2$	二分	$50pts$	$45min$
$T3$	暴力 + 二分	$24pts$	$35min$
$T4$	搜索 + 数学	$0pts$	$25min$

丢分原因：

T1：

100pts

，不说了。

T2：

50pts

，在考试的时候直接暴力去做，看到了数据特别大但是想不到二分做法（大概是不够熟练吧），于是直接暴力去做，只得了一半的分，后面想过优化但是忘记怎么优化了。

T3：

24pts

，骗分得的。在考试的时候写了代码，调试的时候电脑突然卡了，dev 也点不动，保存不了，我就简单记了一下思路然后重启了，结果重启之后想不起来思路了（红温），那个时候时间也不多了，我就先去思考最后一道题目了。

T4：

0pts

，考试的时候题面有点没读懂，就理解错了，所以代码思路也就错了，下来之后找其他人问了一下，大概知道了题目意思也想了一种方法 dfs。

T1：number 优美的数

题意：

题面意思就是只要这个数中含有数字

7

，或者是

7

的正整数倍就是个优美的数，求第

i

个优美的数。

思路：

直接暴力，他的

n \le 2021

，完全不用担心超时，直接从第一个优美的数到第

2021

个优美的数算出来，再输出就可以了，非常的

easy

。

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=2030;
int a[N],k=0;
vector<int> v; //是优美数就存进来 
bool HS(int m){
	while(m){
		int n=m%10;
		if(n==7) return true;
		m/=10;
	}
	return false;
}
void ym(){
	for(int i=1;i<=5477;i++){
		if(v.size()==2021) return ;
		if(HS(i)||i%7==0) v.push_back(i); 
	}
}
int main(){
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	int T;cin>>T;
	int M=T; 
	while(M--){k++;cin>>a[k];}
	ym();
	for(int i=1;i<=T;i++) cout<<v[a[i]-1]<<'\n';
	return 0;
}

T2：xor 异或

题意：

给

n

个数和一个数

k

，求这

n

个数之中两数异或值为

k

的不同组的个数。

思路：

50pts

：先给数组

a

排一下序，然后直接双重循环遍历数组

a

，算

a_i

和

a_j

的异或值是否为

k

，是的话

ans++

，最后输出

ans \times 2

就可以了（每组两个数字可以互换）。

100pts

：根据异或的性质，可以知道

a \oplus b = c

等价于

a \oplus c = b

，所以就不用专门费工夫去求

b

的值了，然后二分查找，靠左和靠右分别找出两个下标，最后输出

ans+=p1-p2+1

就可以了。

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
int a[1000005],n,k;
int lower(int f){ //靠左查找
    int l=1,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(a[mid]>=f) r=mid;
        else l=mid+1;
    }
    if(a[l]!=f) return 1;
    else return l;
}
int upper(int f){ //靠右查找
    int l=1,r=n;
    while(l<r){
        int mid=l+r+1>>1;
        if(a[mid]>f) r=mid-1;
        else l=mid;
    }
    if(a[l]!=f) return 0;
    else return l;
}
int main(){
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    cin>>n>>k;int ans=0;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        int f=a[i]^k; //a^c=b 等价于 a^c=b 
        int p1=upper(f);
        int p2=lower(f);
        ans+=p1-p2+1;
    }
    cout<<ans;
	return 0;
}

T3：separation 分身术

题意：

求一个区间地址，使

min(a[i],a[j])

，和

max(b[i],b[j])

的差值大于等于

k

，同时使得

i

与

j

的差最小。

思路：

24pts

：骗分，输出 So Sad! 即可。

30pts

：按照题意直接模拟即可，在老师的数据下可以获得

36pts

。

60pts

：把

30pts

的循环优化一下，就可以有

60pts

了。

80pts

：用一个 dp 去选择最优的地址，然后用一个二分，确定

l

的地址，去便利

r

的地址，得到

ans

的最小值。（在老师的数据下可以 AC）。

100pts

：用两个双向队列去存取数组中的元素，然后找到最小的

t

。

$100pts$ （实际上是 $80pts$ ）Code：

CPP

#include<bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
int n,k;
int read(){
    int s=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
    return s*f;
}
const int N=1e6+5;
int dp[2][N][25];
//dp[0][][] => a 序列
//dp[1][][] => b 序列 
bool check(int l,int r){ //左端点和右端点 
	int x=log2(r-l+1);
	int minn=min(dp[0][l][x],dp[0][r-(1<<x)+1][x]);
	int maxn=max(dp[1][l][x],dp[1][r-(1<<x)+1][x]);
	return minn+k<=maxn;
}
int a[N],b[N],ans=1e9+5;
int main(){
    freopen("separation.in","r",stdin);
	freopen("separation.out","w",stdout);
	n=read(),k=read();
	_for(i,1,n) dp[0][i][0]=read();
	_for(i,1,n) dp[1][i][0]=read();
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			dp[0][i][j]=min(dp[0][i][j-1],dp[0][i+(1<<j-1)][j-1]); //最小值 
			dp[1][i][j]=max(dp[1][i][j-1],dp[1][i+(1<<j-1)][j-1]); //最大值 
		}
	}
	//枚举左端点，二分右端点
	_for(i,1,n){
		int l=i,r=n+1; //r => 合法的序列
		while(l<r){
			int mid=(l+r)>>1;
			if(check(i,mid)) r=mid;
			else l=mid+1;
		}
		if(r<=n) ans=min(ans,r-i+1);
	} 
	if(ans>n) cout<<"So Sad!";
	else cout<<ans;
	return 0;
}

AC Code：

CPP

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int read(){
    int s=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
    return s*f;
}
int a[MAXN],b[MAXN],ans=1e9;
deque<int> dmin,dmax;
#define _for(i,a,b) for(int i=(a);i<=(b);i++)
int main(){
	freopen("separation.in","r",stdin);
	freopen("separation.out","w",stdout);
	int n,k;n=read(),k=read();
	_for(i,1,n) a[i]=read();
	_for(i,1,n) b[i]=read();
	int r=1; //区间右边的指针 
	_for(l,1,n){
		while(r<=n&&(dmin.empty()||a[dmin.front()]+k>b[dmax.front()])){
			while(!dmin.empty()&&a[dmin.back()]>a[r]) dmin.pop_back();
			dmin.push_back(r);
			while(!dmax.empty()&&b[dmax.back()]<b[r]) dmax.pop_back();
			dmax.push_back(r);
			r++;
		}
		if(a[dmin.front()]+k<=b[dmax.front()]) ans=min(ans,r-l);
		if(!dmin.empty()&&dmin.front()==l) dmin.pop_front();
		if(!dmax.empty()&&dmax.front()==l) dmax.pop_front();
	}
	if(ans>n) cout<<"So Sad!";
	else cout<<ans;
	return 0;
}

T4：tree 种树

思路：

用 dfs 去搜索（只是想到了这种思路，还没有去实现）。

CSP-J模拟赛3—总结

文章操作

CSP-J模拟赛3—总结

2025.10.3

王语曦

方法：

丢分原因：

T1：

T2：

T3：

T4：

T1：number 优美的数

题意：

思路：

AC Code：

T2：xor 异或

题意：

思路：

AC Code：

T3：separation 分身术

题意：

思路：

$100pts$ （实际上是 $80pts$ ）Code：

AC Code：

T4：tree 种树

思路：

相关推荐

评论

CSP-J模拟赛3—总结

文章操作

CSP-J模拟赛3—总结

2025.10.3

王语曦

方法：

丢分原因：

T1：

T2：

T3：

T4：

T1：number 优美的数

题意：

思路：

AC Code：

T2：xor 异或

题意：

思路：

AC Code：

T3：separation 分身术

题意：

思路：

100pts100pts100pts（实际上是 80pts80pts80pts）Code：

AC Code：

T4：tree 种树

思路：

相关推荐

评论

$100pts$ （实际上是 $80pts$ ）Code：