【DEF题十连测C】[Codeforces 1068D]AWLM

Description

有一个长度为$n$的序列,满足对于所有的$a[x]$,与它相邻的两个元素$a[x-1]$和$a[x+1]$中至少有一个大于等于它,其中$a[1]$和$a[n]$只有一个相邻元素, 现在这个序列中有些数字被破坏了(标记为$-1$),问有多少种合法恢复方案(每个数字$\in [1,200]$)
继续阅读 【DEF题十连测C】[Codeforces 1068D]AWLM

0

【DEF题十连测B】[Codeforces 333D]Characteristics of Rectangles

Description

给定一个$n \times m$的表格,求其中一个子矩阵
使得这个矩阵四个角的最小值最大
$n, m \leq 1000$
继续阅读 【DEF题十连测B】[Codeforces 333D]Characteristics of Rectangles

0

【DEF题十连测A】[Codeforces 895D]String Mark

Description

给出等长的$AB$串,问有多少$A$串的重排列得到的串字典序大于$A$串,小于$B$串。
继续阅读 【DEF题十连测A】[Codeforces 895D]String Mark

3+

[BZOJ1566]NOI2009管道取珠

Solution

状态$F[i_1,j_1,i_2,j_2]$可以表示为取珠方法$X$状态为$(i_1,j_1)$,取珠方法$Y$状态为$(i_2,j_2)$,$X,Y$的输出序列相同的有序对$(X,Y)$的数量。设$U[i]$为上管道第$i$个珠子,$L[i]$为下管道第$j$个珠子。则状态$F[i_1,j_1,i_2,j_2]$可以更新的状态为:
$$\mathrm { F } \left[ \mathrm { i } _ { 1 } , \mathrm { j } _ { 1 } , \mathrm { i } _ { 2 } , \mathrm { j } _ { 2 } \right] \rightarrow \left\{ \begin{array} { l } { \mathrm { F } \left[ \mathrm { i } _ { 1 } + 1 , \mathrm { j } _ { 1 } , \mathrm { i } _ { 2 } + 1 , \mathrm { j } _ { 2 } \right] \left| \mathrm { U } \left[ \mathrm { i } _ { 1 } + 1 \right] = \mathrm { U } \left[ \mathrm { i } _ { 2 } + 1 \right] \right. } \\ { \mathrm { F } \left[ \mathrm { i } _ { 1 } + 1 , \mathrm { j } _ { 2 } , \mathrm { i } _ { 2 } , \mathrm { j } _ { 2 } + 1 \right] \left| \mathrm { U } \left[ \mathrm { i } _ { 1 } + 1 \right] = \mathrm { L } \left[ \mathrm { j } _ { 2 } + 1 \right] \right. } \\ { \mathrm { F } \left[ \mathrm { i } _ { 1 } , \mathrm { j } _ { 1 } + 1 , \mathrm { i } _ { 2 } + 1 , \mathrm { j } _ { 2 } \right] \left| \mathrm { L } \left[ \mathrm { j } _ { 1 } + 1 \right] = \mathrm { U } \left[ \mathrm { i } _ { 2 } + 1 \right] \right. } \\ { \mathrm { F } \left[ \mathrm { i } _ { 1 } , \mathrm { j } _ { 1 } + 1 , \mathrm { i } _ { 2 } , \mathrm { j } _ { 2 } + 1 \right] \left| \mathrm { L } \left[ \mathrm { j } _ { 1 } + 1 \right] = \mathrm { L } \left[ \mathrm { j } _ { 2 } + 1 \right] \right. } \end{array} \right.$$
由于$X,Y$应当同步,所以当$i_1,j_1,i_2$都确定以后$j_2$可以被表示为$i_1 + j_1 – i_2$,于是状态表示可以减少一维。




0

[Codeforces 1003D]Coins and Queries – 贪心

Description

给你\(n\)个硬币,每个硬币的面值都为\(2\)的幂次方。先有\(q\)个询问,每个询问给出一个数\(b\),问你至少用多少个硬币才能使得他们的面值凑成\(b\)。若不能凑出,则输出\(-1\)。

Solution


1+