iOS
题解 CF1777D Score of a Tree
Score of a Tree 思维题。 我们考虑一个点 (u) 在所有时刻内的点权为多少。 可以发现，假如 (u) 的深度为 (0)，那么 (t) 时刻时它的权值为其子树内所有深度为 (t) 的点的初始权值异或和。 现在只考虑每个子树内相同深度的点集在 (2^n) 种情况中的贡献。 根据异或的性质可知，当且仅当点集内有奇数个 (1) 时才会造成贡献，而满足这种情况的方案数为 (sumlimits
【动态规划】动态规划基础、背包 dp 学习笔记
动态规划基础概念 动态规划（Dynamic Programming，dp）是一类用来解决最优化问题（和部分计数问题）的算法。动态规划的学习和题目从普及组到 IOI 都会出现。 动态规划可解问题的特点 如果一个问题可以通过动态规划求解，则这个问题一定（充分不必要）满足这两个特点： 最优子结构 动态规划可以解决的问题通常是求问题最优解的问题。且这种问题可被分割为多个子问题，子问题的解也是最优的。通过各
题解 P5339 [TJOI2019]唱、跳、rap和篮球
组合容斥问题。 定义 (operatorname{sum}(i)) 为至少有 (i) 组人会讨论的方案数。 那么最终答案就为 (sumlimits_{i=0}(-1)^itimes operatorname{sum}(i))。 在 (n) 个人中选 (m) 组人讨论的方案数为 (dbinom{n-3times m}{m})，相当于将 (m) 组 (4) 个人捆绑起来当成一个人来算。 接下来的 (n
题解 CF840C On the Bench
更好的阅读体验 这是一篇简洁易懂的良心题解，提供了多种做法。 对于两个数 (x,y)，定义 (x=n^2 cdot tx,y=m^2 cdot ty)。如果 (xcdot y) 为平方数，则说明 (tx=ty)。所以我们可以将每个数除去其平方因子，比较相邻两数是否相等即可。 F1： 定义 (f_{i,j,k}) 为插入 (i) 个数、有 (j) 对相邻相等的数、有 (k) 对相邻且与 (a_i)
题解 P8338 [AHOI2022] 排列
恶心题。 每次操作，相当与把第 (i) 个数置换到 (p_i)，于是可以连边。 因为 (i) 和 (p_i) 互不相同，所以对于每一个点，有且仅有一条出边和一条入边，即若干个简单环。 那么最少操作 (operatorname{lcm}(a_1,a_2,a_3...a_{x-2},a_{x-1},a_x)) 次点会都回到原位。其中 (a_i) 表示第 (i) 个环的大小。 交换两个点 (i,j) 相
题解 P3803 【模板】多项式乘法（FFT）
感觉题解区不是写的太高深，就是写的太高深。所以给初中、小学和幼儿园的萌新准备一篇简单易懂的良心题解~ 前置知识 一、多项式的系数表示法和点值表示法。(A(x)=sumlimits_{i=0}^{n-1}a_icdot x^i) 系数：((a_0,a_1,a_2...a_{n-2},a_{n-1}))。 点值：((x_0,y_0),(x_1,y_1)...(x_{n-1},y_{n-1}))。易证，
题解 CF41D Pawn
基础 DP 题。 定义 (f_{i,j,k}) 表示从第一行走到 ((i,j))，且数字总和模 (p) 等于 (k)。 转移方程为： [f_{i+1,j-1,(k+a_{i+1,j-1})bmod p}=max (f_{i,j,k}+a_{i+1,j-1}) ][f_{i+1,j+1,(k+a_{i+1,j+1})bmod p}=max(f_{i,j,k}+a_{i+1,j+1}) ]同时还需要定
题解 CF417D Cunning Gena
(mle 20)，状压 DP。 首先可以根据每个人的 (k) 从小到大排序。 定义 (f_{i,j}) 表示考虑到第 (i) 个人，完成了 (j) 状态的题目，不考虑显示器所需的最小价格。 转移显然为 (f_{i,j|s_i}=min(f_{i-1,j}+x_i))。 最终答案为 (ans=minlimits_{i=1}^{n}f_{i,S}+bcdot k_i)。 考虑到当前状态只与上一个有关，
题解 CF985E Pencils and Boxes
贪心+DP。 先从小到大排序。 定义 (f_i) 表示序列 ([1,i]) 能否分组。 转移为 (f_i|=f_j[a_i-a_jle d,jle i-k+1])。 右区间可以直接算出来，左区间可以二分或根据单调性弄个指针。 定义 (sum_i=sumlimits_{t=1}^{i}f_t)，前缀和减一下判断是否为正即可。 复杂度 (O(nlog n)) 或 (O(n))。 code:
题解 CF1338B Edge Weight Assignment
小清新思维题。 先找一个不是叶子的节点，令它为根。 那么当且仅当，对于每一个非叶子节点，它包含的叶子节点到它的异或路径相等时，才满足题目要求。 考虑第一问，显然如果每个叶子的深度奇偶性相同，可以全填一样的数字，答案为 (1)。反之为 (3)（可以在一条链上试一试）。 对于第二问，定义 (f_i) 表示子树 (i) 最多能填多少种边权，转移方程如下。 [f_{i}=left(sumlimits_{j
题解 CF799D Field expansion
有趣的 BFS 题。 首先发现，一个数最多乘 (2^{17}) 次后超过上限，所以我们可以考虑 BFS。 将 (a) 数组元素从大到小排序，定义 ((x,y,t)) 表示当前长为 (x)，宽为 (y)，操作了 (t) 次。每次操作将两个数中没超过上限的乘上 (a_i)。 由于可以旋转 (90degree)，把长宽交换一下再跑一遍。 复杂度 (O(2^{17}))。 code:
题解 CF9D How many trees?
经典 DP。 定义 (f_{i,j}) 表示 (i) 个节点，深度小于等于 (j) 的二叉树的个数。 则转移方程为： [f_{i,j}=sumlimits_{k=0}^{i-1}f_{k,j-1}cdot f_{i-k-1,j-1} ]最终答案为 (f_{n,n}-f_{n,h-1})。 复杂度 (O(n^3))。 code:
题解 CF1313D Happy New Year
带有小 trick 的 DP，长知识了。 (m) 很大，需要离散化。 为了方便，采用扫描线的方式，不对其进行实际意义上的离散，而是对于第 (i) 个区间 ([l,r])，插入 ((l,i),(r+1,-i)) 两个 pair，最后排个序。这样相邻两个 pair 之间的部分就缩成了一个点。 同时我们还发现 (kle 8)，也就是说经过每个点的区间个数不超过 (8)。于是在遍历每一个点的时候，我们记录
题解 CF213C Relay Race
考虑朴素 DP。定义 (f_{i,j,i2,j2}) 表示两个人分别在 ((i,j),(i2,j2)) 时获得的最大收益。复杂度 (O(n^4))，不行。 我们换种方法，定义 (f_{st,x,y}) 表示两人同时走了 (st) 步，分别向右走了 (x,y) 步。显然如果向右的步数确定了，向下的也确定了。 转移方程如下： [f_{st,x,y}=max(f_{st-1,x,y},f_{st-1,x
题解 CF930C Teodor is not a liar!
好题啊好题。 定义 (a_i) 为有多少个区间包含 (i)。 拍脑袋一想，当且仅当存在顺序的三个坐标 ((i,j,k)) 满足 (a_i>a_j) 且 (a_j<a_l) 时，可以确定没有数被所有区间包含。 这个结论很简单，因为如果存在，则 (a) 序列必定为一个“山峰”。而如果出现上面这种情况，说明有“山谷”。 所以我们可以用树状数组求出 (f_i) 表示以 (i) 结尾的最长不下降
题解 CF1265E Beautiful Mirrors
期望 DP。 定义 (f_i) 表示第 (i) 个镜子照成功的期望天数，(p_i) 为第 (i) 天成功的概率，(q_i) 为第 (i) 天失败的概率。 根据题意容易列出方程： [f_i=(f_{i-1}+1)cdot p_i+(f_{i-1}+1+f_i)cdot q_i ]移项得： [(1-q_i)cdot f_i=(f_{i-1}+1)cdot(p_i+q_i) ]同除以 ((1-q_i))
题解 CF156C Cipher
容易发现，如果把字母表映射到 ([1,26]) 上，那么无论怎么操作总和都不变。 于是可已将问题转化为：有多少种长度为 (n) 的序列，满足每个元素在 ([1,26]) 之间，总和为 (sum)。 定义 (f_{i,j}) 表示处理到第 (i) 个元素，总和为 (j) 的合法方案数。 转移方程为 (f_{i,j}=sumlimits_{k=1}^{26}f_{i-1,j-k})，其中 (f_{0,
题解 P6772 [NOI2020] 美食家
观察数据范围，(T) 很大，(n) 很小，用矩乘。 对于一条边 ((u,v,w))，我们将 (u) 拆成 (w-1) 个点，并连接 ((u_0,u_1,0),(u_1,u_2,0)...(u_{w-2},u_{w-1},0)) 和 ((u_{w-1},v_0,c_{v}))，总点数 (5n)。 将美食节按时间排序，相邻两个美食节之间用矩阵快速幂转移，然后再加上附加贡献，复杂度 (O((5n)^3c
题解 CF1202C You Are Given a WASD-string
不错的题，需要点思维和码力。 容易发现，左右和上下互不影响，可以分开处理，这里以左右举例。 定义向左走一格 (-1)，向右走一格 (+1)，求个前缀和找到最大值和最小值，和出现最值的最早时间与最晚时间。定义为 (l,r,l2,r2)。 只有当我们放了一个 A 或 D 使得所有最大值 (-1) 且最小值不变，或最小值 (+1) 且最大值不变时，面积才会减小。 假如我们要让最大值 (-1)，那么当且仅
题解 CF1106E Lunar New Year and Red Envelopes
小清新 DP 题。 定义 (f_{i,j}) 表示在时刻 (i)，干扰了 (j) 次，最小贡献。 定义 (nex_i) 表示在时刻 (i) 会收集哪个红包。 那么转移方程为： [f_{d_{nex_i}+1,j}=min(f_{i,j}+w_{nex_i}) ][f_{i+1,j+1}=min(f_{i,j}) ]其中，(f_{1,0}=0)，(ans=minlimits_{j=0}^{m}f_{
题解 CF900D Unusual Sequences
如果 (y) 不是 (x) 的倍数，答案为 (0)。 否则计算有多少种数列满足所有数 (gcd) 为 (1) 且和为 (frac{y}{x})。 定义 (f_i) 表示和为 (i) 且 (gcd) 为 (1) 的数列的数量。 显然有如下等式： [2^{x-1}=sumlimits_{dmid x}f_d ]其中 (2^{x-1}) 是和为 (x) 的数列的个数。 稍微转化一下为： [f_x=2^{
题解 CF1271E Common Number
找规律。 我们看有哪些数的 (path) 经过 (x)。 当 (x) 为奇数时，有：(x,2x,2x+1,4x,4x+1,4x+2,4x+3...) 当 (x) 为偶数时，有：(x,x+1,2x,2x+1,2x+2,2x+3,4x,4x+1...) 规律很明显，不解释。 因为当 (x) 为奇数和 (x) 为偶数时都分别具有单调性，所以可以做两次二分，再在 (O(log n)) 的复杂度内算出有多少
题解 CF840B Leha and another game about graph
构造题。 首先判断无解。每选一条边贡献两个度数，所以如果没有 (-1) 的点，且度数和为奇数，那么无解。 接下来考虑构造。我们考虑从图中扣下来一棵树（dfs 树），如果度数为奇数，令 (-1) 的点为根，否则随便选一个。 定义 (tp_i) 表示第 (i) 个节点是否需要与父亲连边，(0) 表示不用，(1) 表示用。然后对于当前点 (u)，向所有满足 (tp_v=1) 的儿子连边，容易证明这是正确
题解 P4074 [WC2013] 糖果公园
树上带修莫队。 带修莫队复杂度分析： 带修莫队比普通莫队多了一个时间戳，排序的时候先排左端点，再排右端点，如果左右端点所在块对应相等，则按时间戳排序。 设区间长度为 (n)，询问数为 (q)，修改数为 (c)，块长为 (B)。 我们分别考虑时间戳、左端点和右端点的移动次数。 时间戳：对于每一对块，时间戳都有可能从 (0) 变到 (c)，所以总次数为 (left(frac{n}{B}right)^2
题解 P7215 [JOISC2020] 首都
点分治。 考虑当前的分治重心的城市被完全联通。 这可以用队列接解决。每次放入一种城市，就把那些城镇的父亲加入队列，如果存在城镇不在当前分治重心的联通块内，那么说明必定存在另一个分治重心能算到它，直接退出即可。 剩下的和模板没有任何区别。 复杂度 (O(nlog n))。 code:
题解 P6329【模板】点分树 | 震波
点分树模板题。是个神奇的算法。 点分树就是将分治重心按照层级连边，每个节点父亲的联通块都包含了当前节点的联通块，且高度为 (log n)。可以解决不考虑树的形态的多次询问带修改的问题。 对于这道题，我们可以在点分树的每个节点上记录两棵树状数组，分别与当前节点距离为 (k) 的节点的权值和，以及与当前节点父亲距离为 (k) 的权值和。 这里的 LBT 要用 vector 存，空间复杂度 (O(nlo
题解 P3345 [ZJOI2015] 幻想乡战略游戏
点分树。 本题的核心问题在于不好直接确定补给站的位置。 但是仔细思考后我们发现，对于当前节点，如果存在一个儿子的答案比它优，那么补给站一定在那个儿子的子树中。 增量为 (wtimes(sum_u-2cdot sum_v))。当 (v) 优于 (u) 时，(2cdot sum_v>sum_u)。如果 (v_2) 也满足，则 (sum_v+sum_{v2}>sum_u)，不符合条件，所以一
浅析vue3中如何使用动态组件、如何快速理解Vue3的 toRaw和markRaw、ref与shallowRef、shallowReactive 区别
一、Vue3中使用 component :is 加载动态组件 1、不使用setup语法糖，这种方式和vue2差不多，is可以是个字符串 2、使用setup语法糖，这时候的is如果使用字符串就会加载不出来，得使用组件实例 3、问题：为什么 vue3 需要对引入的组件使用 markRow？ vue2中 is 是通过组件名称切换的，vue3中setup是通过组件实例切换的。直接把组件实例放到
决策单调性优化DP 学习笔记 & P4767 [IOI2000] 邮局 题解
0. 题面 题目描述 高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。 邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。 你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。 输入