多校A层冲刺NOIP2024模拟赛08
\(T1\) A. 传送 (teleport) \(0pts\)
-
弱化版： [ABC065D] Built? | luogu P8074 [COCI2009-2010#7] SVEMIR | “迎新春，过大年”多校程序设计竞赛 H 二次元世界之寻找珂朵莉
-
先不管后面加入的 \(m\) 条边。
-
对于两点间的路径 \(i \to j\) ，经过中转点 \(k\) 更优当且仅当 \(i \to k\) 和 \(k \to j\) 的路径不同向（不同时是 \(x\) 轴路线且不同时是 \(y\) 轴路线）。
-
为处理同向间的不必要路径，不妨让所有点先后以横纵坐标排序，相邻两点之间连一条边即可。此时所连的边只有 \(2(n-1)\) 条，加上后面加入的 \(m\) 条边后跑 \(Dijsktra\) 即可。
点击查看代码
vector<pair<ll,ll> >e[200010]; ll p[200010],x[200010],y[200010],vis[200010],dis[200010]; void add(ll u,ll v,ll w) {e[u].push_back(make_pair(v,w)); } bool cmp_x(ll a,ll b) {return x[a]<x[b]; } bool cmp_y(ll a,ll b) {return y[a]<y[b]; } void dijsktra(ll s) {memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));priority_queue<pair<ll,ll> >q;dis[s]=0;q.push(make_pair(-dis[s],s));while(q.empty()==0){ll x=q.top().second;q.pop();if(vis[x]==0){vis[x]=1;for(ll i=0;i<e[x].size();i++){if(dis[e[x][i].first]>dis[x]+e[x][i].second){dis[e[x][i].first]=dis[x]+e[x][i].second;q.push(make_pair(-dis[e[x][i].first],e[x][i].first));}}}} } int main() {freopen("teleport.in","r",stdin);freopen("teleport.out","w",stdout);ll n,m,u,v,w,i;cin>>n>>m;for(i=1;i<=n;i++){cin>>x[i]>>y[i];p[i]=i;}for(i=1;i<=m;i++){cin>>u>>v>>w;add(u,v,w);add(v,u,w);}sort(p+1,p+1+n,cmp_x);for(i=2;i<=n;i++){add(p[i],p[i-1],x[p[i]]-x[p[i-1]]);add(p[i-1],p[i],x[p[i]]-x[p[i-1]]);}for(i=1;i<=n;i++){p[i]=i;}sort(p+1,p+1+n,cmp_y);for(i=2;i<=n;i++){add(p[i],p[i-1],y[p[i]]-y[p[i-1]]);add(p[i-1],p[i],y[p[i]]-y[p[i-1]]);}dijsktra(1);for(i=2;i<=n;i++){cout<<dis[i]<<" ";}fclose(stdin);fclose(stdout);return 0; }
\(T2\) B. 排列 (permutation) \(20pts\)
- 部分分
- 子任务 \(1\) ：爆搜。
- 子任务 \(3\) ：至多有一个数为 \(k\) 的倍数，故 \(n!\) 即为所求。
- 正解
-
将 \(1 \sim n\) 中是 \(k\) 的倍数的数看做断点。
-
观察到 \(\frac{n}{k} \le 10\) ，枚举全排列后对相邻两数 \(\gcd=1\) 的进行插板法，最后再乘以 \((n-\left\lfloor \frac{n}{k} \right\rfloor)!\) 即可。
点击查看代码
const ll p=998244353; ll a[3010],inv[3010],jc[3010],jc_inv[3010]; 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; } ll C(ll n,ll m,ll p) {return (n>=m&&n>=0&&m>=0)?(jc[n]*jc_inv[n-m])%p*jc_inv[m]%p:0; } ll A(ll n,ll m,ll p) {return (n>=m&&n>=0&&m>=0)?(jc[n]*jc_inv[n-m])%p:0; } int main() {freopen("permutation.in","r",stdin);freopen("permutation.out","w",stdout);ll n,k,m,ans=0,sum=0,i;cin>>n>>k;m=n/k;for(i=1;i<=m;i++){a[i]=i;}jc[0]=jc_inv[0]=1;for(i=1;i<=n;i++){inv[i]=qpow(i,p-2,p);jc[i]=jc[i-1]*i%p;jc_inv[i]=jc_inv[i-1]*inv[i]%p;}do{sum=0;for(i=2;i<=m;i++){sum+=(gcd(a[i],a[i-1])==1);}ans=(ans+C(n-m-sum+m+1-1,m+1-1,p))%p;}while(next_permutation(a+1,a+1+m));cout<<ans*A(n-m,n-m,p)%p<<endl;fclose(stdin);fclose(stdout);return 0; }
-
\(T3\) C. 战场模拟器 (simulator) \(9pts\)
-
弱化版： 北京建筑大学2024年程序设计竞赛（同步赛） A 寿命修改
-
部分分
-
子任务 \(1\) ：模拟。
-
子任务 \(2\) ：线段树维护。
-
子任务 \(3\)
-
-
正解
- 因为每个英雄只会死一次，且只有 \(O(q)\) 个护盾，势能线段树即可。
- 特别地，需要维护最小非负生命值出现次数来计算濒死数量。
点击查看代码
ll a[200010]; struct SMT {struct SegmentTree{ll sum,minn,cnt,died,lazy;}tree[800010];ll lson(ll x){return x*2;}ll rson(ll x){return x*2+1;}void pushup(ll rt){tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum;tree[rt].minn=min(tree[lson(rt)].minn,tree[rson(rt)].minn);tree[rt].cnt=(tree[lson(rt)].minn==tree[rt].minn)*tree[lson(rt)].cnt+(tree[rson(rt)].minn==tree[rt].minn)*tree[rson(rt)].cnt;tree[rt].died=tree[lson(rt)].died+tree[rson(rt)].died;}void build(ll rt,ll l,ll r){if(l==r){tree[rt].minn=a[l];tree[rt].cnt=1;return;}ll mid=(l+r)/2;build(lson(rt),l,mid);build(rson(rt),mid+1,r);pushup(rt);}void pushdown(ll rt){if(tree[rt].lazy!=0){tree[lson(rt)].lazy+=tree[rt].lazy;tree[lson(rt)].minn+=tree[rt].lazy;tree[rson(rt)].lazy+=tree[rt].lazy;tree[rson(rt)].minn+=tree[rt].lazy;tree[rt].lazy=0;}}void update1(ll rt,ll l,ll r,ll x,ll y,ll val){if(tree[rt].died==r-l+1){return;}if(l==r){if(tree[rt].sum==0){tree[rt].minn-=val;if(tree[rt].minn<0){tree[rt].minn=0x7f7f7f7f;tree[rt].died=1;}}else{tree[rt].sum--;}return;}if(x<=l&&r<=y){if(tree[rt].sum==0&&tree[rt].minn-val>=0){tree[rt].minn-=val;tree[rt].lazy-=val;return;}}pushdown(rt);ll mid=(l+r)/2;if(x<=mid){update1(lson(rt),l,mid,x,y,val);}if(y>mid){update1(rson(rt),mid+1,r,x,y,val);}pushup(rt);}void update2(ll rt,ll l,ll r,ll x,ll y,ll val){if(tree[rt].died==r-l+1){return;}if(x<=l&&r<=y){tree[rt].minn+=val;tree[rt].lazy+=val;return;}pushdown(rt);ll mid=(l+r)/2;if(x<=mid){update2(lson(rt),l,mid,x,y,val);}if(y>mid){update2(rson(rt),mid+1,r,x,y,val);}pushup(rt);}void update3(ll rt,ll l,ll r,ll pos){if(tree[rt].died==r-l+1){return;}if(l==r){tree[rt].sum++;return;}pushdown(rt);ll mid=(l+r)/2;if(pos<=mid){update3(lson(rt),l,mid,pos);}else{update3(rson(rt),mid+1,r,pos);}pushup(rt);}ll query1(ll rt,ll l,ll r,ll x,ll y){if(x<=l&&r<=y){return tree[rt].died;}pushdown(rt);ll mid=(l+r)/2,ans=0;if(x<=mid){ans+=query1(lson(rt),l,mid,x,y);}if(y>mid){ans+=query1(rson(rt),mid+1,r,x,y);}return ans;}ll query2(ll rt,ll l,ll r,ll x,ll y){if(x<=l&&r<=y){return (tree[rt].minn==0)*tree[rt].cnt;}pushdown(rt);ll mid=(l+r)/2,ans=0;if(x<=mid){ans+=query2(lson(rt),l,mid,x,y);}if(y>mid){ans+=query2(rson(rt),mid+1,r,x,y);}return ans;} }T; int main() {freopen("simulator.in","r",stdin);freopen("simulator.out","w",stdout);ll n,q,pd,l,r,x,i;cin>>n;for(i=1;i<=n;i++){cin>>a[i];}T.build(1,1,n);cin>>q;for(i=1;i<=q;i++){cin>>pd;if(pd==1){cin>>l>>r>>x;T.update1(1,1,n,l,r,x);}if(pd==2){cin>>l>>r>>x;T.update2(1,1,n,l,r,x);}if(pd==3){cin>>x;T.update3(1,1,n,x);}if(pd==4){cin>>l>>r;cout<<T.query1(1,1,n,l,r)<<endl;}if(pd==5){cin>>l>>r;cout<<T.query2(1,1,n,l,r)<<endl;}}fclose(stdin);fclose(stdout);return 0; }
\(T4\) D. 点亮 (light) \(0pts\)
总结
- \(T1\) 输出成了 \(1\) 到 \(1 \sim n\) 的最短路，而且 \(Dijsktra\) 加入队列时把边权当做点的标号加进去了，挂了 \(40pts\) 。
- \(T2\) 误认为只要是 \(k\) 的倍数，相邻两数的 \(\gcd\) 就等于 \(k\) ，得到的 \(O(\frac{n^{2}}{k})\) 做法假了。
- \(T3\) 直接去写势能线段树正解了的，但最后正解没调出来，部分分一点没打。
