CSP-S2024游记
等待处分。。。
update：出分了，100+100+100+0=300.
Part 1: 考前
这次比赛基本上除了复习板子以外没作别的准备，盲目自信！
麻麻允许我考完试参加信息组团建，爽！
lmz和高一学弟们都提前进了考场，可惜没在华科门口留张全体合影。
我这次还是进入高二以来头一次穿着这么酷的衣服呢！自我感觉良好，就是有点小感冒。自备两包纸入场。
听 lzc 说freopen里的 "r" 和 "w" 是 read 和 write 的意思。我的天，长知识了！！紧接着发现好像只有我一个人不知道。/wq
Part 2: 考中
遇见 qwdb、phigy 和 寻逍遥2006 。在同学里面只有zcr和我同考场。
提前15分钟试机，发现自己连快读都不会写。还好旁边坐着的都是初中生，压力不太大。
提前5分钟公布了pdf密码。在开考后8分钟之内看完前三题题面并测完T1的大样例，相当于热个身。这个时候我甚至是用优先队列模拟的T1决斗过程。
（这个T1真的水的离谱）
看到T2要搞浮点数，果断任性看T3去了。
T3是熟悉的双色染色。想DP递推式的时候倔强地想要一口气把线段树优化后的版本的转移式推出来，被爆了。最后老老实实地写了一个没有优化的
树上维护的东西不是很能描述清楚……总之明明很简单却硬控了我大概20分钟。唐完了。优化后的版本可以把大样例 780ms 卡过。当时甚至没注意这个大样例只有 5 个 n=200000 的数据，欢天喜地的以为自己复杂度是对的，拍了九万组 n=2000 的数据验证正确性就走人了……
O2 优化救我！！！
接着回头熬T2。发现第一问就是半开半闭区间，取 eps=1e-7 把开区间转为闭区间，代码写成诗山。
第二问尽显我大唐风范。想了半天：测速仪都是离散的，这还能贪心？？
想了20分钟，发现居然可以二分，把测速仪变成连续的。
当时开心死了，于是忘记可以贪心，反而舍近求远，套了个我并不熟悉的差分约束。期间还忘记前缀和单调不降这个限制，建边调了半天。
第一遍用deque写的01边权bfs，寄了。
写第二遍的时候急了眼，用优先队列搜索的。md跟T2爆了！！！
写完T2之后，我在检查前三题和打最后一题暴力中选择了前者。突然发现T1求的就是众数出现次数，于是重写了一份装B。
最后就只剩下8分钟，于是在第四题代码下面即兴写了几行注释。我试着默写一下：
（回忆版）
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
//I do not have time to finish T4
//And the time now is 18:22
//Hope my conclusion for T1 is correct
//and wish I can get 280+ pts.
//PS: I miss you so!
}献上四题代码：
T1:
#include<bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
using namespace std;
inline int rd(){
int m=0;bool f=0;
char c=getchar();
while(!isdigit(c)) f^=(c=='-'),c=getchar();
while(isdigit(c)) m=(m<<1)+(m<<3)+(c^48),c=getchar();
return f?-m:m;
}
const int N=2e5+10;
int n,m,a[N],cnt[N];
signed main(){
ios::sync_with_stdio(false);
freopen("duel.in","r",stdin);
freopen("duel.out","w",stdout);
cin>>n;
int ans=0;
for(int i=1;i<=n;++i) cin>>a[i],ans=max(ans,++cnt[a[i]]);
cout<<ans;
return 0;
}T2:
#include<bits/stdc++.h>
//#define int long long
#define db double
#define pii pair<int,int>
using namespace std;
inline int rd(){
int m=0;bool f=0;
char c=getchar();
while(!isdigit(c)) f^=(c=='-'),c=getchar();
while(isdigit(c)) m=(m<<1)+(m<<3)+(c^48),c=getchar();
return f?-m:m;
}
const int N=1e5+10,M=1e6+10;
namespace zzy{
pii a[N];
int n,m,b[N],dis[N];
vector<int> v[N],c[N];
priority_queue<int,vector<int>,greater<int>> q;
bool vis[N];
void clear(){
for(int i=1;i<=m;++i) dis[i]=-M,vis[i]=0;
dis[0]=vis[0]=0;
n=m=0;
}
int solve(){
for(int i=0;i<=m;++i) v[i].clear(),c[i].clear();
for(int i=1;i<=n;++i){
a[i].first=lower_bound(b+1,b+m+1,a[i].first)-b;
a[i].second=upper_bound(b+1,b+m+1,a[i].second)-b-1;
v[a[i].first-1].push_back(a[i].second);
c[a[i].first-1].push_back(1);
}
for(int i=1;i<=m;++i) v[i-1].push_back(i),c[i-1].push_back(0);
q.push(0),vis[0]=1;
while(!q.empty()){
int x=q.top();
q.pop();
for(int i=0;i<(int)v[x].size();++i){
int y=v[x][i],z=c[x][i];
dis[y]=max(dis[y],dis[x]+z);
if(!vis[y]) vis[y]=1,q.push(y);
}
}
return m-dis[m];
}
//md 差分约束 我好愚蠢！
}
const db eps=1e-7;
int n,m,L,V,ans,T,sum[M];
db l[N],r[N];
signed main(){
ios::sync_with_stdio(false);
freopen("detect.in","r",stdin);
freopen("detect.out","w",stdout);
cin>>T;
int d,v,a;
while(T--){
ans=0;
zzy::clear();
cin>>n>>m>>L>>V;
for(int i=1;i<=n;++i){
cin>>d>>v>>a;
if(!a){
if(v>V) l[i]=d,r[i]=L;
else l[i]=1,r[i]=0;
}
else if(a>0){
if(v>V) l[i]=d,r[i]=L;
else{
if(V*V-v*v<(L-d)*2*a) l[i]=d+(db)(V*V-v*v)/2/a+eps,r[i]=L;
else l[i]=1,r[i]=0;
}
}
else{
a=-a;
if(v<=V) l[i]=1,r[i]=0;
else{
l[i]=d;
if(v*v-V*V>(L-d)*2*a) r[i]=L;
else r[i]=d+(db)(v*v-V*V)/2/a-eps;
}
}
}
//这都没爆精度真是奇迹
for(int i=0;i<=L;++i) sum[i]=0;
for(int i=1;i<=m;++i) cin>>a,++sum[a],zzy::b[++zzy::m]=a;
for(int i=1;i<=L;++i) sum[i]+=sum[i-1];
for(int i=1;i<=n;++i) if(sum[(int)floor(r[i])]-sum[(int)ceil(l[i])-1]){
++ans;
zzy::a[++zzy::n]=(pii){(int)ceil(l[i]),(int)floor(r[i])};
}
cout<<ans<<' '<<zzy::solve()<<'\n';
}
return 0;
}T3:
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
inline int rd(){
int m=0;bool f=0;
char c=getchar();
while(!isdigit(c)) f^=(c=='-'),c=getchar();
while(isdigit(c)) m=(m<<1)+(m<<3)+(c^48),c=getchar();
return f?-m:m;
}
const int N=3e5+10,M=1e6+10;
int n,T,a[N],id[M],val[M];
namespace zzy{
struct seg{int l,r,v,tag;}tr[N<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
void push_up(int x){
tr[x].v=max(tr[ls(x)].v,tr[rs(x)].v);
}
void push_down(int x){
if(tr[x].tag){
tr[ls(x)].v+=tr[x].tag;
tr[ls(x)].tag+=tr[x].tag;
tr[rs(x)].v+=tr[x].tag;
tr[rs(x)].tag+=tr[x].tag;
tr[x].tag=0;
}
}
void build(int x,int l,int r){
tr[x].l=l,tr[x].r=r,tr[x].v=tr[x].tag=0;
if(l==r) return;
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
}
void update(int x,int l,int r,int v){
if(tr[x].l>r||tr[x].r<l) return;
if(l<=tr[x].l&&tr[x].r<=r){
tr[x].v+=v;
tr[x].tag+=v;
return;
}
push_down(x);
update(ls(x),l,r,v);
update(rs(x),l,r,v);
push_up(x);
}
void reval(int x,int p,int v){
if(tr[x].l==tr[x].r){
tr[x].v=v;
return;
}
push_down(x);
if(p<=tr[ls(x)].r) reval(ls(x),p,v);
else reval(rs(x),p,v);
push_up(x);
}
int query(int x,int l,int r){
if(tr[x].l>r||tr[x].r<l) return -1;
if(l<=tr[x].l&&tr[x].r<=r) return tr[x].v;
push_down(x);
return max(query(ls(x),l,r),query(rs(x),l,r));
}
}
using namespace zzy;
signed main(){
ios::sync_with_stdio(false);
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
cin>>T;
while(T--){
for(int i=1;i<=n;++i) id[a[i]]=val[a[i]]=0;
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,0,n);
for(int i=1;i<n;++i){
int ret1=query(1,0,i-1),ret2=-a[i+1];
if(id[a[i+1]]) ret2=query(1,id[a[i+1]],id[a[i+1]]);
reval(1,i,max(ret1,ret2+a[i+1]));
if(max(ret1,ret2+a[i+1])>=val[a[i]]) val[a[i]]=ret2,id[a[i]]=i;
if(a[i+1]==a[i]) update(1,0,i-1,a[i+1]);
}
cout<<query(1,0,n-1)<<'\n';
}
return 0;
}T4:
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("arena.in","r",stdin);
freopen("arena.out","w",stdout);
return 0;
//I do not have time to finish this problem...
//The time now is 18:22
//Hope my T1's conclusion is correct
//And wish I can get 280+ pts.
//Please!
//PS: I miss you so!
}考完起立的时候听旁边初中哥讨论说所有测试点等分，他还以为T1都那么水了甚至有200分。我在一旁很尽力的在憋笑。
zrc 的T2校验码出了点问题，还好考后工作人员解决了。
发挥在意料之中吧。
Part 3: 考后
场外只跟自己高中同学讨论，好像除了我就只有 wmc 切了前三题，并且他还打了T4的暴力。
也是在这个时候我才发现自己究竟有多唐。md，查分约束！！！！
wmc的T3甚至是线性复杂度的。我好废物啊！
晚上团建的时候把这些都忘干净了。一起去来菜聚个餐，我和lmz去旁边的一家电玩城试了试打音游，剩下的人在王者五排。甚至用的是我的手机。
音游真好玩！
不过接着的密逃就有点拉胯了。我们几个人冒雨挺进密室馆，结果那个剧本还很烂。
更关键的是在密室里面被djw猥亵了！还被wmc强吻了！！！
南通好可怕。wmc在密室里面被电击，大快人心！
玩到11点半才回家。没有地铁，我们四个人合伙打车回家，路上看见luogu自测上面挂着橙绿蓝黑的难度。不禁感叹自己这一年来好像什么进步都没有哇！
听群友们说他们前三题都是两小时之内过的。根本比不了。
应该是要退役了。