最后一次编辑于2019年8月15日上午11点18分   最小生成树 Kruskal \(kruskal\)，一种求最小生成树的算法，其思想与贪心有些相似，具体做法为： 将边按照边权由小到大排序，每次拿出权值最小的一条边，看它连接的两个顶点是否在同一个连通块中（可以用并查集维护），如果在的话就不使用他，否则就加入生成树，一直加入到边数为\(n - 1\)结束 如何证明？ 要我说我也说不明白，还是直接上图吧  图片来自：https://blog.csdn.net/weixin_43272781/article/details/83589394 复杂度：\(O(mlogm)\) 代码实现： #inc...

枚举子集的子集  给定n个元素，问这n个元素组成的每一个集合的所有子集。  for(int S = 1; S < (1 << n); ++S) { for(int S1 = S; S1 != 0; S1 = (S1 - 1) & S) { //do something } }  最外层就是\(O(2^n)\)枚举所有集合。如果要按普通方法枚举子集，应该将\(S1\)从\(S\)开始每次减一，再判断合法性。然而由于&\(S\)的结果只减不增，\(S1\)可以通过\(-1\)然后&\(S\)来直接到达最近合法状态。 复杂度不会证，但是知道是\(O(3^n)...

待更新  背包动态规划 01背包 有\(N\)件物品和一个容量为\(V\)的背包。第\(i\)件物品的费用是\(c[i]\)，价值是\(w[i]\)。求解将哪些物品装入背包可使价值总和最大。 \(f[i][j]\)表示前\(i\)件物品恰放入一个容量为\(j\)的背包可以获得的最大价值，转移方程为 \[f[i][j]=max{f[i-1][j],f[i-1][j-v[i]]+w[i]}\] for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if(j < v[i]) f[i][j] = f[i - 1][...

Day 7 今天要回家了……  Day 6 你好，利奇马. 从早到晚下雨不停的一天~~利奇马你干的不错 不过……你把我裤子和鞋子弄湿了什么意思！！这就不太对了吧 利奇马是沙琪玛的哥哥，安琪拉是利奇马的姐姐哈哈哈 下午考试，日常懵逼 然后沙雕第五… 因为！！ans赋初值小了！！    然后100挂成60……如果我开到1e18！！就A了！！    利奇马好像有点暴力……  Day 5 更新！ 发现\(yxj\)大摇大摆起来走路更加有种大汉小仙女的感觉 等风来！！   当所有的台风波及地区都在害怕的时候，山东人：哇塞，九级台风什么亚子啊？？好期待哦！  晚上看liuzt上课在有老师的群里自己机惨自己...

传送门 思路 由于数据范围很大，所以使用单调队列，和滑动窗口这道题类似 首先第一个数输出\(0\)，因为第一个数之前没有数 然后通过样例我们发现，最后一个数并没有派上什么用场，所以循环\(n-1\)轮即可 这里的单调队列是记录的序号，每次输入\(a[i]\)，检测它是不是比当前的队尾大，如果比队尾大直接入队，反之与队尾比较（\(r--\)）直至比队尾大为止。当长度超过\(m\)时，\(l++\)，最后的队首就是答案 代码 #include <iostream> #include <cstdio> using namespace std; inline int read(...

洛谷 P5021 [NOIP2018]赛道重建 传送门 思路 思路就是常规的思路，所以就不说了……我就是来记录一下我的\(AC\)之路的，真的是太爽了  没错……我也是一个个打的部分分，最后终于AC的，至于为什么中间又会有\(35\)、\(25\)、\(0\)这样的分数……纯粹是因为我犯了zz错误…… 代码 1、\(b_i = a_i + 1\) 链的情况 #include <bits/stdc++.h> using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; for( ; !is...

一首好听的无名之辈，送给大家~~ 虽然我没看电视剧，但是，这首歌，太好听了！！ 传送门！！ 城市黎明的灯火 总有光环在陨落 模仿者一个又一个 无人问津的角***r> 你选择去崇拜谁呢 怨恨谁呢 假装热情的冷落 假装自由的枷锁 你最后成为了什么 燃烧华丽的烟火 绽放一次就足够了 奢求什么 无名之辈 我是谁 忘了谁 也无所谓 谁不是 拼了命走到生命的结尾 也许很累一身狼狈 也许卑微一生无为 也许永远成为不了 你的光辉 无名之辈 我是谁 忘了谁 也无所谓 继续追 谁的光荣不是伴着眼泪 也许很累一身狼狈 也许卑微一生无为 谁生来不都是一样 尽管叫我无名之辈 假装热情的冷落 假装自由的枷锁 你最后...

洛谷 P1168 中位数 传送门 思路 昨天CKW大佬讲的题 用两个优先队列，一个大根堆，一个小根堆 保证小根堆里的数都比大根堆里的数要大，每次输入一个数，看这个树是否比大根堆的堆顶要大，如果比大根堆堆顶大的话放进小根堆中，否则放入大根堆中，如果两个堆中元素个数差大于了1，那就看看是哪个堆的元素更多一些，将这个元素的堆顶放到另一个堆中，保证了两个堆的堆顶之中一定有一个数是目前中位数，然后输出的时候看看哪个堆元素多输出哪个堆的堆顶就好了 需要注意的是，第一个数需要特殊处理，直接输出即可 还有就是，在洛谷上用\(size()\)函数不行，会\(CE\)，所以这里用了两个\(cnt\) 代码 #in...

7.20 线段树忘记开四倍空间！ 7.27 考试数组开小！ 8.02 \(y = e[i].to\) 写成 \(y = e[x].to\) 调了大半个小时…… 8.11 半年OI一场空，不开1e18见祖宗

Day 0 早上九点赶到学校，发现直接从门口出发……结果没有拿学习的书，尴尬 坐上车之后就直接出发了，发现有几个博园的小朋友，他们一路上闹得真欢，连睡觉都睡不着 下午一点，到达了山外——山东外国语职业技术大学，从此开启了八天多的夏令营生活 到了之后，老师让我们在边上等着，他们去报到，回来之后发现男生在7号宿舍 于是跟着老师进了宿舍，宿舍外头写着：女生宿舍，男生止步 ……………… 吓到我了，我们住女生宿舍？？ 没错是这个亚子的 找到自己宿舍，发现里面有三张同一个小姐姐的图片，底下写着留言板 我们不禁感叹，这女的真丑…… 不过宿舍条件还是不错的，有独立卫生间，还能洗澡，一个宿舍只有四个人，宿舍里还...

洛谷 P5461 赦免战俘 传送门 思路 洛谷7月月赛第一题 着实是一道大水题，然后我月赛的时候没做出来...... 就是一道大模拟题呀，直接dfs就好了，我是反着处理的，所以最后要输出\(1-a[i][j]\) #include <bits/stdc++.h> #define N 1 << 10 using namespace std; int a[N][N], n; void solve(int x, int y, int l) { //x、y表示起点的横纵左边，l表示长度 if(a[x][y]) return;//sd的剪枝？ for(int i = x; i &...

洛谷 P2158 [SDOI2008]仪仗队 传送门 思路 从\((0，0)\)开始，抛开可以看到的\((0,1),(1,0),(1,1)\)三个点,做出一个\(5*5\)的矩阵试一下，发现当每个点的斜率的分母和分子互质时，这个点才能被看到（\(y==x\)时除外，因为已经被\((1,1)\)点挡住了），所以我们可以求欧拉函数累加，最后再加上原先的\((0,1),(1,0),(1,1)\)三个点，因为是从\(0\)开始的所以求到\(n-1\)就好了，需要注意的是\(ans\)需要乘以二，因为我们求的只是被\(y=x\)这条线分开的半个部分的可以看到的数量，而上下对称，所以直接乘二，最后的答案就...

1 想和你重新认识一次 从你叫什么名字说起。    2 人这种东西，除了为了永不满足的欲望追求新的刺激之外，也是重视稀少价值之物的奇怪生物。    3 迷失的人迷失了，相逢的人会再相逢.    4 A Winner is a dreamer who never gives up.    5 有时清晨醒来，连我的灵魂也是湿的。 海远远地发声，回响。 这里是港口。 在此我爱你。    6 很多时候蒙蔽我们双眼的不是假象，而是自己的执念。    7 你来走这一遭，奇迹般万物生长。    8 走了很久才发现，远方一样是茶米油盐的样子。    9 没有说出口的话，比什么都让人耿耿于怀。    10 旧梦...