zcmimi's blog

arrow_back共2篇文章

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

我们假设现在要合并的两个数是x,y,那么合并后是x\cdot10^{\ln y+1}+y

我们可以预处理出 a_i \cdot 10^t \mod k(t\le 10)

每个a_i统计有多少个数接到它前面符合要求

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

好题!

重新排序后能变成回文串,出现次数为奇数的字母最多只能有一种

因为只有22种字符所以我们可以用状态压缩来记录每种字母出现的次数是奇数或者偶数

设路径端点的两端为x,y,d_x表示1~x所有状态的异或值,D_x表示x的深度

那么如果这条路径满足条件,则d_x \oplus d_y在二进制下最多只有一个1

它的长度为D_x + D_y - 2 \times D_{lca(x,y)}

我们可以开一个桶来记录每种状态出现的最深的位置是哪里

sta为满足条件的状态

用每个店更新答案的时候就ans=\max(ans,b[sta \oplus d_x] + D_x - 2 \times D_{lca})

接下来就按静态链分治的套路操作就可以了

复杂度: \Theta( n \log n)

1/1
Search
search