总算闲下来一些辣！然后最近发现其实看书是真真很有效但是一直没有落实！所以决定落实一下这段时间把这本书看完题目做完！
然后发现还有挺多题目挺巧妙的于是一堆博客预警,,,可能最近会写很多比较水(但是我还是不会做)的题目的题解
啊还有就是依然是[ ]表示没写 [X]表示已经写完辣! 本来是染色标明要不要写题解的,然而染色太麻烦了QAQ所以就写完题解&&写完代码才会是[X]!
[X]64位整数乘法
快速幂/神仙方法
写了个题解qwq
[X]最短Hamilton路径
状压dp
又写了题解,,,(因为,灵巧太弱了,大部分题目都做不出来,所以可能基本上所有题目都是说"写了题解
[ ]成对变换
知识点
不是一道题目辣qwq
是一个思想,好像挺有趣的qwq
不详细说了只是mk下,好像之后港邻接表的时候会详解那就懒得深入研究辣qwq
[ ]log运算取代
知识点
又是一个思想,不知道有没有类似题目呢qwq
就是说如果我们要求logn,最简单的方法就是直接用函数log嘛
但是这样的话,常数比较大听说
这里讲两种方法(其实是一种,,,另一种只是优化qwq)(哦这个只是搞一下2k鸭
懒得写了到时候写个博客趴qwq
[X]费解的开关
枚举
以前做过,但是太弱了再看一遍依然不会,,,感到十分焦虑QAQ太弱了!做过的题目还是不会!这种事情是最最最恶心的!所以一定要写题解!
枚举(...我觉得是dp呢但是放在了枚举的板块?先当枚举?
其实并不知道这题是啥,因为没有题目描述QAQ
主要书中港可以推广到n盘m塔?很有趣呢,所以mk下!
会写题解研究下dei!
[X]激光炸弹
前缀和
总算来了个不用写题解的!感动QAQ
其实和NOIP2014的无线网络发射器差不多,都是二维前缀和搞定的嘛
就O(n2)前缀和下然后O(n2)枚举下每个矩阵的右下角,没了
[ ]tallest cow
前缀和
这道题趴,怎么说呢,,,首先你要明白这题是个什么玩意儿暴力怎么求,,,然后再想怎么优化,,,
像我这种傻逼,暴力都没有想到?当场GG了QAQ
好滴也会写题解的因为没看懂题QAQ
来和前面的一样,沙雕灵巧在线讲题解
这题是,首先假设所有都尽量就都=H,然后如果能相互看见就让他们之间都-1
于是很容易想到差分优化?大概就是酱
但是我实在是傻逼,数据结构搞多了没有脑子了,我开始想的是线段树维护
这样会做成NlogN,但完全没必要的呢,可以直接做个差分数组然后就O(n+m)的做就行了,,,哇我实在是太傻逼了?不行受不了自己了!太傻逼QAQ
[ ]sumdiv
分治
有点快速幂思想的有趣玩意儿,挺有趣,会写题解的
然后其实这题大概可以比较基础地用等比数列求和+逆元做掉?顺便把这个也搞了好了,巩固基础qwq
这题是酱的,求ab的所有约数和 mod 9901
首先把a表示成质因数乘积形式,然后显然可以得到ab=(1+...+约数1b)*(1+...+约数2b)*...
然后这里其实可以用等比数列求和公式做掉,就用下逆元就成也没有太大问题吼
但是这里还有个挺有趣的法子,有点快速幂的感觉
这样的
设sum(a,b)=1+a+a2+...+ab
显然当b为奇数时sum(a,b)=(1+a+...+ab-1/2)+(ab+1/2+...+ab)=(1+ab/2)*sum(a,b-1/2)
偶数时差不多改一点儿就成
然后就可以递归做掉了!
或者递推也星?
感觉还是有点奇妙的呢!
递归
没太仔细看,但有点傻逼暴力题的意味在感觉,,,哪天心情不好的时候可以做做这题磨下耐心?反正我当前是不会闲的没事儿做这题给自己添堵的QAQ
[ ]递归的机器实现
知识点
这个是很妙的!就是因为你纯递归可能爆栈,然后可以考虑用计算机对递归的实现方式把递归变成一个栈
但是我太弱了还没太懂,先mk着会写博客研究的qwq
[ ]三分求单峰函数极值
知识点
能理解,打算有时间把板子打了写个博客,over
二分答案
主要它的check函数有点妙感觉
但是我觉得应该可以优化到预处理,再单调栈优化+二分O(logn)扫遍?不知道能否做到,待落实来着qwq
会写题解的会写题解的!
[ ]to the max
最大子段和
umm入门题?主要书上顺便提到了然后想着最近多做点儿题趴所以就顺手放上来了qwq
[ ]innovative business
二分答案
一个很有趣的题目,而且是个交互题!想做qwq
然后想法也还算妙?到时候写不写题解看心情趴?
哦插入怎么实现啊,,,不会啊感觉,,,有点,哭哭QAQ
[ ]基数排序,计数排序
知识点
O(n)的神仙排序呢,要学!要写博客!over
[ ]cinema
离散化
相对而言比较简单?这几天会直接在这儿写下解法qwq
就开数组离散化统计每个语言有多少人高兴然后排序?over
好趴说实话题目描述没给得很好我只是猜应该是酱的,具体的如果有变化我会更新的qwq
[ ]货仓选址
中位数(...小学奥数?
绝对值min,,,小学奥数既视感,,,还是最低级的小学奥数,,,
天呐这种题我连题解都不想写?懒得废这个打字的力气×
就是|a1-x|+|a2-x|+...+|an-x|的min,,,话说这都不算是奥数了?就绝对值的几何意义得x=a[]中位数,over
[ ]七夕祭
中位数+贪心
会写题解的趴?因为开始并没想到呢
又是一道连暴力都没想出来的题目,完了最近脑子锈了什么东西都想不出来,,,药丸药丸QAQ
[ ]running median
对顶堆/链表
哇真的有趣!真的妙啊!!!不行我一定要写博客!很妙!两种方法都要写!!!
[ ]第k大数
知识点
整体二分?嘛?
理解了已经,会写博客的qwq
[ ]奇数码问题
逆序对
之前考过一个,和这个相关的?
然后之后(比较远了好像,,,)讲A*搜索的时候会讲到这题的详细搜索怎么搞
但首先先搞定这个,记得写博客
也是挺妙的,然后可以拓展到偶数码和n*m数码,但是书中好像没有详解,自己会推下然后结论放博客里?
[ ]一个书上的问题可能没题目qwq
倍增
先复述题目qwq
是说有个长度为N的数列A,进行若干次询问,每次给定一个整数T,求kmax使得a[1]+...+a[k]<=T,要求必须在线
然后会写博客先暂时写这儿qwq
首先显然最简单是前缀和+lower_bound
但是这样子的时候如果T很小可能还不如直接从前往后枚举优是趴
这时候就考虑,倍增
剩下的博客里面写去,今儿只是先把目录基本架构搭下qwq
[ ]genius acm
倍增
...好难der,,,而且我连它的第一句话都不会证明,,,哭死
所以这题题解中药包含几个方面
第一个是正解
然后是归并排序优化
还一个是证明那个"显然balabala
[ ]st算法(rmq
倍增 知识点
会写博客的这里不说了先qwq
[ ]sunscreen
贪心
重点是要再博客中证明贪心决策正确性,希望不要看书
然后顺便总结下证明贪心正确性的几个方法?可能会另写一篇然后举例之类的时候就放这几道贪心的链接qwq
[ ]stall reservations
贪心
同上
[ ]radar installaion
贪心
同上
[ ]国王游戏
贪心
同上
[ ]color a tree
贪心
同上
没看懂题目QAQ先把题目看懂QAQ
[ ]一些练习(P44 45
有12道题,都还没看,看了之后会拆成一道道的和其他一样的性质放上来qwq
[ ]push,pop,getmin
栈 神仙想法
好晚了困死了不说了,会写博客over
[ ]editor
对顶栈 又是个神仙
感觉自从NOIp之后就没有脑子了?思维僵化,随便一道题目都能卡死我,随便一道题的解法感觉对我来说都是神仙:(
这种状态还是布星!
但是这个我是真的觉得挺神仙的,,,虽然并没有太仔细看,,,但是和对顶堆类似的算法一定也是神仙!over
[ ]进出栈序列问题
递推/dp/数论
讲了四个方法，一个暴力不说了,其他几个都要落实,over
[ ]largest rectangle in a histogram
单调栈
感觉也许还能用悬线法...?布吉岛我悬线法并不会来着只是做过一道题但并没研究清楚QAQ
然后这题也很神仙,打算写博客qwq
[ ]team queue
队列
...我是真的药丸了,认真的港我好担心我现在的状态啊QAQ
其实是道挺简单的傻逼题?然后我是真的没想出来???真的我现在连最暴力最傻逼的数据结构的最基础的部分都想不到了?我怕是成普及三等奖的水平了已经QAQ
然后不难就直接写下?就开一堆队列,一个是存队伍顺序的,一堆是存每个队伍中有哪些人的,然后就可以了,基础操作走一波,结束
然后我真的没想到,,,大概是学科限制了我的智商趴QAQ
[ ]双端队列
神仙思维题
不会,勉强懂了题解,要早点儿写博客不然怕过几天又无法理解了QAQ
挺妙的我觉得?反正我不会qwq
[ ]最大子序和
单调队列
挺妙的 也可能是因为最近没脑子随便一道题都是妙妙妙好好好...
会写博客.over
然后感觉用了一点儿单调栈的思想?umm好趴其实单调队列单调栈啥的都是单调性的所以是共通的嘛qwq
[ ]邻值查找
链表orSTL
umm,,,话说这题我并没有理解那个链表做法?好迷的我觉得?为什么要删除?什么玩意儿?真的我满脸懵?有时间查下这个代码学习一下,,,
大概不会打算写博客,到时候大概就在这儿写下?(如果,那个链表的方法实在太太太妙了也会写博客的辣qwq)
[ ]hash+字符串hash
知识点
学到了,之前一直听学长们港什么哈希啊balabala的就一直想学,发现并不难其实挺入门的...话说我是真的弱连hash都不会,,,我NOIp是真的运气好才水到的省一QAQQQ(,,,是不是省一还不知道呢QAQQQ不是就监介辣QAQQQ)
[ ]snowflake snow snowflakes
hash
大概算是个典型hash题?因为hash是新学的知识点所以会写博客的!
[ ]兔子与兔子
hash
这个是真的板子题,,,不写博客辣直接模板复制粘贴过去就是?
[ ]palindrome
hash/manacher
昂hash的那个是nlogn我觉得海星了,,,简单又好理解的×
其实都不好理解
会写博客,两种方法都做一次qwq
[ ]后缀数组
倍增/DC3/hash
后缀数组,又名SA,是个很重要的数据结构
所以!我们要比较熟练地掌握它的这几种方法!
然而我目前大概只能把hash落实掉QAQ不管怎么的先mk着QAQ
[ ]KMP模式匹配
知识点
早写了博客一直没写完QAQ
[ ]period
kmp
似懂非懂感觉,,,之后会写题解的qwq
[ ]最小表示法
知识点
没懂,先mk着qwq
[ ]前缀统计
trie树
是板子题呢qwq不会写题解了实在比较简单呢qwq
[ ]the xor largest pair
trie树
又是个板子呢,不过是最大亦或的前缀,我记得我写过位运算的博客,到时候放上来
这个就不另写题解辣qwq
[ ]the xor largest path
trie树
有个对我而言还是比较妙的思想,所以大概会写题解的qwq
[ ]二叉堆
知识点
还不会手写二叉堆呢...要学下qwq
然后不会另外写题解了大概,感觉没有太大的理解难度
会把代码放到垂死挣扎那儿大概qwq
[ ]supermarket
二叉堆/并茶几
感觉这题长得有点儿像蔬菜那题的简化版?好像学长确实是在讲蔬菜那题的时候讲到了并茶几相关balabala的?(...虽然我并没有看懂来着QAQ)
也是非常非常非常地妙,然而没有很懂呢QAQ所以会写题解的qwq
哦另外洛谷上有这题,可以去看下题解帮助理解qwq
over
[ ]数据备份
二叉堆+链表
!神仙做法了真的
很妙的想法
会写题解
所以CTSC2007居然就这么难了嘛,,,哭泣QAQ
[ ]合并果子
二叉堆+贪心(也就是,haffman树呢)
没有太太太大难度?只是可以用haffman树帮助理解,over
不写题解了qwq
[ ]荷马史诗
haffman树
umm...没有看懂题目TT
但是似乎是haffman树有一定应用层面的东西了呢,所以会写题解qwq
而且题目都没看懂的是一定要写题解的呢×
[ ]haffman树
知识点
本来想着没有太太太难不想另外写了
想了想还是要总结一下这个知识点
大概会放在垂死挣扎里qwq
[ ]一些练习(P86 87
有13道题呢也
但是也先不会动,先把前面的都搞完再说qwq
[ ]树与图的遍历
知识点
发现有挺多我还不会...基础不牢地动山摇啊QAQ
所以会专门写个博客
然后在考虑专门再做个图论专题的博客总结下各个知识点汇总下题解啊学习笔记的网址
因为图论实在太烂
烦躁QAQ
[ ]可达性统计
拓扑排序
妙的
然后还会要用到bitset就想着顺便学习下bitset的用法qwq
会写题解,over
[ ]小猫爬山
dfs
简单题,不会写题解的,就冲个做题量qwq
[ ]sudoku
dfs+神仙剪枝
哇这题真的是,剪枝有一大堆
而且都很妙然后很多还挺有启发性的实用意义挺广(后面剪枝专题还讲了点儿可以合并一下qwq
真的会写题解,剪枝太多了太牛逼了!
over
[ ]sticks
dfs+神仙剪枝
布星我发现我是真的弱?剪枝都不会?
完全想不到剪枝星人就是我了好嘛QAQ
没了,会写题解qwq
[ ]生日蛋糕
dfs+神仙剪枝
学长好像港过呢?然后叶佬是不是也讲过这题?反正好像是主题差不多,然而题面和问题是不是一样的我就忘了QAQ
又是个牛逼剪枝,这个大概会在过停课集训专题的时候过掉qwq
会写题解,over
[ ]迭代加深
知识点
这个想法还是挺妙的,写肯定是会写,只是在想是另外开个新的还是写在垂死挣扎里qwq
over
[ ]addition chains
迭代加深
昂迭代加深的板子题呢,大概作为例题用掉了,不另外写个题解辣qwq
[ ]双向搜索
知识点
双向搜索,和,双向bfs不太一样呢感觉,,,但是大概会一起写个题解qwq
[ ]送礼物
双向搜索
感觉这题,长得有点像之前的一道考试题?QAQ忘了什么名字了只记得是zsy学长教的神仙解法?大概被虐日常里有到时候翻下qwq
哦考试题也要整理呢QAQ
[ ]bloxorz
bfs
bfs板子题了呢,但是细节好像有点麻烦?到时候看代码复杂度决定写不写题解qwq
[ ]矩阵距离
bfs
没有想到QAQ依然生锈的脑子QAQ
所以会写题解!
[ ]pushing boxes
bfs
开始连题解都没看懂?然后大概看了下发现和华容道有点儿像的感觉?方法还是明白了
实现依然可能有点困难QAQ神一般的双重bfs?
[ ]01队列bfs
知识点
是个很妙的bfs知识点呢!之前在xzy学长的博客里看到过qwq但是没有理解QAQ
然后现在总算明白了,还会涉及bfs的性质们呢,所以会写题解qwq
[ ]电路维修
01序列bfs
板子题,可能直接作为知识点中的例题出现?就不另外开题解辣qwq
[ ]full tank
dij
傻逼题?不想多说qwq真·纯刷个做题量qwq
[ ]双向bfs
知识点
说好了要和双向搜索一起写题解,就一起写啦qwq
[ ]nightmare II
双向广搜
板子?可能和前面的板子题命运一样了趴qwq
[ ]A*搜索
知识点
一直一直一直想学,也一直一直一直在说要学
然后直到现在才学QAQ执行效率太低QAQ
不过还是get到了呢,然后关于正确性什么的还是证下,所以会写题解qwq
[ ]第K短路
[ ]八数码eight
[ ]康拓展开
[ ]IDA*
[ ]the rotation game
[ ]booksort
[ ]square destroyer
[ ]练习P128.129
[ ]程序自动分析
[ ]supermarket
[ ]银河英雄传说
[ ]parity game
[ ]拓展域并查集 戴荃带权并查集
[ ]食物链
[ ]楼兰图腾
[ ]a tiny promblem with integers
[ ]a simple promblem with integers
[ ]lost cow
[ ]interval gcd
[ ]扫描线
[ ]atlantis
[ ]stars in your window
[ ]分块
[ ]蒲公英
[ ]磁力快
[ ]莫队
[ ]小z的袜子
[ ]点分治
[ ]tree
[ ]二叉查找树bst
[ ]平衡树treap
[ ]普通平衡树
[ ]cdq分治
[ ]天使玩偶
[ ]整体分治
[ ]k-th number
[ ]可持久化trie
[ ]最大异或和
[ ]可持久化线段树(主席树)
[ ]
[ ]
[ ]
[ ]
[ ]