Kur1su

题解

paper(8) 机器学习(2) 生活记录(6) 读书笔记(1)

/ 注册

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

2021牛客暑期多校训练营5 J. Jewels(KM模板) 来自专栏

Description 打捞个货物，货物会动，每一个时刻只能打捞一个，货物会动，打捞的代价是三维空间上的距离平方。 Solution 个货物只需要时刻就能全部打捞，对于每个货物在每一个时刻都有相应的代价，可以构建二分图，左边是时刻，右边是货物，做带权二分图的最优匹配（KM算法）即可。听说网...

2021-08-03

6 589

2021牛客暑期多校训练营6 F.Hamburger Steak 来自专栏

谨以本文纪念我两小时的青春，如有错误请指出~ Description 个汉堡，个锅，汉堡制作耗时，允许拆分时间，由制作得到。 Solution 首先思考最终需要多少时间? 思维误区：Max足够大时，需要时间 1 2 100 ans: 100 //虽然有两个锅，但是不能拆成[0, 50...

2021-08-02

14 996

2021牛客暑期多校训练营5 D.Double Strings (dp,组合数学) 来自专栏

Description 难以描述，看图： Solution 简单的来说就是在区间里找一个公共子序列在这个点后面的可以任意取。方案统计对于公共子序列部分，显然对于公共子序列可以做一次统计方案数, 令表示串遍历到，串遍历到时有多少个公共子序列，类似于最长公共子序列...

2021-07-31

8 981

2021牛客暑期多校训练营4 E.Tree Xor(dfs) 来自专栏

Description 给出一棵树，权值未知，但是给出每条边两个端点权值的异或值，求原来的权值。 Solution 假设权值，那么从它开始进行一遍赋值可以得到所有点当前的权值。当然不一定等于，假设，那么真实的。现在给出每个的范围满足，即，设，等式两边异或上得到，...

2021-07-28

16 979

牛客小白月赛36 部分题解

D.哥三好 Solution 容易想到用三维加记忆化搜索得到答案，但是，不能开这么大的数组，考虑如何压缩数据。注意到每次花费分别为，不难证明对花费和金额同时做乘法除法后与原问题等价，先分别乘2，此时花费为，金额，再同时除以100，花费变为，此时金额为。金额均满足，做朴素的记忆化搜...

2021-07-20

2 480

2021牛客暑期多校训练营2 K(树状数组、构造)

Description 有一个排列 , 令表示中满足的的个数，现在给出个不重复的和，问能否构造一个排列符合条件。 Solution (这个做法感觉比拓扑排序好理解)显然对于每一个，必须满足，那么对于未给出数值的，可以考虑先给它们填充上数值，不妨令，这样构造能够满...

2021-07-19

12 1415

牛客IOI周赛普及组27 D.旅游(floyd)

Description 给出一个有向图，提供两种操作：将当前点加入到最短路规划中计算当前点到的距离 Solution 数据范围满足，操作1最多只会执行次，考虑每次都使用进行的任意两点最短路径计算，总体时间复杂度，那么对于操作2，每次只需要判断并输出答案即可。注意到 ...

2021-07-04

6 603

牛客小白月赛35 部分题解

F. 连续非空子序列 Solution 很容易想到用前缀和并枚举端点解决该原题，即枚举其中，, 找到满足的即可。实际上就是找到前面满足的有多少个，设为。很容易想到二分这个用主席树验证，时间复杂度，由于无法通过，那么考虑用离散化后对值域开树状数组，每次求和找前面有多少个，...

2021-06-19

7 681

牛客IOI周赛26-提高组 A.逆序对题解

Solution 先统计出原序列的逆序对，这部分可以用树状数组/归并排序完成。随后我们只关心逆序对的奇偶性。对于三种操作分别考虑：操作1，交换两个数字，逆序对的奇偶性改变。操作2，翻转序列，设当前的逆序对为 , 翻转后为，长度为，考虑到翻转前后序列的逆序对满足，如果是偶数，必为两奇或两偶...

2021-06-07

3 638

牛客IOI周赛普及组26 题解

A. 平行四边形 Solution 平行四边形判定法则：有一组边平行且长度相等，注意要先检测有没有三点共线的存在。三点共线可以用三点组成的三角形面积来计算，如果面积是说明三点共线。剩下的就是枚举点了，我用了一个全排列暴力枚举。 Code https://ac.nowcoder.com/acm...

2021-06-05

3 672