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

午尘 · 2025-07-20 21:47:17 · 个人记录

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种油它是哪个加油站来的。
走到每一个加油站时，我们先对目前这个加油站前的所有可加的油进行加油，然后如果不够再用初始油箱。完成这个操作之后，我们对此加油站种类的油进行一个油量加满的更新即可。

#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)

#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！
这题一开始挂了是因为：求三角形的面积的时候采用底乘以高（因为要算距离最近的点，既然距离都算了，就偷懒直接去用这东西算了），然后爆精度了：用叉乘！！！

#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）

一道可撤销背包。

#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)

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

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

1006. 半 (1024/2734)

树状数组即可。

#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 的值。然后我们就不难想到怎么区间合并啦！

#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）~

#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了一发，战犯了。

#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 ，我们构造一个初始矩阵。

然后我们对每一个 f[j]，我们把它所在列的那个 f[j] 改成 0 就行了。

    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)

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$ 数组的质因数分解写法。（自己赛后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) ](https://ac.nowcoder.com/acm/contest/108300/H) 最后一小时队友看着写的，谢谢李老师（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)](https://ac.nowcoder.com/acm/contest/108300/B) 赛时成功给出了一个hack，有空自己补一下这题的完整代码。