暑假集训CSP提高模拟3
\(T1\) P117. abc猜想 \(100pts\)
-
由题，有 \(\dfrac{(a^{b}-a^{b} \bmod c) \bmod c^{2}}{c}\) 即为所求。
- 证明
- 设 \(\left\lfloor \dfrac{a^{b}}{c} \right\rfloor= \dfrac{a^{b}-a^{b} \bmod c}{c}=kc+r\) ，其中 \(r \in [0,c)\) 。
- 移项有 \(a^{b}-a^{b} \bmod c=kc^{2}+rc\) ，且 \(rc \in [0,c^{2})\) 。
- 将 \(rc\) 试作 \(a^{b}-a^{b} \bmod c\) 除以 \(kc^{2}\) 的余数，即 \(rc=(a^{b}-a^{b} \bmod c) \bmod c^{2}\) 。
- 将系数 \(c\) 移项，有 \(r=\dfrac{(a^{b}-a^{b} \bmod c) \bmod c^{2}}{c}\) 。
点击查看代码
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; } int main() { ll a,b,c,ans,r; scanf("%lld%lld%lld",&a,&b,&c); r=qpow(a,b,c); ans=(qpow(a,b,c*c)-r+c*c)%(c*c)/c; printf("%lld\n",ans); return 0; } - 证明
\(T2\) T118. 简单的排列最优化题 \(0pts\)
-
等价于求 \(\min\limits_{k=0}^{n-1}\{ \sum\limits_{i=1}^{n-k}|a_{i}-(i+k)|+ \sum\limits_{i=n-k+1}^{n}|a_{i}-(i-(n-k))| \}\) 。
-
部分分
- \(45pts\) ：暴力 \(O(n^{2})\) 枚举所有的 \(k,i\) 并进行判断，及时进行剪枝来减小常数。
-
正解
- 由 [ABC351F] Double Sum 的套路，尝试展开绝对值及 \(\min,\max\) 。
- 将式子拆开有 \(\begin{aligned} & \min\limits_{k=0}^{n-1}\{ \sum\limits_{i=1}^{n-k}|a_{i}-(i+k)|+ \sum\limits_{i=n-k+1}^{n}|a_{i}-(i-(n-k))| \} \\ &=\min\limits_{k=0}^{n-1}\{ \sum\limits_{i=1}^{n-k}( \max(a_{i},i+k)- \min(a_{i},i+k))+ \sum\limits_{i=n-k+1}^{n}( \max(a_{i},i+k-n)- \min(a_{i},i+k-n)) \} \\ &=\min\limits_{k=0}^{n-1}\{ \sum\limits_{i=1}^{n-k}(a_{i}+i+k-2 \min(a_{i},i+k))+ \sum\limits_{i=n-k+1}^{n}(a_{i}+i+k-n-2 \min(a_{i},i+k-n)) \} \\ &=\sum\limits_{i=1}^{n}(a_{i}+i)+\min\limits_{k=0}^{n-1}\{- \sum\limits_{i=1}^{n-k}2 \min(a_{i},i+k)- \sum\limits_{i=n-k+1}^{n}2 \min(a_{i},i+k-n) \} \\ &=\sum\limits_{i=1}^{n}(a_{i}+i)-2 \max\limits_{k=0}^{n-1}\{\sum\limits_{i=1}^{n-k} \min(a_{i},i+k)+\sum\limits_{i=n-k+1}^{n} \min(a_{i},i+k-n) \} \end{aligned}\) 。
- 好像式子推多了，懒得改了，只是常数大点。
- 现在问题来到了怎么求 \(\max\limits_{k=0}^{n-1}\{\sum\limits_{i=1}^{n-k} \min(a_{i},i+k)+\sum\limits_{i=n-k+1}^{n} \min(a_{i},i+k-n) \}\) 。
- 令 \(\begin{cases} x_{i}=a_{i}-i \\ y_{i}=a_{i}+n-i \end{cases}\) ，由于是排列所以 \(\{ x \},\{ y \}\) 均满足内部两两不同，则转化为求 \(\max\limits_{k=0}^{n-1}\{\sum\limits_{i=1}^{n-k}([k \ge x_{i}] \times a_{i}+[k<x_{i}] \times (i+k))+\sum\limits_{i=n-k+1}^{n}([k \ge y_{i}] \times a_{i}+ [k<y_{i}] \times (i+k-n)) \}\) ，前半部分将其拆成 \(\begin{cases} [k \ge x_{i}] \times a_{i} \\ [k<x_{i}] \times i \\ [k<x_{i}] \times k \end{cases}\) 三部分，后半部分同理。
- 将 \(\{ x \},\{ y \}\) 分别插入到权值树状数组里，分别维护 \(\begin{cases} [k \ge x_{i}] \times a_{i}/[k \ge y_{i}] \times a_{i} \\ [k<x_{i}] \times i/[k<y_{i}] \times (i-n) \\ [k<x_{i}]/[k<y_{i}] \end{cases}\) 即可，注意及时消除影响。
- 对于负数整体向右移来处理。
点击查看代码
ll a[3000010],x[3000010],y[3000010],c[6][3000010]; ll lowbit(ll x) { return (x&(-x)); } void add(ll n,ll x,ll val,ll c[]) { x+=1000001; n+=1000001; for(ll i=x;i<=n;i+=lowbit(i)) { c[i]+=val; } } ll ask(ll x,ll c[]) { ll ans=0; x+=1000001; for(ll i=x;i>=1;i-=lowbit(i)) { ans+=c[i]; } return ans; } int main() { ll n,ans=0,pos=0,sum=0,i,k; scanf("%lld",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); x[i]=a[i]-i; y[i]=a[i]+n-i; add(2*n,x[i],a[i],c[0]); add(2*n,x[i],i,c[2]); add(2*n,x[i],1,c[4]); } for(k=0;k<=n-1;k++) { sum=0; sum+=ask(k,c[0]); sum+=ask(2*n,c[2])-ask(k,c[2]); sum+=(ask(2*n,c[4])-ask(k,c[4]))*k; sum+=ask(k,c[1]); sum+=ask(2*n,c[3])-ask(k,c[3]); sum+=(ask(2*n,c[5])-ask(k,c[5]))*k; if(sum>ans) { ans=sum; pos=k; } add(2*n,x[n-k],-a[n-k],c[0]); add(2*n,x[n-k],-(n-k),c[2]); add(2*n,x[n-k],-1,c[4]); add(2*n,y[n-k],a[n-k],c[1]); add(2*n,y[n-k],n-k-n,c[3]); add(2*n,y[n-k],1,c[5]); } ans*=-2; for(i=1;i<=n;i++) { ans+=a[i]+i; } printf("%lld %lld\n",pos,ans); return 0; }
\(T3\) P119. 简单的线性做法题 \(5pts\)
-
部分分
- \(1\) ：输出样例 \(1\)
- \(2 \sim 4\) ：分块/莫队/主席树处理出所有区间的众数出现次数，依次判断。
-
正解
点击查看代码
\(T4\) P120. 简单的线段树题 \(100pts\)
-
原题： luogu P4145 上帝造题的七分钟 2 / 花神游历各国 | GSS4 - Can you answer these queries IV | LibreOJ 6281. 数列分块入门 5
-
懒得再复制一遍了，直接贴当时写的 题解 了。
-
一个数最多被开方加向下取整 \(6\) 遍就会变成 \(1\) ，并查集维护下有没有变成 \(1\) ，然后对于区间进行暴力单点修改，随便一个单点修改、区间查询的数据结构维护就行了。
点击查看代码
总结
- \(T2\)
- 处理 \(k\) 与 \(\{ x \},\{ y \}\) 时将两者搞反了，说明对权值树状数组的认识仍不够。
- 赛时式子推多了。
- 空间开大加上不会算空间，挂了 \(100pts\) 。
后记
- \(T2\) 下发文件里的大样例造假了，中途才换，导致写的暴力对着假数据拍了半天没拍出来。
- \(T3\) 下发文件里的大样例造假了，中途才换，还换了两次。最后发现贺的 \(std\) 造的数据假了（换大样例时顺带换了数据），结果发现第一组数据是真的。