多校A层冲刺NOIP2024模拟赛07
\(T1\) A. 限速（speed） \(40pts\)
-
设最终保留的边的权值构成的集合为 \(S\) 。那么其贡献为 \(\begin{cases} k-\max\limits_{x \in S}\{ x \} & \max\limits_{x \in S}\{ x \} \le k \\ \sum\limits_{x \in S}[x>k] \times (x-k) & \max\limits_{x \in S}\{ x \}>k \end{cases}\) 。
-
两种情况一起考虑贡献不太好做，考虑分开统计。
-
若仅用边权 \(\le k\) 的边无法使整张图连通，则类似 \(Kruskal\) 的写法逐个将边权 \(>k\) 的边加入其中，直接统计贡献。
-
若仅用边权 \(\le k\) 的边可以使整张图连通，又分为两种情况。
- 若仅用边权 \(\le k\) 的边，则直接统计贡献。
- 否则可以证明最多加入一条边权 \(>k\) 的边（且任意一条边均可以）替换一条边权 \(\le k\) 的边从而使得图连通，得到的贡献和上个贡献取 \(\min\) 。
点击查看代码
struct node { ll from,to,w; }e[200010]; bool cmp(node a,node b) { return a.w<b.w; } struct DSU { ll fa[200010]; void init(ll n) { for(ll i=1;i<=n;i++) { fa[i]=i; } } ll find(ll x) { return (fa[x]==x)?x:fa[x]=find(fa[x]); } }D; int main() { freopen("speed.in","r",stdin); freopen("speed.out","w",stdout); ll n,m,k,len,maxx=0,sum=0,cnt=0,ans=0,x,y,i; cin>>n>>m>>k; len=m; for(i=1;i<=m;i++) { cin>>e[i].from>>e[i].to>>e[i].w; } sort(e+1,e+1+m,cmp); for(i=1;i<=m;i++) { if(e[i].w>k) { len=i-1; break; } } D.init(n); for(i=len;i>=1;i--) { x=D.find(e[i].from); y=D.find(e[i].to); if(x!=y) { D.fa[x]=y; cnt++; maxx=max(maxx,e[i].w); } } if(cnt==n-1) { ans=k-maxx; if(len+1<=m) { ans=min(ans,e[len+1].w-k); } } else { for(i=len+1;i<=m;i++) { x=D.find(e[i].from); y=D.find(e[i].to); if(x!=y) { D.fa[x]=y; sum+=e[i].w-k; } } ans=sum; } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T2\) B. 酒鬼 （drunkard） \(18pts\)
-
部分分
- 子任务 \(1\) ：先走到 \(q_{i}\) ，然后开始左右移动从而拖延时间，故 \((q_{i}-p_{i}+1) \mod 2\) 即为所求。
- 子任务 \(2\) ：直接走到 \(q_{i}\) ，故 \(q_{i}-p_{i}+1\) 即为所求。
点击查看代码
string s; int main() { freopen("drunkard.in","r",stdin); freopen("drunkard.out","w",stdout); int n,m,p,q,i; cin>>n>>m; if(m==2) { cin>>s>>p>>q; cin>>s; if(s=="min") { if((q-(p-1))%2==0) { cout<<0<<endl; } else { cout<<1<<endl; } } else { cout<<q-(p-1)<<endl; } } else { for(i=1;i<=m;i++) { cin>>s; if(s=="clue") { cin>>p>>q; } else { cout<<"bad"<<endl; } } } fclose(stdin); fclose(stdout); return 0; }
\(T3\) C. 距离（distance） \(70pts\)
- 部分分
-
\(40pts\) ：模拟，会被链卡到飞起，时间复杂度为 \(O(n^{3})\) 。
点击查看代码
const int p=1000000007; struct node { int nxt,to; }e[1000010]; int head[1000010],dfn[1000010],out[1000010],pos[1000010],a[1000010],b[1000010],cnt=0,tot=0; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x,int fa) { tot++; dfn[x]=tot; pos[tot]=x; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dfs(e[i].to,x); } } out[x]=tot; } int qadd(int a,int b,int p) { return a+b>=p?a+b-p:a+b; } int main() { freopen("distance.in","r",stdin); freopen("distance.out","w",stdout); int n,u,v,ans=0,i,j,k; scanf("%d",&n); for(i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); } dfs(1,0); for(i=1;i<=n;i++) { ans=0; for(j=dfn[i];j<=out[i];j++) { for(k=dfn[i];k<=out[i];k++) { ans=qadd(ans,min(abs(a[pos[j]]-a[pos[k]]),abs(b[pos[j]]-b[pos[k]])),p); } } printf("%d\n",ans); } fclose(stdin); fclose(stdout); return 0; } -
\(70pts\) ：子树信息可以直接合并，每对点对之间的贡献只会被算一次，随便写个什么维护即可，时间复杂度为 \(O(n^{2})\) 。
点击查看代码
const int p=1000000007; struct node { int nxt,to; }e[1000010]; int head[500010],dfn[500010],out[500010],pos[500010],a[500010],b[500010],ans[500010],cnt=0,tot=0; vector<short>rt[10010]; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void merge(int x,int y) { if(rt[x].size()<rt[y].size()) { swap(rt[x],rt[y]); } for(int i=0;i<rt[y].size();i++) { rt[x].push_back(rt[y][i]); } } int qadd(int a,int b,int p) { return a+b>=p?a+b-p:a+b; } void dfs(int x,int fa) { tot++; dfn[x]=tot; pos[tot]=x; rt[x].push_back(x); for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dfs(e[i].to,x); ans[x]=qadd(ans[x],ans[e[i].to],p); for(int j=0;j<rt[e[i].to].size();j++) { for(int k=0;k<rt[x].size();k++) { ans[x]=qadd(ans[x],min(abs(a[rt[e[i].to][j]]-a[rt[x][k]]),abs(b[rt[e[i].to][j]]-b[rt[x][k]]))*2%p,p); } } merge(x,e[i].to); } } out[x]=tot; } int main() { freopen("distance.in","r",stdin); freopen("distance.out","w",stdout); int n,u,v,i; scanf("%d",&n); for(i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); } dfs(1,0); for(i=1;i<=n;i++) { printf("%d\n",ans[i]); } fclose(stdin); fclose(stdout); return 0; }
-
- 正解
-
先将 \(\min(|a_{i}-a_{j}|,|b_{i}-b_{j}|)\) 容斥成 \(|a_{i}-a_{j}|+|b_{i}-b_{j}|-\max(|a_{i}-a_{j}|,|b_{i}-b_{j}|)\) ，难点在于怎么求后面的 \(\max(|a_{i}-a_{j}|,|b_{i}-b_{j}|)\) 。
-
将 \(\{ a \}\) 看做横坐标， \(\{ b \}\) 看做纵坐标，等价于询问曼哈顿坐标系下以 \(x\) 为根的子树内的节点两两距离之和。
-
考虑转化成曼哈顿距离，令 \(\forall i \in [i,n],p_{i}=\frac{a_{i}+b_{i}}{2},q_{i}=\frac{a_{i}-b_{i}}{2}\) ，则 \(\max\limits(|a_{i}-a_{j}|,|b_{i}-b_{j}|)=|p_{i}-p_{j}|+|q_{i}-q_{j}|\) ，等价于询问 \(\sum\limits_{i \in Subtree(x)}\sum\limits_{j \in Subtree(x)}|a_{i}-a_{j}|+|b_{i}-b_{j}|-|p_{i}-p_{j}|+|q_{i}-q_{j}|\) 。
- 拆绝对值，有 \(\begin{aligned} &|p_{i}-p_{j}|+|q_{i}-q_{j}| \\ &=\max\limits(p_{i}-p_{j},p_{j}-p_{i})+\max\limits(q_{i}-q_{j},q_{j}-q_{i}) \\ &=\max(\frac{a_{i}+b_{i}-a_{j}-b_{j}}{2},\frac{a_{j}+b_{j}-a_{i}-b_{i}}{2})+\max(\frac{a_{i}-b_{i}-a_{j}+b_{j}}{2},\frac{a_{j}-b_{j}-a_{i}+b_{i}}{2}) \\ &=\max(a_{i}-a_{j},a_{j}-a_{i},b_{i}-b_{j},b_{j}-b_{i}) \\ &=\max(|a_{i}-a_{j}|,|b_{i}-b_{j}|) \end{aligned}\) 。
-
以 \(\{ a \}\) 为例，用线段树对 \(\{ a \}\) 开一个桶数组。当插入一个新的数 \(a_{i}\) 时维护 \(<a_{i}, \ge a_{i}\) 的元素的数量及和，从而得到贡献。树上启发式合并的时间复杂度为 \(O(n \log^{2} n)\) ，因为 accoders NOI 和学校 \(OJ\) 上开了 \(7s/5s\) ，所以可以通过。
-
线段树合并的时间复杂度为 \(O(n \log n)\) 。具体地，对于以 \(x\) 为根的子树内的节点的值构成的有序数组 \(\{ a \}\) ，设 \(ans_{l,r},sum_{l,r},cnt_{l,r}\) 分别表示 \([l,r]\) 的贡献/元素和/元素数量，则有 \(ans_{l,r}=ans_{l,mid}+ans_{mid+1,r}+sum_{mid+1,r} \times cnt_{1,mid}-sum_{1,mid} \times cnt_{mid+1,n}\) 。向上递归时
pushup即可。点击查看代码
const ll mod=1000000007; struct node { int nxt,to; }e[1000010]; int head[500010],cnt=0; ll a[500010],aa[500010],b[500010],bb[500010],p[500010],pp[500010],q[500010],qq[500010],ans[500010]; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } struct SMT { int root[500010],rt_sum=0; struct SegmentTree { int ls,rs; ll sum,cnt,ans; }tree[500010*32]; #define lson(rt) (tree[rt].ls) #define rson(rt) (tree[rt].rs) void clear() { rt_sum=0; memset(root,0,sizeof(root)); } int build() { rt_sum++; lson(rt_sum)=rson(rt_sum)=tree[rt_sum].sum=tree[rt_sum].cnt=tree[rt_sum].ans=0; return rt_sum; } void pushup(int rt) { tree[rt].sum=(tree[lson(rt)].sum+tree[rson(rt)].sum)%mod; tree[rt].cnt=(tree[lson(rt)].cnt+tree[rson(rt)].cnt)%mod; tree[rt].ans=((tree[lson(rt)].ans+tree[rson(rt)].ans)%mod+tree[rson(rt)].sum*tree[lson(rt)].cnt%mod-tree[lson(rt)].sum*tree[rson(rt)].cnt%mod+mod)%mod; } void update(int &rt,int l,int r,int pos,int val) { rt=(rt==0)?build():rt; if(l==r) { tree[rt].cnt=(tree[rt].cnt+1)%mod; tree[rt].sum=(tree[rt].sum+val)%mod; return; } int mid=(l+r)/2; if(pos<=mid) { update(lson(rt),l,mid,pos,val); } else { update(rson(rt),mid+1,r,pos,val); } pushup(rt); } int merge(int rt1,int rt2,int l,int r) { if(rt1==0||rt2==0) { return rt1+rt2; } if(l==r) { tree[rt1].sum=(tree[rt1].sum+tree[rt2].sum)%mod; tree[rt1].cnt=(tree[rt1].cnt+tree[rt2].cnt)%mod; return rt1; } int mid=(l+r)/2; lson(rt1)=merge(lson(rt1),lson(rt2),l,mid); rson(rt1)=merge(rson(rt1),rson(rt2),mid+1,r); pushup(rt1); return rt1; } }T; void dfs(int x,int fa,ll d,ll a[],ll aa[]) { for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dfs(e[i].to,x,d,a,aa); T.root[x]=T.merge(T.root[x],T.root[e[i].to],1,aa[0]); } } T.update(T.root[x],1,aa[0],a[x],aa[a[x]]); ans[x]=(ans[x]+T.tree[T.root[x]].ans*d%mod+mod)%mod; } void solve(int n,ll d,ll a[],ll aa[]) { T.clear(); for(int i=1;i<=n;i++) { aa[i]=a[i]; } sort(aa+1,aa+1+n); aa[0]=unique(aa+1,aa+1+n)-(aa+1); for(int i=1;i<=n;i++) { a[i]=lower_bound(aa+1,aa+1+aa[0],a[i])-aa; } for(int i=1;i<=aa[0];i++) { aa[i]=(aa[i]+mod)%mod; } dfs(1,0,d,a,aa); } int main() { freopen("distance.in","r",stdin); freopen("distance.out","w",stdout); int n,u,v,i; ll inv=qpow(2,mod-2,mod); scanf("%d",&n); for(i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } for(i=1;i<=n;i++) { scanf("%lld%lld",&a[i],&b[i]); p[i]=a[i]+b[i]; q[i]=a[i]-b[i]; } solve(n,1,a,aa); solve(n,1,b,bb); solve(n,(mod-inv)%mod,p,qq); solve(n,(mod-inv)%mod,q,pp); for(i=1;i<=n;i++) { printf("%lld\n",ans[i]*2%mod); } fclose(stdin); fclose(stdout); return 0; }
-
\(T4\) D. 团队选拔（selection） \(8pts\)
-
部分分
- \(8pts\) ：爆搜。
点击查看代码
const ll p=998244353; ll a[100010],vis[100010],ans[100010]; ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } void dfs(ll pos,ll n,ll pre) { if(pos==n+1) { ll flag=1,pos=0,d=0,last=0; for(ll i=1;i<=n;i++) { if(vis[i]!=0) { last=gcd(last,a[i]); if(vis[i]!=vis[i+1]) { pos=i; break; } } } for(ll i=pos+1;i<=n;i++) { if(vis[i]!=0) { d=gcd(d,a[i]); if(vis[i]!=vis[i+1]) { flag&=(d==0||d==last); d=0; } } else { flag&=(d==0||d==last); d=0; } } if(flag==1) { for(ll i=1;i<=n;i++) { if(vis[i]!=0) { ans[i]=(ans[i]+1)%p; } } } } else { if(vis[pos-1]!=0) { vis[pos]=vis[pos-1]; dfs(pos+1,n,pos); } vis[pos]=vis[pre]+1; dfs(pos+1,n,pos); vis[pos]=0; dfs(pos+1,n,pre); } } int main() { freopen("selection.in","r",stdin); freopen("selection.out","w",stdout); ll n,i; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); } dfs(1,n,1); for(i=1;i<=n;i++) { printf("%lld ",ans[i]); } fclose(stdin); fclose(stdout); return 0; }
总结
- \(T1\) 边权 $ \le k$ 的边界点初始值写错了，而且误认为 \(k-\max\limits_{x \in S}\{ x \}=\max\limits_{x \in S} \{ k-x \}\) ，挂了 \(60pts\) 。
- \(T2\) 写完后以为原来代码搞反了 \(p,q\) 的含义遂反转了过来，结果是原来代码没写反，挂了 \(9pts\) 。
- 写 \(T4\) 爆搜的时间用得太多了。
后记
- \(T2\) 的大样例下发文件里夹杂着 \(T4\) 的大样例， \(T4\) 的大样例下发文件里不知道是个什么东西。
- \(T1,T2,T4\) 均出自 [2024暑期交流小组] CSP-S & NOIP模拟赛 4 ，故直接搬的官方整个 PDF 题解； \(T3\) 单独下发了题解。