多校A层冲刺NOIP2024模拟赛12
多校A层冲刺NOIP2024模拟赛12
\(T1\) A. Alice 和璀璨花 \(65pts/65pts/65pts\)
-
部分分
- 测试点 \(1 \sim 10\) ：设 \(f_{i,j}\) 表示前 \(i\) 位中生长趋势子序列长度为 \(j\) 时的末尾最小元素，然后进行暴力转移。
- 测试点 \(11 \sim 13\) ：观察到至多选择 \(\left\lceil \log_{2}10^{18} \right\rceil=40\) 个数。
- 测试点 \(14 \sim 16\) ：做法同最长上升子序列。
点击查看代码
ll a[1000010],b[1000010],d[1000010],f[1000010],g[1000010]; struct BIT { ll c[1000010]; ll lowbit(ll x) { return (x&(-x)); } void update(ll n,ll x,ll val) { for(ll i=x;i<=n;i+=lowbit(i)) { c[i]=max(c[i],val); } } ll getsum(ll x) { ll ans=0; for(ll i=x;i>=1;i-=lowbit(i)) { ans=max(ans,c[i]); } return ans; } }T; int main() { freopen("alice.in","r",stdin); freopen("alice.out","w",stdout); ll n,ans=0,flag=1,i,j; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); d[i]=a[i]; } for(i=1;i<=n;i++) { scanf("%lld",&b[i]); flag&=(b[i]==1); } if(flag==1) { sort(d+1,d+1+n); d[0]=unique(d+1,d+1+n)-(d+1); for(i=1;i<=n;i++) { a[i]=lower_bound(d+1,d+1+d[0],a[i])-d; g[i]=T.getsum(a[i]-1)+1; T.update(d[0],a[i],g[i]); ans=max(ans,g[i]); } } else { flag=1; for(i=1;i<=n;i++) { flag&=(b[i]>1); } memset(f,0x3f,sizeof(f)); f[0]=0; if(flag==1) { for(i=1;i<=n;i++) { for(j=min(i,40ll);j>=1;j--) { if(f[j-1]!=0x3f3f3f3f3f3f3f3f&&f[j-1]*b[j-1]<a[i]) { f[j]=min(f[j],a[i]); } } } for(i=min(n,40ll);i>=1;i--) { if(f[i]!=0x3f3f3f3f3f3f3f3f) { ans=i; break; } } } else { for(i=1;i<=n;i++) { for(j=i;j>=1;j--) { if(f[j-1]!=0x3f3f3f3f3f3f3f3f&&f[j-1]*b[j-1]<a[i]) { f[j]=min(f[j],a[i]); } } } for(i=n;i>=1;i--) { if(f[i]!=0x3f3f3f3f3f3f3f3f) { ans=i; break; } } } } printf("%lld\n",ans); fclose(stdin); fclose(stdout); return 0; } -
正解
- 在 \(i\) 一定时，有 \(f_{i,j}\) 随 \(j\) 单调递增。
- 不妨把 \(f_{i-1}\) 分为两部分使得前半部分的数 \(<a_{i}\) ，后半部分的数 \(\ge a_{i}\) ，并设前半部分在 \(k\) 处结尾。
- 当 \(j \in [1,k] \bigcup [k+2,n]\) 时，转移是没有意义的；当 \(j=k+1\) 时才可能进行转移。
- \(\forall j \in [1,k]\) 是比较显然的。
- \(\forall j \in [k+2,n]\) ，由 \(k\) 的分割性有 \(a_{i} \le f_{i-1,k+1} \le f_{i-1,j-1}\) ，自然不会再进行转移。
点击查看代码
ll a[1000010],b[1000010],f[1000010]; int main() { freopen("alice.in","r",stdin); freopen("alice.out","w",stdout); ll n,ans=0,i,j; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(i=1;i<=n;i++) { scanf("%lld",&b[i]); } memset(f,0x3f,sizeof(f)); f[0]=0; for(i=1;i<=n;i++) { j=lower_bound(f+1,f+1+n,a[i])-f; if(f[j-1]*b[j-1]<a[i]) { f[j]=min(f[j],a[i]); } } for(i=n;i>=1;i--) { if(f[i]!=0x3f3f3f3f3f3f3f3f) { ans=i; break; } } printf("%lld\n",ans); fclose(stdin); fclose(stdout); return 0; }
\(T2\) B. Bob 与幸运日 \(30pts/30pts/30pts\)
-
部分分
- 测试点 \(1 \sim 3\)
- 等价于求 \(\begin{cases} (x-1)d+y \equiv a \pmod{w} \\ (y-1)d+x \equiv b \pmod{w} \\ 1 \le x,y \le \min(m,d) \end{cases}\) 的数量.
- 同余两边同时加 \(d\) ，得到 \(\begin{cases} xd+y \equiv a+d \pmod{w} \\ yd+x \equiv b+d \pmod{w} \end{cases}\) 。
- 设 \(xd+y=k_{1}w+a+d\) ，有 \(y=k_{1}w+a+d-xd \ge 1\) ，得到 \(\left\lceil \frac{xd+1-a-d}{w} \right\rceil \le k_{1} \le \left\lfloor \frac{\min(m,d)+xd-a-d}{w} \right\rfloor\) 。
- 将 \(y=k_{1}w+a+d-xd\) 代入第二个式子，并设 \((k_{1}w+a+d-xd)d+x=-k_{2}w+b+d\) ，移项得到 \(k_{1}wd+k_{2}w=b+d-ad-d^{2}+xd^{2}-x\) 。
- 为方便书写，用 \((a+d) \bmod w,(b+d) \bmod w\) 分别代替 \(a,b\) ，可以证明其并不会对答案产生影响。
- 此时有 \(k_{1}wd+k_{2}w=b-ad+xd^{2}-x\) ，而容易得到 \(k_{1}wd+k_{2}w=w\) 的一组特解 \(\begin{cases} k_{1}=0 \\ k_{2}=1 \end{cases}\) ，从而得到 \(k_{1}\)
- 由 \(k_{2} \in \mathbb{Z}\) 进一步化简可以得到 \(b-ad+xd^{2}-x=x(d^{2}-1)+b-ad \equiv 0 \pmod{w}\) ，即 \(x(d^{2}-1) \equiv ad-b \pmod{w}\) 。
- \(O(\min(m,d))\) 枚举合法的 \(x\) 即可。
- 测试点 \(4 \sim 6\)
- 考虑直接枚举 \(x \bmod w\) 的值，进一步求出 \(y \equiv a-xd \pmod{w}\) ，接着手动判断是否有 \(x+yd \equiv b \bmod{w}\) 。
- 而计算 \([1,\min(m,d)]\) 中模 \(w\) 等于一个特定值的数个数是平凡的。
- 时间复杂度为 \(O(w)\) 。
- 测试点 \(7 \sim 8\)
- 因为数据点随机，所以不会有 \(d^{2}-1 \equiv 0 \pmod{w}\) 的数据。
- 直接移项得到 \(x \equiv \frac{ad-b}{d^{2}-1} \pmod{w}\) ，进一步求出 \(y \equiv a-xd =a-\frac{ad^{2}-bd}{d^{2}-1}\pmod{w}\) 。
- 时间复杂度为 \(O(\log w)\) 。
点击查看代码
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 work(ll m,ll d,ll x,ll w) { return (min(m,d)-x)/w+(1<=x&&x<=min(m,d)); } int main() { freopen("bob.in","r",stdin); freopen("bob.out","w",stdout); ll t,m,d,w,a,b,c,e,ans,x,y,i,l,r; scanf("%lld",&t); for(i=1;i<=t;i++) { scanf("%lld%lld%lld%lld%lld",&m,&d,&w,&a,&b); ans=0; a=(a+d)%w; b=(b+d)%w; c=(b-a*d%w+w)%w; e=(d*d-1)%w; if(e==0) { if(min(m,d)<=w) { for(x=1;x<=min(m,d);x++) { if((c+e*x%w)%w==0) { l=ceil(1.0*(x*d+1-a)/w); r=(min(m,d)+x*d-a)/w; ans+=(l<=r)*(r-l+1); } } } else { for(x=0;x<=w-1;x++) { y=(a-x*d%w+w)%w; ans+=((y*d+x)%w==b)*work(m,d,x,w)*work(m,d,y,w); } } } else { x=(w-c)%w*qpow(e,w-2,w)%w; y=(a-x*d%w+w)%w; ans=work(m,d,x,w)*work(m,d,y,w); } printf("%lld\n",ans); } fclose(stdin); fclose(stdout); return 0; } - 测试点 \(1 \sim 3\)
-
正解
- 考虑 \((d^{2}-1)=(d-1)(d+1) \equiv 0 \pmod{w}\) 时怎么处理。
- 当 \(d \equiv 1 \pmod{w}\) 时
- 展开得到 \(x+y \equiv a \equiv b \pmod{w}\) ，并令 \(a \equiv b \pmod{w}\) 。
- 枚举 \(x\) 的时间复杂度是 \(O(w)\) ，但枚举 \(x+y\) 的时间复杂度是 \(O(\frac{\min(m,d)}{w})\) ，直接根号分治即可。
- 当 \(d \equiv -1 \pmod{w}\) 时
- 展开得到 \(y-x \equiv a \equiv -b \pmod{w}\) ，并令 \(a \equiv -b \pmod{w}\) 。
- 类似地根号分治即可。
点击查看代码
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 work(ll m,ll d,ll x,ll w) { return (min(m,d)-x)/w+(1<=x&&x<=min(m,d)); } int main() { freopen("bob.in","r",stdin); freopen("bob.out","w",stdout); ll t,m,d,w,a,b,c,e,ans,x,y,s,i,j; scanf("%lld",&t); for(i=1;i<=t;i++) { scanf("%lld%lld%lld%lld%lld",&m,&d,&w,&a,&b); ans=0; a=(a+d)%w; b=(b+d)%w; c=(b-a*d%w+w)%w; e=(d*d-1)%w; if(e==0) { s=sqrt(min(m,d))+1; if(d%w==1) { if(a==b) { if(w<=s) { for(x=0;x<=w-1;x++) { y=(a-x+w)%w; ans+=work(m,d,x,w)*work(m,d,y,w); } } else { for(j=a;j<=2*min(m,d);j+=w) { ans+=(j<=min(m,d))?j-1:2*min(m,d)-j+1; } } } } else { if(a==w-b) { if(w<=s) { for(x=0;x<=w-1;x++) { y=(a+x)%w; ans+=work(m,d,x,w)*work(m,d,y,w); } } else { for(j=a;j<=min(m,d)-1;j+=w) { ans+=min(m,d)-j; } for(j=b;j<=min(m,d)-1;j+=w) { ans+=min(m,d)-j; } } } } } else { x=(w-c)%w*qpow(e,w-2,w)%w; y=(a-x*d%w+w)%w; ans=work(m,d,x,w)*work(m,d,y,w); } printf("%lld\n",ans); } fclose(stdin); fclose(stdout); return 0; }- 挂一下官方题解的
set维护做法。-
用 \(a-1,b-1\) 分别代替 \(a,b\) ；且 \(x,y \in [0,\min(m,d)-1]\) 。
-
\(T3\) C. Charlie 的运输网 \(5pts/5pts/5pts\)
-
没看出来是二分图。
\(T4\) D. David 与和谐号 \(0pts/0pts/0pts\)
-
容易想到的一种翻转方案是，从大到小枚举 \(i\) ，每次将 \(i\) 翻转到 \(a_{1}\) 再翻转到 \(a_{i}\) ，故答案上界为 \(2n-2\) 。
-
观察到 \(n \le 25\) ，故步数不多，考虑迭代加深。
-
每次翻转只会改变一对相邻数对之间的差，故最终答案一定会大于相邻数对之间差 \(>1\) 的数量。
-
需要适当剪枝，时间复杂度为 \(O(能过)\) 。
点击查看代码
int a[30],flag; bool check(int n) { for(int i=1;i<=n;i++) { if(a[i]!=i) { return false; } } return true; } void dfs(int sum,int cnt,int last,int ans,int n) { if(sum+cnt>ans)//最优性剪枝 { return; } if(check(n)==true) { flag=1; return; } for(int i=n;i>=2;i--) { if(i!=last)//转回来一定不优 { int tmp=cnt-(i!=n&&abs(a[i]-a[i+1])>1)+(i!=n&&abs(a[1]-a[i+1])>1); reverse(a+1,a+1+i); dfs(sum+1,tmp,i,ans,n); reverse(a+1,a+1+i); if(flag==1) { return; } } } } int main() { freopen("david.in","r",stdin); freopen("david.out","w",stdout); int t,n,cnt,ans=0,i,j; cin>>t; for(j=1;j<=t;j++) { cin>>n; cnt=flag=0; for(i=1;i<=n;i++) { cin>>a[i]; } for(i=2;i<=n;i++) { cnt+=(abs(a[i]-a[i-1])>1); } for(ans=0;;ans++) { dfs(0,cnt,0,ans,n); if(flag==1) { cout<<ans<<endl; break; } } } fclose(stdin); fclose(stdout); return 0; }
总结
- \(T1\) 一开始以为做法和最长上升子序列差不多，遂写了权值树状数组、动态开点线段树优化转移，然后发现假了。在写完 \(50pts\) 的部分分后去上了趟厕所，回来的时候已经快 \(9:10\) 了，强逼着自己把测试点 \(14 \sim 16\) 部分分写完了就去推 \(T2\) 的式子了。
- 貌似最长上升子序列做法也是对的，详见 @ccxswl 的做法，但是需要平衡树维护，没理解为啥对。
- \(T2\) 推了半天式子才写了个 \(O(m)\) 的做法，结果发现和 \(O(m^{2})\) 一个分。
- \(T3,T4\) 仅留了半个小时看题，直接摆烂了。
版权声明：本作品采用 「署名-非商业性使用-相同方式共享 4.0 国际」许可协议（CC BY-NC-SA 4.0） 进行许可。