1.25 Namomo Camp

ACM

Day1 DP

Todo

ZJOI2012 波浪、Fountains（ICPC 2020 Shanghai）、String Transformation（CF 1383 C）（...看ppt吧）

波浪

隐蔽的居所

https://blog.csdn.net/Johnny817/article/details/102979270
https://blog.csdn.net/sz_165394732/article/details/102979948

$f[i][s][0/1]$

Good Bye 2017 G. New Year and Original Order(数位DP)

一个简单的做法是枚举$1\sim 9$每个数$k$，DP时维护$=k$、$>k$的数位各有多少个。复杂度是$O(100n^3)$。
观察一下$S$的形式，比如：$112333=111111+1111+111$，可以发现数位$1$的贡献是$\begin{matrix}\underbrace{11...1}\\6个1\end{matrix}$，数位$2$的贡献是$\begin{matrix}\underbrace{11...1}\\4个1\end{matrix}$...也就是$k$的贡献是$\begin{matrix}\underbrace{11...11}\\cnt个1\end{matrix}$，其中$cnt$是$\geq k$的数位个数。
所以DP时只需要维护$\geq k$的数位有多少个，求出方案数后乘$\begin{matrix}\underbrace{11...11}\\cnt个1\end{matrix}$就是贡献。
这样复杂度$O(100n^2)$。

Fountains

https://www.cnblogs.com/reverymoon/p/14153891.html

Sum

Lucky Numbers

$Description$
数$x$的价值定义为：$x$十进制表示中第$i$位为$3$则该位价值为$F_i$，该位为$6$价值为$2F_i$，为$9$价值为$3F_i$，否则为$0$，然后所有位上价值相加。
给定$K$。$Q$次询问，每次询问给定$n$，求满足$K$个数的和为$n$情况下，这$K$个数的最大价值和。
$n,K\leq 999999,q\leq 10^5$。
$Solution$
假如$K$个数的所有位上只有$0,3,6,9$，那么每一位都可以看作 总数为$3K$、体积为$3\times10^i$、价值为$F_i$的物品，就是$6$个物品、容量为$n$的多重背包。
那么考虑怎么让尽可能多的数位上是$0,3,6,9$。
求和时每位是独立的，对于某一位，如果有两个数该位分别是$a,b$而不是$0,3,6,9$，则若$a+b\leq 9$，那么可以将$a,b$换成$0,a+b$；否则$a+b>9$则可以将$a,b$换成$9,a+b-9$。
所以对于每一位，可以满足最优情况下只有一个数该位不为$0,3,6,9$。将这些不为$0,3,6,9$的位放到一个数上，就满足$K-1$个数的所有位上为$0,3,6,9$，剩下一个数任意。
像最上面一样，对每位$3(K-1)$个物品做二进制优化多重背包，然后加上剩下的一个数就ok。
复杂度$O(6m\log K)$。
细节：预处理一下，先把单独的那个数价值求出来，再做背包。

HDU. 6566. The Hanged Man(树形背包DP DFS序 重链剖分)

$Description$
给一棵$n$个点的树，每个点有体积$a_i$和价值$b_i$，求总容量分别为$1\sim m$时选出一个最大价值独立集（相邻节点不能同时选）的方案数。
$n\leq 50,m\leq 5000$。
$Solution$
还是先考虑最简单的，$f[i][j][0/1]$表示当前为点$i$，已选$j$体积，选/不选$i$的方案数。树上背包复杂度$O(nm^2)$。
考虑用DFS序优化树形背包。问题在于 DFS序从$i$到$i+1$时，这个点$A_i$可能先向上走很多步到$x$，然后再向下到$A_{i+1}$，所以需要记录$x$的状态才能知道$fa[A_{i+1}]$选没选。同理，DP时要记一个点到根节点路径上所有点的状态，状态数就成了$2^n$。
优化是，用重链剖分来求DFS序，先DFS轻儿子再走重儿子。这样$i$到$i+1$需要向上跳时，会跳过$i$所在的一整条重链（走一条轻边$fa[top[A_i]]-top[A_i]$到$i+1$所在重链），对$i+1$我们只需记$fa[top[A_i]]$的状态。
同理，只需对每一条轻边$u\to v$记点$u$的状态，一共要记当前点到根节点路径上$O(轻边条数)=O(\log n)$个点的状态，状态数为$2^{\log n}=n$。
复杂度$O(n^2m)$。
细节：先把所有点要记的所有$fa[top[i]]$求出来（记为$sta$）。转移时，先枚举$sta_i$求出$sta_{i+1}$的状态，然后再枚举选不选$i+1$更新$s_{i+1}$即可。

Day3 数论

• $a/b\ mod\ m=(a\ mod\ bm)\ /b$
• 令$w(n)$表示$n$的质因子个数，$2^{w(n)}=\sum_{ij=n}[(i,j)=1]=\sum_...$

Day4 构造

CF. 1477C. Nezzar and Nice Beatmap(构造)

$Description$
给定平面上$n$个不同的点，求一个排列$P_i$，使得$\forall i\in[1,n-2]$，$P_i,P_{i+1},P_{i+2}$依次相连构成的角为锐角。无解输出-1。
$n\leq 5000$。
$Solution$
连边和判断锐角，考虑大角对大边，只需要让$|P_{i}P_{i+2}|$不是最长边即可。所以直接令$|P_iP_{i+1}|>|P_iP_{i+2}|$，即$i$每次向最远的点连边，一定可以满足$|P_iP_{i+2}|$不是最长边，这样一定有解。

CF. 1477D. Nezzar and Hidden Permutations(构造)

$Description$
给定$m$个二元组$(a,b)$，求两个排列$p,q$，使得$\forall i\in[1,m]$，$(p_{a_i}-p_{b_i})(q_{a_i}-q_{b_i})>0$并最大化$\sum_i[p_i\neq q_i]$。
$n,m\leq 5\times 10^5$。
$Solution$
把限制看成边。题意可以化为：给一个无向图，给边定向，使存在两个拓扑序且$p_i=q_i$的点尽量少。（感觉也很抽象，对我没什么用）
考虑什么时候点$x$一定有$p_x=q_x$：和其它所有点相连的点肯定是。所以先将度数为$n-1$的点删掉。
然后每个点至少和一个点没有连边。考虑一个点$x$和一个点集$S$（$k=|S|\geq 1$），满足$x$与$S$中所有点无连边（即$x$与$S$大小关系任意），那么取$p_{x,S_1,S_2,...}=1,2,3,...,k,\ q_{x,S_1,S_2,...}=k,1,2,...,k-1$显然可以使$x,S$合法。
那如果能将图划分成若干个$(x,S)$的结构，因为每个$(x,S)$内部编号连续，$(x,S)$之间的大小关系就不会改变，那么就找到解了。

那我们就模拟这个过程。称上面的与$S$无连边的$x$为关键点。
对于一个尚未考虑的$x$，任取与$x$无连边的点记为$y$。

• 如果$y$也还没考虑过（没加入任何$(x,S)$），那么将$x,y$划分到一个结构中。
• 如果$y$在某个结构中，且是该结构的关键点 或 该结构大小为$2$，那么$y$仍作为关键点，将$x$加入该结构的$S$里。
• 如果$y$在某个结构中但不是该结构的关键点（有$|(x,S)|>2$），那么将$y$从该结构中删掉，将$x,y$划分到一个结构中。

可以发现这个构造只需满足“对任意点存在一个和它没有连边的点”，且最终每个点都属于一个结构且每个结构有一个关键点和$|S|\geq 1$。所以一定有解使所有$i$满足$p_i\neq q_i$。
用set维护，复杂度$O(n\log n)$。或者unordered_map可以$O(n)$。（不过找一个与$x$无连边的点需要sort一下与$x$相连的点，桶排太麻烦所以没必要$O(n)$）

另一种做法（官方题解）：
考虑补图，补图里的边即大小关系未定的点对。
只需考虑度数$\leq n-2$的点，它们在补图中度数$\geq 1$，也即至少和一个点未确定大小关系。
考虑一个最小的能调整的结构：菊花图（一个点$x$和一个集合$S$中所有点均有边构成的菊花，$|S|\geq 1$）。调整方式同上。
所以题意变成：给一个图，求一个边集使得每个连通块都是一个菊花图。
那只需对每个连通块求出任意一棵生成树，DFS就可以且一定可以拆出若干菊花图。然后在每个菊花上调整大小关系即可。
DFS是$O(n)$的。但第一种写法好强啊/kel。

区域划分

平面上有n条直线，将平面划分成若干个区域。对这些区域黑白染色，使得相邻区域颜色都是不同的。
增量构造。每次加一条直线，将直线一边的取反即可。

LEARN FROM A GAME

确定一个右下角的点，每次将一行/一列的点依次弄过去（八数码）。
保持$n,m\geq 2$，so尽量保持一个方形$n=m$。$=1$的情况特判。

90 AND 270

左转右转并绕回去
90 270 90、90 270 270：一个矩形的一角，凹下/凸出一块
90 270 可以删掉，之后再做调整
调整成整数坐标：每次乘$2$加$1$然后凸/凹，最后还要离散化一次。

Jinan E

https://ac.nowcoder.com/acm/contest/10662
思路：从$S$变成一个比较好的中间状态$M$，再变到$T$。若操作可逆，则可判断是否有$S\to M$、$T\to M$。
但不可逆。so找一个中间状态：一条链。
直径$\geq 3$的树每次都可选直径和一个点$O(n)$次内使直径+1。

已经不知道哪个题..

找中间状态：全朝一个点连边的状态。

Jinan J

$100,60\to 一半$。而树是一个二分图。
弄出二分图左边$2^i$，右边对应点$2^{n}-2^i$。然后避免左边、右边内部相连，左边数前加个$01$，右边数前价格$10$。

HDU. 5334. Virtual Participation(构造)

$Description$
给定$K$。构造一个字符集大小没有限制、长度不超过$10^5$的字符串，使得不同的子串个数恰好为$K$。
$K\leq 10^9$。
$Solution$
做法1：
考虑简单的$\begin{matrix}\underbrace{111...1}\\a_1个\end{matrix}\begin{matrix}\underbrace{222...2}\\a_2个\end{matrix}\begin{matrix}\underbrace{333....}\\a_3个..\end{matrix}$，$\sum a_i=n$，则不同子串数为：$C_{n+1}^2-\sum_{a_i\geq 2} C_{a_i}^2$。
不妨先求出最小的$n$使得$C_{n+1}^2\geq K$。令$x=C_{n+1}^2-K$，有一个结论是“任何一个数可由最多三个三角数构成”，所以从大到小找出构成$x$的$C_{a_i}^2\ (a_i\geq 2)$即可。剩下$L-\sum a_i$的数直接补$4\ 5\ 6\ 7\ 8...$。
网上有个题解是从小到大找，似乎是会超过三个的（不满足结论）。

细节：$K$较小如$K=4$时（实测只有$K=4$或$K=16$），$\sum a_i$会大于$n$（因为$C_n^2$增长不够快还是？）。所以$K$较小时需特判，直接输出$K$个$1$就ok。

做法2：
直接考虑构造$\begin{matrix}\underbrace{111...1}\\a个\end{matrix}\begin{matrix}\underbrace{222...2}\\b个\end{matrix}\begin{matrix}\underbrace{111...1}\\c个\end{matrix}$，令$a\geq c$，则子串数为$ab+bc+ac+a+b$。
条件为$ab+bc+ac+a+b=K$即$(a+c+1)(b+c+1)=K+(c+1)^2$，枚举$c+1$和$a$，保证$a\geq c$且$a+b+c\leq 10^5$即可找到解。
$K$较大的时候，这个枚举效率似乎就不如做法1了。

网上这题题解都是远古时代的了... 不过dls这课件也是远古-的了（但还加新题好良心）

Festival

$FESTIVALFESTIVAL...FESTIVAL$，设有$n$组，只需保证$x_1\leq x_2\leq ...$，总数$\binom{n+7}8$。
调整：变成$FF..ESTIVALFF..ESTIVAL...FF..ESTIVAL$。

ICPC2020 南京. A. Ah, It's Yesterday Once More(构造)

$Description$
在一个$20\times20$的网格上，构造一棵树（边是四连通），满足：树上每个点上有一个人，每次随机上下左右走一格（走到树外则原地不动消耗一次），有超过$25\%$的概率$50000$步后所有人不会走到同一个点。
$Solution$
只需尽可能让路径长（是吧？）。
也就是要让空间利用率尽可能高。蛇形路径空间利用率低（约$\frac12$）（可以随机一百次求一下概率），阶梯型路径利用率高就可以过了（约$\frac23$）。

阶梯型拿excel随便搞搞就弄出来了：

主要是注意可以弄这个结构：
然后能额外扩展的部分就多扩展一下，尽可能覆盖多的格子。

Day5 线段树

区间等比数列：$(a,b),(ad,bd),(ad^2,bd^2)...$
fibonacci：用通项表示：$f_i=ad_1^i+bd_2^i+c$，维护区间等比数列；矩阵

询问区间本质不同子序列个数：
矩阵，$a_{i,j}$表示有多少串以$i$开头以$j$结尾，且不是$s$的子序列但去掉最后一个字符$j$后是$s$的子序列。
区间合并：$a_{rt\ i,j}=a_{l\ i,k}*a_{r\ k,j}$，即$A_{rt}=A_l*A_r$。
$01$串：加一个不出现的字符$\#$，则$a_{0,\#}$即所有以$0$开头的子序列数。
反转：$a_{s\ 0,0}=a_{s'\ 1,1}$，$a_{s\ 0,1}=a_{s'\ 1,0}$，转置

标记：$(a_1,k_1) (a_2,k_2)$，修改：$\max(a_2,\max(a_1,x+k_1)+k_2)\to \max(a_2,a_1+k_2,x+k_1+k_2)\to \max(\max(a_2,a_1+k_2),k_1+k_2)$。
历史最值：$(a,k)$（因为形式为水平线+一条直线，称作上折线），表示值为$\max(a,x+k)$。
历史最值与当前最值合并：两条上折线合并仍是一条上折线，所以可以用$(a,k)$表示。

$*x\%k$：乘一个$x$模$k$会合并某几种数。对$k$给定情况，有约数个数种合并情况。维护约数个数个序列信息，可以发现乘某个数时这些序列可方便更新或由其它序列更新。

区间加减、开根：
先考虑修改区间是$[1,n]$，数据随机。
区间加减复杂度考虑相邻两项差的绝对值$|A_i-A_{i-1}|$的变化（可以差分然后只影响$O(1)$个点）。$\sqrt x-\sqrt y<\sqrt{(\sqrt x-\sqrt y)(\sqrt x+\sqrt y)}=\sqrt{x-y}$，即差在开根号，所以需$\log\log n$次变为$1$（$n^{\frac12}$）。
而$\lfloor\sqrt x\rfloor-\lfloor\sqrt y\rfloor$和$\sqrt x-\sqrt y$最多差$1$。

COGS. 2638. 数列操作(吉司机线段树)

$Description$
给定长为$n$数列，需支持区间$\text{or}$、$\text{and}$、求区间最大值。
$n,m\leq10^5$。
$Solution$
考虑更简单的情况：所有操作区间为$[1,n]$。
如果$\text{and},\text{or}$的值随机，那么几次之后所有数就全相同了。
如果不随机，至少在$\text{and}$中为$1$、$\text{or}$中为$0$的这些位都全相同了。
对于不同的二进制位直接对所有数求最大值。

若区间不为$[1,n]$，维护一个$same$表示某区间所有数都相同的那些位，以及区间最大值$mx$。
若当前修改 $\text{and}$中为$1$的位 或 $\text{or}$中为$0$的位 是当前节点$x$的$same[x]$的子集，就可以直接整体修改，而且就是对该区间所有$mx$加上 $改后的值-mx[x]$。直接打区间加减的$tag$修改$mx$即可。
所以，直接用吉司机线段树的写法，记$\text{and}$中为$1$的位 或 $\text{or}$中为$0$的位集为$s$，若当前区间是修改区间的子区间 且 s&same[x]=s，则$O(1)$进行区间加/减；否则递归子区间。
查询时可以直接查区间$mx$。

复杂度（🌿没好好听jls讲），应该也是$O(n\log^2n)$常表现为$O(n\log n)$的？
代码可以看这儿。

PS：关于暴力写法，涉及到两种$tag$，需要先定义标记的优先级（先下放哪个）。优先级低的标记修改直接改，优先级高的标记修改时，需要用优先级高（先下放）的修改一下优先级低的（后下放）的。
如区间加、乘，若先下放乘再加，则加操作时直接加，乘操作时加标记需要乘一下。

HDU.

http://acm.hdu.edu.cn/showproblem.php?pid=6089

Day6 最小乘积问题 斯特林数

最小乘积生成树： BZOJ2395
1.
平面上随机$n$个点，凸包上的点期望个数为$O(\log n)$。
$x$最小的点$A$和$y$最小的点$B$一定在下凸包上，且离凸包上两点形成线段最远的点一定也在凸包上。
所以需要求离$AB$最远的点$C$。化简距离公式，可以转成新图上的最小生成树。
然后再对$AC$、$BC$做同样算法（新图上生成树找到最远点即凸包上的点），
2.
某个线性加权下的最小生成树。
naive：将边权设为$ce_a+de_b+f$，只需考虑$e_a+de_b+f$（除以$c$）。
相对关系
变化时假设$e_1>e_2$变为$e_2<e_1$。若$e_1,e_2$均在树上，则MST不变；若$e_2$不在树上，则直接换掉$e_1$。

2求出的每个生成树一定是凸包上的生成树，即1是2的子集；1也是求一条过某点切线和其上面的部分点，2是枚举所有方向的切线和其上面的点，所有2是1的超集。所有1的复杂度一定小于2。

ps：需满足$a,b\geq 0$，否则是NPC的。（so最大乘积生成树没法做，不能取反边权）

线性无关集合 价值最大：BZOJ 2460
所有满足条件的集合$S$可以构成$n$个数上的拟阵（可证三个条件均满足）。

CC Oct
假设答案$t$已知，则$A$在以$B,C$为焦点的椭圆上（落在什么区域），椭圆是凸的-> 存在一条过最优点的切线，其它点都在其一侧-> 最小乘积问题
所以最小化$\sum x_i+ky_i$，$k$是任意实数，取最小的。
假设$k$固定，则可以证明能简单贪心从小到大取小于等于$k$个最小的$x_i+ky_i$，所以也只需要考虑相对关系，也能找到若干分界点，然后考虑分界点做。

杜爷题
加过的边有可能再加（不影响但会加）
$f_t$表示加$t$条边后集合$S_t$仍不连通的概率。