Karashi

分类

树链剖分(2) 补题记(5) 题解(13)

/ 注册

TA的专栏 4篇文章 0人订阅

2022杭电多校题解（补题记）

4篇文章 467人学习

全部文章（共20篇）

北华大学第九届大学生程序设计竞赛-题解

北华大学第九届大学生程序设计竞赛-题解预估难度：ACM<GH<BD<LEI<KFJ （结果发现没人写L这个大模拟题） L题已经更新数据并重测，给部分补题的同学带来困扰实在抱歉（T-T） A-“北华”有几何签到题，输出“11”即可。 C-小杜的字符串题意：给定3个字符串，...

C++

2023-05-07

12 973

HDU多校4 来自专栏

HDU多校4 赛中5题（都是队友过的 1004 题意：给一个边长为n的大正三角形，由许多边长为1的小正三角形组成。在所有小三角形的每个顶点中填写0,1或2，满足大三角形的左侧不应出现0。大三角形的右侧不应出现1。大三角形的底侧不应出现2。对于每个小三角形，三个顶点的总和不应是3的倍数。询问是否可以填...

2022-08-07

0 466

HDU多校3 来自专栏

HDU多校3 赛中3题，菜… 1003 签到题，将每个单词压缩成大写的首字母 1012 题意：给定两个长度都为n的排列P、Q以及一个一开始为空的序列R，每次操作你可以从P或Q中弹出最左边的一个数字放入R的最右边。给定R，求有多少种操作方式能生成序列R。思路：动态规划，考虑R[i]是由P[j]还是Q...

2022-08-07

0 409

HDU多校2 来自专栏

HDU多校2 赛中五题，总结：签到、签到、枚举、枚举以及一道讨论到头大的线段树 1002 题意：去掉字符串中的“std::make_tuple”。思路：遇到's'直接i+=14即可。遍历输出。 #include<bits/stdc++.h> #define ll long long #...

2022-07-22

0 430

HDU多校1 来自专栏

HDU多校1 赛中过了四题，代码能力真的捞，都是一眼思路然后敲大半个小时…… 1011 题意：[0,1]随机生成n个数，然后m次操作，每次随机删除最小或最大的一个数，求最终剩下的数的和的期望。思路：众所周知，期望这东西应用在随机数上，那就是他的平均值，即0.5。m次操作后剩下(n-m)个数，那么它...

2022-07-22

0 467

题解 | 北华大学计算机程序设计算法提高训练营个人赛题解

北华大学计算机程序设计算法提高训练营个人赛 · 题解前言：由于实力有限，在命题方面可能尚有不足，望各位海涵。 A-签到题 B-签到题设二元一次方程组求解即可 C-签到题化简式子 ∑i=1n−1(ai+1−ai)=an−a1\sum_{i=1}^{n-1}(a_{i+1}-a_i)=a_n-a_...

2022-07-08

4 471

Subpermutation

Subpermutation 题意：将 n 的所有排列按字典序连接成一个新的序列，求在该序列中有多少连续子序列是 m 的排列。(1≤m≤n) (mod 1e9+7) 思路：很明显，m的排列要么出现在一个n的排列中，要么出现在连续的两个n排列中。分类讨论。 1. m的排列在一个n的排列中 1 至 ...

组合数学动态规划

2022-04-12

6 445

题解 | #好心情没了#

G-好心情没了（愚人节快乐，很明显，这篇题解是在愚人节的背景下赶出来的很明显，这题就是一个A题的hard版本，那么我们先回顾一下A题我们是怎么做的。 A题：愚人节是个令人开心的节日，所以小沙为了让大家开心，选择让大伙乐呵乐呵，如果你说的话让小沙开心了，小沙也会让你开心。我们可以发现，A题的题目...

2022-04-01

26 1236

树上行走

题7 - 树上行走最近做到的牛客挑战赛57的C题，我拿来分析一下题目要求两个操作：给定 x,y，令 x→y 的最短路上的点构成的点序列为 p，对于所有 i>1，令 b[ p[i] ] 增加 a[ p[i-1] ] 给定 x，输出 b[x] 的值。很明显的树链操作，对于 x ...

树链剖分

2022-02-24

1 607

小沙的身法

题6 - 小沙的身法寒假训练营2的一道题给定一棵树的路径关系，每个结点有一个高度，从低到高需要花费它俩高度之差的体力。有m个询问，每次询问从 x 到 y 结点需要花费多少体力（刚开始在地面，需要从地面上到结点x）。思路：因为没有修改操作，直接前缀和即可（ max(0,差值) 的前缀和）。做df...

树链剖分

2022-02-24

0 480