多校A层冲刺NOIP2024模拟赛18
\(T1\) A. 选彩笔（rgb） \(100pts/100pts\)
-
观察到 \(0 \le r,g,b \le 255\) 且答案具有单调性，故考虑二分答案。
-
将 \(r,g,b\) 分别抽象成三维坐标下的 \(x,y,z\) 。
-
设当前二分出的答案为 \(mid\) ，由调整法分析可知若存在一个边长为 \(mid\) 的正方体中点的数量 \(\le k\) 则合法。
-
三维前缀和加速匹配即可。
- 三维前缀和详见 暑假集训CSP提高模拟26 T1' 前缀 。
点击查看代码
int cnt[260][260][260]; int sum(int x1,int y1,int z1,int x2,int y2,int z2) { return cnt[x2][y2][z2]-(-cnt[x1-1][y1-1][z2]-cnt[x1-1][y2][z1-1]-cnt[x2][y1-1][z1-1]+cnt[x1-1][y2][z2]+cnt[x2][y1-1][z2]+cnt[x2][y2][z1-1]+cnt[x1-1][y1-1][z1-1]); } bool check(int mid,int n,int m) { for(int i=1;i<=256-mid;i++) { for(int j=1;j<=256-mid;j++) { for(int k=1;k<=256-mid;k++) { if(sum(i,j,k,i+mid,j+mid,k+mid)>=m) { return true; } } } } return false; } int main() { freopen("rgb.in","r",stdin); freopen("rgb.out","w",stdout); int n,m,r,g,b,l=0,mid,ans=0,i,j,k; cin>>n>>m; for(i=1;i<=n;i++) { cin>>r>>g>>b; r++; g++; b++; cnt[r][g][b]++; } for(i=1;i<=256;i++) { for(j=1;j<=256;j++) { for(k=1;k<=256;k++) { cnt[i][j][k]+=-cnt[i-1][j-1][k]-cnt[i-1][j][k-1]-cnt[i][j-1][k-1]+cnt[i-1][j][k]+cnt[i][j-1][k]+cnt[i][j][k-1]+cnt[i-1][j-1][k-1]; } } } r=256; while(l<=r) { mid=(l+r)/2; if(check(mid,n,m)==true) { ans=mid; r=mid-1; } else { l=mid+1; } } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T2\) B. 兵蚁排序（sort） \(0pts/0pts\)
-
考虑手动模拟下排序的过程，不妨选择冒泡排序。
-
冒泡排序的过程中不断选择长度为 \(2\) 的区间进行排序/交换，从而消除逆序对。这个过程中不会再产生新的逆序对，故若 \(\{ b \}\) 中存在 \(\{ a \}\) 中没有的逆序对则无解。
-
交换的过程中在 \(j \in [i,n]\) 中找到第一个满足 \(a_{j}=b_{i}\) 的 \(j\) ，这个时候直接对 \([i,j]\) 排序是假的（因为破坏内部的关系），就只能自右向左依次交换来保证内部相对大小顺序不变。
- 如果不需要同步交换的话，找到 \(b_{i}\) 对应的 \(a_{j}\) 即可。
-
此时若无法进行交换（大的数不可能跑到小的数前面）即说明 \(\{ b \}\) 中存在 \(\{ a \}\) 中没有的逆序对。
-
考虑加强版时，不进行同步交换，等价于 \(\min\limits_{k=1}^{j}\{ a_{k }\}=b_{i}\) ，可以使用线段树维护区间查询和单点删除（转化为修改）。
点击查看代码
int a[1010],b[1010]; vector<pair<int,int> >ans; int main() { freopen("sort.in","r",stdin); freopen("sort.out","w",stdout); int t,n,flag,pos,i,j,k; cin>>t; for(k=1;k<=t;k++) { cin>>n; flag=0; ans.clear(); for(i=1;i<=n;i++) { cin>>a[i]; } for(i=1;i<=n;i++) { cin>>b[i]; } for(i=1;i<=n;i++) { for(j=i;j<=n;j++) { if(b[i]==a[j]) { pos=j; break; } } for(j=pos;j>=i+1;j--) { if(a[j-1]<a[j]) { flag=-1; break; } swap(a[j-1],a[j]); ans.push_back(make_pair(j-1,j)); } if(flag==-1) { break; } } cout<<flag<<endl; if(flag==0) { cout<<ans.size()<<endl; for(i=0;i<ans.size();i++) { cout<<ans[i].first<<" "<<ans[i].second<<endl; } } } fclose(stdin); fclose(stdout); return 0; }
\(T3\) C. 人口局 DBA（dba） \(7pts/0pts\)
-
部分分
-
\(34pts/10pts\) ：当成数位 \(DP\) 拆位做即可，记忆化搜索。
点击查看代码
const ll p=1000000007; unordered_map<ll,ll>f[2010]; ll a[2010]; ll dfs(ll pos,ll pre,ll limit,ll m,ll sum) { if(pos<=0) { return (pre==sum&&limit==0); } if(limit==0&&f[pos].find(pre)!=f[pos].end()) { return f[pos][pre]; } ll ans=0,maxx=(limit==1)?a[pos]:m-1; for(ll i=0;i<=maxx&&pre+i<=sum;i++) { ans=(ans+dfs(pos-1,pre+i,(limit==1)*(i==maxx),m,sum))%p; } return (limit==0)?f[pos][pre]=ans:ans; } int main() { freopen("dba.in","r",stdin); freopen("dba.out","w",stdout); ll m,sum=0,i; cin>>m>>a[0]; for(i=1;i<=a[0];i++) { cin>>a[i]; sum+=a[i]; } reverse(a+1,a+1+a[0]); cout<<(dfs(a[0],0,1,m,sum)+p)%p<<endl; fclose(stdin); fclose(stdout); return 0; } -
\(64pts/10pts\) ：将记忆化搜索改成递推版。
点击查看代码
const int p=1000000007; int a[2010],f[2][2][4000010]; int qadd(int a,int b,int p) { return a+b>=p?a+b-p:a+b; } int main() { freopen("dba.in","r",stdin); freopen("dba.out","w",stdout); int m,sum=0,i,j,k; cin>>m>>a[0]; for(i=1;i<=a[0];i++) { cin>>a[i]; sum+=a[i]; } reverse(a+1,a+1+a[0]); for(i=0;i<=a[a[0]]-1;i++) { f[a[0]&1][0][i]=1; } f[a[0]&1][1][a[a[0]]]=1; for(i=a[0];i>=1;i--) { for(k=0;k<=sum;k++) { f[(i-1)&1][0][k]=f[(i-1)&1][1][k]=0; } for(k=0;k<=sum;k++) { for(j=0;j<=a[i-1]-1&&k+j<=sum;j++) { f[(i-1)&1][0][k+j]=qadd(f[(i-1)&1][0][k+j],f[i&1][1][k],p); } if(k+a[i-1]<=sum) { f[(i-1)&1][1][k+a[i-1]]=qadd(f[(i-1)&1][1][k+a[i-1]],f[i&1][1][k],p); } for(j=0;j<=m-1&&k+j<=sum;j++) { f[(i-1)&1][0][k+j]=qadd(f[(i-1)&1][0][k+j],f[i&1][0][k],p); } } } cout<<f[1&1][0][sum]<<endl; fclose(stdin); fclose(stdout); return 0; }
-
-
正解
- 观察递推的写法，猜测可能与组合计数有关。
- 考虑枚举填入的数补足 \(l\) 位（空位补 \(0\) ）后和 \(l\) 的极长公共前缀的长度 \(len\) ，设其 \(S\) 值等于 \(s\) ，等价于求 \(\begin{cases} \forall i \in [1,len],x_{i}=n_{i} \\ x_{len+1} \in [0,n_{len+1}) \\ \forall i \in [len+2,l],x_{i} \in [0,m) \end{cases},\sum\limits_{i=1}^{l}x_{i}=S(n)\) 即 \(\begin{cases} x_{len+1} \in [0,n_{len+1}) \\ \forall i \in [len+2,l],x_{i} \in [0,m) \end{cases},\sum\limits_{i=len+1}^{l}x_{i}=S(n)-\sum\limits_{i=1}^{len}n_{i}\) 的整数解的方案数。
- 不妨设 \(s=S(n)-\sum\limits_{i=1}^{len}n_{i},a=l-len-1\) ，等价于求 \(\begin{cases} x_{0} \in [0,n_{len+1}) \\ \forall i \in [1,a],x_{i} \in [0,m) \end{cases}x_{0}+\sum\limits_{i=1}^{a}x_{i}=s\) 的整数解的方案数 \(\sum\limits_{x_{0}=0}^{n_{len+1}-1}\sum\limits_{i=0}^{a}(-1)^{i}\dbinom{a}{i}\dbinom{s-x_{0}-im+a-1}{a-1}\) 。
- 推导过程详见 冲刺CSP联训模拟2 T2 P295. 工地难题 。
- 尝试化简这个式子，有 \(\begin{aligned} & \sum\limits_{x_{0}=0}^{n_{len+1}-1}\sum\limits_{i=0}^{a}(-1)^{i}\dbinom{a}{i}\dbinom{s-x_{0}-im+a-1}{a-1} \\ &=\sum\limits_{i=0}^{a}(-1)^{i}\dbinom{a}{i}\sum\limits_{x_{0}=0}^{n_{len+1}-1}\dbinom{s-x_{0}-im+a-1}{a-1} \\ &=\sum\limits_{i=0}^{a}(-1)^{i}\dbinom{a}{i}(\dbinom{s-im+a}{a}-\dbinom{s-im+a-n_{len+1}}{a}) \end{aligned}\) 。
- 从第二步到第三步利用了一个结论 \(\sum\limits_{i=0}^{k-1}\dbinom{n-i}{m}=\dbinom{n+1}{m+1}-\dbinom{n-k+1}{m+1}\) 。
- 证明
- 考虑从杨辉三角上 \(\dbinom{n+1}{m+1}\) 的来源入手，有 \(\begin{aligned} &\sum\limits_{i=0}^{k-1}\dbinom{n-i}{m} \\ &=\sum\limits_{n-k+1}^{n}\dbinom{n}{m} \\ &=\sum\limits_{n-k+1}^{n}\dbinom{n+1}{m+1}-\dbinom{n}{m+1} \\ &=\dbinom{n+1}{m+1}-\dbinom{n-k+1}{m+1} \end{aligned}\) 。
点击查看代码
const ll p=1000000007; ll inv[4002010],jc[4002010],jc_inv[4002010],n[2010]; 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 ask(ll s,ll a,ll up,ll m) { ll ans=0; for(ll i=0;i<=a;i++) { if(i%2==0) { ans=(ans+C(a,i,p)*((C(s-i*m+a,a,p)-C(s-i*m+a-up,a,p)+p)%p)%p)%p; } else { ans=(ans-C(a,i,p)*((C(s-i*m+a,a,p)-C(s-i*m+a-up,a,p)+p)%p)%p+p)%p; } } return ans; } int main() { freopen("dba.in","r",stdin); freopen("dba.out","w",stdout); ll m,l,ans=0,sum=0,i; cin>>m>>l; for(i=1;i<=l;i++) { cin>>n[i]; sum+=n[i]; } inv[1]=1; jc[0]=jc_inv[0]=jc[1]=jc_inv[1]=1; for(i=2;i<=l*m+l+10;i++) { inv[i]=(p-p/i)*inv[p%i]%p; jc[i]=jc[i-1]*i%p; jc_inv[i]=jc_inv[i-1]*inv[i]%p; } for(i=0;i<=l-1;i++) { sum-=n[i]; ans=(ans+ask(sum,l-i-1,n[i+1],m))%p; } cout<<ans<<endl; fclose(stdin); fclose(stdout); return 0; }
\(T4\) D. 银行的源起（banking） \(3pst/0pts\)
-
部分分
-
\(10pts\) ：枚举两个银行，时间复杂度为 \(O(n^{3})\) 。
点击查看代码
ll a[100010],dfn[100010],dis[100010],tot=0; vector<pair<ll,ll> >e[100010]; void add(ll u,ll v,ll w) { e[u].push_back(make_pair(v,w)); } ll sx_min(ll x,ll y) { return dfn[x]<dfn[y]?x:y; } struct ST { ll fminn[100010][25]; void init(ll n) { for(ll j=1;j<=__lg(n);j++) { for(ll i=1;i+(1<<j)-1<=n;i++) { fminn[i][j]=sx_min(fminn[i][j-1],fminn[i+(1<<(j-1))][j-1]); } } } ll query(ll l,ll r) { ll t=__lg(r-l+1); return sx_min(fminn[l][t],fminn[r-(1<<t)+1][t]); } }T; void dfs(ll x,ll fa,ll w) { tot++; dfn[x]=tot; dis[x]=dis[fa]+w; T.fminn[tot][0]=fa; for(ll i=0;i<e[x].size();i++) { if(e[x][i].first!=fa) { dfs(e[x][i].first,x,e[x][i].second); } } } ll lca(ll u,ll v) { if(dfn[u]>dfn[v]) { swap(u,v); } return (dfn[u]==dfn[v])?u:T.query(dfn[u]+1,dfn[v]); } ll get_dis(ll u,ll v) { return dis[u]+dis[v]-2*dis[lca(u,v)]; } int main() { freopen("banking.in","r",stdin); freopen("banking.out","w",stdout); ll t,n,sum,ans,u,v,w,i,j,k,h; scanf("%lld",&t); for(h=1;h<=t;h++) { tot=0; ans=0x7f7f7f7f7f7f7f7f; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); e[i].clear(); } for(i=1;i<=n-1;i++) { scanf("%lld%lld%lld",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(1,0,0); T.init(n); for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { sum=0; for(k=1;k<=n;k++) { sum+=min(get_dis(i,k),get_dis(j,k))*a[k]; } ans=min(ans,sum); } } printf("%lld\n",ans); } fclose(stdin); fclose(stdout); return 0; } -
\(34pts\) ：观察到两个银行的覆盖实际上是将整个图分成了两个连通块，枚举断的那条边后跑换根 \(DP\) 即可，做法同 luogu P2986 [USACO10MAR] Great Cow Gathering G | CF1092F Tree with Maximum Cost ，时间复杂度为 \(O(n^{2})\) 。
点击查看代码
ll a[100010],siz[100010],f[100010],g[100010],u[100010],v[100010],w[100010]; vector<pair<ll,ll> >e[100010]; void add(ll u,ll v,ll w) { e[u].push_back(make_pair(v,w)); } void dfs(ll x,ll fa) { f[x]=0; siz[x]=a[x]; for(ll i=0;i<e[x].size();i++) { if(e[x][i].first!=fa) { dfs(e[x][i].first,x); f[x]+=f[e[x][i].first]+siz[e[x][i].first]*e[x][i].second; siz[x]+=siz[e[x][i].first]; } } } ll reroot(ll x,ll fa,ll rt,ll n,ll w) { ll minn=g[x]=((x!=rt)?g[fa]+(n-siz[x])*w-siz[x]*w:f[x]); for(ll i=0;i<e[x].size();i++) { if(e[x][i].first!=fa) { minn=min(minn,reroot(e[x][i].first,x,rt,n,e[x][i].second)); } } return minn; } int main() { freopen("banking.in","r",stdin); freopen("banking.out","w",stdout); ll t,n,w,ans,i,j; scanf("%lld",&t); for(j=1;j<=t;j++) { ans=0x7f7f7f7f7f7f7f7f; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); e[i].clear(); } for(i=1;i<=n-1;i++) { scanf("%lld%lld%lld",&u[i],&v[i],&w); add(u[i],v[i],w); add(v[i],u[i],w); } for(i=1;i<=n-1;i++) { dfs(u[i],v[i]); dfs(v[i],u[i]); ans=min(ans,reroot(u[i],v[i],u[i],siz[u[i]],0)+reroot(v[i],u[i],v[i],siz[v[i]],0)); } printf("%lld\n",ans); } fclose(stdin); fclose(stdout); return 0; }
-
-
正解
总结
- \(T2\) 觉得写迭代加深或者普通搜索有点麻烦遂最后再开始写。
- \(T3\) 理解错输入了，以为给出的是 \(n=(n_{l}n_{l-1} \dots n_{1})_{10}\) （实际上是 \(n=(n_{l}n_{l-1} \dots n_{1})_{m}\) ），遂先将 \(n\) 转化成了 \(m\) 进制再进行数位 \(DP\) ，并为此写了高精模低精，高精除低精，高精减高精（因为不会写高精减低精）。同时因为知道自己大样例肯定跑不过去遂没看大样例，并错过了知道自己读假题的机会。挂了 \(57pts/10pts\) 。
- \(T4\) 最后半个小时想出换根 \(DP\) 后换根时连通块点数传成了总点数，挂了 \(31pts/30pts\) 。
后记
-
学校 \(OJ\) 上 \(T2\) 赛时才加的文件读写，但没通知我们更改了。
-
赛后下发的 \(T2\) 的
Special Judge貌似直接写的是 \(O(mn \log n)\) 的暴力代码，都不屑于写珂朵莉树加线段树分裂的 \(O(m \log n)\) 是吧。点击查看代码
#include "testlib.h" #include<bits/stdc++.h> #define MAXN 200005 using namespace std; int n; int a[MAXN], b[MAXN]; bool chk_ok(){ for(int i=1;i<=n;i++){ if(a[i]!=b[i]) return 0; } return 1; } int main(int argc, char* argv[]){ registerTestlibCmd(argc, argv); int T = inf.readInt(); while(T--){ n = inf.readInt(); for(int i=1;i<=n;i++){ a[i] = inf.readInt(); } for(int i=1;i<=n;i++){ b[i] = inf.readInt(); } int ans1 = ouf.readInt(); int ans0 = ans.readInt(); if(ans0 != ans1){ //cerr<<ans0<<" "<<ans1<<endl; quitf(_wa, "ans is wrong! %d %d", ans0, ans1); } if(ans1 == -1) continue; int m = ouf.readInt(); if(m > n*n){ quitf(_wa, "m is larger than n^2!"); } int l,r; for(int t=1;t<=m;t++){ l = ouf.readInt(1,n); r = ouf.readInt(1,n); if(l > r) quitf(_wa, "l > r!"); sort(a+l, a+r+1); } if(chk_ok()==0){ quitf(_wa, "a and b are different!"); } } quitf(_ok, "The answer is correct."); return 0; } // -
\(T3,T4\) 的捆绑测试在学校 \(OJ\) 上没有绑包，直接散着测试了。