赛   道   修   建    赛道修建   赛道修建         D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description  给出一棵树, 在树上找出      m    m   m 条路径, 路径之间不互相覆盖, 求出 最小边最大 的方案        S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution  1. 主体思路 “最小边最大” 直接可以想到 二分答案 : 第一步, 二分 最小边权:      M  ...

S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution   建图过程: 交换操作 可以看作魔术球在 帽子序列 中的 移动, 使用每个魔术帽的 位置 为 编号 建图, 操作序列中的      a   ,   b    a, b   a,b 连两条 有向边, 分别为      a    a   a ->      b    b   b 和      a    a   a <-      b    b   b, 边权 为当前 操作序号  带有小球的帽子交换一次, 表示小球走过一条边, 设该边 编号 为      i  ...

S   o   l   u   t   i   o   n    \mathcal{Solution}   Solution  设当前砍到了第      2    2   2 个怪物, 则 代价 为      (    a   i    +   d   )   (    b   i    +   d   )   =    a   i     b   i    +    a   i    d   +   d    b   i    +    d   2    =    a   i     b   i    +   d   (    a   i    +    b   i    )   +    ...

感谢      L   B   X    LBX   LBX 赞助 链接       星   空    星空   星空  Description  链接 给出一列长度为      N    N   N 有      K    K   K 个位置未被点亮的灯泡, 允许反转      M    M   M 种不同长度, 问最少反转多少次使所有灯泡亮起 .   Solution  异或差分: 作用: 用来对      0   ,   1    0, 1   0,1 数列进行多次区间反转 具体步骤:  在原来      A    A   A 数组的基础上建立      B    B   B (异或差分...

T   i   n   y  <mtext>     </mtext>  C   o   u   n   t   i   n   g    Tiny\ \ \ Counting   Tiny   Counting   Description   样例输入: 4 1 4 3 2 样例输出: 3   Solution  对每个数字       S   i     S_i   Si​, 可以将其在二维平面上表示      ↓    ↓   ↓  如图得到       S   i     S_i   Si​ 与其他数字的 位置 与 值 的大小关系  第一象限 的数字与     ...

将   军   令    将军令   将军令   Description 链接    Solution 不断从深度最大的节点的     K    K   K级父节点进行扩展    Attention 注意 扩展 时使用      D   F   S    DFS   DFS, 因为      B   F   S    BFS   BFS 保存上一个经过的节点较麻烦 代码中有     B   F   S    BFS   BFS 函数, 仅供参考, 由于回环往复地入队,      T   L   E    TLE   TLE 不可避免,   Code #include<bits/stdc+...

入   阵   曲    入阵曲   入阵曲   Description 链接 给出      N   ∗   M    N*M   N∗M的矩阵, 矩阵中的每个数都是不超过      K    K   K 的正整数, 求有多少矩阵的和满足      m   o   d  <mtext>   </mtext>  K   =   0    mod\ K = 0   mod K=0    Solution      O   (    N   4    )    O(N^4)   O(N4)枚举矩阵人尽皆知, 就不说了   枚举行的上界和下界      O   (    N ...

#include<bits/stdc++.h> #define reg register int read(){ char c; int s = 0, flag = 1; while((c=getchar()) && !isdigit(c)) if(c == '-'){ flag = -1, c = getchar(); break ; } while(isdigit(c)) s = s*10 + c-'0', c = getchar(); return s * flag; } const int maxn = 10005; const int inf = 0x7f...

金   字   塔    金字塔   金字塔   Description  链接 虽然探索金字塔是极其老套的剧情，但是有一队探险家还是到了某金字塔脚下。经过多年的研究，科学家对这座金字塔的内部结构已经有所了解。首先，金字塔由若干房间组成，房间之间连有通道。如果把房间看作节点，通道看作边的话，整个金字塔呈现一个有根树结构，节点的子树之间有序，金字塔有唯一的一个入口通向树根。并且，每个房间的墙壁都涂有若干种颜色的一种。 探险队员打算进一步了解金字塔的结构，为此，他们使用了一种特殊设计的机器人。这种机器人会从入口进入金字塔，之后对金字塔进行深度优先遍历。机器人每进入一个房间（无论是第一次进入还是返回...

Hihocoder KMP  #include<bits/stdc++.h> #define reg register const int maxn = 1000005; char s[maxn], T[maxn]; int len_s, len_t, cnt, N; int nxt[maxn]; void Getnxt(){ nxt[0] = -1; int i = 0, t = -1; while(i < len_s) if(t == -1 || s[i] == s[t]) nxt[++ i] = ++ t; // "==" --> "...

Solution      O   (    N   2    )    O(N^2)   O(N2) 暴力自然不用说, 用手中石子去检查地上石子是否捡的起来, 若捡的起来就捡, 直到没有石子可以捡为止  正解: 分块  对于这种有多个属性的若干物品需要比较大小来检查合法不合法的问题, 可以尝试这个方法:  1. 整个数组排序 2. 分块 3. 块内排序 4. 暴力  于是先将地上石子按 距离 排序 分成      N     \sqrt{N}   N ​个 块, 每个 块 内按 质量排序 此时手中就有了 处理过后的整个数组, 每个块的包含的极值 (由于对每个小块排序乱了距离的单调性, 质量单...

区   间   最   优   覆   盖   问   题    区间最优覆盖问题   区间最优覆盖问题 Description 给出一个长度为      L   e   n    Len   Len 的区间      A    A   A, 再给出      N    N   N 个不同的区间 求      A    A   A 一次性最多覆盖多少区间, 并且输出该方案的     A    A   A左端点下标     Solution 首先舍弃那些长度比     L   e   n    Len   Len大的区间, 设每个区间左端点     L    L   L, 右端点     R  ...

Solution 因为B的防护罩开启 时间上的区间 已经确定, 所以只需要考虑A防护 时间上的区间 即可 因为只需考虑A受到的伤害, 所以开始时将所有可能对A造成伤害的导弹保存, 其余不管 现在手上就有了一个导弹序列, 那该怎么处理呢?  对于一个即将击中A的导弹, 想要拦截它, 必须使用防御区间覆盖其所有落在A的时间点 (由于导弹会反弹, 所以一个导弹可能会多次光临)  暂且称导弹到达A的时刻为危险时刻  可以使A的保护区间左端点从最早 危险时刻 至最晚 危险时刻遍历 每次计算该区间拦截成功的导弹伤害, 用总伤害减去减免伤害即为受到的伤害  此过程可以使用差分维护 具体分两种情况讨论  设该...

L   C   I   S    LCIS   LCIS   Description 链接 给出两个长度分别为     N   ,   M    N, M   N,M的数列, 求最长上升公共子序列的长度    Solution 设阶段为      i   ,   j    i, j   i,j 表示第一个串前     i    i   i个元素与第二个串前     j    j   j个元素      L   C   I   S    LCIS   LCIS 根据     L   C   S    LCS   LCS的转移方程, 初步得出 :       i   f   (    A   i ...