【比賽記錄】2025CSP-S模擬賽58
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| - | 25 | 20 | 75 | 120 | 19/25 |
亂序放題，被 T1 硬控了啊啊啊啊啊
A. 鐵軌
考慮圖論。連邊：\(s_i\xrightarrow{0}t_i,v\xrightarrow{1}v-1\)。但是 \(\le s_i\) 這個限制十分難搞，考慮把它強制變為 \(=s_i\)，再連邊 \(v\xrightarrow{0}v+1\)。再加一條鐵軌 \((+\infty,1)\)，于是我們只需求一條包含了所有 \(s_i\to t_i\) 的歐拉回路即可。
因為所有點都在數軸上，所以所有 \(v\to v+1\) 和 \(v+1\to v\) 的經過次數應是相等的。首先差分出對每個 \(v\)，所有 \(s_i\to t_i\) 經過 \(v\to v+1\) 的次數與經過 \(v+1\to v\) 的次數之差。若不為 \(0\)，則需要一定量的 \(v\xrightarrow{1}v-1\) 或 \(v\xrightarrow{0}v+1\) 來補齊。
此時我們將圖連成了若干連通塊，不一定構成回路，又需要一些 \(v\to v+1\) 和 \(v+1\to v\) 來連通。于是縮點跑 kruskal 即可。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int maxn=4e5+5,inf=1e18;
int n,a[maxn],b[maxn],lsh[maxn],tot,c[maxn],fa[maxn],cnt;
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
struct edge{
int u,v,w;
il bool operator<(const edge &x)const{
return w<x.w;
}
}e[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
lsh[++tot]=a[i];
lsh[++tot]=b[i];
}
a[++n]=inf,b[n]=1;
lsh[++tot]=1,lsh[++tot]=inf;
sort(lsh+1,lsh+tot+1);
tot=unique(lsh+1,lsh+tot+1)-lsh-1;
for(int i=1;i<=tot;i++){
fa[i]=i;
}
for(int i=1;i<=n;i++){
a[i]=lwrb(lsh+1,lsh+tot+1,a[i])-lsh;
b[i]=lwrb(lsh+1,lsh+tot+1,b[i])-lsh;
c[a[i]]++,c[b[i]]--;
fa[find(a[i])]=find(b[i]);
}
int ans=0;
for(int i=1;i<=tot;i++){
c[i]+=c[i-1];
if(c[i]){
fa[find(i)]=find(i+1);
if(c[i]>0){
ans+=(lsh[i+1]-lsh[i])*c[i];
}
}
}
for(int i=1;i<tot;i++){
int u=find(i),v=find(i+1);
if(u!=v){
e[++cnt]=(edge){u,v,lsh[i+1]-lsh[i]};
}
}
sort(e+1,e+cnt+1);
for(int i=1;i<=cnt;i++){
int u=find(e[i].u),v=find(e[i].v);
if(u!=v){
ans+=e[i].w,fa[u]=v;
}
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
B. 參加
看到區間操作想不到差分，設差分數組為 \(b\)，那么要求即為 \(\forall i\in[1,k],b_i>0,\forall i\in[k+1,n],b_i<0\)。最小操作數即為前后的 \(\max\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5,inf=1e18;
int n,a[maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int pre=0,suf=0;
for(int i=n;i>1;i--){
a[i]-=a[i-1];
if(a[i]>=0){
suf+=a[i]+1;
}
}
// for(int i=1;i<=n;i++){
// cout<<a[i]<<' ';
// }
// cout<<'\n';
int ans=inf;
for(int i=1;i<=n;i++){
// cout<<i<<' '<<pre<<' '<<suf<<'\n';
ans=min(ans,max(pre,suf));
if(a[i+1]<0){
pre-=a[i+1]-1;
}else if(a[i+1]>0){
suf-=a[i+1]+1;
}else{
pre++,suf--;
}
}
cout<<ans;
return 0;
}
}
signed main(){return asbt::main();}
C. 決斗
首先考慮求出最大得分，考慮權值線段樹，合并時用左區間的 \(A\) 數量和右區間的 \(B\) 數量貢獻即可。考慮構造解，對每一位二分，考察取掉這個數后能否在線段樹上湊出答案即可。時間復雜度線性對數方。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,a[maxn],b[maxn];
int tr[maxn<<2][2],sum[maxn<<2],sz[maxn<<2];
il void pushup(int id){
sum[id]=sum[lid]+sum[rid]+min(tr[lid][0],tr[rid][1]);
tr[id][0]=max(tr[lid][0]-tr[rid][1],0ll)+tr[rid][0];
tr[id][1]=tr[lid][1]+max(tr[rid][1]-tr[lid][0],0ll);
sz[id]=sz[lid]+sz[rid];
}
il void add(int id,int l,int r,int p,bool opt,int v){
if(l==r){
tr[id][opt]+=v;
if(opt){
sz[id]+=v;
}
return ;
}
int mid=(l+r)>>1;
if(p<=mid){
add(lid,l,mid,p,opt,v);
}else{
add(rid,mid+1,r,p,opt,v);
}
pushup(id);
}
il int rank(int id,int l,int r,int p){
if(l==r){
return sz[id];
}
int mid=(l+r)>>1;
if(p<=mid){
return rank(lid,l,mid,p);
}else{
return sz[lid]+rank(rid,mid+1,r,p);
}
}
il int kth(int id,int l,int r,int k){
if(l==r){
return l;
}
int mid=(l+r)>>1;
if(sz[lid]>=k){
return kth(lid,l,mid,k);
}else{
return kth(rid,mid+1,r,k-sz[lid]);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
add(1,1,1e5,a[i],0,1);
}
for(int i=1;i<=n;i++){
cin>>b[i];
add(1,1,1e5,b[i],1,1);
}
int tar=sum[1],cur=0;
for(int i=1;i<=n;i++){
add(1,1,1e5,a[i],0,-1);
int c=rank(1,1,1e5,a[i]);
int l=c+1,r=sz[1],res=0;
while(l<=r){
int mid=(l+r)>>1;
int t=kth(1,1,1e5,mid);
add(1,1,1e5,t,1,-1);
if(sum[1]+1+cur==tar){
l=mid+1,res=mid;
}else{
r=mid-1;
}
add(1,1,1e5,t,1,1);
}
if(!res){
l=1,r=c;
while(l<=r){
int mid=(l+r)>>1;
int t=kth(1,1,1e5,mid);
add(1,1,1e5,t,1,-1);
if(sum[1]+cur==tar){
l=mid+1,res=mid;
}else{
r=mid-1;
}
add(1,1,1e5,t,1,1);
}
}
res=kth(1,1,1e5,res);
add(1,1,1e5,res,1,-1);
cur+=(res>a[i]);
// cout<<res<<'\n';
cout<<res<<' ';
}
return 0;
}
}
signed main(){return asbt::main();}
D. 回文串問題
發現只要長度相同那么一定不會出現 Not equal。考慮并查集，并對字符串進行哈希。時間復雜度瓶頸有兩個：合并和維護哈希值。
考慮最終頂多將所有點都合并成一個點，也就是說暴力合并的話有許多合并操作都是多余的。考慮不斷二分出 lcp 后對下一個位置進行合并，于是頂多合并 \(O(n)\) 次。而哈希值，可以用樹狀數組維護。但是我們每次合并，哈希值要改變的位置是有很多的，啟發式合并即可。時間復雜度線性對數方。
Code
#include<bits/stdc++.h>
#define ull unsigned long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=1e5+5;
const ull bas=1e5+393;
int n,m,fa[maxn];
ull pw[maxn];
set<int> s[maxn];
struct{
#define lowbit(x) (x&-x)
ull tr[maxn];
il void add(int p,ull v){
for(;p<=n;p+=lowbit(p)){
tr[p]+=v;
}
}
il ull query(int p){
ull res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
#undef lowbit
}F1,F2;
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
u=find(u),v=find(v);
if(u==v){
return ;
}
if(s[u].size()>s[v].size()){
swap(u,v);
}
fa[u]=v;
for(int x:s[u]){
s[v].insert(x);
F1.add(x,(v-u)*pw[x]);
F2.add(n-x+1,(v-u)*pw[n-x+1]);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
pw[0]=1;
for(int i=1;i<=n;i++){
fa[i]=i,s[i].insert(i);
pw[i]=pw[i-1]*bas;
F1.add(i,i*pw[i]);
F2.add(i,(n-i+1)*pw[i]);
}
while(m--){
int opt,l,r,x,y;
cin>>opt>>l>>r;
if(opt==1){
// puts("666");
int ll=1,rr=(r-l+1)>>1;
while(ll<=rr){
while(ll<rr){
int mid=(ll+rr)>>1;
ull hl=F1.query(l+mid-1)-F1.query(l-1);
ull hr=F2.query(n-r+mid)-F2.query(n-r);
if(hl*pw[n-r+1]==hr*pw[l]){
ll=mid+1;
}else{
rr=mid;
}
}
// cout<<l+ll-1<<' '<<r-ll+1<<'\n';
merge(l+ll-1,r-ll+1);
ll++,rr=(r-l+1)>>1;
}
}else{
cin>>x>>y;
if(r-l!=y-x){
cout<<"Not equal\n";
}else{
ull hl=F1.query(r)-F1.query(l-1);
ull hx=F1.query(y)-F1.query(x-1);
cout<<(hl*pw[x]==hx*pw[l]?"Equal":"Unknown")<<'\n';
}
}
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號