2025暑期算法竞赛学习笔记（多校/vp记录2）

2025.7.19

CCPC 2024 哈尔滨

M. Weird Ceiling （685/690）

签到题，过。

C. Giving Directions in Harbin（677/684）

签到题，过。

G. Welcome to Join the Online Meeting （654/671）

签到题，可以考虑对不忙碌的点跑个最小生成树。

K. Farm Management （594/651）

先给每一个分配

l_i

，然后考虑它被选的情况：它要么变成它能做到的最大值，要么变成它能做到的最小值，前缀和后缀和+二分即可。

J. New Energy Vehicle (476/636)

赛时队友是用二分写的：这种题一看题目就应该想到二分答案，但是其实这个不是很容易写的做法。
其实很容易想到一个策略：油箱的使用顺序一定是加油的顺序（除了初始的油）。
然后我们按照这个策略模拟即可。 $cnt[i]$ 表示第 $i$ 种油目前还剩下多少， $now[i]$ 表示目前的第 $i$ 种油它是哪个加油站来的。
走到每一个加油站时，我们先对目前这个加油站前的所有可加的油进行加油，然后如果不够再用初始油箱。完成这个操作之后，我们对此加油站种类的油进行一个油量加满的更新即可。

CPP

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=200005;
int T,n,m,sum,ans,now[N],a[N],cnt[N],vis[N],hext[N];
vector <int> vec[N];
struct qwq{
    int x,t;
}b[N];
set<pair<int,int> > s;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n>>m;
        sum=ans=0; for (int i=1;i<=n;i++) vec[i].clear();
        s.clear();
        for (int i=1;i<=max(n,m);i++) vis[i]=0,now[i]=0,hext[i]=-1;
        for (int i=1;i<=n;i++) cin>>a[i];
        for (int i=1;i<=n;i++) sum+=a[i],cnt[i]=a[i];
        for (int i=1;i<=m;i++) cin>>b[i].x>>b[i].t;
		
        for (int i=1;i<=m;i++) {
            vec[b[i].t].push_back(i);
            if (!vis[b[i].t]) {
                s.insert({i,b[i].t}); 
			    vis[b[i].t]=1;
				now[b[i].t]=i;
            }
        }
        for (int i=1;i<=n;i++) {
            for (int j=0;j<(int)vec[i].size();j++) {
                if (j==(int)vec[i].size()-1) {
                    hext[vec[i][j]]=m+1;
                }
                else hext[vec[i][j]]=vec[i][j+1];
            }
        }
        		
		for (int i=1;i<=m;i++) {
			if (ans+sum<b[i].x) break;
			int ned=b[i].x-b[i-1].x;
			while (ned>0&&(!s.empty())) {
				pair<int,int>u=*s.begin(); s.erase(*s.begin());
				if (cnt[u.second]>ned) {
					cnt[u.second]-=ned; ned=0; s.insert(u); 
				}
				else {
					ned-=cnt[u.second]; cnt[u.second]=0;
				}
			}					
			int col=b[i].t;
			if (s.find({now[col],col})!=s.end()) s.erase({now[col],col});
			ans+=(a[col]-cnt[col]); cnt[col]=a[col];
			s.insert({hext[i],col});now[col]=hext[i]; 				
		}
        cout<<ans+sum<<'\n';
    }		
    return 0;
}

L. A Game On Tree （230/251）

vp时一直没有想出来。赛后看了题解，自己推了一遍学会了。

主要是第一步就寄了：对于一条路径，我们把它拆为 $e_1+e_2+e_3+...+e_n$ 这几条单位边，边权均为 $1$ 。所以 $X^2$ 可拆为 $\sum_{i=1}^{n} a_i^2$ （记作 (a) 部分）和 $\sum_{}^{} a_i * a_j$ （记作 (b) 部分）。
关于 (a) 部分：对于边 $u \to v$ （ $u$ 为 $v$ 的父亲），小红有 $siz_v*(n-siz_v)$ 种选法使她选的这条路径包含了 $u \to v$ 这条边，小蓝同理，因此 $(siz_v*(n-siz_v))^2$ 即为答案。对所有 $v$ 相加即可。
关于 (b) 部分：我们要选两条边，求小红、小蓝选的两条路径都经过这两条边的方案数。对于这两条边，我们很自然想到，枚举 $LCA$ （记为 $u$ ）这一个点。我们在此将这两条边记为 $A : x_1 \to y_1$ 和 $B : x_2 \to y_2$
- 若 $A$ 和 $B$ 二者位于 $u$ 的不同子树（子树的根节点为 $v_1$ 和 $v_2$ ），则对于 $A$ 和 $B$ 两边来说, 小红可选 $siz_{y_1} * siz_{y_2}$ ，所以两人共有 $(siz_{y_1}^2)* (siz_{y_2}^2)$ 。而对于这个 $LCA(u)$ ，我们会有 $sum[v_1] * sum[v_2]$ （ $sum[v]$ 表示 $v$ 及子树所有结点的所有 $siz^2$ ）
- 若 $A$ 和 $B$ 二者位于 $u$ 的同一子树，可知其中一条边肯定是 $u \to v$ （ $v$ 是 $u$ 的一个儿子）。则对于另一条边 $x->y$ ，小红可以选 $siz_y*(n-siz_v)$ ，所以二人可选 $siz_y^2 * (n-siz_v)^2$ 。合并起来，就是行内公式示例： $\sum_{v \in son_u} 2 \times (n - siz[v])^2 (sum[v] - siz[v]^2)$

CPP

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=200005;
const int MOD=998244353;
int T,n,tot,ans;
int head[N],sum[N],siz[N];
vector <int> son[N];
struct qwq{
	int hext,to;
}e[N<<1];
void add(int x,int y) {
	e[++tot].hext=head[x];
	e[tot].to=y;
	head[x]=tot;
}
void dfs1(int x,int fath) {
	siz[x]=1; sum[x]=0;
	for (int i=head[x];i;i=e[i].hext) {
		int v=e[i].to;
		if (v==fath) continue;
		dfs1(v,x);
		son[x].push_back(v);
		siz[x]+=siz[v]; sum[x]=(sum[x]+sum[v])%MOD;
	}
	sum[x]=(sum[x]+siz[x]*siz[x]%MOD)%MOD;
}
int Sqr(int x) {
	return x*x%MOD;
}
int mi(int A,int B) {
	int t=1;
	while (B) {
		if (B&1) t=t*A%MOD;
		A=A*A%MOD;
		B>>=1;
	}
	return t;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n; ans=0;
		for (int i=1;i<=n-1;i++) {
			int x,y; cin>>x>>y;
			add(x,y); add(y,x);
		}
		dfs1(1,0);
		for (int u=1;u<=n;u++) {
			for (auto v:son[u]) {
				ans=(ans+Sqr(siz[v]*(n-siz[v])%MOD))%MOD;
				ans=(ans+2*Sqr(n-siz[v])%MOD*(sum[v]-Sqr(siz[v])+MOD)%MOD)%MOD;
			}
		}
		for (int u=1;u<=n;u++) {
			int t=0,s=0;
			for (auto v:son[u]) {
				s=(s+sum[v])%MOD;
				t=(t+sum[v]*sum[v]%MOD)%MOD;
			}
			ans=(ans+(s*s%MOD-t%MOD+MOD))%MOD;
		}
		ans=ans*4%MOD*mi(Sqr(n*(n-1)%MOD),MOD-2)%MOD;
		ans%=MOD;
		cout<<ans<<endl; 
		for (int i=1;i<=n;i++) head[i]=siz[i]=sum[i]=0;
		for (int i=1;i<=n;i++) son[i].clear();
		tot=0;
	}
	return 0;
}

B. Concave Hull (188/252)

vp时队友嘴出了正确做法，不过没机时了，做法如下：

先对所有点跑一遍凸包（在这里我们记为 $s$ ）
然后对除了刚才 $s$ 凸包中的点以外的所有点，再跑一遍凸包，记为 $ss$
易知，最大面积的凹多边形一定是 $s$ 中的所有点连成的凸多边形，减去其中两个相邻点与 $ss$ 中的一个点相连而形成的三角形。
凸多边形的总面积是不变的。我们想要三角形面积最小，即令底 * 高最小。
按序遍历每一个底，然后跑双指针求出哪里距离最小，即可。

调这题调了一个晚上，要点：

用 long double 时，内置函数的引用也要配套！如：sqrtl、acosl！
这题一开始挂了是因为：求三角形的面积的时候采用底乘以高（因为要算距离最近的点，既然距离都算了，就偷懒直接去用这东西算了），然后爆精度了：用叉乘！！！

CPP

#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N=500005;
int cnt1,cnt2,T,n;
struct qwq{double x,y;int xh;}p[N],pp[N],s[N],ss[N];
int vis[N],viss[N];
double dabs(double x) {
	if (x<0) return -x;
	return x;	
}
double check(qwq xa,qwq xb,qwq ya,qwq yb) {
	return ((xb.x-xa.x)*(yb.y-ya.y)-(yb.x-ya.x)*(xb.y-xa.y));
}
double fsqr(double x) {return x*x;}
double d(qwq a,qwq b) {
	return sqrtl(fsqr(a.x-b.x)+fsqr(a.y-b.y));
}
double dot(qwq a,qwq b) {
	return a.x*b.x+a.y*b.y;
}
double len(qwq a) {
	return sqrtl(a.x*a.x+a.y*a.y);
}
double coss(qwq a,qwq b) {
	double res=dot(a,b)/(len(a)*len(b));
	return res;
}
bool cmp(qwq a,qwq b) {
	double tmp=check(p[1],a,p[1],b);
	if (tmp>0) return 1;
	if (tmp==0 && d(p[0],a)<d(p[0],b)) return 1;
	return 0;
}
double cross(qwq a,qwq b) {
	return dabs(a.x*b.y-b.x*a.y);
}
void solve1() {
	for (int i=1;i<=n;i++) {
		if (i!=1&&(p[i].y<p[1].y||p[i].y==p[1].y&&p[i].x<p[1].x)) {
			swap(p[1],p[i]);
		}
	}
	sort(p+2,p+n+1,cmp);
	s[1]=p[1]; cnt1=1;
	for (int i=2;i<=n;i++) {
		while (cnt1>1&&check(s[cnt1-1],s[cnt1],s[cnt1],p[i])<=0)  cnt1--;
		cnt1++;
		s[cnt1]=p[i];
	}
	for (int i=1;i<=cnt1;i++) vis[s[i].xh]=1;
}

void solve2() {
	int tott=0;
	for (int i=1;i<=n;i++) {
		if (!vis[p[i].xh]) pp[++tott]=p[i];	
	}
	n=tott; 
	for (int i=1;i<=n;i++) {
		p[i]=pp[i];
	}
	for (int i=1;i<=n;i++) {
		if (i!=1&&(p[i].y<p[1].y||p[i].y==p[1].y&&p[i].x<p[1].x)) {
			swap(p[1],p[i]);
		}
	}
	cnt2=n;
	if (n<1) return ;
	sort(p+2,p+n+1,cmp);
	ss[1]=p[1]; cnt2=1;
	for (int i=2;i<=n;i++) {
		while (cnt2>1&&check(ss[cnt2-1],ss[cnt2],ss[cnt2],p[i])<=0)  cnt2--;
		cnt2++;
		ss[cnt2]=p[i];
	}	
}
double dist(qwq c,qwq A,qwq B) {
	qwq v1; v1={c.x-B.x,c.y-B.y}; 
	qwq v2; v2={A.x-B.x,A.y-B.y};
	double costheta=dabs(coss(v1,v2));
	double tmp=1-costheta*costheta;
	tmp=sqrtl(tmp)*len(v1);
	return tmp;
}
double tri(qwq c,qwq A,qwq B) {
	qwq v1; v1={c.x-B.x,c.y-B.y}; 
	qwq v2; v2={c.x-A.x,c.y-A.y};
	double tmp=cross(v1,v2);
	return tmp;
}
double jsS() {
	double tmp=0;
	for (int i=2;i<=cnt1-1;i++) {
		qwq v1={s[i].x-s[1].x,s[i].y-s[1].y};
		qwq v2={s[i+1].x-s[1].x,s[i+1].y-s[1].y};
		tmp=tmp+dabs(cross(v1,v2));
	}
	return tmp;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n;
		for (int i=1;i<=n;i++) vis[i]=0;
		for (int i=1;i<=n;i++) {
			cin>>p[i].x>>p[i].y; p[i].xh=i;
		}
		solve1(); solve2();
		int r=0; double minn=1e9+7;minn*=1000000;
		for (int i=1;i<=cnt2;i++) {
			double tmp=dist(ss[i],s[1],s[2]); 
			if (tmp<minn) {
				minn=tmp;
				r=i;
			}
		}
		if (cnt2==0) {
			cout<<-1<<endl;
			continue;
		}
		double S=jsS();
		double ans=0;
		s[cnt1+1]=s[1]; ss[cnt2+1]=ss[1];
		for (int i=1;i<=cnt2;i++) viss[i]=0;
		for (int l=1;l<=cnt1;l++) {
			double tmp=S-tri(ss[r],s[l],s[l+1]);;
			ans=max(ans,tmp);
			while (dist(ss[r],s[l],s[l+1])>dist(ss[r%cnt2+1],s[l],s[l+1])&&!viss[r%cnt2+1]) {
				r=(r%cnt2)+1;
				tmp=S-tri(ss[r],s[l],s[l+1]);	ans=max(ans,tmp);
				if (viss[r]) break;  viss[r]=1;
			}
		}
		cout<<(int)round(ans)<<'\n';
	}
	return 0;
}

A. Build a Computer (220/308)

官方tutorial

官方题解的构造方法太巧妙了（震撼）。

E. Marble Race （161/174）

一道可撤销背包。

CPP

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2333;
const int MOD=1e9+7;
int n,m,X[N],V[N],p[N],dp[N];
vector<pair<int,int> > vec;
bool cmp(pair<int,int>x,pair<int,int>y) {
    return X[x.first]*V[y.second]<X[y.first]*V[x.second];
}
int mi(int A,int B) {
    int tmp=1;
    while (B) {
        if (B&1) tmp=tmp*A%MOD;
        A=A*A%MOD;
        B>>=1;
    }
    return tmp;
}
int inv(int x) {
    return mi(x,MOD-2);
}
void ins(int x) {
    for (int i=m;i>=1;i--) {
        dp[i]=(dp[i-1]*x%MOD+dp[i]*(n-x)%MOD)%MOD;
    }
    dp[0]=dp[0]*(n-x)%MOD;
}
void del(int x) {
	int t=inv(n-x);
    dp[0]=dp[0]*t%MOD;
    for (int i=1;i<=m;i++) {
        dp[i]=(dp[i]-dp[i-1]*x%MOD+MOD)*t%MOD;
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>X[i]; X[i]=-X[i];
    }    
    for (int i=1;i<=m;i++) {
        cin>>V[i];
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            vec.push_back({i,j});
        }
    }
    sort(vec.begin(),vec.end(),cmp);
    int ans=0; dp[0]=mi(n,m);
	for (auto u:vec) {
        int x=X[u.first],v=V[u.second];
        int i=u.first,j=u.second; //i:出发点 j:球 
        del(p[j]); //p[j]:当前第j球的累计计算次数 
        int tmp=(dp[m/2]*mi(inv(n),m)%MOD)%MOD;
        tmp=tmp*x%MOD*inv(v)%MOD;
        ans=(ans+tmp)%MOD;
        p[j]++;
        ins(p[j]);
    }
    cout<<ans<<endl;
    return 0;
}

2025.7.21

2025“钉耙编程”中国大学生算法设计暑期联赛（2）

赛时写完部分签到题后开始写1012。思路是对的，但是因为没有仔细思考，所以没想到写可撤销线性基那么简单，就写了个小优化，因为数据水也过了（但是不敢交，过了很久才敢交）。

后来试图找1001规律，没有尝试成功。不过还有警钟敲烂的一点，是，甚至暴力运行得也好慢，暴力优化也要好好学习。

1002. 数上的图 (1128/2553)

易知，用两次肯定能解决。

再特判一下0次和1次的情况即可，不述。

1008. 井 (1046/1780)

按对角线放，数学推导即可。

CPP

	cin>>T;
	while (T--) {
		cin>>n;
		double ans=3.0*(double)n/2.0;
		cout<<fixed<<setprecision(4)<<ans<<endl;
	}

1006. 半 (1024/2734)

树状数组即可。

CPP

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1000006;
int T,n,a[N],b[N],tree[N];
int pos1[N],pos2[N],ans[N];
int lowbit(int x) {
	return x&(-x);
}
void add(int x,int k) {
	for (;x<=n;x+=lowbit(x)) {
		tree[x]+=k;
	}
}
int query(int x) {
	int t=0;
	for (;x;x-=lowbit(x)) {
		t+=tree[x];
	}
	return t;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n;
		for (int i=1;i<=n;i++) {
			cin>>a[i]; pos1[a[i]]=i;
		}
		for (int i=1;i<=n;i++) {
			cin>>b[i]; pos2[b[i]]=i;
		}
		for (int i=1;i<=n;i++) tree[i]=0;
		for (int i=1;i<=n;i++) {
			int t=query(pos2[a[i]]);
			add(pos2[a[i]],1);
			ans[a[i]]=(i-1)+(pos2[a[i]]-1)-(t);
		}
		for (int i=1;i<=n;i++) {
			cout<<ans[i]<<" ";
		}		
		cout<<'\n';
	}
	return 0;
}

/*
pos1[x]<pos1[i] && pos2[x]<pos2[i]
*/

1009. 苹果树 (479/2855)

我们把

2 x z

这个操作，分为两个部分：

一个是 $x$ 的父亲：因为父亲只有一个，那我们只要修改 $x$ 的父亲的 $a[fa_x]$
一个是 $x$ 的儿子们：我们直接更改 $x$ 的 $z$ 值。

我们在树链剖分的基础上进行线段树：

对于一个区间， $z$ 表示这个区间的 $dfn$ 最大的数的 $z$ 的值， $a$ 表示这个区间的 $dfn$ 最小的数的 $a$ 的值。然后我们就不难想到怎么区间合并啦！

CPP

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=100005;
int T,n,m,tot,cnt,head[N],Z[N],A[N],a[N],w[N];
int top[N],dfn[N],fa[N],siz[N],dep[N],son[N];
struct qwq{
    int z,a,maxn;
    friend qwq operator + (qwq AA,qwq BB) {
        qwq c;
        c.z=BB.z;
        c.a=AA.a;
        c.maxn=max(max(AA.maxn,BB.maxn),AA.z+BB.a);
        return c;
    }
}tree[N<<2];
struct edge{
    int hext,to;
}e[N<<1];
void add(int x,int y) {
    e[++tot].hext=head[x];
    e[tot].to=y;
    head[x]=tot;
}
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
void push_up(int rt) {
    tree[rt]=tree[ls(rt)]+tree[rs(rt)];
}
void dfs1(int x,int fath) {
    siz[x]=1; dep[x]=dep[fath]+1; fa[x]=fath;
    int maxn=-1;
    for (int i=head[x];i;i=e[i].hext) {
        int v=e[i].to;
        if (v==fath) continue;
        dfs1(v,x);
        siz[x]+=siz[v];
        if (siz[v]>maxn) {
            maxn=siz[v];
            son[x]=v;
        }
    }
}
void dfs2(int x,int topf) {
    dfn[x]=++cnt;
    w[dfn[x]]=a[x];
    top[x]=topf;
    if (!son[x]) return ;
    dfs2(son[x],topf);
    for (int i=head[x];i;i=e[i].hext) {
        int v=e[i].to;
        if (v==fa[x]||v==son[x]) continue;
        dfs2(v,v);
    }
}
void build(int rt,int l,int r) {
    if (l==r) {
        tree[rt].z=0;
        tree[rt].a=w[l];
        tree[rt].maxn=w[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls(rt),l,mid);
    build(rs(rt),mid+1,r);
    push_up(rt);
}
void update1(int rt,int l,int r,int x,int k) {
    if (l==r) {
        tree[rt].a+=k;
        tree[rt].maxn+=k;
        return ;
    }
    int mid=(l+r)>>1;
    if (x<=mid) update1(ls(rt),l,mid,x,k);
            else update1(rs(rt),mid+1,r,x,k);
    push_up(rt);
}
void update2(int rt,int l,int r,int x,int k) {
    if (l==r) {
        tree[rt].z+=k;
        return ;
    }
    int mid=(l+r)>>1;
    if (x<=mid) update2(ls(rt),l,mid,x,k);
            else update2(rs(rt),mid+1,r,x,k);
    push_up(rt);
}
qwq query(int rt,int l,int r,int nl,int nr) {
    if (nl<=l&&r<=nr) {
        return tree[rt];
    }
    int mid=(l+r)>>1;
    if (nl>mid) return query(rs(rt),mid+1,r,nl,nr);
    else if (nr<=mid) return query(ls(rt),l,mid,nl,nr);
    else return (query(ls(rt),l,mid,nl,nr)+query(rs(rt),mid+1,r,nl,nr));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while (T--) {
        cin>>n>>m;
        for (int i=1;i<=n;i++) cin>>a[i];
        for (int i=1;i<=n-1;i++) {
            int x,y; cin>>x>>y;
            add(x,y); add(y,x);
        }
        dfs1(1,0);
        dfs2(1,1);       
        build(1,1,n);
        for (int i=1;i<=n;i++) A[dfn[i]]=a[i];
        while (m--) {
            int opt,x,y; cin>>opt>>x>>y;
            if (opt==1) {
                int res=0;
                while (top[x]!=top[y]) {
                    if (dep[top[x]]<dep[top[y]]) swap(x,y);
                    int t=query(1,1,n,dfn[top[x]],dfn[x]).maxn;
                    res=max(res,t);
                    t=A[dfn[top[x]]]+Z[dfn[fa[top[x]]]];
                    res=max(res,t);
                    x=fa[top[x]];
                }
                if (dep[x]>dep[y]) swap(x,y);
                int t=query(1,1,n,dfn[x],dfn[y]).maxn;
                res=max(res,t);
                t=A[dfn[x]]+Z[dfn[fa[x]]];
                res=max(res,t);
                cout<<res<<endl;
            }
            else {
                if (x!=1) {
                    update1(1,1,n,dfn[fa[x]],y); A[dfn[fa[x]]]+=y;
                }
                update2(1,1,n,dfn[x],y);
                Z[dfn[x]]+=y; 
            }
        }
        cnt=tot=0;
        for (int i=1;i<=n;i++) head[i]=fa[i]=dfn[i]=0;
        for (int i=1;i<=n;i++) w[i]=a[i]=son[i]=Z[i]=A[i]=0;
        for (int i=1;i<=4*n;i++) tree[i].a=tree[i].maxn=tree[i].z=0;
    }
    return 0;
}

1012. 子集 (364/5193)

我们选定一些数，跑线性基取max。
因为相邻的不能取，但是我们又利用贪心，发现不可能同时出现三个不取的情况（因为这样就可以取中间那个，线性基里面不加白不加，反正不会更劣）。
关注线性基的撤销操作（del函数），赛时脑子糊了没写，用 $(int)(log2(maxn+1))$ 这边加优化过去的，实则可以用1个1e18和49个1来进行hack（TLE）。用撤销就好啦（复杂度正确qwqq）~

CPP

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define int long long 
using namespace std;
int T,n,ans,cnt,lll,p[233],a[233],maxn;
int pre[233],rec[233];
bool vis[233];
void ins(int x,int tim) {   
    for (int i=lll;i>=0;i--) {
        if (x&(1ll<<i)) {
            if (!p[i]) {pre[tim]=p[i];rec[tim]=i;p[i]=x;break;}
                else    x^=p[i];
        }
    }
}
void del(int x,int tim) {
	if (pre[tim]==-1||rec[tim]==-1) return ;
	p[rec[tim]]=pre[tim];
	pre[tim]=-1,rec[tim]=-1;
}
int askmax() {
    int res=0;
    for (int i=lll;i>=0;i--) {
        if ((res^p[i])>res) res^=p[i];
    }
    return res;
}
int js() {
    int tmp=askmax();
    return tmp;
}
void dfs(int x) {
    if (x==n) {
        if (vis[n]==0&&vis[n-1]==0) return ;
        int tmp=js(); cnt++;
        if (ans<tmp) {
            ans=tmp;
        }
        return ;
    }
    if (vis[x]==1) {
        vis[x+1]=0;
        dfs(x+1);
        return ;
    }
    if (!(vis[x]||vis[x-1])) {
        vis[x+1]=1; ins(a[x+1],x+1);
        dfs(x+1); del(a[x+1],x+1);
    }
    else {
        vis[x+1]=1; ins(a[x+1],x+1);
        dfs(x+1); del(a[x+1],x+1);
        vis[x+1]=0;
        dfs(x+1);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;
    while (T--) {
        ans=0; maxn=0;
        cin>>n;
        for (int i=1;i<=n;i++) {
            cin>>a[i]; vis[i]=0;
            maxn=max(maxn,a[i]);
        }
        lll=(int)(log2(maxn+1));
        for (int i=0;i<=62;i++) p[i]=0,pre[i]=rec[i]=-1;
        vis[1]=1; ins(a[1],1);
   

---

     dfs(1); del(a[1],1);
        vis[1]=0;
        dfs(1);
        cout<<ans<<'\n';
    }
    return 0;
}

1011. 10010 (65/638)

1001. 骰子 (54/279)

2025.7.22

"现代汽车前瞻杯"2025牛客暑期多校训练营3

F. Flower (1597/2710)

水题，不述。

J. Jetton (1510/5586)

队友嘴的结论题，但是注释处TLE了一发，战犯了。

CPP

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int T,n,a,b,mi2[233];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>T;
	mi2[0]=1;
	for (int i=1;i<=32;i++) mi2[i]=mi2[i-1]*2;
	while (T--) {
		int x,y; cin>>x>>y;
		if ((x+y)&1) {
			cout<<-1<<'\n';
			continue;
		}
		int tot=0;
		int g=__gcd(x,y);
		x/=g,y/=g;
		bool tf=1;
		while ((x!=1&&y!=1)) {
			tot++;
			if (x>y) swap(x,y);
			if (x<y) {
				int xx=x;
				x+=xx; y-=xx;
			}
			g=__gcd(x,y);
			x/=g,y/=g;	
			if ((x+y)&1) { //加这句，不然会TLE！ 
				tf=0;
				break;
			}
		}
		if (tf==0) {
			cout<<-1<<'\n';
			continue;
		}
		int ans=-1;
		for (int i=0;i<=32;i++) {
			if ((x+y)==mi2[i]) {
				ans=i;
				break;
			}
		}
		if (ans==-1) cout<<-1<<'\n';
				else cout<<ans+tot<<'\n';
	}	
	return 0;
}

D. Distant Control (1534/3163)

签到题，不述。

A. Ad-hoc Newbie (1040/2892)

赛时是队友写的。但是自己vp时候卡住了/ll

以下是提交记录里的一个很巧妙的构造方法：

对于每一个

n

，我们构造一个初始矩阵。

CPP

然后我们对每一个

f[j]

，我们把它所在列的那个

f[j]

改成

0

就行了。

CPP

	while (T--) {
		cin>>n;
		for (int i=1;i<=n;i++) cin>>f[i].val;
		for (int j=1;j<=n;j++) {
			a[j][j]=1;
			for (int i=1;i<=j-1;i++) a[i][j]=i+1;
		}	
		for (int j=1;j<=n;j++) {
			if (f[j].val==1) {
				a[j][j]=0;
			}
			else {
				a[f[j].val-1][j]=0;
			}
		}
		for (int j=1;j<=n;j++) {
			for (int i=1;i<=j-1;i++) {
				a[j][i]=a[i][j];
			}
		}
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=n;j++) {
				cout<<a[i][j]<<" ";
			}
			cout<<endl;
		}
	}

E. Equal (950/6982)

CPP

i=2 factor[i]=0
i=3 factor[i]=0
i=4 factor[i]=2
i=5 factor[i]=0
i=6 factor[i]=2
i=7 factor[i]=0
i=8 factor[i]=2
i=9 factor[i]=3
i=10 factor[i]=2
i=11 factor[i]=0
i=12 factor[i]=2
i=13 factor[i]=0
i=14 factor[i]=2
i=15 factor[i]=3
i=16 factor[i]=2
i=17 factor[i]=0
i=18 factor[i]=2
i=19 factor[i]=0
i=20 factor[i]=2
i=21 factor[i]=3
i=22 factor[i]=2
i=23 factor[i]=0
i=24 factor[i]=2
i=25 factor[i]=5
i=26 factor[i]=2
i=27 factor[i]=3
i=28 factor[i]=2
i=29 factor[i]=0
i=30 factor[i]=2
i=31 factor[i]=0
i=32 factor[i]=2
i=33 factor[i]=3
i=34 factor[i]=2
i=35 factor[i]=5
i=36 factor[i]=2
i=37 factor[i]=0
i=38 factor[i]=2
i=39 factor[i]=3
i=40 factor[i]=2
i=41 factor[i]=0
i=42 factor[i]=2
i=43 factor[i]=0
i=44 factor[i]=2
i=45 factor[i]=3
i=46 factor[i]=2
i=47 factor[i]=0
i=48 factor[i]=2
i=49 factor[i]=7

factor[i]

表示

i

的最小质因数（非自己本身）

这是队友的赛时代码：注意利用

factor

数组的质因数分解写法。（自己赛后vp一开始写的TLE了，小丑了）

CPP

#pragma GCC optimize("Ofast,unroll-loops,inline")
#include <bits/stdc++.h>

const int N = 5e6 + 7;

std::vector<int> prime;
int n, a[N], factor[N], cnt[N]; bool isprime[N];

bool solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a + i);

    if(n == 2) return a[1] == a[2];

    std::vector<int> lis;
    for(int i = 1; i <= n; i++) {
        int x = a[i];
        while(!isprime[x]) cnt[factor[x]]++, lis.push_back(factor[x]), x /= factor[x];
        if(x > 1) cnt[x]++, lis.push_back(x);
    }

    bool ans = 1;
    for(int i : lis) ans &= (cnt[i] % 2 == 0 || ((n - cnt[i]) % 2 + 2) % 2 == 0);
    
    for(int i : lis) cnt[i] = 0;
    return ans;
}

int main() {
    memset(isprime, 1, sizeof isprime);
    for(int i = 2; i <= 5e6; i++) {
        if(isprime[i]) prime.push_back(i);
        for(int j = 0; j < (int)prime.size() && i * prime[j] <= 5e6; j++) {
            isprime[i * prime[j]] = 0, factor[i * prime[j]] = prime[j];
            // factor[i]表示i的最小质因数（非自己本身） ！ 
            if(i % prime[j] == 0) break;
        }
    }

    int T; scanf("%d", &T); while(T--) puts(solve() ? "YES" : "NO");
    return 0;
}

H. Head out to the Target (451/1418)

最后一小时队友看着写的，谢谢李老师（doge）/kel

但是战犯了，不仅写得慢，而且//!!!的初始化忘了（队友查出来的）。

赛时一开始想这道题的思路：我们的策略肯定是只往深度更大的点走。但是想到这然后卡机了，一直想着从上往下去遍历，然后树剖，然而纯属想麻烦了。
所以我们对于这种题，可以考虑从下往上做！怎么做呢？我们可以想到倍增往上跳（这个复杂度和难度也都很合理qwq）：
我们用 $col[x]$ 表示边 $fa[x][0] \to x$ 这条边是否被覆盖过。
所以我们知道，对于每一条树上的链，从上到下，边的 $col$ 肯定是先是一堆1再是一堆0。
按时间遍历，对于每一个出现目标，我们找到最上面的、没有被覆盖过的边 $v->son[v]$ （ $son$ 指这一条链上的）。然后从这个 $v$ 往下走目标存在时间长度的边，看能不能走到 $u$ ，如果能走到就直接输出了。
如果不能走到，就从这个 $v$ 往下覆盖目标存在时间的长度的边即可。
写的时候要记得考虑 $l$ ， $r$ 的那些加一减一的边界问题。

自己的代码能力还是抽象了/ll 菜就多练吧qwq

CPP

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1000006;
struct qwq{
	int hext,to;
}e[N<<1];
struct QAQ{
	int u,l,r;
}a[N];
int n,k,tot,col[N],dep[N],head[N],fa[N][22];
void add(int x,int y) {
	e[++tot].hext=head[x];
	e[tot].to=y;
	head[x]=tot;
}

void dfs1(int x,int fath) {
	dep[x]=dep[fath]+1;
	for (int i=1;i<=20;i++) {
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for (int i=head[x];i;i=e[i].hext) {
		int v=e[i].to;
		dfs1(v,x);
	}
	return ;
}
int query(int x,int d) { //寻找x的深度为d的祖先 
	for (int i=20;i>=0;i--) {
		if (dep[fa[x][i]]>=d) {
			x=fa[x][i];
		}
	}
	return x;	
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>k;
	for (int i=2;i<=n;i++) {
		cin>>fa[i][0];
		add(fa[i][0],i);
	}
	for (int i=1;i<=k;i++) {
		cin>>a[i].u>>a[i].l>>a[i].r;
	}
	col[0]=col[1]=1; //!!!
	for (int i=2;i<=n;i++) col[i]=0;
	dfs1(1,0);
	for (int qwq=1;qwq<=k;qwq++) {
		int u=a[qwq].u,l=a[qwq].l,r=a[qwq].r;
		int v=u;
		if (col[u]==1) {
			cout<<l<<endl;
			return 0;
		}
		for (int i=20;i>=0;i--) {
			if (col[fa[v][i]]==0) {
				v=fa[v][i];
			}
		}
		if (v==0) v=1;
		if (dep[u]-(r-l)<=dep[v]) {
			cout<<dep[u]-dep[v]+l<<endl;
			return 0;
		}
		int w=query(u,dep[v]+(r-l));			
		int x=w;col[w]=col[v]=1;
		while (x!=v) {
			col[x]=1;
			x=fa[x][0];
		}
	}
	cout<<-1<<endl;	
	return 0;
}

B. Bitwise Puzzle (412/3034)

赛时成功给出了一个hack，有空自己补一下这题的完整代码。

2025暑期算法竞赛学习笔记（多校/vp记录2）

文章操作

2025.7.19

CCPC 2024 哈尔滨

M. Weird Ceiling （685/690）

C. Giving Directions in Harbin（677/684）

G. Welcome to Join the Online Meeting （654/671）

K. Farm Management （594/651）

J. New Energy Vehicle (476/636)

L. A Game On Tree （230/251）

B. Concave Hull (188/252)

A. Build a Computer (220/308)

E. Marble Race （161/174）

2025.7.21

2025“钉耙编程”中国大学生算法设计暑期联赛（2）

1002. 数上的图 (1128/2553)

1008. 井 (1046/1780)

1006. 半 (1024/2734)

1009. 苹果树 (479/2855)

1012. 子集 (364/5193)

1011. 10010 (65/638)

1001. 骰子 (54/279)

2025.7.22

"现代汽车前瞻杯"2025牛客暑期多校训练营3

F. Flower (1597/2710)

J. Jetton (1510/5586)

D. Distant Control (1534/3163)

A. Ad-hoc Newbie (1040/2892)

E. Equal (950/6982)

H. Head out to the Target (451/1418)

B. Bitwise Puzzle (412/3034)

相关推荐

评论

2025暑期算法竞赛学习笔记（多校/vp记录2）