CSP-S2024 游记
mmh08100566
·
·
生活·游记
总体上来说考的还行吧，（比去年
考点在北理工，有一说一，大学的环境还是比中学好很多的。
| 题号 |
估分 |
| T1 |
100 |
| T2 |
100 |
| T3 |
20 |
| T4 |
45 |
| 总分 |
220 |
感觉题比去年简单，一等的分数线应该会高不少，现在一是怕挂分，二是怕分数线奇高无比。
考场感觉
T1 比去年还简单，在看错题面的情况下30min AC
T2 需要动动脑子，认真想一想前面的细节，后面的贪心也不太好想对，我感觉我就是歪打正着。
T3 之前听过？想不太清楚了，所以脑子里只有一个模糊的概念。在一维正解和二维暴力dp之间来回摇摆，一会觉得能写正解，一会又觉得做法假了。
T4 考场上就觉得是黑，题面都没看懂，想想还是算了吧，凭自己的实力也做不到这个题。
思路分享
T1 决斗
题面很简单，简化一下就是有一个r数组，对于每一个r_i，都可以找到一个j \ne i \text{且}r_j < r_i并删除。求最后数组长度的最小值。
思路，直接排序，对于每一个i，可以O(\log N)找到比i小的数的个数x，并从中取一个数删除，用ans记录之前删除过的数的数量。
如果ans < x，那么就是小于它的数还没有被删完，它可以再删掉一个，所以ans++。
最后n-ans即为答案。
考场代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
int x=lower_bound(a+1,a+1+n,a[i])-a-1;
if(ans<x) ans++;
}
printf("%d\n",n-ans);
return 0;
}
T2 超速检测
包想出来的。
~题意简述~（算了太长了不写了）
考场上能过我觉得没到蓝。
第一问，分六种情况：
$a=0,v_0 > V$ 从出现到$L$一直超速。
$a>0,v_0 \leqslant V$ 刚出现时没有超速，走过$\frac {V^2-{v_0}^2} {2a}\text{m}$后超速，直到$L$。
$a>0,v_0 > V$ 从出现到$L$一直超速。
$a<0,v_0 \leqslant V$ 永远不可能超速。
$a<0,v_0 > V$ 刚出现时超速，走过$\frac {V^2-{v_0}^2} {2a}\text{m}$后不超速。
为了更加清楚列个表表示超速区间：
||$a<0$|$a=0$|$a>0$|
|:-:|:-:|:-:|:-:|
|$v \leqslant V$|$\varnothing$|$\varnothing$|$(d_i+\frac {V^2-{v_i}^2} {2a_i},L]$|
|$v>V$|$[d_i,d_i+\frac {V^2-{v_i}^2} {2a_i})$|$[d_i,L]$|$[d_i,L]$|
通过观察，发现可以对$v$和$V$的大小关系先分两类，再根据$a$和$0$的大小再分两类。
据此，我们可以在$p$数组中二分两个位置：$d_i$和$d_i+\frac {V^2-{v_i}^2} {2a_i}$，这样便可以求出每个点的超速区间中有多少个检测点，只要区间不为空，那么这辆车就会被检测到超速，需要统计进答案中。
同时我们也处理出了所有的超速区间，第二问的题意简化一下其实就是有$n$个区间，要选出尽可能少的点使得每一个区间里都包含一个选出来的点。
做法就是很经典的区间贪心，先将区间按照左端点排序，依次遍历每一个区间，若与先前的区间有交，那么就不必为了它多选一个点。如果没有交，就从它开始新统计一个交集。
这两问就做出来了，这道题其实我很快就想出来了第二问的贪心，可是因为第一问的取等条件和`ifelse`的判断上写的不好导致浪费时间。（比如我在考场上写的代码分了六类，但是现在写游记的时候发现只用分四类。。。）
总结：过了，但是还是菜。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n,m,L;
int a[N],pp;
long long d[N],v[N],V;
double p[N];
int top,ans;
struct Range{
int l,r;
bool operator <(const Range &x)const{
return l<x.l;
}
void init(){
l=0,r=0;
}
}R[N],now;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d%d%lld",&n,&m,&L,&V);
for(int i=1;i<=n;i++) scanf("%lld%lld%d",&d[i],&v[i],&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&pp),p[i]=pp;
for(int i=1;i<=n;i++){
int c1=lower_bound(p+1,p+1+m,1.0*d[i])-p;
if(c1==m+1) continue;
if(a[i]==0){
if(v[i]>V)
R[++top]=(Range){c1,m};
}
else{
double x=d[i]+(V*V-v[i]*v[i])/(2.0*a[i]);
int c2;
if(a[i]>0){
c2=upper_bound(p+1,p+1+m,x)-p;
if(v[i]>V) R[++top]=(Range){c1,m};
else
if(c2!=m+1) R[++top]=(Range){c2,m};
}
else{
c2=lower_bound(p+1,p+1+m,x)-p-1;
if(v[i]>V&&c1<=c2) R[++top]=(Range){c1,c2};
}
}
}
printf("%d ",top);
sort(R+1,R+1+top);
for(int i=1;i<=top;i++){
if(R[i].l<=now.r){
now.l=max(R[i].l,now.l);
now.r=min(R[i].r,now.r);
}
else ans++,now=R[i];
}
printf("%d\n",m-ans);
memset(d+1,0,sizeof(d));
memset(a+1,0,sizeof(a));
memset(v+1,0,sizeof(v));
memset(p+1,0,sizeof(p));
for(int i=1;i<=top;i++) R[i].init();
top=ans=0;
now.init();
}
return 0;
}
```
又臭又长。。。
### [T3 染色](https://www.luogu.com.cn/problem/P11233)
暴力深搜，没啥可说的
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,a[N],n;
int now[N];
long long dp[N],ans;
vector<long long> ve[N];
void dfs(int dep,long long sc){
if(dep==n+1){
ans=max(ans,sc);
return;
}
now[dep]=1;
for(int i=dep-1;i>=0;i--)
if(now[i]||i==0){
if(a[i]==a[dep])
dfs(dep+1,sc+a[dep]);
else dfs(dep+1,sc);
break;
}
now[dep]=0;
for(int i=dep-1;i>=0;i--)
if(!now[i]||i==0){
if(a[i]==a[dep])
dfs(dep+1,sc+a[dep]);
else dfs(dep+1,sc);
break;
}
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
if(n<=15){
dfs(1,0);
printf("%lld\n",ans);
ans=0;
continue;
}
for(int i=1;i<=n;i++) ve[a[i]].push_back(i);
for(int i=1;i<=n;i++){
int x=(int)(lower_bound(ve[a[i]].begin(),ve[a[i]].end(),i)-ve[a[i]].begin())-1;
for(int j=0;j<=x;j++){
dp[i]=max(dp[i],max(dp[ve[a[i]][j]-1],dp[ve[a[i]][j]+1]));
}
if(x>=0) dp[i]+=a[i];
dp[i]=max(dp[i],dp[i-1]);
}
printf("%lld\n",dp[n]);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) ve[i].clear();
}
return 0;
}
```
前面是$2^n$暴力，后面试图跟了一个$O(n)$的dp，可惜爆0。
T4没啥可说的，甚至没交。。。。
遗憾离世