当前位置：首页 > news >正文

CSP-S模拟20

news 2025/9/17 10:16:07

前言：

一场通过乱搞获得如下成绩的比赛。

$T1：$

思路：

一场情况超级复杂（bushi）的大模拟（应该可以这么叫吧？）直接先这样这样，在那样那样，最后在叽里呱啦就好了。

嘿嘿，开个玩笑嘛。首先，我们知道一定至少从$S'$跳到$S$到$T$的那条链上，这样我们可以就$S'$跳到$S$到$T$的链上的位置大致分为两大种情况进行讨论：第一种，跳到$S$和$T$的$lca$上。此时$S$和$T$在同一个子树上；第二种，跳到$S'$和$T$或$S'$和$S$的$lca$上，此时$S$和$T$在不同一个子树上。然后再分为几个小的情况再讨论就好了。

代码：追逐游戏 (chase)

$code time$

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,q,u,v,cnt,s,t,ss,point,dep[N],fa[N][20],head[N];
struct node{int to,nxt;}e[N<<1];
inline void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;
}//建边 
inline int find(int x,int y){if(x==y) return x;if(dep[x]>dep[y]){for(int i=19;i>=0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];if(x==y) return x;}else if(dep[x]<dep[y]){for(int i=19;i>=0;i--) if(dep[fa[y][i]]>=dep[x]) y=fa[y][i];if(x==y) return x;}for(int i=19;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];return fa[x][0];
}//倍增求lca 
inline void dfs(int x,int daddy){dep[x]=dep[daddy]+1;fa[x][0]=daddy;for(int i=1;i<=19;i++) fa[x][i]=fa[fa[x][i-1]][i-1];for(int i=head[x];i;i=e[i].nxt){int y=e[i].to;if(y!=daddy) dfs(y,x);}
}//固定树的形态 
inline int getpoint(int s,int e,int t){int lca=find(s,e);if(t<=dep[s]-dep[lca]){point=s;for(int i=19;i>=0;i--) if(dep[fa[point][i]]>=dep[s]-t) point=fa[point][i];}//S翻不过去lca else{point=e;for(int i=19;i>=0;i--) if(dep[fa[point][i]]>=dep[e]-(dep[s]+dep[e]-2*dep[lca]-t)) point=fa[point][i];}//S翻过去了lca return point;
}//一个小分讨 
inline int getdis(int x,int y){return dep[x]+dep[y]-2*dep[find(x,y)];
}//求两点之间的距离 
int main(){freopen("chase.in","r",stdin);freopen("chase.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>q;for(int i=1;i<n;i++) cin>>u>>v,add(u,v),add(v,u);dfs(1,0);while(q--){cin>>s>>t>>ss;int lcs=find(ss,s),lst=find(s,t),lct=find(ss,t),stop,st,ct;if(dep[lct]<=dep[lst]&&dep[lcs]<=dep[lst]) stop=lst;else if(dep[lcs]<dep[lct]) stop=lct;else stop=lcs;st=getdis(s,stop);//S到该点的时间 ct=getdis(ss,stop);//S'到该点的时间 if(st==ct) cout<<st<<" "<<stop<<'\n';//相等直接输出 else if(st<ct) cout<<ct+getdis(stop,t)<<" "<<t<<'\n';//S'大的话就只能追到T点了 else{//S到该点的时间长 所以S'还可以从该点再向S点的方向追 int delta=(st-ct)>>1;//小学数学：相向而行问题 cout<<st-delta<<" "<<getpoint(s,t,st-delta)<<'\n';}}return 0;
}

$T2：$统计（st）

思路：

给$[1,m-1]$每个值赋一个随机值，然后给$m$赋为$[1,m-1]$所赋值的总和的相反数，然后求一边前缀和，若前缀和为0，则证明他们出现的次数一样多（再往后就没听懂了😛）

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int T,a[N],b[N],sum[N],n,m,ans,tot;
mt19937 mrd(time(0));
signed main(){
//	freopen("st.in","r",stdin);
//	freopen("st.out","w",stdout);cin>>T;while(T--){cin>>n>>m;ans=0,tot=0;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<m;i++) b[i]=mrd(),tot+=b[i];b[m]=-tot;//赋值 for(int i=1;i<=n;i++) sum[i]=sum[i-1]+b[a[i]];//前缀和 sum[++n]=0;//这后面的就不会了 sort(sum+1,sum+n+1);for(int i=1;i<=n;i++){int j=i;while(sum[j+1]==sum[j]&&j<n) j++;int num=j-i+1;ans+=num*(num-1)/2;i=j;}printf("%lld\n",ans);}return 0;
}

$T3：$ 软件工程（se）

思路：

凭借乱搞做法喜提96高分，正确性无法保证 ~~（因为根本没有）~~ 。我们观察样例可得，我们可以将线段按顺序排序，然后将$n-k+1$条短的边分到一组，然后剩下的边分别单独一组。然后数据范围告诉我们$k=2$是一种特殊情况，然后当$k=2$时，将线段按$l$的大小排序，然后把它分成两段，跟第一条线段相交的分为第一组，其余的为第二组，然后你就可以愉快稀里糊涂的$AC$掉此题了。

代码：

点击查看代码

#include<iostream>
#include<algorithm>
#define int long long 
using namespace std;
const int N=5200;
int n,k,ans,res,l,r=1e6+5;;
struct node{int l,r;}a[N];
inline bool cmp(node a,node b){return (a.r-a.l)<(b.r-b.l);}
inline bool css(node a,node b){return a.l<b.l;} 
signed main(){
//	freopen("se.in","r",stdin);
//	freopen("se.out","w",stdout);ios::sync_with_stdio(false);cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;if(k>=n){for(int i=1;i<=n;i++) ans+=a[i].r-a[i].l;cout<<ans<<'\n';return 0;//特判 }sort(a+1,a+1+n,cmp);//排序 for(int i=1;i<=n-k+1;i++){l=max(l,a[i].l);r=min(r,a[i].r);}ans+=max(r-l,0ll);for(int i=n-k+2;i<=n;i++) ans+=a[i].r-a[i].l;l=0,r=1e6+5; if(k==2){sort(a+1,a+1+n,css);l=a[1].l;r=a[1].r;for(int i=2;i<=n;i++){if((a[i].l>=l&&a[i].l<=r)||(a[i].r>=l&&a[i].r<=r)){l=max(l,a[i].l);r=min(r,a[i].r);}else{res+=r-l;l=a[i].l;r=a[i].r;}}res+=r-l;ans=max(ans,res);}cout<<ans;return 0;
}//代码挺简单的 就不写注释了哈