Lskkkno1

题解

/ 注册

全部文章 / 题解（共25篇）

题解 [牛客练习赛62 C] 牛牛染颜色

牛牛染颜色题目描述把树上一些染成黑色，满足任意两个黑色点的 lca 也被染成黑色了。求染色方案数对取模。正解考虑 dfs 的过程中：一个点的两个不同的子树内有节点被染色，这个节点就必须被染色。否则这个点它可以任意选择染色或者不染色。那么很容易设出状态表示一个点的子树...

2020-04-24

0 872

题解 [牛客练习赛62 B] 病毒扩散

病毒扩散题目描述题目讲的很清楚，这里就不加赘述了。正解考虑病毒扩散的组合意义，把它转化成从的方案数。一个点它在一秒内可以进行以下三种操作。不动（往上走（往右走至于这样为啥是对的，自己感性理解一下吧，直接讲也不太好讲。最后答案就是。 upd : 证明考虑暴力...

2020-04-24

4 1811

题解 [牛客练习赛62 A] 牛妹的游戏

牛妹的游戏题目描述给定一个无向图，问这个图中是否存在三元环，或者这个图的补图中是否存在三元环。正解三元环计数有一个很经典的根号分治的做法，这里不详细讲，网上博客讲得很清楚。补图的边是级别的，就不能三元环计数了，怎么办？由于边很多，随机三个点找到三元环的概率很大，直接随他大概次就...

2020-04-24

2 973

题解 [美团2018年CodeM大赛-复赛 A] 子序列

子序列题目描述给定一个序列，问有多少子序列满足。正解这种子序列里面元素不独立的题一般不好做，考虑如何将元素的值独立。现在和的值独立了，发现原问题就是求一个上升子序列个数。用树状数组单点加，区间求和可以做到。注意到并不是整数，但其实只要知道相对大小就行，即还需要离散化...

2020-04-23

1 950

题解 [美团2018年CodeM大赛-复赛 C] 边的染色

边的染色题目描述给定一个无向图，边权为 0 / 1。给定一些边的权，然后要你去把剩下的边权给定了。要求对于图中每一个环,边权异或和为 0。求方案数对 998'244'353 取模。正解先给出一个构造解的方法：将每一个点随便定一个点权，然后令边权等于两端点权异或和。这样一定是合法的，...

2020-04-22

2 963

题解 [牛客挑战赛39E] 牛牛与序列

牛牛与序列先口胡一下做法，明天再来补充一下吧。主要问题其实是求单调不降的序列个数。考虑把原序列转化成差分序列。然后就是一个插板的事情了。 #include <bits/stdc++.h> #define N 1000005 using namespace std; con...

2020-04-17

1 695

题解 [牛客挑战赛39B] 密码系统

密码系统题目描述给定一个长度为的环状字符串。将这个字符串划分成段，每段长度为，这个划分的代价为字典序最大的划分子段。求所有划分方案下，字典序最小的划分代价。题目太难描述了自己看题吧。正解环状字符串按照套路先倍长，然后枚举起始位置就能枚举到所有的划分了。现在问题就是如何快速...

2020-04-17

2 679

题解 [牛客挑战赛39D] 牛牛的数学题

牛牛的数学题题目描述辣鸡多项式板子题不配拥有描述。正解先来康康三道模板题。子集卷积多项式乘法快速沃尔什变换题目中那个一坨，其实相当于分别按顺序做上面的三个东西。这题真的很没有营养，会就会，不会怎么想都写不了。 #include <bits/stdc++.h>...

2020-04-17

3 865

题解 [牛客练习赛61D] 最短路变短了

最短路变短了题目描述给定一个有向带权图，每次询问将一条边反向会不会使的最短路变短。正解先以 1 号点为源点在正图跑最短路，第个点的距离记为。再以号点为源点在反图跑最短路，第个点的距离记为。设号边为有序三元组。（题目给定的）修改号边，最短路变短当且仅当。...

2020-04-10

7 955

题解 [牛客练习赛61E] 相似的子串

相似的子串题目描述给定一个字符串，询问出现次数大于等于的最长子串的长度（子串不相交）。正解二分 + 哈希。首先答案显然满足单调性。二分长度后，如何判断答案可行？设表示以为开头，长度为的子串，到为止，在不相交的情况下，最多出现了多少次。更新数组的时候有个比...

2020-04-10

5 830