- 博客(41)
- 收藏
- 关注
RSS订阅
原创 DP（动态规划）入门基础详解
DP总结ps：学了近两个月的DP，是时候总结一波了…DP基本概要：动态规划算法把原问题视作若干个重叠子问题的逐层递进,每一个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后,动态规划才会执行下一阶段的计算。无后效性 ： 为了保证这些计算能够按顺序，不重复进行，动态规划要求当前阶段不会对前面的阶段产生影响的基本条件。最优子结构性质：大多数情况下，动态规划是用来求解最优化问题。此...
2019-05-01 09:38:39
2522
1
原创 题解：黑箱(容斥计数)
题面描述在小yy面前摆着一个大箱子，箱子被划分成了 个格子，箱子的侧面都是透明的，而且箱子很高，所以小yy只能从侧面观察箱子。现在，箱子中有些格子被不透明的物体塞满了，由于小yy只能从侧面看，所以他只知道有哪些行和列有不透明的格子，求有多少种方案满足行和列不透明的情况满足小yy所看到的实际情况，对998244353取模。小yy对于OI题造诣不深，所以被这道题难住了，但是身为男主的他不能输在新手村。所以你能帮他解决这个问题吗？（不能，咕咕 ）输入格式输入第一行，两个整数n,m。接下来两行，每行一个
2020-08-22 20:27:54
258
原创 题解： [HAOI2015]树上染色
[HAOI2015]树上染色题目描述有一棵点数为 n 的树，树边有边权。给你一个在 0∼n之内的正整数 kkk ，你要在这棵树中选择 k 个点，将其染成黑色，并将其他 的 n−k个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。输入格式第一行包含两个整数 n,k。第二到 n 行每行三个正整数 fr,to,dis，表示该树中存在一条长度为 dis 的边 (fr,to)。输入保证所有点之间是联通的。输出格式输出一个正整数，表示收益的最大值
2020-07-20 21:07:03
415
原创 20200621总结
T1:初看以为是隔板法的组合计数期望，后来我发现我题目理解错了。概率只是代表了每一个位置的可能而不是整一个矩形0和1的数量之比。然后就是组合计数问题了，根据期望基本定义，我们枚举最小权值为i，计算出方案数，最后统计。不过T1最后的注释还真是挺良心的，将概率转化成组合。T2:敲完T3才回来看的，发现没有什么思路。想到回到历史版本，我竟还想到了可持久化线段树？发现在线做不太好弄，于是敲了一个暴力。题解是构建搜索树，互相可以到达的问题连边，离线处理，妙啊。T3:貌似很像山谷这一道题，不过直接DP只能拿到70
2020-06-21 16:39:23
137
原创 20200607总结
快乐省选模你赛一看T1，想到了枚举中位数，但是直接枚举复杂度是O(n2)，然后我在考场上用大把时间去尝试寻找单调性或者二分，但是没有什么大发现。后来仔细想想应该是有单调性的，就可以二分了。（考场代码枚举次数减少到只枚举5个就就可以A了，下次考试要时刻想到如何骗分 ）T2的话没有什么思路，没有想到DP，一开始想到的是容斥，即总方案数减去至少一个相邻的方案数加上至少两个相邻的方案数…，但是我发现至少x个相邻的方案数算不出来，于是暴力打表。题解是DP，状态设置的很精彩，没有想到，可能是练太少了。T3，不会。
2020-06-07 15:47:02
99
原创 2020第三轮 NOI online总结
庆幸今天是星期天。考试前看了以前比赛的总结以及教训，感觉我又可以了。看了T1，大水题，只是有陷阱，还好我发现了。然后看了一下T2，没什么想法。大概手玩了一会发现，这仿佛有点矩阵的味道。然后计算了一下最大的时间复杂度，差不多也1e8的样子(极限)。反正当下也没什么其他更优解，于是敲了一个矩阵。(转移矩阵的自方我是猜的 )，小数据过了，大数据的话无法和暴力拍，也不知道能不能过。此时大约十点钟，还有两个小时搞T3，时间充裕。看了挺久，好像也只能想到特解和优化剪枝dfs。(我自己跑了一下好像能过n=1000
2020-05-24 11:54:47
231
原创 20200512总结
T1:贪心+线段树。然而我线段树写错了，看着空间有点大，然后大概调了1个多小时…T2:看着n的范围仿佛是floyd，往这边试了很久没能调出来，而且复杂度也有点高。改了状态用dj做转移，好像可以，过了样例 。大概用了一个小时多。T3:想着机器人之间相互到达就连一条边，然后图建出来后做一下dp或者…，但是我没时间了。T4:看着几乎没有小数据的数据以及时间所剩无几，give up。发现基础的小细节出错就会调很久，然后时间分配就不咋样(有时间也不一定做得出来)。果然，要写一行代码然后迅速花几秒钟检查，不然后
2020-05-12 10:57:44
90
原创 20200412总结
这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入欢迎使用Ma...
2020-04-12 12:10:30
75
原创 20200405总结
T1:说实话我是猜的结论，手推发现第二个样例过了，然后就交了，A了T2:这道题一开始题目还看错了，以为是要求矩阵内的所有子矩形之和。没想出来。然后再想了一会，发现和前缀和有很大的联系之处。将题目问题转化为式子。然后花了很多时间去推式子，利用多次前缀和解决问题。不过不知道为什么挂了10分…T3:原本对期望题蛮有信心的，但是发现有个交换条件，顿时没什么思路了，就没写。T4:感觉有点分治的味道，不...
2020-04-05 12:30:54
90
原创 20200329总结
T1：按理说T1应该挺容易想的；自己手推了一波样例后，发现仿佛可以贪心，于是十几分钟交了一发，只有三十分，我很奇怪，这贪心应该没毛病啊。后来我将问题转化后发现其实可以进行一种类似分组DP的模型，因为其实i+k,i+2k…这些肯定是排好序后的数列中连续的一段，那么很容易联想到分组dp，直接dp。大约花了一个小时多。T2：求简单路径数。感觉有什么技巧，手玩了半个多小时推出了基环树的性质(不过貌似出错...
2020-03-29 12:23:07
82
原创 20200322总结
T1：开始看没什么思路，手玩了几组数据后感觉无论什么顺序答案总是一样，然后做一编类似欧拉序的玩意儿，以为A了。但是好像挂了。T2：感觉得用某种数据结构优化，想到扫描线，但是好像不太会的样子，于是最后敲了一个暴力，好像分数高了45分。T3：一开始看还以为是最大生成树，但是仔细想想感觉不严谨，并且时间复杂度也不太够，就没怎么深入思考，去看T4了。T4：上次补给的容斥知识我以为要用上去了，但是想到...
2020-03-22 12:32:12
90
原创 20200315总结
老刘昨天晚上爆出一个方案数的题目，慌张。不会又是什么奇怪的容斥吧。看了一眼T1，有点慌张，就是老刘昨天说的那道题。不过想了一会发现容易做出，简单dp。做T2，推出公理最少即是入度为0的点，然后利用这些点将整个图进行染色覆盖最小值，利用记忆化搜索实现。T3，题面都有点懵，没怎么推得出来，想了一会去看T4。T4感觉在哪里做过，反向建图跑DJ，判断一条边是否一定在最短路上即可。感觉预估有30...
2020-03-15 12:40:41
74
原创 2020第一轮 NOI online总结
8:30的考试，因为录屏和网页卡直到九点钟才进去。一开始看T1发现不可做，怎么做？感觉有点像图论，但是没有什么明显的结论。看了一会题后没什么思路就去看T2了。感觉T2有点水，冒泡排序本质被我发觉，感觉就是统计一个逆序对然后加加减减，利用树状数组维护一下就好了…大概在考试最后半小时的时候我发现有一些情况我的算法过不去，在交换过程中产生的逆序对变化没有考虑。但是如果数据水的话可以过去…T3的话没有什...
2020-03-08 08:27:29
254
原创 2020 0221&0223模拟赛总结
2.21总结：这还是第一次在家里考试，莫名有些紧张。当天作业很多，16：45-18：00仅有一个小时再减去吃饭时间，时间所剩寥寥。作业的拖欠和考试莫名显得有些沉重，我的心态有些烦琐。题目发了下来，先看了一下T1，以为是个结论题。然后猜结论，我猜了一下x一定是a中的一个，b中的一个，a+b中的一个等，最后猜了一个零点，发现和样例相符和，于是就去写。然后发现最后的比较好像是O（n）的？应该能够加...
2020-02-22 17:18:33
101
原创 回滚莫队(小学生一看就懂了！)
拓展一波回滚莫队：对于一般插入和删除较为简单的操作我们可以使用普通莫队来搞。但是如果题目要求讯问的求满足某些条件的最值，那么插入简单，删除的操作就很骚（即很难处理），大多数情况下都要使用某些神奇的数据结构或者？？？，这样复杂度就会提升至少一个log，然后1e5的数据就有点呛了,一般都跑不过去…于是我们就人为的将区间的收缩变为扩张，对于每一个询问先按左端点所处块从小到大，相同按右端点从小到大。...
2020-01-15 13:30:07
409
1
原创 2019 CSP-S 自闭传
NOIP的死带来的以为是和善的CSP-S的测试，谁知道一来就给我们一个下马威。考试总结几个字：这是一个关于"SHU"的考试。树，还有数。果然复习什么，什么就不考。考试前一个晚上，努力温习所有的模板，努力回忆犯过的所有错误，努力看之前模拟赛的经验教训，看自己考试总结的经典模型和问题的转化…但是一个都没有考，或者说根本没想到。那天晚上九点钟上床，不知是心理因素还是环境因素，每每想到明天就要...
2019-11-17 15:58:37
175
原创 ACM图论+数据结构杂题总结
ACM：图论+数据结构杂题总结T1:题目描述：（出处：Atcoder Regular Contest 067 Yakiniku Restaurants）一条街上有N家烧烤餐馆。餐厅从西到东编号为1到N，I餐厅和i+1餐厅之间的距离为Ai。乔伊辛诺有M张票，编号从1到M。每个烧烤餐厅都提供烧烤餐来交换这些票。餐厅i提供美味的Bi,j餐，以换取j票。每张票只能使用一次，但是餐厅可以使用任意数量...
2019-11-02 21:51:30
280
原创 (树上启发式合并)dsu on tree 学习报告总结
树上启发式合并：简介：它是用来解决一类树上询问问题，一般这种问题有两个特征1、只有对子树的询问2、没有修改一般这时候就可以强上dsu on tree了update：可能特征1不会很显然，就是说题目中不一定明确的问你子树i的答案，可能是把问题转化后需要算子树的答案（妈妈再也不用担心我不会线段树合并了… ）流程：1.O(n)计算出每一个点的重儿子2.对于节点i：–遍历每一个节点：递...
2019-10-30 19:09:04
315
原创 复赛复习计划
初赛已经结束，下一步便是至关重要的复赛准备环节，计划如下。大体计划：1.考试题目尽量订正完成，理解思想，运用知识。2.算法进阶指南基础内容掌握，熟悉思想。3.做题表格的跟进总结。4.知识点的额外拓展。5.专题内容的巩固。详细计划：时期 集体安排 10.25 联考#5day1 刷题–算阶作业 10.26 联考#5day2&&正睿十连测#3 ...
2019-10-24 19:49:46
162
原创 liu_runda NOIP 联考 DAY1[飞]题解(小学生都看得懂！)
原题重现，最为致命【本题的空间限制：32MB】题目描述：liu_runda决定提高一下知识水平,于是他去请教郭神.郭神随手就给了liu_runda一道神题,liu_runda并不会做,于是把这个题扔到联考里给高二的做.郭神有n条位于第一象限内的线段,给出每条线段与x轴和y轴交点的坐标,显然这样就可以唯一确定每一条线段.n条线段和y轴交点的纵坐标分别为1,2,3,4…n.我们记和y轴交点纵...
2019-10-12 15:57:20
361
3
原创 【NOIP模拟赛】迷路 expand 题解
DescriptionMarah要出去买菜，但不小心迷路了，它记得所有菜店的坐标，也知道它现在的坐标。请你帮帮她，找 到一条买完菜的路吧。它已经急得快哭了，它想要买完菜回家。因此它需要你找到一条最短的路买菜。她穿上了最新研发的机甲，这个机甲的体格能够变化， 为了使自己尽量炫酷，她因此它希望在路径最短 的情况下使自己的体格最大，即在移动时离障碍尽可能远。因为你开着上帝视角，所以你知道小T所在 的...
2019-10-04 21:59:56
373
原创 Comet OJ 模拟赛day1 高速公路/树的双直径
想到今天刚写一道换根DP的题，我觉得这题可以搞一搞，然后就!@5#21∗@21*@21∗@#一波，这里说说我的ZZ理解。题目描述：X 国有 n 座城市，n - 1 条道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。X 国现在想要将树上的两条链对应的所有道路改造成高速公路，为避免改造工程相互影响，这两条链不存在公共点。注意，链可以退化为一个点...
2019-09-28 10:58:46
179
原创 【2019正睿金华集训】0807总结
ACM网址：https://vjudge.net/contest/317675#problem/C密码七夕节撞上生日又撞上ACM赛，总结一下ACM赛。早上听到酒店客房，心想再睡5分钟不是事，没想到一下子睡了1小时30分钟…然后就被主力倪行大力喊醒，然后早饭都没吃朦朦胧胧地到班打ACM赛。A题是一个水题，我一想到是DP，过了样例然后挂了…队友写了一个枚举然后也挂了…然后我发现这不是SB题吗，...
2019-08-08 10:34:25
150
原创 【2019正睿金华集训】0806总结
在C班打模拟赛也一样被吊打了…发现暴力的分真的很好拿，随便写写就可以。T1就不说了，毒瘤大模拟，我真的不想写。T2是一个中位数统计，我想到一个O(n^2)的做法，预计可以拿70分，但是不知道为什么挂了，至今还在调试。T3是一个删除权值区间求剩下原序列不降的方案书，我大力暴力拿了50，正解是双指针区间维护统计方案。T4是树上统计问题，感觉自己对树上问题的感觉不是很好，统计子树贡献和如何转移...
2019-08-07 15:36:26
155
原创 【2019正睿金华集训】0805总结(后缀数组)
今日学习：后缀数组我还记得几天前在B班的时候，dls两句话讲完了后缀数组，然后说：大家都会了吧？然后我整个人都不好了。今天R姓大佬一反前天在B班的淡淡不耐烦，变成了一个耐心讲解的好老师，我居然神奇的听懂了%%%感觉后缀数组基本上是一个模板，主要操作就是对三个数组SA,rk,height数组进行操作，常用的有二分答案等。推荐博客：https://www.cnblogs.com/victori...
2019-08-06 22:10:15
136
原创 【2019正睿金华集训】0804总结
今天感受了B班考试的难度，果然好难，接近爆蛋，暴力分都不太好拿。考试历程：先看了一下三个题面，发现就第二题的暴力好写一点，随后又想到了并查集，然后去写T2,过了样例然后我就不管了【以为自己可以拿到暴力分】，T3这道题我只想说，貌似除了暴力我好像也写不了，于是我写了一个大暴力，由于是输出方案，评测机是spj的，我自己测了样例手跑一遍是正确的，然后就认为又可以拿到暴力分，不过好像又写炸了。T1这道题...
2019-08-05 08:23:37
140
原创 【2019正睿金华集训】0803总结
今天是R姓大佬讲解的（简单？）数论。果然数论还是那么的毒瘤，前面还好，讲到类欧就挂机了。讲到二次剩余，woc什么鬼东西，直接挂机。讲到莫比乌斯反演又挂机了，直到看完一篇有关数论函数的博客才上线。数论真难。QAQ知识性的总结我准备单独写一篇博客来总结数论内容，这里不再累述。明天便是为期十天的（SD）刷题营，让我感受提高+\省选的考试是怎么样的（爆蛋预警）…已经做好受虐的准备了…对于已经过...
2019-08-03 21:49:41
252
原创 【2019正睿金华集训】0802总结(树上DP)
今日学习： DP && 树上数据结构DP：基本DP我便不再累述，可以参考我的博客这里我就是想讲一下老师上课讲的一些稀奇古怪 毒瘤DP题。（这里先讲一下我已经理解了的）例1：树上互质最长链；给出⼀棵n个节点的树，每个节点上有点权a_i。求最⻓的树上路径，满⾜条件：路径上经过节点（包括两个端点）点权的gcd和不等于1每一个点权<=2*105,考虑将每一个点都分解质因数。...
2019-08-02 20:21:25
196
原创 【2019正睿金华集训】0801总结(网络流)
今天终于讲了久仰其大名的网络流。网络流基础概念：网络流是一个有向图，其中有两个特殊点源点s和汇点t，每条边有容量c(权值），实际的流量f比容量c小。特别的，如果一条边不在图中，令该边的容量为0.三个性质：1.容量限制：流量小于等于容量,即f(u,v)<=c(u,v)2.流量守恒：除了源点和汇点，每个点的总流入量等于总流出量【即无法存储量】3.斜对称性：f(u,v)= - f(u,...
2019-08-02 12:55:10
161
原创 【2019正睿金华集训】0731总结
今天的ACM赛，虽然说是欢乐赛，却一点也不欢乐。我深深认识到了自己和别人的差距，我们队只做出2道题而有的队伍已经AK，并且一些写了8，9题的队伍的成员还是新初二的，这让我意识到了自己的不足。A题一眼是个中国剩余定理的板子题，本来想是直接敲一个模板，然后突然发现不会敲了，最后还是敲了一个暴力过关。【论熟悉模板的重要性】B题是队友写出的，水题。F题的话我们一开始也是敲了一个暴力加上记忆化，然而...
2019-07-31 20:32:20
166
原创 【2019正睿金华集训】0730总结(容斥原理)
补集思想：正难则反。将不太好求的满足条件的方案转化成总方案-不合法的方案容斥原理 ：推荐博客：https://blog.csdn.net/m0_37286282/article/details/78869512容斥原理便是补集思想的一部分。来自度娘的解释：在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情...
2019-07-31 19:28:54
216
原创 【2019正睿金华集训】0729总结(分治 图论 字符串)
分治 图论 字符串每一个大知识点分出很多小知识点，有些知识点尚未完全理解（蒙）很多都没有学过啊，老师第一次讲的挺着急的，我也听的雾。一.分治：普通分治：通过划分区间，将问题变为多种情况，一些可以转换为子问题处理，跨区间的特殊处理。例1：求一个区间所有区间的最大值之和假设a[x]为区间a[l…r]的最大值，那么区间可分为在x左边，在x右边这两种情况就转换为子问题解决，还有一种情况就是跨...
2019-07-29 20:49:32
249
原创 【2019正睿金华集训】0728总结(概率期望)
期望概念学习上午的学习还算好，听得懂，但是下午老师讲的挺快，题目难度增大，有点懵逼。基础概念：随机变量：有多种可能的取值的变量P(A)P(A)P(A):事件A发生的概率E(X)E(X)E(X):随机变量X的期望值，E(X)=Sum[P(X=i)∗i]E(X)=Sum[P(X=i)*i]E(X)=Sum[P(X=i)∗i]独立事件：互相不影响的事件，满足以下性质：P(AB)=P(A)P(B...
2019-07-29 19:06:29
249
1
原创 2019海亮暑假集训总结
2019暑假集训总结：心路历程：起先是信心满满地去迎接集训，可是前几天的考试都考得不是很好，导致心态有点炸掉，逐渐失去信心。正当我迷茫之时，岳老师和刘老师分别与我谈话，道出了这次集训的目的：通过测试来提高自我，从不断的失败中吸取经验，强大自我。的确，在C班我们算是学的最短的，也正因如此，我们必须得比别人更加努力，更加充满自信。之后的考试中，时好时坏，考好了不骄傲，考差了也不气馁，都是一种经历，都...
2019-07-22 17:51:27
368
原创 Count---学习报告
这题太坑了，我考试的时候差那么一丢丢就想出正解了…为了纪念一下ZZ的我，写一个总结来防坑。题目出处：Codeforces-375D【 题面 】：有一个大小为n且以1为根的树，树上每个点都有对应的颜色ci。现给出m次询问v, k，问以v为根的子树中有多少种颜色至少出现了k次。【输入格式】第一行两个数n,m表示树的大小以及询问的次数。第二行n个数表示树上每个结点的颜色。接下来的n-1...
2019-07-19 21:31:47
223
原创 可持久线段树学习总结
可持久化线段树看了许多博客，思路有点乱，写一篇博客总结。预备知识:线段树首先来一道例题：【题面】：Q k l r 查询数列在第k个版本时，区间[l, r]上的最大值M k p v 把数列在第k个版本时的第p个数修改为v，并产生一个新的数列版本最开始会给你一个数列，作为第1个版本。每次M操作会导致产生一个新的版本。【输入格式】：第一行两个整数N, Q。N是数列的长度，Q表示询问数...
2019-07-18 07:21:17
160
原创 0704暑假集训前的欢乐大杂烩总结
0704暑假集训前的欢乐大杂烩总结在TM迎接暑假超级无敌20天happy乐的前夕来了一场巨多人的超级爽的欢乐赛然而老刘的数据翻车了 （所以我们在这里就暂且不去论第5题）T1 --质因数分解【正解】：我都不想说什么，爆0是最骚的。这么睿智的一道题我居然GG了，平时的板子要去多多复习啊。（话说我自己还写过相应的博客啪啪 ）重点：被分解的数在long long范围内这题后来订正的时候，...
2019-07-04 20:22:29
248
原创 20190514测试总结
情人节你还考试（滑稽 ）怪不得我考的这么差。考试历程：这场考试考的很迷糊，第一题说是一个送分题，那么大家就都想A掉，但是我又一时间想不出什么法子，于是汗一坨一坨地冒出来，然后又想兼顾后面几题，就都没有怎么的深入思考，导致分数不堪入目，可以说是倒数。难受的很。气氛逐渐严肃起来一.Classroom Watch【问题描述】给出一个正整数 n，现在问存在多少个 x，使得 x在十进制下的每...
2019-05-23 20:38:08
164
原创 20190521测试总结
0521测试总结这次测试不是考的很好，因为没有考过qt啊啊啊！！！！我还是要努力啊！fighting！fighting！fighting！考试历程：上次考试一下跌入谷底，是因为每一道题都兼顾导致每一道题都没能深刻思考，分数不堪入目。于是我下定决心要扳回一城。第一题的DP状态设置的时候设了好多种情况，很多种写在程序上时写着写着就转移不下去了，或者说有什么后效性吧，最后好不容易才花了1小时多...
2019-05-23 19:24:46
238
原创 【usaco4.3.3】街道赛跑 c++ 解题报告
【usaco4.3.3】街道赛跑题目描述图一表示一次街道赛跑的跑道。可以看出有一些路口（用 0 到 N 的整数标号），和连接这些路口的箭头。路口 0 是跑道的起点，路口 N 是跑道的终点。箭头表示单行道。运动员们可以顺着街道从一个路口移动到另一个路口（只能按照箭头所指的方向）。当运动员处于路口位置时，他可以选择任意一条由这个路口引出的街道。图一：有 10 个路口的街道 一个良好的跑道具有如...
2019-04-09 18:58:44
311
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人