zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

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

点击跳转

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

点击跳转

先考虑每种硬币可以用无数次

f_i表示金额为i有多少种方案

f_i = \sum_{j=1}^4 f_{i-c[j](i \ge c_j)}

我们再来考虑硬币使用次数有限制怎么办

不合法的情况有:

1超额

1,2超额

1,3超额

1,4超额

1,2,3超额

1,2,4超额

1,3,4超额

1,2,3,4超额

...

要注意的是在多种硬币限制的情况下可能会减去多次,或加上多次

比如1超额,2超额,(1,2同时超额被减去两次,这是就要加回来

(1,2,3)(1,2,4)又是多算的...

是不是更直观的了解了容斥?

为了方便,我们可以枚举二进制下状态来更加优美实现。

(当有奇数种不合法的时候减去,偶数种不合法时加上)

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)

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

点击跳转

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

点击跳转

类似Moo

我们可以发现字符串每次长度变成原来的两倍

我们可以把之前不需要的状态删去

一开始按套路用递归写

然后爆栈了

应该用循环写

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

点击跳转

枚举当前合法序列放了多少个i(2i>n)的,记数量为x,那么对于i(2i\le n)的数量为m-x

对于答案的贡献为x!\times (m-x)!\times {x \times C(m-x)} \times {C(x,\frac{n}{2}})\times {C({m-x},\frac{n+1}{2}})

(因为第二类数只能放在第一类数前面,所以一共x个空放m-x个数,方案为C({m-x},x)

选出x个第一类数和vm-x个第二类数的方案分别为C(x,\frac{n}{2})C({m-x},\frac{n+1}{2})

然后x个数和m-x个数的排列为x!(m-x)!

所以就得到了这个贡献式子

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

点击跳转

有趣的题

我们可以发现只有一组相邻两数只能求差的绝对值,其他数都可以取绝对值求和

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

点击跳转

题解很妙

f[i][j][k]为从ijk步的方案数

f[i][j]这个矩阵的k次方就是答案

ans = \sum f[1][i]

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

点击跳转

  1. 如果个数中没有奇数,那么答案就是所有数字的gcd,然后构造答案就是输出\frac {gcd}2个回文串

  2. 如果个数中只有一个奇数,那么答案也是所有数字的gcd,然后构造答案就是输出gcd个回文串,个数为奇数的颜色放在回文串的中间

  3. 如果个数中有两个或以上的奇数,那么答案就是0,因为两个奇数就已经构造不出有优美cut的环来了

48/73
Search
search