0%

好久没更了,水平下降严重 = =

AtCoder Japanese Student Championship 2019 Qualification E

题意

有 $n$ 个写着数字的卡片放在 $h\times w$ 的网格上,第一次你可以在每一行选择至多一张卡片取走,第二次在每一列选择至多一张卡片取走,要求最大化取走卡片上的数字总和。

同一个位置可能有多个卡片。

$n,h,w\le 10^5$

Read more »

好久没更了 = =

现在看到什么题都感觉一脸不可做,水平太低了

题意

给出仅包含小写字母的长度为 $n$ 的字符串 $s$

每次取出 $s$ 的一个子串 $t_i$(可以为空),执行 $m$ 次,顺次拼接成一个大字符串 $t=t_1 t_2\dots t_m$,求可以得到多少种本质不同的 $t$

$q$ 次询问,每次给出一个 $m$

$n,q\le 10^5, m\le 10^{10}$

Read more »

Codeforces 1090H. Linearization

题意

定义一个长度为 $n(n=2^k,k\in N)$ 的 01 串 $s$(从 0 开始标号)是线性的,当且仅当存在整数 $x$ 和 二进制数位 $b$,使得 $\forall i\in [0,n),s_i=P(i{\rm and}x){\rm xor}b$,其中 $P(a)$ 表示 $a$ 的二进制表示中 $1$ 的数量的奇偶性

定义一个 01 串的线性化难度为,进行最少的取反一个区间的操作,使之成为线性的操作次数

给定一个长度为 $m$ 的 01 串 $t$,$q$ 次询问指定一个子串,要求计算其线性化难度

$m,q\le 2\times 10^5$

Read more »