0%

A - 数一数

总感觉是做过的题,甚至清晰的记得给赵爷讲过,但是想不起来做法了…… :sob:

ZJK 告诉我题意是有问题的,每一列只能有恰好一个 1 ,否则样例 1 的答案就应该是 34

Read more »

Sol

假设 A 按照从小到大排好序之后得到的数组是 B 。对于相邻的两个位置,假设其中一个是 Bi ,另一个是 Bj ,其中 i<j ,那么这两个位置对 |fifi+1| 的贡就是 BjBi=k=ij1(Bi+1Bi) 。这个式子启发我们,对每个 Bi+1Bi 算有多少对相邻的位置满足其中一个数 Bi 另一个 Bi+1 ,就能得到 |fi+1fi| 。这也等价于我们把所有 Bi 的数插入之后得到的序列中,极大连续段的端点数。

fi,j,k,d 表示已经插入了 i 个数,插入了的数在序列中形成了 j 个极长的连续段,已经统计过的 |fifi+1| 的贡献和是 k ,两个端点是否被占用过,对应的方案数。转移 O(1) ,最后的答案是 jmfn,1,j,2 ,总复杂度 O(n2m)

Read more »

Sol

考虑给一个第一行确定的矩形涂色的方案数:

  • 第一行是红蓝交错的(RBRBRBR…或者BRBRBRB…)
    • 那么,接下来的每一行都有恰好两种选择,RBRBR…或者BRBRBR…,方案数是 2n1
  • 第一行存在两个相邻的位置颜色相同
    • 显然在第二行中,那两个位置的颜色也是相同的;以此类推,这个矩形中的每一行都会有两个相邻的位置颜色相同
    • 对于第二行来说,由于上一行和这一行的至少两个格子的颜色是确定的,所以第二行每个格子的颜色都是确定的;后面的行也是同理
    • 所以涂色的方案数是 1
Read more »