hydd的博客

博客

群论 学习笔记

2023-03-03 15:57:58 By hydd

格式有点问题,可以到 https://blog.hydd.cf/p/group/ 去看,但是加载比较慢。

群论

群的定义

定义:给定集合 $G$ 和集合 $G$ 上的二元运算 $\cdot$,满足以下条件称为群:

1、封闭性(Closure):若 $a,b\in G$,则 $\exists c\in G$,使得 $a\cdot b=c$。

2、结合律(Associativity):对 $\forall a,b,c\in G$,有 $(a\cdot b)\cdot c=a\cdot(b\cdot c)$。由于结合律成立,可记作 $a\cdot b\cdot c$。

3、有单位元(Identity):$\exists e\in G$,满足对 $\forall a\in G$,有 $a\cdot e=e\cdot a=a$。

4、有逆元(Inverse):$\forall a\in G$,满足 $\exists b\in G$,使得 $a\cdot b=b\cdot a=e$,记作 $b=a^{-1}$。

一些概念

群元素的个数是有限的,是有限群;群元素的个数是无限的,是无限群。

有限群 $G$ 的元素个数叫做群的阶,记做 $|G|$。

设 $G$ 是群,$G'$ 是 $G$ 的子集,若在 $G'$ 原有的运算之下也是一个群,则称为 $G$ 的一个子群。

若群 $G$ 的任意两元素 $a,b$ 恒满足 $a\cdot b=b\cdot a$。则称 $G$ 为交换群,又称 Abel 群。

一些性质

单位元唯一:$e_1e_2=e_2=e_1$

左右逆元相等:$ab=e,ca=e\rightarrow b=c$

证明:$cab=(ca)b=eb=b, cab=c(ab)=ce=c \Rightarrow b=c$

消去律成立:$ab=ac\rightarrow b=c$

证明:$ab=ac \Rightarrow a^{-1}ab=a^{-1}ac\Rightarrow b=c$

每个元的逆元唯一:$ab=ba=e,ac=ca=e \rightarrow b=c$

证明:$e=ab=ac\Rightarrow b=c$

多个数乘积的逆元:$(ab\cdots c)^{-1}=c^{-1}\cdots b^{-1}a^{-1}$

证明:$(c^{-1}\cdots b^{-1}a^{-1})(ab\cdots c)=c^{-1}\cdots b^{-1}(a^{-1}a)b\cdots c=\cdots=e$

对于有限群,逆元存在于消去律存在等价。

证明:上面已经证明逆元存在则消去律存在,接下来证明消去律存在则逆元存在。

$ab=ac\rightarrow b=c$,则令 $G'=\{ax|x\in G\}$,根据消去律 $ax$ 两两不同,则 $|G|=|G'|$,而根据封闭性,$G'\subseteq G$,(对有限群)故 $G=G'$,则必然存在 $e\in G'$,即 $\exists x\in G,ax=e$。

对于有限群,若 $a\in G$,则存在最小正整数 $r$,使得 $a^r=e$,且 $a^{-1}=a^{r-1}$。

证明:设 $g=|G|$,则 $a,a^2,\cdots,a^g,a^{g+1}\in G$ 中必有相同项(鸽巢原理)。

设 $a^j=a^k(1\leq j\lt k\leq g+1)$,则 $e=a^{k-j}$(消去律)。令 $r=k-j$,则 $a^r=a^{r-1}a=e$,即 $a^{-1}=a^{r-1}$。

既然存在正整数 $r$ 使得 $a^r=e$,其中必有最小者,不妨仍设为 $r$。

$r$ 称为 $a$ 的阶(和群的阶不同,这是一个元的阶),容易证明 $H=\{a,a^2,\cdots,a^r=e\}$ 在原有运算意义下也是一个群。

置换群

置换

置换:$[1,n]$ 到自身的一一映射称为 $n$ 阶置换,共有 $n!$ 个。$S_n$ 为所有 $n$ 阶置换组成的置换群。

置换群的运算:双射的复合(不满足交换律)。

循环

循环:$p=(a_1,a_2,\cdots,a_n)$ 称为 $n$ 阶循环,$a_1\rightarrow a_2\rightarrow a_3,\cdots\rightarrow a_n\rightarrow a_1$。$p^n=(1)(2)\cdots (n)=e$。

若两个循环无共同文字,称为不相交的,不相交的循环相乘可交换。任一置换可表示成若干不相交循环的乘积。

共轭类

$P=(a_1a_2\cdots a_{k_1})(b_1b_2\cdots b_{k_2})\cdots(h_1h_2\cdots h_{k_l})$,其中 $a,b,\cdots,h$ 都是不相交循环,$k_1+k_2\cdots k_l=n$。设 $k_i=j$ 的出现次数为 $c_j$,用 $(j)^{c_j}$ 表示,$\sum_{j=1}^njc_j=n$ 则它的格式为 $(1)^{c_1}(2)^{c_2}\cdots (n)^{c_n}$。

共轭类:$S_n$ 中所有相同格式的置换全体构成一个共轭类。

对换

任意循环都可以表示为对换的积:$(1\ 2\cdots n)=(1\ 2)(1\ 3)\cdots (1\ n)$。

每个置换的分解方式不是唯一的,但是表示成对换的个数的奇偶性是唯一的。

陪集

陪集:对于 $G$ 的一个子群 $G'$,它关于 $a\in G$ 的右陪集为 $G'_a=\{x\cdot a|x\in G'\}$,左陪集为 $_aG'=\{a\cdot x|x\in G'\}$。

根据消去律,陪集的元素两两不同,故 $G'$ 每一个陪集的大小都和 $G$ 相等。

方便起见,以下均以右陪集为例,左陪集同理。

一个性质:对于 $a,b\in G$,若 $G'_a \cap G'_b\neq \varnothing$,则 $G'_a=G'_b$。

证明:因为 $G'_a \cap G'_b\neq \varnothing$,所以 $\exists x,y\in G',x\cdot a=y\cdot b$,$y^{-1}\cdot x\cdot a=b$。

对 $\forall z\in G'_b$,设 $z=tb(t\in G')$,则 $z=tb=t\cdot y^{-1}\cdot x\cdot a=(t\cdot y^{-1}\cdot x)\cdot a$,而 $t\cdot y^{-1}\cdot x\in G'$,故 $z\in G'_a$,即 $G'_b\subseteq G'_a$。同理可以证明 $G'_a\subseteq G'_b$,故 $G'_a=G'_b$。

拉格朗日定理

拉格朗日定理(Lagrange's theorem):对任意 $G$ 的一个子群 $G'$,$|G'||G':G|=|G|$($|G':G|$ 表示 $G'$ 在 $G$ 中的陪集个数)。

证明:上面说明了 $G'$ 的陪集的大小都是 $|G'|$,而且任意两个相等或不交。

又因为 $e\in G'\Rightarrow x\in G'_x \Rightarrow \bigcup_{x\in G} G'_x=G $,所以共有 $|G':G|=\frac{|G|}{|G'|}$ 个不同的陪集。

这个定理说明了一个群的子群大小是整除该群大小的。

不动点、轨道和稳定化子

很多概念在中文翻译的描述上有差异,我们主要用不动点/轨道/稳定化子来描述。

设群 $G$ 作用在集合 $X$ 上。对于 $X$ 中的一个元素 $x$,每个 $G$ 中元素 $g$ 都把 $x$ 映射到某个 $g(x)\in X$ 上。

注意,$g(x)$ 表示将 $g$ 作用在 $x$ 上得到的结果。

不动点(fixed point):对于 $X$ 中的一个元素 $x$,如果 $x\in X$ 在任意 $g\in G$ 的作用下都不变,即 $g\cdot x=x$,那么称 $x$ 为该群作用的一个不动点。不动点集 $X^g=\{x\in X\mid g(x)=x, \forall g\in G\}$。

轨道(orbit):对于 $X$ 中的一个元素 $x$,所有能被映射到的元素 $g(x)$ 构成了 $X$ 的一个子集,称为元素 $x$ 的轨道。$\mathrm{orbit}(x)=\{g(x)\mid g\in G\}$。轨道集合 $X/G$ 为所有不同轨道的集合。

(另外的一种描述,等价类。)

稳定化子(stablizer):对于 $X$ 中的一个元素 $x$,所有满足 $g(x)=x$ 的 $g$ 构成了 $G$ 的一个子群,称为元素 $x$ 的稳定化子。$\mathrm{stab}(x)=\{g\in G\mid g(x)=x\}$。

(另外的一种描述,$k$ 不动置换类:设 $G$ 是 $S_n$ 的一个子群。对于 $k\in [1,n]$,$G$ 中使得 $k$ 元素保持不变的置换全体,称为 $k$ 不动置换类,记作 $Z_k$。)

轨道-稳定化子定理

轨道-稳定化子定理(Orbit-stabilizer theorem):对 $\forall x\in X$,有 $|\mathrm{stab}(x)||\mathrm{orbit}(x)|=|G|$。

证明:首先我们有对于 $\forall x\in X$,满足 $\forall g,h\in G,g(x)=h(x) \Longleftrightarrow g$ 和 $h$ 在稳定化子的同一个左陪集上,证明如下 $g(x)=h(x)\Leftrightarrow (g^{-1}\cdot h)(x)=x\Leftrightarrow g^{-1}\cdot h\in \mathrm{orbit}(x)\Leftrightarrow h\in \ _g\mathrm{orbit}(x)$。

故轨道数量 $|\mathrm{orbit}(x)|$ 就是稳定化子的陪集数量 $|\mathrm{stab(x)}:G|$,根据拉格朗日定理,可以得到 $|\mathrm{stab}(x)||\mathrm{orbit}(x)|=|G|$。

Burnside 引理

伯恩赛德引理(Burnside's lemma):$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$。轨道数(等价类)数量为所有置换下不动点数量的平均值。

证明:$|X/G|=\sum_{x\in X}\frac{1}{|\mathrm{orbit}(x)|}=\frac{\sum_{x\in X} |\mathrm{stab}(x)|}{|G|}=\frac{\sum_{g\in G} |X^g|}{|G|}$。

解释:第一个等号是,每个 $x$ 出现在大小为 $|\mathrm{orbit}(x)|$ 的轨道,而每个轨道应该被计算恰好一次,相当于其中每个元素贡献 $\frac{1}{|\mathrm{orbit}(x)|}$;第二个等号是轨道-稳定化子定理;第三个等号是两个分子都等于 $x\in X,g\in G,g(x)=x$ 的数量。

Pólya 定理

波利亚计数定理(Pólya enumeration theorem):对于 $n$ 阶置换群 $G$,用 $t$ 种颜色给 $n$ 个位置着色的不同方案数为 $|X/G|=\frac{1}{|G|}\sum_{g\in G}t^{c(g)}$,其中 $c(g)$ 表示置换 $g$ 拆出的不相交循环个数。

证明:只需证明 $|X^g|=t^{c(g)}$。$X^g$ 中的元素在 $g$ 作用下不变,等价于同一个循环上的颜色都相同,而不同循环间独立,故 $|X^g|=t^{c(g)}$。

IOI2022 部分题解

2022-08-27 23:11:50 By hydd

https://blog.hydd.cf/p/ioi2022/

Day2 T3 Thousands Islands 待填。

Catfish Farm

第 $i$ 列哪些鱼被抓住,只和第 $i$ 列堤的高度,以及 $i-1/i+1$ 列中较高堤的高度有关。

容易想到按列 dp,这样第 $i$ 列就有两种情况,较高的列是 $i-1/i+1$。

这个较高没有必要,仅仅多加了限制,所以可以每个 $i$ 自由选择 $i-1/i+1$,这样如果选的不是较高的答案只会更小。

我开始想的是,对于选择 $i-1$ 的,记录第 $i$ 列的高度;对于选择 $i+1$ 的,记录这列抓的鱼最高的高度。这样状态就表示算完了前 $i$ 列的答案,当前是选择 $i-1/i+1$。

其实不用这样,题目要求我们每一列选择一个堤的高度,就按照题目来,状态改为表示固定完了前 $i$ 列堤的高度,当前是选择 $i-1/i+1$。选择 $i+1$ 的答案在 $i+1$ 时再计算。

具体来说,记 $dp(i,j,0/1)$ 表示前 $i$ 列,堤恰好不覆盖这一列从下往上第 $j$ 条鱼,当前选择 $i+1/i-1$(当前列贡献 未计算/已计算)。对于前一列选当前列/这一列选前一列的,要算上增加的贡献。

https://qoj.ac/submission/44615

Prisoner Challenge

比较大小,容易想到在二进制下按位比较。$x$ 需要记录当前存的是第几位,当前位为 $\varnothing/A$ 的当前位的值是多少。

每次,如果当前记录的是 $A$,就拿 $B$ 这一位比较,如果相同跳到下一位,否则返回;记录的是 $\varnothing$,就把 $A$ 这一位记录进去。

这样次数太多(大概是 $3\log n$),但是用 $B$ 比较完相同后,你其实可以知道 $B$ 下一位的信息,把 $B$ 下一位信息存进去。可以发现,比较是按照位数 $B,A,B,A$ 交替,不需要记录里面存的是 $A/B$,现在只需要记录位数和当前位的值,大概是 $2\log n$。

一种思路是换进制,$k$ 进制应该是 $k\lceil\log_k n\rceil$,但还是不能通过。

二分和从高到低贪心填是几乎等价的。按照同样思路,可以改为每次把值域范围分成 $k$ 份,看是否在同一个值域区间,次数是 $f(n)=f(\lceil \frac n k\rceil)+k$,没区别。

题目保证了两个数不同,故如果当前数为 $1$ 或 $n$ 就直接返回,把剩下的范围再分成 $k$ 份,也就是 $f(n)=f(\lceil \frac {n-2} k\rceil)+k$。

把这个式子拿去 $dp$,对于不同的 $n$,$k$ 不固定,$f(n)=\min_k f(\lceil \frac {n-2} k\rceil)+k$,这样算出来 $f(5000)$ 恰好为 $20$。就按照 dp 出的方案选 $k$ 即可。

https://qoj.ac/submission/45397

Radio Towers

先考虑固定 $D$,对于选择的两个信号塔 $i,j$,中间要存在一个塔 $k$,$H_k\geq \max(H_i,H_j)+D$。

可以发现只有相邻的两个选择的信号塔才需要判断。

对每个 $i$,找到左右第一个 $k$,满足 $H_k\geq H_i+D$,分别记作 $L_i,R_i$。

$i,j$ 之间要有满足条件的塔,就要求 $R_i\leq L_j$($i,j$ 中较大的对应的位置一定满足 $k$ 的条件),也就是区间 $[L_i,R_i)$ 两两不交。

同理易证区间只会有包含和不交两种情况($D\geq 0$),对于两个位置 $i,j$,不妨假设 $H_i\geq H_j$,若 $R_i>L_j$,则区间 $[L_j,R_j)$ 都不满足条件,即 $R_i\geq R_j$。

不考虑询问的区间限制,$D$ 增加时,$L$ 只可能减小,$R$ 只可能增大,且根据证明,只有 $H$ 大的包含 $H$ 小的,故只会一些不是包含关系的区间变成了包含关系。

按照 $D$ 从小到大,每次把所有包含其它区间的区间全部删去(维护 $i$ 对应区间包含相邻某个的最小时刻),剩下的区间个数就是当前 $D$ 能选的数量。

有询问给定的区间限制 $l,r$ 时,把当前 $D$ 所有剩下的 $i$ 在 $[l,r]$ 内的个数求出来,但这样可能两边各少 $0/1$ 个区间(一个 $i$ 在 $[l,r]$ 内的,包含了一个在 $[l,r]$ 外的被删除了,实际上这个 $i$ 可以选)。

如果求出来的个数不为 $0$,看其中最小的 $L$ 和最大的 $R$,看 $[l,L),(R,r]$ 内是否还能选。要求区间内 $x\lt y,H_x-H_y$(或 $H_y-H_x$)的最大值,类似于 $ST$ 表的方法预处理即可。

https://qoj.ac/submission/45344

Digital Circuit

必须有一个叶子节点到根一路都是黑色,但是直接计数会算重

要每一种方案对应唯一的叶子节点(相当于添加了限制条件)。

树的形态固定,由于根节点为黑色,说明儿子里至少有 $p$(参数)个是黑色,那么选择其中的第 $p$ 个黑色儿子,往下走。

最终会走到一个叶子节点,则设这种方案对应这个叶子节点。

现在考虑每个叶子节点 $x$,算对应到它的方案的数量。首先它到根的都必须是黑色,此外其它点的参数毫无关系,因为固定其它点的参数后其它点的颜色固定后,要求对应到的是 $x$,则 $x$ 到根路径的所有的参数是唯一确定的。

对每个叶子节点预处理出到根路径外的点的参数选择的方案数。线段树支持区间取反操作,维护所有黑色叶子节点的方案数之和即可。

https://qoj.ac/submission/45436

Rarest Insects

把不同的数放在不同的列,这个东西很像一个柱形图(?)

一种思路是每次删掉一行(删掉所有出现过的数各一次,需保证数量始终为 $1$),次数是行数(最多数出现次数)$\times n$。

另一种思路是每次删掉一列(删掉某种数的所有出现,需保证数量每次必须加 $1$),次数是列数(数字种数)$\times n$。

两种各做 $\sqrt n$ 次后一定能删完(数字总数为 $n$)。这样是 $O(n\sqrt n)$ 次。没什么优化空间。

第一种思路其实可以扩展成每次删掉 $r$ 行,需保证数量始终不超过 $r$ 即可。

求出数字种类数 $c$。考虑二分答案(上界 $\frac nc$),用第一种思路来 check 当前答案 $mid$,是 $O(n\log n)$ 次。

这个可以继续优化,如果 check 成功了(加入了 $mid\times c$ 个数),已经加入的数之后就不需要加了;如果 check 失败了,未加入的数之后也不可能加。

这样每次数量接近减半(有个上取整),次数共 $2n$ 左右。再加上外面求种类数的 $n$,总次数 $3n$ 左右。

这样一交得了 99.89 分,再加点优化,比如已经达到 $mid\times c$ 之后的就不需要尝试加入了,再 shuffle 一下序列防止被卡,就通过了。

不知道有没有不用随机化严格在 $3n$ 内的做法?

https://qoj.ac/submission/45454

new-3-constructive

2022-07-07 16:51:52 By hydd

566E

  • 对于一对相邻的点 $(x,y)$,它们其它的相邻点之间的交集就是 $\{x,y\}$。且如果有两个相邻点交集的大小为 2 也一定是两个相邻的(出现的点如果不相邻那么它们路径上的也应该在交集中)。
  • 这样可以求出所有非叶子节点之间的连边,剩下的都是叶子节点。叶子节点的连边就看是哪个点和它相邻的所有点都包含了它。
  • 这样非叶子节点数量 $\leq 2$。如果没有非叶子节点则 $n=2$,特判;如果只有一个非叶节点,那么所有集合都是 $\{1,2,\cdots,n\}$;如果只有两个可以先用上面的方法找出两个非叶节点,但是不能用上面的方法判,叶子节点只会有两种不同的集合,一种接到一个点即可。
  • 用 bitset 优化,时间复杂度 $O(\frac{n^3}w)$。

1637G

  • 倒过来考虑,要把两个数 $x,y$ 变为 $\frac{x+y}2,\frac{x-y}2$。可以发现如果它们都是奇质数 $p$ 的倍数变化后还是 $p$ 的倍数,就不可能还原成 $1,2,\cdots,n$ 了。
  • 说明最后的结果一定是 $2$ 的幂,则最小的是满足 $2^k\geq n$ 的最小整数。通过构造证明可以取到。
  • 可以先把所有数都变成 $2^x(x\leq k)$ 的形式,再造出一个 0 然后再处理($(0,x)\rightarrow (x,x)\rightarrow (0,2x)$)。
  • 先找到 $2^t\lt n$ 最大的 $t$,对于 $[2^t+1,n]$ 的数和它们关于 $2^k$ 对称的位置先做一次操作,会变成一大堆 $2^k$ 和 $2,4,6,8,\cdots$,也可以看作是一个前缀,递归下去两个剩下的前缀即可,次数是一个 log 级别的。

1530G

  • 先找不变量,发现 1 的个数不变,且操作可逆。
  • 设 1 的个数为 $t$,$k=0,k=t,k>t$ 先特判。
  • 下面讨论 $0\lt k\lt t$,由于可逆所以可以把 $s,t$ 变成相同的字符串。
  • 看相邻两个 1 之间 0 的个数 $d_i$,如果 reverse 的两端都是 1 那么就是把中间的 $d$ 翻过来。
  • 对于一般的 reverse,不仅把中间的翻过来,且对于左右两边,可以给 $d_i+=x,d_{i+k}-=x$,$x\in [-d_i,d_{i+k}]$,就是带上若干个 0。对每个 $i$ 取 $j=d_{i+k}$ 把 $d_{k+1},d_{k+2},\cdots,d_t$ 归零。
  • 对于 $k$ 是奇数,剩下的可以一直交替做 $i=0,j=d_k$ 和 $i=1,j=d_{k+1}$。这样会隔一个清一个,而由于 $k$ 是奇数最后会把所有都清了,只剩下第一个位置,次数是 $2k+(m-k)\lt 2n$。
  • 对于 $k$ 是偶数,无论怎样翻转奇数位还在奇数位置上,偶数同理,所以可以再判断 $s,t$ 奇数位之和是否相同。剩下的可以一直交替做 $i=0,j=d_k$ 和 $i=1,j=-d_1$。这样清的位置是一个前缀或后缀,且会不停地翻,只剩下第一个和最后一个位置,次数是 $k+(m-k)\lt 2n$。且两个位置奇偶性不同,故只要满足之前的条件就一定可以。

804E

  • 有一个经典结论,排列交换相邻两个位置逆序对恰好变化 1,而交换距离为 $d$ 的可以等价于交换相邻的 $d+(d-1)$ 次,所以逆序对奇偶性一定会改变,故交换次数是奇数时一定不会和原序列相同。
  • $n\bmod 4=2,n\bmod 4=3$ 时交换次数为奇数,故无解。
  • $n\bmod 4=0$,可以 4 个分一组,然后就是组内要两两交换一次,两个组间要两两交换一次。最好的情况是组内和组间的做完都不变。组内的交换一种方案为 $(1,2),(3,4),(1,3),(2,4),(1,4),(2,3)$。两组之间,考虑把每组再分成两部分,两组的一部分之间容易构造出两边都翻转的方案 $(1_a,1_b),(2_a,2_b),(1_a,2_b),(2_a,1_b)$,那么两组每一部分都做一次就可以归位。
  • $n\bmod 4=1$,此时多了一个数,考虑在 $(2i,2i+1)$ 交换的时候多加入和 $n$ 的交换,以 $(1,2)$ 为例,把原先的 $(1,2)$ 改成 $(1,n),(1,2),(2,n)$,就可以了。

923F

  • 发现某棵树是菊花图一定无解,中心没法分配标号。此外 $n\leq 5$ 的都有解,可以暴力求出,其它的递归考虑。
  • 如果当前某棵树有点删掉后就会使得树变成菊花图,设这个点为 $u$,它父亲是 $v$,它父亲的父亲(菊花中心)为 $w$。为了使得另一棵树不能有其它点和 $w$ 连边,就从另一棵树选个叶子节点 $w'$ 与 $w$ 对应,$w'$ 父亲 $u'$ 就与 $u$ 对应。那么 $v'$ 就不能和 $u'$ 相邻,由于不是菊花图,所以一定存在 $v'$。而菊花图的限制只是除了 $u$ 的所有点都不能和 $w$ 相邻,$u$ 和 $v$ 不能相邻,所以剩下的可以随意分配。
  • 否则,两棵树都删除两个距离 >2 的叶子使得不是菊花图,递归即可。

833E

  • 先离散化然后讨论。
  • 如果一个位置覆盖了超过两个,这个位置就一定不会被照到。
  • 如果一个位置覆盖了正好两个,想要照到就必须让两个都消失。
  • 如果一个位置覆盖了恰好一个,若相交的有覆盖恰好两个的那么之前一定算到了,如果没有则说明相交部分没有贡献,可以都当作没有相交的来算,数据结构维护即可。

1060H

  • 它没有两个未知数的乘法操作,只有加法操作。
  • 可以想到能表示成 $((x+y)^2-x^2-y^2)/2$。
  • $/2$ 可以表示成 $\times 2^{-1}$,求逆元可以在外面求,而乘法可以用龟速乘。$-x$ 可以表示成 $(p-1)\times x$,也用龟速乘。
  • 现在问题在于平方,它只有 $d$ 次方,能否通过 $d$ 次方的值求出平方?给 $x,x+1,x+2,\cdots,x+d$ 前带个系数,让它们凑出 $x^2$。用高斯消元消一下,发现是可行的。每个都用龟速乘把系数带上求和即可求出平方后的值。

317E

  • 牛逼题。如果你走不到影子那里,又因为两人都不能穿墙,就永远不可能抓到影子。
  • 否则,你先走到当前影子的位置,然后看它现在在哪里,再继续走过去。如果你走出了这个 100*100,就可以再通过原来障碍的四个角,把影子靠上去再往它的方向走,就可以移动到一起。
  • 每一步走了后长度要么减少要么不变,且如果你出不去的话那么每一次走到影子要么距离减小(影子被挡了一下),要么两个的增量相同,而不可能一直增量相同,那么你就走出去了,所以一定会求出解。

1292E

  • 直接问 C,H 各一次剩下的都是 O,这样代价为 $2$。
  • 考虑优化,问一下 CC,CH,CO 就可以求出 C 的位置,再求出 H 的位置可以用 OH,HH,剩下的都是 O(第一个位置可能是 H,O,最后一个位置可能是 C,O),这总共问了 $5$ 次长度为 $2$。
  • 确定第一个和最后一个位置可以问 $3$ 次长度为 $n$,如果都不是就是剩下的一种。这样的代价总共是 $\frac 54+\frac 3{n^2}$,当 $n>4$ 时不超过 $1.4$。

  • 题目的限制是 $n\geq 4$,所以要特判 $n=4$。

  • 还是先问 CC,CH,CO,OH,如果问出了结果就至少确定了两个数,剩下的数还是用问 $3$ 次的方法解决,代价不超过 $\frac 44+\frac 3{16}$。但是接下来不能和之前一样了,否则代价就超了。
  • 如果问 HH 出了结果,就有几种情况:HHHH,HHH*,HH**。有些不可能(*HHH,*HH*,**HH)的原因是 CH,OH,HH 都问过了,不可能存在某个 H 前一个位置没问出来。而 HHHH 不用考虑;HHH* 最后一个只有可能是 C,OHH** 倒数第二个只可能是 OCC,CH,CO 都问过了),最后一个只有可能是 C,O。由于只有最后一个有两种不确定,所以可以直接问 $1$ 次长度为 $4$ 的,代价为 $\frac 54+\frac 1{16}$。
  • 如果问 HH 还不出结果,那么说明除了开头结尾一定是 O,且开头不是 C 结尾不是 H,如果其中有 O 就一定可以一次 OOO 问出来,否则就是另一个,代价为 $\frac 54+\frac 19$。

1267H

  • 显然的一点是在任何一步不能有两个相同的数字相邻。
  • 假设本身某个区间是合法的,往其中加入一些没有出现过的数,还是合法的。
  • 考虑每次拿出一些不相邻的位置,然后变成一个子问题。
  • 从后往前拆,倒着过来把每个能加入使得不会有数字相邻的选出,把它们分配一个新的权值,剩下的递归。
  • 这样能选出 $\frac{n}{3}$ 个数(近似),即每次 $n$ 变为原来的 $\frac 23 n$(近似),那么需要的颜色数为 $\log_{\frac 32} n$(近似)。

1526F

  • 考虑倒着推过来,假设知道了 $1,2$ 的位置或 $n-1,n-2$ 的位置,通过 $n-2$ 次询问就可以得到其它所有的(这个比较常见,求出某个特殊的可以推出全部)。
  • 如果你求出了两个差比较小的 $a,b$,如果两个数的距离不超过 $\frac {n-4}3$,用它们两个询问出的距离最大次大分别是 $1,2$ 或 $n,n-1$。
  • 那么假设你询问出的结果 $\leq \frac{n-4}6$,则任意两个距离都不超过 $\frac {n-4}3$。其实可以大力随机找,找不到的概率很小。不过也可以证明 13 个数中的所有三元组必定有符合条件的。其实也容易证明,考虑按照顺序两两之间的距离(共 12 个),现在相当于问是否有相邻两个都 $\leq \frac{n-4}6$。这个可以用鸽巢原理,总和不超过 $n-1$,则一定只有最多 5 个 $\geq \frac {n-4}6+1$,那么剩下的 7 个必定有两个相邻,它们就满足条件。

联合省选2022-序列变换(D2T2)

2022-04-19 14:43:09 By hydd

$x=0,y=0$ 答案显然为 $0$。

先把括号序列建树。和WC那题区别在于,那题建的是二叉树,这题建的是普通的多叉树(二叉树其实就是普通多叉转二叉得到的)。

左括号的权值即要求边上带权。操作1就是把相邻的两个子树,右边的并到左边,中间加一条新的边,权值为右边子树原先和父亲连边的权值。

操作2就是交换相邻两个子树的顺序。

最终要求没有一个点有两个儿子,也就是结果形如一条链,对应括号序列 ((((...))))

如果括号序列本身就不需要操作,直接特判,答案为 $0$。

容易发现最优策略是按照深度从小到大依次合并,因为两个子树并起来后再做会比两个子树先分别做再并会更优。

做完前 $i-1$ 层会变成一条链,第 $i$ 层的点只剩下一个,往下连了原先第 $i$ 层的所有边,且新增了一些边(如上图红色的 $c$ 边)的权值产生影响。故树的形态无关紧要,只需要考虑第 $i$ 层所有往下的边的权值。

现在操作可以简化为,每次在当前层选取任意两条往下一层的边,把其中一条丢到下一层,并计算新增代价,直到只剩下一条。

一方面要这一层新增的代价尽量小,另一方面要往下一层丢的权值尽量小。

丢的权值尽量小,每一层只能留下一条,所以丢下去的尽量小就是把最大值留在当前层。

简单情况

当 $x=0,y=1$ 时,假设保留边 $a$,唯一策略是每次选择 $a$ 边和非 $a$ 边合并保留 $a$ 边。 除了保留的边外其它边恰好贡献了一次,设保留边权值为 $w$,所有边之和为 $s$,代价为 $s-w$。 $s$ 固定,故 $w$ 越大越好,所以把最大的留在当前层,同时满足了丢的权值尽量小的条件。

当 $x=1,y=1$ 时,此时每次合并代价与保留谁无关(都选与最小边合并)。 设边数量为 $t$,保留最小边权值为 $m$,所有边之和为 $s$,代价为 $s+(t-2)m$。 还是可以把最大的留在当前层,也满足了丢的权值尽量小的条件。

重头戏

当 $x=1,y=0$ 时,还是先与最小值合并,保留的不是最小值最后把保留值和最小值合并丢到下一层。 设边数量为 $t$,保留最小边权值为 $m$,代价为 $w+(t-2)m$。 此时这种情况新增代价最小的并不是保留最大值而是保留最小值,两个不一致,不能直接贪心。

仔细研究一下,首先每一层的 $t$ 是无论保留什么都不变的,设前 $i$ 层共有 $s_i$ 个值,那么第 $i$ 层的 $t$ 就是 $s_i-i+1$。而树是不能出现断层的,故在 $i$ 不超过树高之前 $t$ 是不降的,超过树高之后 $t$ 就每次 $-1$。

还是拆成两部分,一部分是每一层的 $m$ 尽量小,另一个是 $w$ 尽量小。

最开头的一段 $t=1$ 的一定没用,每一个被保留的都会算一次代价,所以你要 $w$ 之和尽量小也就是最后的一层(也就是合并结束时的那层 $t=1$)的 $w$ 值尽量大。

倒数第二层(合并结束前的那层 $t=2$)的策略也显然是保留最小值,把较大的 $w$ 扔下去。

当 $t\geq 3$ 开始你就可以每次保留非最小值和最大值的一个值,这样即保证了每次能传下去最小值使得 $m$ 尽量小,又保证了最后保留的 $w$ 能是 $t\geq 3$ 开始的最大值。

关键就在于开头 $t=1$ 后的那段 $t=2$,这一段的代价和保留的值决定了最终的代价。如果这一段保留的值比较小,那么它可以变为后面几层的 $m$;如果保留的值比 $t\geq 3$ 开始的最大值还要大,那么可以变成最后保留的 $w$。如果两个都不是的一定不优。

如果你保留的数不比之后的最大值还要大,那么你可以减小保留的值,从而缩小后面几层的 $m$;如果比最大值还要大,那么你一定不会对后面几层的 $m$ 有影响,这样不如继续加大保留的值使得最后剩下的 $w$ 尽量大。

所以对于开头的这段 $t=2$,你只需要保留最小值/最大值即可。两个都算一下取个 $\min$ 就是答案。

这个两段分开考虑还是不好写,可以直接考虑把策略变成每次保留次大值/次小值,这样就不需要把前面的 $t=2$ 和之后 $t\geq 3$ 的分开写了。最后的一个 $t=2$ 直接手动处理一下,也就是把两个数较小值加进答案即可。

代码(不知道对不对):

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,x,y,cnt,v[810000],p[810000];
int num[810000],nxt[810000],z[810000];
string s; multiset<int,greater<int> > q;
vector<int> vec[810000];
void solve(int l,int r,int dep){
    while (l<r){
        vec[dep].push_back(v[p[l]]);
        solve(l+1,nxt[l]-1,dep+1);
        l=nxt[l]+1;
    }
}
void build(){
    int sum=0,tot=0;
    for (int i=1;i<=n+n;i++)
        if (s[i-1]=='(') sum++,num[sum]=i,p[i]=++tot;
        else nxt[num[sum]]=i,sum--;    
    solve(1,n+n,1);
}
ll solve01(int l,int r){
    ll sum=0,ans=0; q.clear();
    for (int i=l;i<=r;i++){
        for (int v:vec[i]) q.insert(v),sum+=v;
        sum-=*q.begin(); q.erase(q.begin()); ans+=sum;
    }
    return ans;
}
ll solve11(int l,int r){
    ll sum=0,ans=0; q.clear();
    for (int i=l;i<=r;i++){
        for (int v:vec[i]) q.insert(v),sum+=v;
        int mn=*q.rbegin();
        ans+=sum; ans+=(q.size()-2)*mn;
        sum-=*q.begin(); q.erase(q.begin());
    }
    return ans; 
}
ll solve10_min(int l,int r){
    ll sum=0,ans=0; q.clear();
    for (int i=l;i<r;i++){
        for (int v:vec[i]) q.insert(v),sum+=v;
        int c=*++q.begin(),mn=*q.rbegin();
        ans+=c; ans+=(q.size()-2)*mn;
        sum-=c; q.erase(q.find(c));
    }
    for (int v:vec[r]) q.insert(v),sum+=v;
    return ans+*q.rbegin();
}
ll solve10_max(int l,int r){
    ll sum=0,ans=0; q.clear();
    for (int i=l;i<r;i++){
        for (int v:vec[i]) q.insert(v),sum+=v;
        int c=*++q.rbegin(),mn=*q.rbegin();
        ans+=c; ans+=(q.size()-2)*mn;
        sum-=c; q.erase(q.find(c));
    }
    for (int v:vec[r]) q.insert(v),sum+=v;
    return ans+*q.rbegin();
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin>>n>>x>>y; cin>>s;
    for (int i=1;i<=n;i++) cin>>v[i];
    build();

    z[1]=vec[1].size(); int pos=0;
    for (int i=2;i<=n+1;i++){
        z[i]=(z[i-1]-1)+vec[i].size();
        if (z[i]==0){ pos=i; break;}
    }
    pos--; assert(z[pos]==1);

    int cur=0;
    for (int i=1;i<pos;i++)
        if (z[i]>1){ cur=i; break;}
    if (!cur){ cout<<"0\n"; return 0;}


    if (x==0&&y==1){ cout<<solve01(cur,pos-1)<<'\n'; return 0;}
    if (x==1&&y==1){ cout<<solve11(cur,pos-1)<<'\n'; return 0;}
    if (x==1&&y==0){ cout<<min(solve10_min(cur,pos-1),solve10_max(cur,pos-1))<<'\n'; return 0;}
    cout<<"0\n";
    return 0;
}

我这写的什么离谱题解。。。

NOIP2021 T3 方差 题解

2021-11-21 12:37:30 By hydd

$$ \begin{align*} n\overline{a}&=\sum_{i=1}^na_i\\ \\ n^2D &=n\sum_{i=1}^n(a_i-\overline{a})^2\\ &=n\sum_{i=1}^n a_i^2-2n\overline{a}\sum_{i=1}^n a_i+n^2\overline{a}^2\\ &=n\sum_{i=1}^n a_i^2-2(\sum_{i=1}^n a_i)^2+(\sum_{i=1}^n a_i)^2\\ &=n\sum_{i=1}^n a_i^2-(\sum_{i=1}^n a_i)^2\\ \end{align*} $$

观察题目中的式子,$a'_i\leftarrow a_{i-1}+a_{i+1}-a_i$,根据 CF1110E 的套路,可以差分,令 $d_i=a_{i+1}-a_i(1\leq i\lt n)$,一次操作 $(2\leq i\lt n)$ 即:

$$ d'_{i-1}=a'_{i}-a'_{i-1}=(a_{i-1}+a_{i+1}-a_i)-a_{i-1}=a_{i+1}-a_i=d_i\\ d'_i=a'_{i+1}-a'_{i}=a_{i+1}-(a_{i-1}+a_{i+1}-a_i)=a_i-a_{i-1}=d_{i-1} $$

相当于交换 $d_{i-1},d_i(2\leq i\lt n)$,故 $d$ 可以通过若干次操作,变为任意 $d$ 的排列。

由于 $a_1$ 不变,那么 $a$ 和 $d$ 是一一对应的。现在要求一个 $d$ 的排列使得 $n^2D$ 最小,继续推式子: $$ \begin{align*} n^2D &=n\sum_{i=1}^n a_i^2-(\sum_{i=1}^n a_i)^2\\ &=n\sum_{i=1}^n a_i^2-\sum_{i=1}^n\sum_{j=1}^na_ia_j\\ &=\frac{1}{2}(n\sum_{i=1}^n a_i^2-2\sum_{i=1}^n\sum_{j=1}^na_ia_j+n\sum_{j=1}^n a_j^2)\\ &=\frac{1}{2}(\sum_{i=1}^n\sum_{j=1}^n(a_i-a_j)^2)\\ &=\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(a_{j+1}-a_i)^2\\ &=\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(d_i+d_{i+1}+\cdots+d_j)^2\\ \end{align*} $$ $n^2D$ 取最小值时,$d$ 一定是先递减后递增的。

考虑在分界位置(即递减到递增)从小到大往两边加数,由于 $$ \begin{align*} n^2D &=n\sum_{i=1}^n a_i^2-(\sum_{i=1}^n a_i)^2\\ \end{align*} $$ 维护 $dp[k][s]$ 表示当前已经加入了 $k$ 个数,现在的 $a$ 之和为 $s$ 的最小 $\displaystyle \sum_{i=1}^n a_i^2$。

初始 $dp[1][s]=0$。

转移时考虑加到左边还是右边:

  • 左边:原来是 $a_1,a_2,\cdots,a_k$,现在变为 $d,a_1+d,a_2+d,\cdots,a_k+d$,新增的贡献为

$$ \begin{align*} \Delta &=d^2+\sum_{i=1}^k (d+a_i)^2-\sum_{i=1}^k a_i^2\\ &=(k+1)d^2+2d\sum_{i=1}^ka_i\\ &=(k+1)d^2+2ds\\ \end{align*} $$

  • 右边:原来是 $a_1,a_2,\cdots,a_k$,现在变为 $a_1,a_2,\cdots,a_k,a_k+d$,新增的贡献为 $$ \begin{align*} \Delta &=(a_k+d)^2\\ \end{align*} $$ 其实可以发现 $a_k$ 是固定的,为之前所有的 $d$ 之和,不需要再记录。

答案为 $\displaystyle \min_s\{n\times dp[n][s]-s^2\}$。

分析一下时间复杂度,第一维是 $O(n)$ 的,第二维是 $O(nV)$ 的,转移 $O(1)$。

但是可以发现 $d$ 为 $0$ 的转移可以忽略,第一维是 $O(\min(n,V))$ 的,总复杂度为 $O(nV^2)$,可以通过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1ll<<60;
int n,a[11000],d[11000]; ll dp[510000];
ll sqr(ll x){ return x*x;}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<n;i++) d[i]=a[i+1]-a[i];
    sort(d+1,d+n);

    for (int i=0;i<=500000;i++) dp[i]=INF;
    dp[0]=0; int lim=0,sum=0;
    for (int i=1;i<n;i++){
        if (!d[i]) continue;
        for (int s=lim;s>=0;s--){
            if (dp[s]==INF) continue;
            dp[s+sum+d[i]]=min(dp[s+sum+d[i]],dp[s]+sqr(sum+d[i]));
            dp[s+i*d[i]]=min(dp[s+i*d[i]],dp[s]+2*s*d[i]+i*sqr(d[i]));
            dp[s]=INF;
        }
        lim+=i*d[i]; sum+=d[i];
    }
    ll ans=INF;
    for (int i=0;i<=lim;i++)
        if (dp[i]!=INF) ans=min(ans,n*dp[i]-1ll*i*i);
    printf("%lld\n",ans);
    return 0;
}
hydd Avatar