• avatar f_zyj(赵闲) 2021-05-21 20:11:40

    51Nod-1244-莫比乌斯函数之和

    ACM模版 描述 题解 先来分析题,设 f(n)=∑ni=1μ(i) ,那么 ans=f(b)−f(a−1) 。 接下来我们来说莫比乌斯函数,在《具体数学》中对莫比乌斯的性质讲述的十分详细,其中有一个是 ∑d|nμ(d)=[n=1] 所以呢,对于我们所需要求

  • avatar f_zyj(赵闲) 2021-05-21 20:12:01

    51Nod-1685-第K大区间2

    ACM模版 描述 题解 二分 + 树状数组。 二分枚举答案,判断中位数大于等于当前答案的个数是否足够 k 个,至于怎么判断,我们需要借助树状数组。首先我们可以通过前缀的方法获取前 i 个数字有几个大于 m 的,这里的 m 是我们枚举的答案,

  • avatar f_zyj(赵闲) 2021-05-21 20:12:23

    51Nod-1597-有限背包计数问题

    ACM模版 描述 题解 我想,这个出题人一定是一个很淘气的人……这时限和被模数(姑且这么叫)真的很有趣。 这个题我不是特别会做,找了大牛的题解看了看,感觉十分详细,分享给大家,我就不多说什么了……我要去看母函数了。 mrazer’s blog,该大佬十分幽默,但是也很细心,从他的博客中

  • avatar f_zyj(赵闲) 2021-05-21 20:13:05

    51Nod-1295-XOR key

    ACM模版 描述 题解 第一次知道原来可持久化并不只是主席树的专利…… Tire 也可以持久化操作……学习了。原谅我对可持久化理解的不够深刻,目前还只是套套模版的样子……至于为什么要用 Tire 倒是十分容易理解,这种求 Xor 最大的题,需要从高位贪心处理,尽量找高位不同的

  • avatar f_zyj(赵闲) 2021-05-21 20:13:28

    51Nod-1693-水群

    ACM模版 描述 题解 这个题真的很神很神的…… 我先说一下这个题怎么解:这个题可以转化为图论,将 i 与 i−1 连边,非要为 1 ,再将 i 与 i∗k 连边,费用为 k ,然后跑一遍最短路。但是因为边数略多,我们需要优化一下,边数

  • avatar f_zyj(赵闲) 2021-05-21 20:13:49

    51Nod-1515-明辨是非

    ACM模版 描述 题解 这里主要涉及到相等和不相等以及不确定关系三种,初始化全部是不确定关系,通过 n 组操作对其进行修改,所有有效操作( YES )都会改变其不确定性关系,那么我们可以通过两种数据结构来表示这关系,相等的关系很容易想到,就是并查集,相等的我们并入一个并

  • avatar f_zyj(赵闲) 2021-05-21 20:14:12

    51Nod-1228-序列求和

    ACM模版 描述 题解 很想要轻描淡写的告诉大家,在《具体数学》一书第六章第五节有“伯努利数”的详细讲解,但是感觉这又有些长篇大论讲得着实不错,但是对于第一次接触伯努利数并且数学不是特别好的人来说,实在是有些难以接受,于是我选择更加简单的,直接用结论吧。 这里很明显的用到了伯努利数,那么

  • avatar f_zyj(赵闲) 2021-05-21 20:14:35

    HDU-2017 多校训练赛6-补题

    ACM模版 话说昨天因为前天生病了而去医院看了病,所以多校训练赛 5 5 我都没有补题,现在又多校训练赛 6 6 也结束了,看来这个周末要好好干了……现在算是明白了,刘春英老师几乎场场比赛都要说的这场比赛有很好地区分度是说给谁

  • avatar f_zyj(赵闲) 2021-05-21 20:14:56

    HDU-2017 多校训练赛6-1011-Classes

    ACM模版 描述 题解 最基础的容斥,但是一开始没有读懂题,看了半天没有看懂题意……后来仔细看了 Hint 才明白原来就是一个容斥,按照 Hint 的提示求出来各个部分的值是多少即可,比如说,只报了 A 课程的人数一定是 A−AB−AC+ABC ,其他都是同理

  • avatar f_zyj(赵闲) 2021-05-21 20:15:18

    HDU-2017 多校训练赛6-1008-Kirinriki

    ACM模版 描述 题解 这个题要难为死我了,搞半天也不知道怎么做…… 首先我们可以假设 A 一定在 B 左边,然后我们可以考虑 A 的尾部和 B 的起点,如果暂时不考虑长度不固定,我们每次查找都让长度尽可能长,那么,我们一定需要将 A

  • avatar f_zyj(赵闲) 2021-05-21 20:15:40

    HDU-2017 多校训练赛6-1003-Inversion

    ACM模版 描述 题解 这个题实际上就是一个排序,然后暴力查找就好了,复杂度看似高,其实最坏情况下的复杂度为: nlogn+n/2+n/3+n/4+…+n/n ,也就是 nlogn 。 然而一开始我将这个题想难了……以为是一个线段树求区间最值的题……折腾好久。 代码 #includ

  • avatar f_zyj(赵闲) 2021-05-21 20:16:03

    51Nod-1363-最小公倍数之和

    ACM模版 描述 题解 每次做到数论题我就头疼……实在是不知道怎么办了……给大家推荐一个不错的题解吧,数论实在是我的一个致命弱点。 >>>dance_in_the_dark<<< 的博客,大佬公式给的十分清晰,可以好好看看,我发现现在我的思维越来越死了

  • avatar f_zyj(赵闲) 2021-05-21 20:16:25

    51Nod-1188-最大公约数之和 V2

    ACM模版 描述 题解 题目要求所有小于等于 N 的两两之间的最大公约数的和,如果我们直接这么考虑两者之间的关系其实并不好想,我们可以先固定一个来考虑。如果我们求 [1,n] 与 m 的 GCD 的和是多少呢? 设 GCD(m,i)==x

  • avatar f_zyj(赵闲) 2021-05-21 20:16:47

    HDU-2017 多校训练赛5-补题

    ACM模版 我发现,多校是越来越不能打了……太 bug b u g 了,一场比一场难,这场又是只 A A 了三道题,啥也做不了了,一场看热闹的娱乐局。 1006-Rikka with Graph >>>图论<<< 实际上就是一个找找规律的构造题。

  • avatar f_zyj(赵闲) 2021-05-21 20:17:08

    HDU-2017 多校训练赛5-1008-Rikka with Subset

    ACM模版 描述 题解 这个题很明显是 dp ,我们从小到大枚举 i ,进行判断我们需要加几个 i ,用 dp 来维护此时我们能够凑到多少个 i ,不够的我们就只能直接添加数 i ,因为我们是从小到大枚举的,如果添加小的数不合适,会改变前边的结

  • avatar f_zyj(赵闲) 2021-05-21 20:17:30

    HDU-2017 多校训练赛5-1006-Rikka with Graph

    ACM模版 描述 题解 这个题看着很复杂,代码却是十分简单,直接看代码吧,不是特别难。几个判断就能搞定了…… 代码 #include <iostream> using namespace std; typedef long long ll; ll n, m; int

  • avatar f_zyj(赵闲) 2021-05-21 20:17:51

    2017"百度之星"程序设计大赛-资格赛

    ACM模版 忙里偷闲的写了几道题,这两天好忙啊……只过一道题就能通过资格赛,所以并没有什么签到题……但是的确有的题被我想难了~~~ 1002-度度熊的王国战略 >>>并查集<<< 很简单的一道图论。 1003-度度熊与邪恶大魔王 >>>

  • avatar f_zyj(赵闲) 2021-05-21 20:18:12

    2017"百度之星"程序设计大赛-资格赛-1004-度度熊的午饭时光

    ACM模版 描述 题解 我真想吐槽这次比赛出题人是多么的糙,题意难以理解也就算了,还有错别字……有强迫症的我十分痛苦。 反正又是一个 dp ,有些像 01 背包,看看代码吧,没啥太大区别。虽然也有那么一丢丢的差别,主要是要记录一下哪些选取了而已。 代码 #include <

  • avatar f_zyj(赵闲) 2021-05-21 20:18:34

    2017"百度之星"程序设计大赛-资格赛-1003-度度熊与邪恶大魔王

    ACM模版 描述 题解 就是 dp ,处理出来对于所有伤害和防御的最优代价。因为防御是有限的,范围十分小,所以这个部分十分好干,根本不用担心超时问题,具体的看代码吧,应该说是很好理解了。这也是 AC 人数最多的一个题了。没有之一。 代码 #include <iostream

  • avatar f_zyj(赵闲) 2021-05-21 20:18:57

    2017"百度之星"程序设计大赛-资格赛-1002-度度熊的王国战略

    ACM模版 描述 题解 其实这个题简单的有些让人不敢写,因为资格赛应该是没有签到题的……一直怀疑自己是不是读错题了,或者没有搞懂它真正的意图。 其实就是判断一下连通性,一个并查集就好了,如果一开始就没有联通,那么结果就是 0 ,如果是连通的,我们只消的将某一个点删掉即可,这个点是哪个呢

  • avatar f_zyj(赵闲) 2021-05-21 20:19:18

    51Nod-1175-区间中第K大的数

    ACM模版 描述 题解 遇见这种题,果断直接套模版,主席树,也就是可持久化线段树。 这里需要说一下,由于比较懒,我的模版求得是第 K 小,并且下标是从 0∼n ,所以呢,我直接在输出时下标偏移了一,并且对 k 稍加修饰,变成了求第 r−l+2−k 小的数,效果是

  • avatar f_zyj(赵闲) 2021-05-21 20:19:42

    HDU-2017 多校训练赛2-1008-To my boyfriend

    ACM模版 描述 题解 给定一个矩阵,求任选一个子矩阵的所拥有的不同颜色的期望个数。大致就是这么个意思。这里我们换位思考,可以考虑为求每一种颜色的贡献次数,也就是每一个颜色所出现的产生贡献的子矩阵个数。最后将所有颜色的贡献之和除以所有的子矩阵数目就是结果。 至于怎么求贡献,可以去参考一下

  • avatar f_zyj(赵闲) 2021-05-21 20:20:03

    51Nod-1029-大数除法

    ACM模版 描述 题解 这种题除了用 java(代码 One) 外,我就只会套模版(代码 Two)了,写起来贼累,当然,模版出奇迹! 代码 One: import java.math.BigInteger; import java.util.Scanner; public clas

  • avatar f_zyj(赵闲) 2021-05-21 20:20:24

    HDU-2017 多校训练赛4-1007-Matching In Multiplication

    ACM模版 描述 题解 这是我做过的为数不多的二分图的问题中最有趣的一道了,首先确定的是左边的点和右边的点集数目是一样的,另外,我们确定左边的每个点向右边的点伸出两条路,那么,我们可以知悉,左边的点的度全部为 2 ,因为至少有一个完美匹配,所以右边的点度数全部大于等于 1

  • avatar f_zyj(赵闲) 2021-05-21 20:20:47

    HDU-2017 多校训练赛4-1012-Wavel Sequence

    ACM模版 描述 题解 这个题貌似 dp+线段树 维护也能做,但是纯 dp 解需要的优化就巧妙得很了……看了官方题解和 std 后的感觉就是——还有这种操作.jpg 很有趣的优化手段,我肯定想不起来……对了,大致说一下题意:给定两个序列,求有多少种子序列满足两个对应位置值相等

  • avatar f_zyj(赵闲) 2021-05-21 20:21:10

    七月小记

    话说,七月份的任务是把 51Nod 的五级题干完,可是七月结束了我却依然没有干完,终于,在今天,逾期了四天给弄完了……(因为是昨天晚上十一点半搞定) 留张图纪念一下吧~~~ 依稀记得,我第一次接触 51Nod 是在去年三月份底,然后开始爱上了这个 OJ ,把自己的主要刷题阵地移到了

  • avatar f_zyj(赵闲) 2021-05-21 20:21:32

    51Nod-1610-路径计数

    ACM模版 描述 题解 这个题我不会写,看了题解也不怎么会,先 mark 一下吧,给大家提供一下官方题解和一份看起来还不错的代码吧……(╯﹏╰)难受。 我的数学比较差,容斥玩得不是特别好,玩不转,这个 dp 过程大致理解,可是修改操作部分不是特别懂……看了好久也没有理清楚头绪

  • avatar f_zyj(赵闲) 2021-05-21 20:21:53

    51Nod-1811-联通分量计数

    ACM模版 描述 题解 感觉这个题好难啊,虽然知道是要求每条边的贡献,但是完全不知道具体怎么搞,花了 5 盾看了题解…… 虽说是思路上理解了,但是后边的 启发式合并 + 数据结构来维护子树 还是一脸懵逼,于是一狠心,又花了 60 盾看了大牛们的代码……好吧,我

  • avatar f_zyj(赵闲) 2021-05-21 20:22:18

    HDU-2017 多校训练赛4-1004-Dirt Ratio

    ACM模版 描述 题解 十分巧妙的题,只是好考验英语水平啊…… 给定一个序列,求所有区间中的 不同数字的个数 / 区间长度 的最小值。 这里用得是二分答案,线段树维护区间最小即可。 官方题解: 代码 #include <cstdio> #include <i

  • avatar f_zyj(赵闲) 2021-05-21 20:22:40

    51Nod-1480-打广告

    ACM模版 描述 题解 贪心,没什么难的,就是尽可能的匹配到覆盖率高的区间。先对广告进行排序,按照左端点从小到大,右端点从大到小的主次关系来排序,这时,排好的序列中右端点的图像是锯齿形的,我们只取一个单调递增的子序列进行匹配,因为这样我们就能匹配到最大的区间。然后呢,我们根据每一个频道的需

  • avatar f_zyj(赵闲) 2021-05-21 20:23:02

    51Nod-1859-Clarke and number

    ACM模版 描述 题解 这个题,简单的来,就是暴力打表找规律,注意一点, sqrt() 可能存在精度问题,最好自己写一个二分的,因为这个, WA 了四回…… 官方题解也给大家分享一下,写得挺详细的: 代码 #include <cstdio> using name

  • avatar f_zyj(赵闲) 2021-05-21 20:23:24

    51Nod-1582-n叉树

    ACM模版 描述 题解 dp + 矩阵快速幂,复杂度 (d3ilog(x)) ,完全是可行的。 状态转移过程十分好想,没什么可说的,因为 x <script id="MathJax-Element-37" type="math/tex"&

  • avatar f_zyj(赵闲) 2021-05-21 20:23:46

    HDU-2017 多校训练赛4-补题

    ACM模版 这次多校训练赛好难啊,应该是目前最难的一场吧……因为刘老师在比赛后两小时左右就说,服务器压力不大,可以开放题库了……这不是在说,之后可能提交的人数会很少了……感觉老师在骗我们,明明说好的区分度呢?在两点时,榜单第 137A 137 A 了两道,可怕的是 660 660 同样

  • avatar f_zyj(赵闲) 2021-05-21 20:24:09

    HDU-2017 多校训练赛4-1003-Counting Divisors

    ACM模版 描述 题解 话说,这场比赛我只做了三道题,而只有这道题有点收获……其他俩题好水。 首先,我们针对每一个 i 考虑他的因子个数,我们知道 i 可以表示为 px11∗px22∗px33∗…∗pxnn 的形式,最后因子个数为 (x1+1)∗(x2+1)

  • avatar f_zyj(赵闲) 2021-05-21 20:24:30

    HDU-2017 多校训练赛3-1004-Kanade's trio

    ACM模版 描述 题解 这个题思路十分巧妙,没想到竟然可以用字母树解。 题解不难理解,就是有些出人意料了。看了题解后,我拿着官方题解,参考着写了一份,习惯性的将一些东西改成了自己的习惯……比如说,初始化能用 memset() 的都用 memset() ,然后我就超时了……,很纳

  • avatar f_zyj(赵闲) 2021-05-21 20:24:52

    HDU-2017 多校训练赛3-1005-RXD and dividing

    ACM模版 描述 题解 这个题没有做出来我只承认我英语不好,被斯坦纳树给唬住了……没有读懂这个题真正的意图。 实际上就是给定一个树,让你将树划分为多份,然后每份内部的连通花费是固定的,求所有划分块儿的内部连通花费的和的最大值……这不就是一个求每条边贡献的吗?一个搜索就能搞定的事儿……╮(

  • avatar f_zyj(赵闲) 2021-05-21 20:25:14

    HDU-2017 多校训练赛3-1003-Kanade’s sum

    ACM模版 描述 题解 我的意中人是个盖世英雄,有一天他会踩着七色的云彩来娶我,我猜中了开头,可是我猜不着这结局…… 这个题我也是猜中了开头,却没有猜中结尾…… 首先,很明显的一个条件是,人家要求所有子区间的第 k 大的值的和,那么,很明显我们不能求所有子区间,我们必须求每个值的贡

  • avatar f_zyj(赵闲) 2021-05-21 20:25:35

    51Nod-1469-淋漓尽致子串

    ACM模版 描述 题解 这个题用后缀自动机和后缀数组都可以干,官方题解说的是后缀自动机。 我用的是后缀数组, DA 算法,根据求出来的 height[] 的曲线来判定合法的数目,具体的算法思路可以看看 getupdown 的博客,说的挺详细的,这也是我写这个题所参考的博客,赞一

  • avatar f_zyj(赵闲) 2021-05-21 20:25:57

    51Nod-1747-近似多项式

    ACM模版 描述 题解 高斯消元……头疼。最烦数学题…… 官方题解: 代码 #include <stdio.h> #include <algorithm> using namespace std; typedef long long ll; cons

  • avatar f_zyj(赵闲) 2021-05-21 20:26:20

    GoldenDream-八月

    八月来的太快,但是依然感觉暑假好漫长啊…… 七月份,并没有像想象中那般稳定平和,还是有些躁动,躁动的原因多种多样,甚至有些稀奇古怪,各种不顺心,各种不自在。 虽然知道很多事情并不会一帆风顺,但是,当事情发生时,我还是很难过。 上个月,发生了一件让我由内而外无力的一件事,就在月底,我的车子丢了,

  • avatar f_zyj(赵闲) 2021-05-21 20:26:40

    HDU-2017 多校训练赛3-补题

    ACM模版 最近打得三场多校,一场比一场差劲,真让人难受……今天的比赛感觉好坑,不管是不是数学题,都要弄一堆公式在题面,搞得我这数学挂科的笨蛋心累……不知缘何,无法访问官网,看得题也是朋友给我截图发来的,本来就英语差,这下子没法求助百度翻译了,好多题一看不懂就跳过了……最后,比赛只过了两道题,水了

  • avatar f_zyj(赵闲) 2021-05-21 20:27:02

    HDU-2017 多校训练赛3-1008-RXD and math

    ACM模版 描述 题解 拿到这个题开始分析,首先莫比乌斯函数平方后就全部是 0 和 1 ,然后,就没有然后了,我分析不下去了…… 后来看看样例,感觉和 MOD 十分接近,而 1010 刚好约为 MOD 的近十倍,所以强行猜一波,直接快速幂求 nk ,然

  • avatar f_zyj(赵闲) 2021-05-21 20:27:24

    51Nod-1969-Fire!

    ACM模版 描述 题解 数论题,直接调用结论……要是想知道怎么证明,建议去看看那本叫做《初等数论及其应用》第七章部分讲有详细的推论与证明。 至于结论嘛,在题解中说的十分清楚了,贴出来大家看看吧……最讨厌这种题了……对我这样的数学渣滓来说,要命的。 P.s. 这尼玛都是神马玩意儿啊…

  • avatar f_zyj(赵闲) 2021-05-21 20:28:07

    51Nod-1581-摆放骨牌

    ACM模版 描述 题解 之前做的覆盖问题,好像总是 dp ,这次没想到竟然是二分图完美匹配是否唯一。 我学姐的博客对这个题的解释很详细,我感觉凡是我学姐写过的题解,我就没有必要写了,因为我写的题解,任何人都能写出来,可是我学姐写的题解,那可真是精品,详细的令人发指,她不写,应该没有

  • avatar 俞越201811161904122 2021-05-21 20:28:19

    Notes

    计数技巧: (转化计数对象)注意到一个树上连通块满足|V| − |E| = 1 ,而空集满足 |V| − |E| = 0 。所以只需要用合法的点数减去合法的边数即可。bool化int。 权值化组合意义(如:枚举点集 etc.) 差分(>=<=x)(好处:化01,etc.) 考虑贪心策略

  • avatar f_zyj(赵闲) 2021-05-21 20:28:29

    51Nod-1552-白兰地定位系统

    ACM模版 描述 题解 自觉这个题出得十分糟糕,糟糕透了……我到现在也没有弄懂这个题意……到底是始终从 1 到 n 间来回走呢?还是从系统给的点之间来回走?也就是说,起点和终点默认为 1 和 n 了吗? 我找了一下大神们的代码,表示没有

  • avatar f_zyj(赵闲) 2021-05-21 20:28:52

    51Nod-1619-完全二叉树的方差

    ACM模版 描述 题解 这个题的官方题解是我见过最详细的官方题解了……简单的说,这个题就是贪心 + 枚举。 官方题解: 代码 #include <cstdio> #include <algorithm> #define ll long long

  • avatar f_zyj(赵闲) 2021-05-21 20:29:16

    51Nod-1595-回文度

    ACM模版 描述 题解 先吐槽一下,这个题目搬运工可不走心啊……翻译的有问题,还是看了讨论区才知道题意有问题…… 这个题要你求所有前缀回文度的和,这个不难想到,在 macacher 算法中求出来的一个数组中,表示着以某个位置为轴心的回文半径,那么我们完全可以通过这个来判定某一个前缀是

  • avatar f_zyj(赵闲) 2021-05-21 20:29:38

    51Nod-1791-合法括号子段

    ACM模版 描述 题解 这里,我们需要明确区分一个定义,什么叫做子段?什么叫做子序列?子段是子序列的一种,也叫做连续子序列,而子序列呢?如果不要求连续,则是可以从原序列中任意取,但是要保持原先的先后顺序即可。 一开始,并没有仔细区分这个概念,搞得有些手足无措,后来想通了,就是一个简单的分

  • avatar f_zyj(赵闲) 2021-05-21 20:29:59

    51Nod-1800-汉诺塔

    ACM模版 描述 题解 看到一个十分清新脱俗的代码,很强势,有趣得很…… 代码 #include <cstdio> #include <cstring> #include <iostream> using namespace std; con

  • avatar f_zyj(赵闲) 2021-05-21 20:30:21

    HDU-2017 多校训练赛2-1006-Funny Function

    ACM模版 描述 题解 哎,这个题比赛时要是大胆的打表试试也许可以发现一些规律……看到数学公式推导题我就犯怵……这样子不好╮(╯﹏╰)╭不好。 刚拿到这个题时,我认为这个题是类似于斐波那契数列的矩阵求解那样,但是我矩阵好菜的,不会构造单位矩阵,故卒。后来发现这个题除了这种思路,还能找到一

  • avatar f_zyj(赵闲) 2021-05-21 20:30:44

    深夜狂想曲

    说起最美丽的音乐,大概只有那从生活中来又回生活中去的那些了吧…… 最近几日,天气转好,没有往常那么炎热了,我也不用经常去网吧避暑了,凌晨三四点时,总是会下起一些小雨,也是极好的,但是都是雷阵雨,所以时间都不久。 今天晚上,额,不对,其实应该说是从昨天晚上开始,总是感觉有话想说,有些许激动,也有些

  • avatar f_zyj(赵闲) 2021-05-21 20:31:04

    51Nod-1571-最近等对

    ACM模版 描述 题解 挺常见的一种线段树问题,首先对 a[] 进行离散化,然后询问离线处理,处理时需要根据右区间进行排序,然后不断维护左区间就好了……每次添加离散化后的 a[i] 时都要处理完询问中右区间端点为 i <script type="math/tex&

  • avatar f_zyj(赵闲) 2021-05-21 20:31:26

    51Nod-1540-俄罗斯赌轮盘

    ACM模版 描述 题解 这个题,放在五级题有些过了,撑死了三级题难道,如果放在三级题,我想过的人会更多,放在五级题让人高估了它!!! 其实就是一个贪心,我们想要挂的几率最低,实际上就是尽量隔一个放一个,所以也就是说,点都尽量放在前边,而 X 尽量往后隔一个放一个,如果说,我们放不下怎

  • avatar f_zyj(赵闲) 2021-05-21 20:31:48

    51Nod-1810-连续区间

    ACM模版 描述 题解 这个题需要用到分治的思想,最最最重要的一个问题是,合法的连续区间有什么充要条件?这个不难想,某一个区间的最大值和最小值的差加一一定是这个区间的元素个数时才是合法的,因为题中说了,这是 1∼n 的排列,所以不存在重复,而每个相邻的又刚好差 1 <scrip

  • avatar f_zyj(赵闲) 2021-05-21 20:32:10

    51Nod-1679-连通率

    ACM模版 描述 题解 很明显的树归问题,但是状态如何转移帮不好想,第一次见到这个题是我刚开始做 51Nod 时候的一场算法马拉松,很明显,那时候我并不会做,也不知道什么叫做树归,就一直没有再碰过了。今天看到这个题忽然想起来了,但是依然不知道具体怎么转移,先给一下官方题解吧……

  • avatar f_zyj(赵闲) 2021-05-21 20:32:32

    HDU-2017 多校训练赛2-补题

    ACM模版 说什么好呢,我今天才发现,我的网络可能有问题,导致我总是丢包,提交代码时总是莫名其妙的 CE C E ,第一场和第二场我 CE C E 的次数大概有那么二十次左右吧……明明该加的东西都加全了,也没有命名冲突问题啊,反正能想到的问题都试了,就是无限 CE C E ,一度让我

  • avatar f_zyj(赵闲) 2021-05-21 20:32:53

    HDU-2017 多校训练赛2-1001-Is Derek lying?

    ACM模版 描述 题解 这个题的官方题解写的十分繁琐,感觉并没有他的解法那么麻烦,其实就是一个物理中常用的思维——极值考虑法,将各种情况考虑到最极端,只要最极端没问题,那么非极端的就更没有问题,反之,亦然。所以,只要考虑完全几种极值就好了,不难理解,看代码吧~~~ 代码 #includ

  • avatar f_zyj(赵闲) 2021-05-21 20:33:16

    51Nod-1530-稳定方块

    ACM模版 描述 题解 很巧妙的利用两个堆来搞事情,一个大顶堆,一个小顶堆,就是优先队列,维护每次能够拆除的方块儿,每拆除一个向周围扩展一次,并且删除拆掉的这个方块儿,这里用 map 处理。说白了,就是一个有趣的贪心问题,用到两种数据结构罢了, STL …… 代码 #includ

  • avatar f_zyj(赵闲) 2021-05-21 20:33:38

    HDU-2017 多校训练赛2-1011-Regular polygon

    ACM模版 描述 题解 都怪我英语不好,更怪百度翻译个信球,硬生生将正方形给我翻译成了正多边形,导致一上来我就写了一个 搜索 + 凸包 + 判边……后来才发现,我读错题了!!! 这个题需要用到二维平面 HASH 解决,之所以要用到 HASH 是因为我们只需要枚举两个点构成的一条边

  • avatar f_zyj(赵闲) 2021-05-21 20:34:00

    HDU-2017 多校训练赛2-1003-Maximum Sequence

    ACM模版 描述 题解 这个题实际上就是一个尺取法,贪心控制左区间端点,右区间端点每次加一,右区间移动需要添加数据,左区间端点移动需要删除数据,就这样,我采用了多重集合搞,但是一开始一直 CE ,后来发现我这里提交代码十次九次都要 CE ,大概是丢包了吧,然后终于提交上了却 WA

  • avatar f_zyj(赵闲) 2021-05-21 20:34:22

    HDU-2017 多校训练赛2-1009-TrickGCD

    ACM模版 描述 题解 说到怎么做,就是一个莫比乌斯搞的容斥,我一开始竟然想成了 dp ,也是可笑了…… 想看具体的题解,可以去看看我学姐的题解报告,真是很详细的。 >>>佐理慧的 blog<<< 代码 #include <iostrea

  • avatar f_zyj(赵闲) 2021-05-21 20:34:43

    HDU-2017 多校训练赛1-1008-Hints of sd0061

    ACM模版 描述 题解 做这个题真是长见识了,由于序列比较大并且需要生成序列,所以直接快排时间会超,那么怎么做呢?自然是寻求近似线性复杂度的解法了。 官方题解是这么说的: 最慢的情况是 $b$ 的取值为 $0, 1, 2, 3, 5, 8, …$ 的情况,但事实上也只有 $\math

  • avatar f_zyj(赵闲) 2021-05-21 20:35:05

    HDU-2017 多校训练赛1-1003-Colorful Tree

    ACM模版 描述 题解 其实这就是一道树归题而已,比赛时就知道,但是时间不够写了……给一下官方题解吧~~~ 单独考虑每一种颜色,答案就是对于每种颜色至少经过一次这种的路径条数之和。 反过来思考只需要求有多少条路径没有经过这种颜色即可。 直接做可以采用虚树的思想(不用真正建出来), 对每种

  • avatar f_zyj(赵闲) 2021-05-21 20:35:29

    51Nod-1593-公园晨跑

    ACM模版 描述 题解 十分有趣的一个问题,用到线段树了…… 我学姐写这个题解十分的详细,我想我一定不会写的更详细,所以直接给大家一个我学姐的博客吧,可以去哪儿看一下题解……但是学姐的线段树写得真让人感觉不习惯,所以我自己只贴一下代码吧! >>>佐理慧的 blog&l

  • avatar f_zyj(赵闲) 2021-05-21 20:35:52

    51Nod-1533-一堆的堆

    ACM模版 描述 题解 离线处理,先将数据离散化,也就是根据 a 排序即可。因为要维护 k 叉最小堆,所以我们需要从小到大进行处理,加入树状数组中,先一遍循环访问这些结点的孩子所在区间有多少不合法,然后再将这些结点插入,以此而往,这里需要强调的是,这些指的不是所

  • avatar f_zyj(赵闲) 2021-05-21 20:36:14

    雨后闲侃儿

    夏季的考验,总是这么让人窒息,整个人都要化了的感觉……感觉自己快要废了……闷热的天气,躁动的内心,糟糕的睡眠,再加上无尽的孤单,我感觉自己快要压抑死了,之所以到现在还在撑着,大概是因为梦想吧~~~忽然感觉,这句话说的很清晰脱俗啊! 整个夏季,我都计划了一系列的任务,但是,那时想的也没有那么多,只是

  • avatar f_zyj(赵闲) 2021-05-21 20:36:35

    51Nod-1522-上下序列

    ACM模版 描述 题解 十分巧妙的一道动态规划问题,应该算是区间 dp 吧! 首先我们需要考虑,大的数应该更趋向于中间,而小的数则是在两边,所以我们不妨从大到小遍历,不断往已有序列进行插入,插入的方式决定了状态的转移,每次插入的时候我们都同时插入两个,插入方式有三种:两端、首、尾,每

  • avatar f_zyj(赵闲) 2021-05-21 20:36:56

    51Nod-1563-坐标轴上的最大团

    ACM模版 描述 题解 这个题根据题意,我们知道,根据 x 和 w 可以确定某一个点的不可连边的区间,而两个点的区间只要不重叠,就可以连边,那么最大团就是尽可能多的选取互相不重叠的区间,也就变成了类似于 01 背包的问题,可是这个题好像数据比较弱还是怎么回事,直

  • avatar f_zyj(赵闲) 2021-05-21 20:37:18

    HDU-2017 多校训练赛1-补题

    ACM模版 比赛不是特别顺利,第一次打多校,感觉还是英语问题很大,虽然编码水平也很渣……比赛时做了四道,有些心痛了。赛后补补题吧,先将赛中的四道题写一下,占占流量,然后慢慢添加补的题吧! 1001-Add More Zero 描述 题解 水题,就是一个公式。 代码 #include

  • avatar f_zyj(赵闲) 2021-05-21 20:37:40

    HDU-2017 多校训练赛1-1002-Balala Power!

    ACM模版 描述 题解 这个题,是我的一个痛点……真心不难,可是我无限 CE 啊…… 思路上,很简单,判断每个字母的贡献,根据贡献排行进行分配,注意前缀不能为 0 的情况。这就是中心思想,很简单…… 可是一开始我就无限 CE ,先是本机测试编译错误,后来发现是爆内

  • avatar f_zyj(赵闲) 2021-05-21 20:38:02

    HDU-2017 多校训练赛1-1006-Function

    ACM模版 描述 题解 本质上就是求环的,用 tarjan 算法处理一下,求出两个序列的环,然后互相嵌套遍历一遍,判断两环点数之间是否有倍数关系,然后乌七八糟搞搞就行了……惊不惊喜,这是个图论。 代码 #include <iostream> #include <a

  • avatar f_zyj(赵闲) 2021-05-21 20:38:24

    FFT(最详细最通俗的入门手册)

    声明 首先,我需要声明,本文是在转载的基础上稍微修饰的,经过原创作者 ZLH_HHHH(佐理慧学姐) 的许可方才转载并修饰的,由于我就是初学者,并且是数学渣滓,所以我学姐建议我写一下残疾人手册,我当然是欣然接受!!! 正文: 文章写的有点急。有错误的地方望指出 我学习 FFT 是一个比较慢的

  • avatar f_zyj(赵闲) 2021-05-21 20:38:44

    51Nod-1485-字母排序

    ACM模版 描述 题解 一开始看到讨论区有人说,将排序部分改成 O(n) 就行了,然后我就傻傻的以为,计数排序搞一下就行了,然后,果然,无情 TLE 了四五组数据,后来知道了这个可以用线段树写,建 26 棵线段树,分别维护每种字母在不同区间的出现次数(计数部分),试了试,依然挂

  • avatar f_zyj(赵闲) 2021-05-21 20:39:06

    51Nod-1493-数据关联

    ACM模版 描述 题解 贪心问题,不过贪心思路不是特别明了…… 首先我们将两个序列都进行排序,然后分别考虑往 a 序列还是 b 序列凑(复制),当然,复制的时候并不是说将某一个序列里的所有元素都复制到另一个序列的所有块儿,而是将某一个序列的所有元素都复制到另一个序

  • avatar f_zyj(赵闲) 2021-05-21 20:39:27

    51Nod-1554-欧姆诺姆和项链

    ACM模版 描述 题解 这个题思路好巧妙啊,我想了好久都没有想通,找了一个前辈的题解才搞懂……看了好大一会儿~~~ 贴一下该大牛的题解: 来源:_TCgogogo_’s blog 感谢大神详细的题解!!! 代码 #include <cstdio> #include

  • avatar f_zyj(赵闲) 2021-05-21 20:39:50

    51Nod-1623-完美消除

    ACM模版 描述 题解 这个题着实难住了我,虽然知道是数位 dp,但是依然是手足无措,找了 光速小子0511 的代码,看了一下,神还原题解啊,必须点赞,太崇拜了…… 官方题解: 这个官方题解有一个小小的玩笑,我想机智的你仔细看一定是可以看出来的,尽管我没有看出来,我还是看到了讨论区

  • avatar f_zyj(赵闲) 2021-05-21 20:40:12

    51Nod-1684-子集价值

    ACM模版 描述 题解 这个 dp 好难理解…… 官方题解: 似懂非懂还装懂的样子☺(^__^) 代码 #include <cstdio> #include <cstring> #include <algorithm> using n

  • avatar f_zyj(赵闲) 2021-05-21 20:40:35

    51Nod-1781-Pinball

    ACM模版 描述 题解 动态规划 + 线段树 + 离散化优化。 首先,我们说一下为什么是动态规划,题目要求无论从哪儿开始,都要落在一个位置,那么也就意味着他最后一定要从第 i 个漏斗落下来,那么,我们需要考虑从最左边和最右边开始一直到 i 结束的最小花费,因为只要

  • avatar f_zyj(赵闲) 2021-05-21 20:40:57

    51Nod-1496-最小异或和

    ACM模版 描述 题解 这个题可以状压 dp 解,看到一个很玄学的解法——按规律解,虽然这种解法很容易漏,但是 51Nod 有数据,可以补漏,不过很伤点头盾……心疼我的点头盾,花了好几十~~~ 代码 #include <iostream> using namesp

  • avatar f_zyj(赵闲) 2021-05-21 20:41:18

    51Nod-1780-完美序列

    ACM模版 描述 题解 首先,我们先来分析一下如何构造才合法。 先预处理出来每种大小的数的个数,并在这个过程进行判断是否连续(不大于 1 ),然后,我们可以从小到大进行插空法插数,那么如何插呢?假如,此时我们已经查到数 i ,那么合法的插孔分为两种,第一种是插在两个

  • avatar f_zyj(赵闲) 2021-05-21 20:41:39

    51Nod-1719-数值计算

    ACM模版 描述 题解 遇见这种问题,第一感觉就是强行推一波公式,看看能不能发现什么,这个公式推倒后会发现可以化简为: F(x)=Asin(x)+Bcos(x)=Csin(x+α) 很容易得出,这是一个具有周期性的,所以我们只需要找到第一个结果,然后根据周期获取剩下的结果

  • avatar f_zyj(赵闲) 2021-05-21 20:42:03

    51Nod-1673-树有几多愁

    ACM模版 描述 题解 真的感觉这个题好难,看了官方题解也不知道怎么搞,又找了一下代码,稍微懂了一些……总得来说,这个题就是 dp (树归、状压) + 贪心,贴一下官方题解吧……我也说不好。真废…… 代码 #include <cstdio> #include <

  • avatar f_zyj(赵闲) 2021-05-21 20:42:25

    51Nod-1589-移数博弈

    ACM模版 描述 题解 这个题的解法真是奇思妙想,一开始只是知道单调栈搞不定,至于为什么,因为话题这里写得不是单调栈啊……当然也不是特别理解为什么要用链表,看了题解后恍然大悟。 对于这种题,尽管用的数据结构变了,但是不变的是逐个求贡献,那么这个题我们需要根据什么求贡献呢?我们可以求出对于

  • avatar f_zyj(赵闲) 2021-05-21 20:43:07

    51Nod-1630-B君的竞技场

    ACM模版 描述 题解 这个题竟然是积分,第一次遇见积分的问题……好题。 题解我就懒得写了,因为我也是半懂半懵逼状态,给大家一个极其详尽的题解链接,我佐学姐的题解,可以在我的博客左边找到我学姐的博客,里面的博客都是十分详细的题解,(学姐出品,必为精品),当然,懒得话直接点 这里。 没毛

  • avatar f_zyj(赵闲) 2021-05-21 20:43:29

    51Nod-1815-调查任务

    ACM模版 描述 题解 这个题思路倒是很清晰,就是代码有些小长…… 首先,我们来确定答案和什么相关,这里既然规定,结果是路径上不同城市的模值,那么,这个很容易想明白的是,只要我们维护路径最大值和路径严格次大值即可,因为后者模前者依然等于后者并且是最优解,这个毋庸置疑,注意这里是严格次

  • avatar f_zyj(赵闲) 2021-05-21 20:43:54

    51Nod-1494-选举拉票

    ACM模版 描述 题解 线段树的题倒是做过一些,但是和扫描线组合的倒是第一次做,以前甚至不知道什么叫做扫描线,做了这个题感觉有那么丢丢感觉了。 首先,我们默认要拉所有选民,然后开始减少要拉的选民数。这是中心思想。具体的实现方式是,我们先对每个人的选民进行代价排序,然后扫描出来每个候选人的

  • avatar f_zyj(赵闲) 2021-05-21 20:44:16

    51Nod-1510-最小化序列

    ACM模版 描述 题解 这个题,打眼一看就是贪心,然后我就贪心写了一下, WA 了三分之一,分析了一下,感觉只是贪心不行,还有 dp 搞搞才行…… 首先,贪心的思路是,我们需要将数据分为 k 组,其中有 n % k 组的大小为 nk+1 ,剩下的 k−n

  • avatar f_zyj(赵闲) 2021-05-21 20:44:37

    51Nod-1500-苹果曼和树

    ACM模版 描述 题解 树形DP,状态转移方程不是特别容易想。 我们先设置 dp[i][0/1] 表示以当前节点 i 为根的子树且包含该根的联通块儿的方案数,方案数划分为两部分,一部分是不包含黑色的方案数,另一种则包含一个黑色。 这样子我们可以分析出来联通块儿之间的关系,假设两

  • avatar f_zyj(赵闲) 2021-05-21 20:44:59

    51Nod-1716-多项式?

    ACM模版 描述 题解 都怪我数学不好,眼神不好,看半天没有看懂题意,还想着直接 F(n+1)=n+1n+2 呢,后来发现自己真是蠢极了,找了一下官方题解,跟着推导了一遍,感觉懂了一些。哎,数学不好真痛苦…… 贴一下官方题解: 最后结果,我们可以稍微变一下,更容易看出结果:

  • avatar f_zyj(赵闲) 2021-05-21 20:45:21

    51Nod-1831-小C的游戏

    ACM模版 描述 题解 先吐个槽,题面有毒,这题的出题人或者翻译人语文水平堪忧啊……这里说的分成几等分只取其中一份有问题,应该是只留下其中的一份,剩下的全部拿走。真是无语=_= 这个题,没有多想,直接打表,打表后发现胜败和是否为素数有一定的关系,于是又加了一个素数筛,然后打表(代码 On

  • avatar f_zyj(赵闲) 2021-05-21 20:45:43

    51Nod-1513-树上的回文

    ACM模版 描述 题解 这个题也没有想象中那么难,主要是对 dfs 序进行处理,我们获取 dfs 序的过程中,记录下来每个子树在 dfs 序中的位置区域,同时也要记录下来不同深度的结点,添加到 vector 中,当然,添加的顺序也是满足 dfs 序的,这样,我们在查找的

  • avatar f_zyj(赵闲) 2021-05-21 20:46:05

    SHU-“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛-A~K && M

    ACM模版 这个比赛早就知道有,但是因为自己要骑行,结果就没有注册,后来骑行计划延期,但是也忘了注册,赛后重现赛尝试做了 12 道,感觉水题比较多,剩下三个 AC 的人好少啊,感觉我这么菜肯定也是做不出来,所以就先不补了吧…… A-黑白图像直方图 描述 题解 水题,扫描一遍就行了。

  • avatar f_zyj(赵闲) 2021-05-21 20:46:30

    SHU-“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛-M-风力观测

    ACM模版 描述 题解 典型的线段树问题,但是在更新延迟标记时,会出现覆盖问题,所以呢,我们直接对偏移量进行处理,维护一下最大最小偏移量,进行延迟更新,可以避免覆盖带来的问题。具体看代码吧,区间更新,单节点查找,问题不大。 代码 #include <iostream> #i

  • avatar f_zyj(赵闲) 2021-05-21 20:46:52

    SHU-“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛-J-膜一下将带给你好运

    ACM模版 描述 题解 这个题是一道推导题,推导过程如下: 首先,我们应该都知道的是 n=∑d|nphi(d) 所以呢, ∑i=1ni=∑i=1n∑d|iphi(d) goon… ∑i=1ni=∑i=1nphi(i)∗⌊ni⌋

  • avatar f_zyj(赵闲) 2021-05-21 20:47:13

    SHU-“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛-H-调和序列

    ACM模版 描述 题解 暴力筛法预处理,注意坑点是, K 可能很大,大到比 n 还大,但是此时,序列中依然是有东西的,就是 A[0] ,也就是说,当访问的 K 很大时,这个子序列中至少有一个元素,如果此时 S=1 ,那么就输出 A[0] 即

  • avatar f_zyj(赵闲) 2021-05-21 20:47:35

    SHU-“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛-I-丢史蒂芬妮

    ACM模版 描述 题解 与其说是博弈论问题,不如说是伪装成博弈论的记忆化搜索问题,通过记忆化搜索来预处理出来所有状态,然后直接访问即可。 代码 #include <iostream> #include <cstdio> #include <cstring&

  • avatar f_zyj(赵闲) 2021-05-21 20:47:56

    SHU-“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛-K-购买装备

    ACM模版 描述 题解 比较基础的二分+贪心,如果这里要保证的不是最多件装备而是装备价值(不是属性)最大的话,就是二分+背包,因为这里实际上默认的是装备的价值为单位一罢了,大大降低了难度。比较水~~~ 代码 #include <cstdio> #include <cs

  • avatar f_zyj(赵闲) 2021-05-21 20:48:17

    51Nod-1779-逆序对统计

    ACM模版 描述 题解 虽然一眼就看出来了状压 dp,但是再往后我就不知道从何下手了,有些懵逼,不是太清楚如何转移。找了找官方题解,发现我果然想不到这个,但是我依然无法按照题解的提示写出来,这就尴尬了,好在网上很多大神写过这个博客,我就参考了一下他们的代码,我只想说…… ╮(╯▽╰)