XCPC Notes

Appearance

发布时间：2025-06-01

题目链接

M. V图(签到) ​

在这里插入图片描述

cpp
int cmp(int x1,int y1,int x2,int y2){
	int x=x1*y2,y=x2*y1;
	if(x>y)return 1;
	if(x<y)return -1;
	return 0;
}
void solve(){
	int n;
	cin>>n;
	vector<int> a(n+1);
	int x=-1,s=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=2;i<n;i++){
		if(a[i]<a[i-1]&&a[i]<a[i+1]){
			x=i;
			break;
		}
	}
	int fz=0,fm=0;
	int ans=0,res=0;
	for(int i=1;i<=x;i++)s+=a[i];
	fz=s+a[x+1],fm=x+1;
	for(int i=x+2;i<=n;i++){
		s+=a[i];
		if(cmp(fz,fm,s,i)<0)fz=s,fm=i;
	}
	ans=fz,res=fm;
	s=0;
	for(int i=x-1;i<=n;i++)s+=a[i];
	fz=s,fm=n-x+2;
	int j=n-x+2;
	for(int i=x-2;i>=1;i--){
		j++;
		s+=a[i];
		if(cmp(fz,fm,s,j)<0)fz=s,fm=j;
	}
	if(cmp(ans,res,fz,fm)<0)ans=fz,res=fm;
	cout<<setprecision(12)<<fixed<<1.0*ans/res<<"\n";
}

J. 神秘树(交互) ​

在这里插入图片描述 首先询问(1,2)(3,4),...,(n−1,n)(1,2)(3,4),...,(n-1,n)这n2\frac{n}{2}种，如果都不存在，那么必然不是菊花(一个菊花的中心点必然与对应的另一个点有一条边，对应着上面询问至少有一条边存在)

然后需要33次操作内问出来

假设存在边(u,v)(u,v),因为n≥4n \geq 4,假设另外两个点为a,ba,b,询问(u,a),(v,a)(u,a),(v,a)，这两条边只有一条存在；如果都不存在必然是链

假设存在的是(u,a)(u,a)，那么询问(u,b)(u,b)，如果存在就是菊花，否则为链

G. 控制贪吃蛇(最短路) ​

在这里插入图片描述

  • 算出初始蛇身的每个点，蛇尾恰好离开该点的时刻
  • 那么跑dijk的时候，只要到当前点的时刻大于等于蛇尾离开的时刻，就是可达的
  • 统计答案用unsigned long long即可
  • 复杂度O(nmlog⁡(nm))O(nm \log (nm))
cpp
int n,m,k;
char a[N][N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void solve(){
	cin>>n>>m>>k;
	vector<vector<int>> dis(n+1,vector<int>(m+1,INF)),len(n+1,vector<int>(m+1));
	int sx=0,sy=0;
	for(int i=1;i<=k;i++){
		int x,y;
		cin>>x>>y;
		len[x][y]=i;
		if(i==1)sx=x,sy=y;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)cin>>a[i][j];
	}
	priority_queue<array<int,3>,vector<array<int,3>>,greater<>> pq;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)dis[i][j]=INF;
	}
	vector<vector<int>> vis(n+1,vector<int>(m+1));
	pq.push({0,sx,sy});
	dis[sx][sy]=0;
	while(!pq.empty()){
		auto [d,x,y]=pq.top();
		pq.pop();
		if(vis[x][y])continue;
		vis[x][y]=1;
		for(int i=0;i<4;i++){
			int tx=x+dx[i],ty=y+dy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&a[tx][ty]!='#'){
				int dd=d+1;
				if(len[tx][ty])dd=max(dd,k-len[tx][ty]+1);
				if(dis[tx][ty]>dd){
					dis[tx][ty]=dd;
					pq.push({dis[tx][ty],tx,ty});
				}
			}
		}
	}
	unsigned long long ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(dis[i][j]==INF)continue;
			// cout<<i<<" "<<j<<" "<<dis[i][j]<<"\n";
			ans+=dis[i][j]*dis[i][j];
		}
	}
	cout<<ans<<"\n";
}

D. 运算符优先级(构造) ​

在这里插入图片描述 中间项用-1 2构造即可

cpp
void solve(){
	int n;
	cin>>n;
	n*=2;
	vector<int> a(n+1);
	for(int i=2;i<n;i++){
		if(i&1)a[i]=-1;
		else a[i]=2;
	}
	a[n]=1;
	int s=0;
	for(int i=3;i<=n;i+=2)s+=a[i]*a[i+1];
	a[1]=-s;
	for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}

H. 甜蜜的修噶 II(概率) ​

在这里插入图片描述

  • 如果ai<abia_i \lt a_{b_i}事件必然发生
  • 如果ai≤abi+wbia_i \leq a_{b_i}+w_{b_i}事件必然不发生
  • 否则设距离它最近的可能发生的点的距离为LiL_i，则概率为1Li!\frac{1}{L_i!}，可以看作全排列中的一个排列的概率
  • 首先拓扑判环，如果有环，环内部事件都不可能发生
  • 复杂度O(n)O(n)
cpp
int qpow(int a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
void solve(){
	int n;
	cin>>n;
	vector<int> a(n+1),b(n+1),w(n+1),dep(n+1),adj(n+1),din(n+1),fac(n+1),p(n+1,-1);
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)cin>>w[i];
	for(int i=1;i<=n;i++){
		if(a[i]<a[b[i]])dep[i]=1,p[i]=1;
		else if(a[i]>=a[b[i]]+w[b[i]])dep[i]=p[i]=0;
		else{
			adj[i]=b[i];
			din[b[i]]++;
		}
	}
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(!din[i])q.push(i);
	}	
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		int v=adj[u];
		if(--din[v]==0)q.push(v);
	}
	for(int i=1;i<=n;i++){
		if(din[i]){
			dep[i]=p[i]=0;
		}
	}
	function<void(int)> dfs=[&](int u){
		if(p[u]!=-1)return;
		int v=adj[u];
		if(!v)return;
		dfs(v);
		if(p[v]>0){
			dep[u]=dep[v]+1;
			p[u]=qpow(fac[dep[u]],mod-2);
		}
		else{
			p[u]=0;
		}
	};
	for(int i=1;i<=n;i++){
		dfs(i);
	}
	for(int i=1;i<=n;i++)cout<<(a[i]+p[i]*w[i]%mod)%mod<<" \n"[i==n];
}

B. 节日装饰(bitset+根号分治) ​

在这里插入图片描述

  • 首先有一个bitset的暴力做法
  • 对每个颜色开一个bitset记录对应的位置
  • 然后枚举每个位置，对于每个位置，我们可以用总的bitset异或当前颜色的bitset求出与当前颜色不同的位置，然后O(Nω)O(\frac{N}{\omega})枚举这些位置判断
  • 但是这样空间复杂度是O(5003)O(500^3)会爆空间
  • 因为题目中每个位置颜色不一样，设cnticnt_i为颜色个数，则∑cnti=n\sum cnt_i=n
  • 考虑根号分治，
  • 对于颜色位置数小于等于n\sqrt n的，直接暴力
  • 对于大于n\sqrt n的，这样的颜色数量小于n\sqrt n，预处理出来
  • 这样时间复杂度为O(n(n+nω))O(n(\sqrt n+\frac{n}{\omega}))，空间复杂度为O(nnω)O(\frac{n\sqrt n}{\omega})
  • 在更新答案时，我们需要剪枝，每个位置只更新一次答案,bitset数组开在外面
cpp
const int N=250010,sq=510;
bitset<N> bs[501],all,tmp,que;
void solve(){
    int n,q;
    cin>>n>>q;
    vector<int> pos[n+1],id(n+1,-1),X(n+1),C(n+1);
    for(int i=1;i<=n;i++){
        cin>>X[i]>>C[i];
        pos[C[i]].push_back(X[i]);
        all.set(X[i]);
    }
    int cnt=0;
    int idx=0;
    for(int i=1;i<=n;i++){
        if(pos[i].size()>=sq){
            for(auto x:pos[i])bs[idx].set(x);
            id[i]=idx++;
        }
    }
    vector<int> ans(N+1),D(q+1);
    for(int i=1;i<=q;i++){
        cin>>D[i];
        que.set(D[i]);
    }
    for(int i=1;i<=n;i++){
        if(id[C[i]]==-1)for(auto x:pos[C[i]])all.flip(x);
        else all^=bs[id[C[i]]];
        tmp=que&(all>>X[i]);
        for(int j=tmp._Find_first();j<N;j=tmp._Find_next(j)){
            ans[j]=i;
            que.reset(j);
        }
        if(id[C[i]]==-1)for(auto x:pos[C[i]])all.flip(x);
        else all^=bs[id[C[i]]];
    }
    for(int i=1;i<=q;i++){
        cout<<ans[D[i]]<<"\n";
    }
}

F. Top Cluster(LCA+动态维护树的直径) ​

在这里插入图片描述

  • 看到mex想到二分答案，可以先对w排个序，可以预处理出前缀mex，二分出来的答案就是当前前缀的mex，check函数转化为求[1-mid]的点到达x的距离<=k
  • 那么只要最大值小于等于k，一个经典的trick，一个点到达子树的最大值一定是该子树直径的其中一个端点
  • 另一个经典的trick就是，假设当前直径为u,vu,v，新加入一个点xx，直径如果改变，只会是u,xu,x或者v,xv,x，实际上和上面的结论本质是一个道理
  • 因此我们预处理出前缀直径，查询的时候check，dist(u,x)≤kdist(u,x) \leq k且dist(v,x)≤kdist(v,x) \leq k即可
  • 查询dist的时候可以用欧拉序预处理，达到O(1)O(1)查询，减少一个log
  • 复杂度O((n+q)log⁡n)O((n+q)\log n)
cpp
int dep[N],seq[N<<1],fir[N],dfc;
vector<PII> adj[N];
void dfs(int u,int fa){
    seq[++dfc]=dep[u];
    fir[u]=dfc;
    for(auto [v,c]:adj[u]){
        if(v==fa)continue;
        dep[v]=dep[u]+c;
        dfs(v,u);
        seq[++dfc]=dep[u];
    }
}
int st[N<<1][30];
void init(){
    for(int i=1;i<=dfc;i++)st[i][0]=seq[i];
    for(int j=1;j<30;j++){
        for(int i=1;i+(1<<j)-1<=dfc;i++)st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
    }
}
int query(int l,int r){
    int k=__lg(r-l+1);
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
int dist(int u,int v){
    if(fir[u]>fir[v])swap(u,v);
    return dep[u]+dep[v]-2*query(fir[u],fir[v]);
}
void solve(){   
    int n,q;
    cin>>n>>q;
    vector<PII> w(n+1);
    vector<int> ans(n+1);
    for(int i=1;i<=n;i++){
        cin>>w[i].F;
        w[i].S=i;
    }
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    sort(w.begin()+1,w.end());
    dfs(1,0);
    init();
    vector<PII> D(n+1);
    map<int,int> vis;
    int mex=0;
    for(int i=1;i<=n;i++){
        vis[w[i].F]=i;
        while(vis.count(mex))mex++;
        ans[i]=mex;
        if(i==1)D[i]={w[i].S,w[i].S};
        else{
            D[i]=D[i-1];
            auto [x,y]=D[i];
            auto xx=w[i].S;
            int dis1=dist(x,xx),dis2=dist(y,xx),dis3=dist(x,y);
            if(dis1>=dis2&&dis1>=dis3)D[i]={x,xx};
            else if(dis2>=dis1&&dis2>=dis3)D[i]={y,xx};
            else D[i]={x,y};
        }
    }
    while(q--){
        int x,k;
        cin>>x>>k;
        int l=0,r=n;
        auto check=[&](int mid){
            auto [u,v]=D[mid];
            return dist(u,x)<=k&&dist(v,x)<=k;
        };
        while(l<r){
            int mid=l+r+1>>1;
            if(check(mid))l=mid;
            else r=mid-1;
        }
        cout<<ans[l]<<"\n";
    }
}

Wenwei Lin · 2022 — 2025