CSP-J模拟赛3—总结
_Luk_
·
·
个人记录
CSP-J模拟赛3—总结
2025.10.3
王语曦
方法：
|
方法 |
考场得分 |
考场用时 |
| T1 |
暴力 |
100pts |
35min |
| T2 |
二分 |
50pts |
45min |
| T3 |
暴力 + 二分 |
24pts |
35min |
| T4 |
搜索 + 数学 |
0pts |
25min |
丢分原因：
T1：
#### T2：
$50pts$，在考试的时候直接暴力去做，看到了数据特别大但是想不到二分做法（大概是不够熟练吧），于是直接暴力去做，只得了一半的分，后面想过优化但是忘记怎么优化了。
#### T3：
$24pts$，骗分得的。在考试的时候写了代码，调试的时候电脑突然卡了，dev 也点不动，保存不了，我就简单记了一下思路然后重启了，结果重启之后想不起来思路了（红温），那个时候时间也不多了，我就先去思考最后一道题目了。
#### T4：
$0pts$，考试的时候题面有点没读懂，就理解错了，所以代码思路也就错了，下来之后找其他人问了一下，大概知道了题目意思也想了一种方法 dfs。
### T1：[number](http://bbcoj.cn/contest/1013/problem/T1/full-screen) 优美的数
#### 题意：
题面意思就是只要这个数中含有数字 $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](http://bbcoj.cn/contest/1013/problem/T2/full-screen) 异或
#### 题意：
给 $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](http://bbcoj.cn/contest/1013/problem/T3) 分身术
#### 题意：
求一个区间地址，使 $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](http://bbcoj.cn/contest/1013/problem/T4/full-screen) 种树
#### 思路：
用 dfs 去搜索（只是想到了这种思路，还没有去实现）。