2025多校冲刺省选模拟赛7
\(T1\) A. 三色卡(card) \(0pts\)
-
如果存在一个小矩形和大矩形的大小相同，此时另外两个矩形可以任意放，贡献是容易计算的。
-
否则至少需要一个小矩形覆盖大矩形的两个角，通过交换长、宽钦定完全覆盖行的矩形比完全覆盖列的矩形的数量多。
-
完全覆盖行的矩形数量为 \(1,2\) 时判掉无解后是容易统计贡献的。
-
完全覆盖行的矩形数量为 \(3\) 时，直接在两边固定矩形后算另一个矩形可放置的极长区间会算重，不妨直接钦定不能顶到两边的边界，而顶到两边的边界单独提出来计算即可。
点击查看代码
const ll p=1000000007; ll h[5],w[5],a[5]; ll solve(ll a,ll b,ll c,ll m) { ll flag=(max(w[a],w[b])+w[c]>=m);//顶到两边的边界 if(w[a]+w[b]>=m) return flag+m-w[c]-1; return flag+min(m-w[c],w[a]+1)-max(2ll,m-w[b]-w[c]+1)+1; } int main() { #define Isaac #ifdef Isaac freopen("card.in","r",stdin); freopen("card.out","w",stdout); #endif ll t,n,m,cnt,s1,s2,sum,minn,ans,i,j; cin>>t; for(j=1;j<=t;j++) { cin>>n>>m; cnt=s1=s2=sum=ans=0; minn=0x7f7f7f7f; for(i=1;i<=3;i++) { cin>>h[i]>>w[i]; a[i]=i; cnt+=(h[i]==n&&w[i]==m); s1+=(h[i]==n); s2+=(w[i]==m); } if(s2>s1) { swap(s1,s2); swap(n,m); for(i=1;i<=3;i++) swap(h[i],w[i]); } if(cnt==0) { if(s1==1) { for(i=1;i<=3;i++) { if(h[i]==n) s2=w[i]; else { sum+=h[i]; minn=min(minn,w[i]); } } ans=(minn+s2>=m&&sum>=n)*4; } if(s1==2) { ans=1; for(i=1;i<=3;i++) { if(h[i]==n) sum+=w[i]; else ans=ans*(n-h[i]+1)%p*(m-w[i]+1)%p; } ans=(sum>=m)?2*ans:0; } if(s1==3) { for(i=1;i<=3;i++) sum+=w[i]; if(sum>=m) { do { ans=(ans+solve(a[1],a[2],a[3],m))%p; }while(next_permutation(a+1,a+1+3)); } } } else { ans=1; for(i=1;i<=3;i++) ans=ans*(n-h[i]+1)%p*(m-w[i]+1)%p; } cout<<ans<<endl; } return 0; }
\(T2\) B. 三项式(sequence) \(20pts\)
-
部分分
-
\(20pts\) ：爆搜。
点击查看代码
const ll p=1000000007; int ans=0; bool check(ll sum,int m) { int s1=0,s2=0; while(sum) { s1=(s1+sum%10)%m; s2=(s2+(sum%10)*(sum%10))%m; sum/=10; } return (s1==s2); } void dfs(int pos,int n,int m,ll sum,int l,int r) { if(pos==n+1) { if(check(sum,m)==true) ans=(ans+1)%p; return; } for(int i=l;i<=r;i++) dfs(pos+1,n,m,sum+i,l,r); } int main() { #define Isaac #ifdef Isaac freopen("sequencel.in","r",stdin); freopen("sequencel.out","w",stdout); #endif int n,m,l,r,lens,lene,i; cin>>n>>m>>l>>r; dfs(1,n,m,0,l,r); cout<<ans<<endl; return 0; }
-
-
正解
\(T3\) C. 三分图(graph) \(0pts\)
-
单看限制条件 \(3\) 太误导人了，等价于在限制 \(1\) 成立的条件下不存在两端属于同个部分的边。
-
考虑扔到 \(DFS\) 树上考虑，从而天然满足第二条限制。
-
将所有点按照深度的奇偶性划分成两个部分 \(V_{1},V_{2}\) ，然后进行分讨。
- 若各部分点数均 \(\le 2n\) ，选择符合第一条限制。由树上完美匹配经典结论贪心选择即可。
- 否则，选择符合第三条限制。具体地，观察到叶子节点构成了独立集且足够多（根据 \( ||V_{1}|-|V_{2}|| \ge n\) 可知），将所有叶子节点扔到 \(V_{3}\) 里即可。
点击查看代码
struct node { int nxt,to; }e[1000010]; int head[1000010],dep[1000010],vis[1000010],son[1000010],ins[1000010],ans[1000010],num[2],cnt=0,n; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs1(int x,int fa) { vis[x]=1; dep[x]=dep[fa]+1; num[dep[x]%2]++; ans[x]=dep[x]%2+1; for(int i=head[x];i!=0;i=e[i].nxt) { if(vis[e[i].to]==0) { son[x]++; dfs1(e[i].to,x); } } } void dfs2(int x) { int flag=0; vis[x]=1; for(int i=head[x];i!=0;i=e[i].nxt) { if(vis[e[i].to]==0) { dfs2(e[i].to); flag|=ins[e[i].to]; } } if(flag==0&&num[dep[x]%2]-1>=n) { num[dep[x]%2]--; ans[x]=3; ins[x]=1; } } int main() { #define Isaac #ifdef Isaac freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); #endif int t,m,u,v,i,j; scanf("%d",&t); for(j=1;j<=t;j++) { scanf("%d%d",&n,&m); fill(e+1,e+1+cnt,(node){0,0}); fill(head+1,head+1+3*n,0); fill(vis+1,vis+1+3*n,0); fill(son+1,son+1+3*n,0); fill(ins+1,ins+1+3*n,0); cnt=num[0]=num[1]=0; for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs1(1,0); if(max(num[0],num[1])<=2*n) { fill(vis+1,vis+1+3*n,0); dfs2(1); } else { for(i=1;i<=3*n;i++) ans[i]=((son[i]==0)?3:ans[i]); } printf("YES\n"); for(i=1;i<=3*n;i++) printf("%d ",ans[i]); printf("\n"); } return 0; }
总结
- \(T1\) 分讨完后觉得太难写就直接摆烂去写左偏树了。而且当时对于三个同时覆盖行的情况算重了贡献，如果在场上估计也想不到解决方案。
- \(T2\) 一开始读假题了，口胡了个 \(O(\dbinom{n+m-1}{m-1})\) 的做法。
后记
- \(T2\) accoders NOI 和学校 \(OJ\) 的文件 IO 不一样。
- \(T3\) 原
checker.cpp的并查集没有初始化导致循环输出 \(1,2,3\) 即可通过本题。