记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步目录10/12 2897. 对数组执行操作使平方和最大10/13 3727. 最大交替平方和10/14 3723. 数位平方和的最大值10/15 2913. 子数组不同元素数目的平方和 I10/16 2916. 子数组不同元素数目的平方和 II10/17 3551. 数位和排序需要的最小交换次数10/18 1569. 将子数组重新排序得到同一个二叉搜索树的方案数10/12 2897. 对数组执行操作使平方和最大AND/OR 操作不会增加或减少某一位上 1 的总数，只会把某个数的 1 挪到另一个数上。平方和要最大，应该把 1 尽量集中到少数几个大数上，因为把一位从小数挪到大数，平方和会变大。先统计每一位上有多少个 1，再贪心拼出 k 个数：每次把还没用完的位都放进当前这个数，让它尽量大，然后把平方加进答案。defmaxSum(nums,k):""" :type nums: List[int] :type k: int :rtype: int """mod=10**9+7cnt=[0]*31forxinnums:foriinrange(31):ifx>>i&1:cnt[i]+=1ans=0for_inrange(k):x=0foriinrange(31):ifcnt[i]:x|=1<<i cnt[i]-=1ans=(ans+x*x)%modreturnans10/13 3727. 最大交替平方和偶数位取正、奇数位取负，平方只和绝对值有关。将绝对值大的放到偶数位，绝对值小的放到奇数位。先取绝对值排序，较小的一半减去平方，较大的一半加上平方。defmaxAlternatingSum(nums):""" :type nums: List[int] :rtype: int """ans=0n=len(nums)l=[abs(x)forxinnums]l.sort()foriinrange(n):ifi<n//2:ans-=l[i]**2else:ans+=l[i]**2returnans10/14 3723. 数位平方和的最大值要凑恰好 num 位、数位和恰好是 sum 的数，让各位数字的平方和最大；平方和一样时取数值最大的那个。平方和固定时数字越集中越大，所以尽量多用 9，剩下不足 9 的部分单独放一位。同分时要数值最大，就把这些 9 放在最高位，余数紧跟其后，剩下的位补 0。如果 sum 比 9*num 还大，凑不出来，返回空串。defmaxSumOfSquares(num,sum):""" :type num: int :type sum: int :rtype: str """ifnum*9<sum:return""k,s=divmod(sum,9)ans="9"*kifs:ans+=str(s)returnans+"0"*(num-len(ans))10/15 2913. 子数组不同元素数目的平方和 I每个子数组都要算一次「里面有多少个不同的数」，再把这个数平方后全部加起来。数组很短，枚举左端点，再从左往右把右端点一格一格延长。用集合记下当前这段出现过的数，集合大小就是不同元素个数，平方后加进答案。defsumCounts(nums):""" :type nums: List[int] :rtype: int """n=len(nums)ans=0foriinrange(n):seen=set()forjinrange(i,n):seen.add(nums[j])ans+=len(seen)*len(seen)returnans10/16 2916. 子数组不同元素数目的平方和 II还是把每个子数组的不同元素个数平方后加起来，但数组很长，不能一段段枚举。固定右端点从左往右扫，记下每个左端点到当前右端点这段里有多少个不同的数。新来的数只对「上次出现位置之后」的那些左端点是新元素，这些段的不同个数都加 1。一段数每个都加 1 时，平方和增加 2×原来的和 + 这段长度。用线段树做区间加 1 并维护平方和，每扫完一个右端点就加进答案，最后对 10^9+7 取模。defsumCounts(nums):""" :type nums: List[int] :rtype: int """mod=10**9+7n=len(nums)sm=[0]*(4*n)sq=[0]*(4*n)lz=[0]*(4*n)defapply(p,l,r,v):length=r-l+1sq[p]=(sq[p]+2*v*sm[p]+v*v*length)%mod sm[p]=(sm[p]+v*length)%mod lz[p]+=vdefpush(p,l,r):iflz[p]andl<r:m=(l+r)//2apply(p*2,l,m,lz[p])apply(p*2+1,m+1,r,lz[p])lz[p]=0defupdate(p,l,r,ql,qr):ifql<=landr<=qr:apply(p,l,r,1)returnpush(p,l,r)m=(l+r)//2ifql<=m:update(p*2,l,m,ql,qr)ifqr>m:update(p*2+1,m+1,r,ql,qr)sm[p]=(sm[p*2]+sm[p*2+1])%mod sq[p]=(sq[p*2]+sq[p*2+1])%mod last={}ans=0forr,xinenumerate(nums):update(1,0,n-1,last.get(x,-1)+1,r)last[x]=r ans=(ans+sq[1])%modreturnans10/17 3551. 数位和排序需要的最小交换次数数位和更小的排前面，数位和相同则数字更小的排前面。先按这个规则排出目标顺序，再看每个数现在在哪、应该去哪。这些「当前位置指向目标位置」会连成若干个圈。一个圈里有 k 个数，最少交换 k-1 次就能各归其位，总次数就是 n 减去圈的个数。defminSwaps(nums):""" :type nums: List[int] :rtype: int """defdigit_sum(x):s=0whilex:s+=x%10x//=10returns n=len(nums)order=sorted((digit_sum(x),x)forxinnums)pos={x:ifori,(_,x)inenumerate(order)}vis=[False]*n ans=nforiinrange(n):ifvis[i]:continueans-=1j=iwhilenotvis[j]:vis[j]=Truej=pos[nums[j]]returnans10/18 1569. 将子数组重新排序得到同一个二叉搜索树的方案数按数组顺序依次插入空的二叉搜索树，第一个数一定是根，根一换树就变了，所以根不能动。比根小的都进左子树，比根大的都进右子树。左右两边各自的先后顺序决定子树长什么样，两边之间可以任意穿插。左边 m 个数、右边 n 个数，穿插方式是从 m+n 个位置里选 m 个给左边。左右再各自按同样规则计算，乘起来就是总方案。题目不要原数组本身，最后减 1，并对 10^9+7 取模。defnumOfWays(nums):""" :type nums: List[int] :rtype: int """importsys sys.setrecursionlimit(10000)mod=10**9+7n=len(nums)c=[[0]*nfor_inrange(n)]c[0][0]=1foriinrange(1,n):c[i][0]=1forjinrange(1,i+1):c[i][j]=(c[i-1][j]+c[i-1][j-1])%moddefdfs(a):iflen(a)<2:return1left=[xforxinaifx<a[0]]right=[xforxinaifx>a[0]]returnc[len(left)+len(right)][len(left)]*dfs(left)%mod*dfs(right)%modreturn(dfs(nums)-1)%mod
记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步目录10/12 2897. 对数组执行操作使平方和最大10/13 3727. 最大交替平方和10/14 3723. 数位平方和的最大值10/15 2913. 子数组不同元素数目的平方和 I10/16 2916. 子数组不同元素数目的平方和 II10/17 3551. 数位和排序需要的最小交换次数10/18 1569. 将子数组重新排序得到同一个二叉搜索树的方案数10/12 2897. 对数组执行操作使平方和最大AND/OR 操作不会增加或减少某一位上 1 的总数，只会把某个数的 1 挪到另一个数上。平方和要最大，应该把 1 尽量集中到少数几个大数上，因为把一位从小数挪到大数，平方和会变大。先统计每一位上有多少个 1，再贪心拼出 k 个数：每次把还没用完的位都放进当前这个数，让它尽量大，然后把平方加进答案。defmaxSum(nums,k):""" :type nums: List[int] :type k: int :rtype: int """mod=10**9+7cnt=[0]*31forxinnums:foriinrange(31):ifx>>i&1:cnt[i]+=1ans=0for_inrange(k):x=0foriinrange(31):ifcnt[i]:x|=1<<i cnt[i]-=1ans=(ans+x*x)%modreturnans10/13 3727. 最大交替平方和偶数位取正、奇数位取负，平方只和绝对值有关。将绝对值大的放到偶数位，绝对值小的放到奇数位。先取绝对值排序，较小的一半减去平方，较大的一半加上平方。defmaxAlternatingSum(nums):""" :type nums: List[int] :rtype: int """ans=0n=len(nums)l=[abs(x)forxinnums]l.sort()foriinrange(n):ifi<n//2:ans-=l[i]**2else:ans+=l[i]**2returnans10/14 3723. 数位平方和的最大值要凑恰好 num 位、数位和恰好是 sum 的数，让各位数字的平方和最大；平方和一样时取数值最大的那个。平方和固定时数字越集中越大，所以尽量多用 9，剩下不足 9 的部分单独放一位。同分时要数值最大，就把这些 9 放在最高位，余数紧跟其后，剩下的位补 0。如果 sum 比 9*num 还大，凑不出来，返回空串。defmaxSumOfSquares(num,sum):""" :type num: int :type sum: int :rtype: str """ifnum*9<sum:return""k,s=divmod(sum,9)ans="9"*kifs:ans+=str(s)returnans+"0"*(num-len(ans))10/15 2913. 子数组不同元素数目的平方和 I每个子数组都要算一次「里面有多少个不同的数」，再把这个数平方后全部加起来。数组很短，枚举左端点，再从左往右把右端点一格一格延长。用集合记下当前这段出现过的数，集合大小就是不同元素个数，平方后加进答案。defsumCounts(nums):""" :type nums: List[int] :rtype: int """n=len(nums)ans=0foriinrange(n):seen=set()forjinrange(i,n):seen.add(nums[j])ans+=len(seen)*len(seen)returnans10/16 2916. 子数组不同元素数目的平方和 II还是把每个子数组的不同元素个数平方后加起来，但数组很长，不能一段段枚举。固定右端点从左往右扫，记下每个左端点到当前右端点这段里有多少个不同的数。新来的数只对「上次出现位置之后」的那些左端点是新元素，这些段的不同个数都加 1。一段数每个都加 1 时，平方和增加 2×原来的和 + 这段长度。用线段树做区间加 1 并维护平方和，每扫完一个右端点就加进答案，最后对 10^9+7 取模。defsumCounts(nums):""" :type nums: List[int] :rtype: int """mod=10**9+7n=len(nums)sm=[0]*(4*n)sq=[0]*(4*n)lz=[0]*(4*n)defapply(p,l,r,v):length=r-l+1sq[p]=(sq[p]+2*v*sm[p]+v*v*length)%mod sm[p]=(sm[p]+v*length)%mod lz[p]+=vdefpush(p,l,r):iflz[p]andl<r:m=(l+r)//2apply(p*2,l,m,lz[p])apply(p*2+1,m+1,r,lz[p])lz[p]=0defupdate(p,l,r,ql,qr):ifql<=landr<=qr:apply(p,l,r,1)returnpush(p,l,r)m=(l+r)//2ifql<=m:update(p*2,l,m,ql,qr)ifqr>m:update(p*2+1,m+1,r,ql,qr)sm[p]=(sm[p*2]+sm[p*2+1])%mod sq[p]=(sq[p*2]+sq[p*2+1])%mod last={}ans=0forr,xinenumerate(nums):update(1,0,n-1,last.get(x,-1)+1,r)last[x]=r ans=(ans+sq[1])%modreturnans10/17 3551. 数位和排序需要的最小交换次数数位和更小的排前面，数位和相同则数字更小的排前面。先按这个规则排出目标顺序，再看每个数现在在哪、应该去哪。这些「当前位置指向目标位置」会连成若干个圈。一个圈里有 k 个数，最少交换 k-1 次就能各归其位，总次数就是 n 减去圈的个数。defminSwaps(nums):""" :type nums: List[int] :rtype: int """defdigit_sum(x):s=0whilex:s+=x%10x//=10returns n=len(nums)order=sorted((digit_sum(x),x)forxinnums)pos={x:ifori,(_,x)inenumerate(order)}vis=[False]*n ans=nforiinrange(n):ifvis[i]:continueans-=1j=iwhilenotvis[j]:vis[j]=Truej=pos[nums[j]]returnans10/18 1569. 将子数组重新排序得到同一个二叉搜索树的方案数按数组顺序依次插入空的二叉搜索树，第一个数一定是根，根一换树就变了，所以根不能动。比根小的都进左子树，比根大的都进右子树。左右两边各自的先后顺序决定子树长什么样，两边之间可以任意穿插。左边 m 个数、右边 n 个数，穿插方式是从 m+n 个位置里选 m 个给左边。左右再各自按同样规则计算，乘起来就是总方案。题目不要原数组本身，最后减 1，并对 10^9+7 取模。defnumOfWays(nums):""" :type nums: List[int] :rtype: int """importsys sys.setrecursionlimit(10000)mod=10**9+7n=len(nums)c=[[0]*nfor_inrange(n)]c[0][0]=1foriinrange(1,n):c[i][0]=1forjinrange(1,i+1):c[i][j]=(c[i-1][j]+c[i-1][j-1])%moddefdfs(a):iflen(a)<2:return1left=[xforxinaifx<a[0]]right=[xforxinaifx>a[0]]returnc[len(left)+len(right)][len(left)]*dfs(left)%mod*dfs(right)%modreturn(dfs(nums)-1)%mod