空気力学の詩

2018年3月31日

摘要：排序（水题）专题，毕竟如果只排序不进行任何操作都是极其简单的。事实上，排序算法十分常用，在各类高级的算法中往往扮演着一个辅助的部分。它看上去很普通，但实际的作用却很大。许多算法在失去排序后将会无法实现。以上在扯P 看2388，求中位数。好，sort一遍（与衢州2017市赛PJ T1一样水）。阅读全文

posted @ 2018-03-31 20:26 空気力学の詩阅读(243) 评论(0) 推荐(0) 编辑

EZ 2018 03 30 NOIP2018 模拟赛（六）

摘要：链接：http://211.140.156.254:2333/contest/67 转眼间上次加回来的Rating又掉完了。这次不知为何特别水，T1想了一段时间没想出来弃了，导致后面心态炸了。 T2也没有注意到有随机数据，少得了10分。 T3也没想过，直接输了些样例再手算了一组数据就没管了。然而阅读全文

posted @ 2018-03-31 14:34 空気力学の詩阅读(271) 评论(0) 推荐(0) 编辑

2018年3月30日

POJ 1459&&3436

摘要：两道比较基础的网络流题目，重点就是建图。 1458：题意就是给你一些东西它们的数据，其中一些是发电站，还有一些是用户的家里，其中还有一些是中转站。让你求最大的输送电量。就是一道很基础的最大流题目，建超级源和汇，分别向发电站连边，从用户那连进边。具体的读入只需要写一下读优即可去括号。、 CODE 阅读全文

posted @ 2018-03-30 13:32 空気力学の詩阅读(147) 评论(0) 推荐(0) 编辑

2018年3月27日

BZOJ 1001: [BeiJing2006]狼抓兔子

摘要：以前打的题目忘记写了。一道比较简单的最大流&最小割的题目，主要运用了最大流&最小割定理。仔细观察题意，其实就是从S到T每次割去一条边，问怎样割可以使得S到T没有通路并且代价最小（代价为路上最多能通过的兔子数）只要你有点网络流方面的姿势，那么就可以很清楚的看出这是一个最小割。对于割，曾经a56爆大奖在线娱乐也听阅读全文

posted @ 2018-03-27 20:22 空気力学の詩阅读(161) 评论(0) 推荐(0) 编辑

Luogu P1231 教辅的组成

摘要：一道比较简单的的网络流拆点题目。首先考虑这样a56爆大奖在线娱乐建模的想法：建超级源点S，超级汇点T，将源点与所有练习册相连，再将所有答案与汇点相连。然后根据各练习册，书本之间的关系进行连边。然后一脸期待的跑Dinic，结果很干脆：WA 但是，为什么？考虑这样一张图（S标为0，T标为N1+N2+N3+1，书为阅读全文

posted @ 2018-03-27 19:55 空気力学の詩阅读(164) 评论(0) 推荐(0) 编辑

2018年3月25日

EZ 2018 03 23 NOIP2018 模拟赛（五）

摘要：链接：http://211.140.156.254:2333/contest/65 这次Rating重回Rank18，a56爆大奖在线娱乐是20的守门员（滑稽）这次题目和数据普遍偏水，a56爆大奖在线娱乐T2打错了一个变量名竟然过了所有的样例而且有90分（滑稽）但最后一题SB了，忽略了还有不为2的几次幂的情况，a56爆大奖在线娱乐炸成10分。 2 阅读全文

posted @ 2018-03-25 16:30 空気力学の詩阅读(217) 评论(0) 推荐(0) 编辑

Luogu T24242 购物券Ⅰ（数据已加强）

摘要：这是一道比赛时的题目，但由于a56爆大奖在线娱乐没报名，a56爆大奖在线娱乐浪费了一个大好的切水题的机会。是经典的meet in middle（折半搜索）的模板题，但是之前一直没找到这种题目，今天终于看到了。由于m的范围极大，因此一般的背包DP是行不通的。如果直接进行2^n的爆搜，也只有40分。 a56爆大奖在线娱乐这里a56爆大奖在线娱乐们观察数据n=40，阅读全文

posted @ 2018-03-25 15:34 空気力学の詩阅读(156) 评论(0) 推荐(0) 编辑

2018年3月24日

EZ 2018 03 16 NOIP2018 模拟赛（四）

摘要：链接：http://211.140.156.254:2333/contest/64 a56爆大奖在线娱乐去掉了一百多分！这次的题目怎么说呢，特别水，但是就是出现了一些很逗的错误导致炸裂。最好笑的是SB的不只a56爆大奖在线娱乐一个： hl666：T1没写负数读优，100炸成40 yu‘ao：T1写了判负数的但最后忘记乘上去了，10 阅读全文

posted @ 2018-03-24 20:28 空気力学の詩阅读(284) 评论(0) 推荐(0) 编辑

EZ 2018 03 09 NOIP2018 模拟赛（三）

摘要：最近挺久没写比赛类的blog了链接：http://211.140.156.254:2333/contest/59 这次的题目主要考验的是爆搜+打表的能力其实如果你上来就把所有题目都看过一次就可以知道：正确的顺序是3->1->2 先切T3的意思是你可以很快的爆搜之后开始打表，但T2考思维，T1考语阅读全文

posted @ 2018-03-24 16:37 空気力学の詩阅读(149) 评论(0) 推荐(0) 编辑

2018年3月17日

Luogu P2055 [ZJOI2009]假期的宿舍

摘要：一道网络有关的问题，还是一句话网络流重在建模！这里主要讲两种算法。 1.二分图匹配：分析题意，a56爆大奖在线娱乐们可以知道题目要求是让所有留在学校的人都能有床睡而所有留在学校的人=本校不回家的人+外校的人；床的总量=所有本校生的数量；理解题意后，a56爆大奖在线娱乐们考虑将所有人的情况拆开来考虑，即： a56爆大奖在线娱乐人有两个信息阅读全文

posted @ 2018-03-17 15:13 空気力学の詩阅读(140) 评论(0) 推荐(0) 编辑

网络流之最大流

摘要：网络流之前一直尝试去学过好多次，但一直都没搞懂。最近一鼓作气终于会最大流的（fuck）其实有些时候可能真的一瞬间就理解了些东西（上语文课的时候突然理解增广路了）也推荐一些学习的博客（a56爆大奖在线娱乐们不生产资料，a56爆大奖在线娱乐们只是资料的搬运工）：关于网络流十分形象的解读以及一些基本概念：http://blog.cs 阅读全文

posted @ 2018-03-17 11:35 空気力学の詩阅读(356) 评论(0) 推荐(0) 编辑

2018年3月13日

POJ 1988&&2236

摘要：并查集，如果只是朴素的路径压缩，那么也就是一句话的事情。但是，一般都没有这种仁慈的裸题（假的，多了去了） 1988：带权并查集，贼鸡儿像Luogu的那道杨威利的并查集（好像是叫银河英雄传说）开两个数组，down[x]a56爆大奖在线娱乐标号为x的箱子下面有多少个箱子，len[x]a56爆大奖在线娱乐以x点为根（即被压在最底部的阅读全文

posted @ 2018-03-13 20:24 空気力学の詩阅读(158) 评论(0) 推荐(0) 编辑

2018年3月11日

POJ 1860&&3259&&1062&&2253&&1125&&2240

摘要：六道烦人的最短路（然而都是水题） a56爆大奖在线娱乐也不准备翻译题目了（笑）一些是最短路的变形（比如最长路，最短路中的最长边，判环），还有一些就是裸题了。 1860：找环，只需要把SPFA的松弛条件改一下即可，这里打的是BFS的。如果一个点入队次数大于n次，那么一定有环存在。 CODE 3259：几乎相同的SPF 阅读全文

posted @ 2018-03-11 15:20 空気力学の詩阅读(176) 评论(0) 推荐(0) 编辑

2018年3月10日

POJ 3041&&3020

摘要：两道二分图的练手题。 3041：题意大概是在一个N*N的图上有K个东西，你每次可以清除一行或一列上的所有东西。让你求最少的操作次数。 a56爆大奖在线娱乐们根据题意建图。对于每一个点的坐标（x，y）之间连一条边。比如样例：由于每条边代表着一个点，因此a56爆大奖在线娱乐们只需要找出最少的点来联结所有的边，也就是最小顶点覆盖=最大匹配阅读全文

posted @ 2018-03-10 20:21 空気力学の詩阅读(201) 评论(0) 推荐(0) 编辑

有关二分图匹配的一些算法

摘要：今天学习了下二分图，算是进来的比较新的一块内容了吧。关于匈牙利算法之前也看过一些，但一直没怎么搞懂，今天看了个很好的博客，茅塞顿开啊。一看就懂的匈牙利算法：http://blog.csdn.net/dark_scope/article/details/8880547 关于二分图的东西a56爆大奖在线娱乐也不是太懂阅读全文

posted @ 2018-03-10 19:40 空気力学の詩阅读(185) 评论(1) 推荐(0) 编辑

POJ 3253

摘要：作业上的一道哈夫曼树的入门题。题意大概是在一段无限长的木板上截下n段与要求相同的木板。每次切割需要花费切割长度的代价。让你求最小的代价是多少。很容易想到这种贪心策略：每次割下最长的长度，这样可以使长的尽量少割。但很容易发现这是行不通的，因为有些时候截下来的是几段的和而不是一段。因此a56爆大奖在线娱乐们反向思阅读全文

posted @ 2018-03-10 14:26 空気力学の詩阅读(138) 评论(1) 推荐(0) 编辑

2018年3月9日

Luogu P1993 小 K 的农场

摘要：其实很早以前就打好了，但一直忘记写了。也就是差分约束的模板题。关于差分约束，也就是用来求关于一些不等式互相约束算出最优解。推荐一个讲的很好的博客：http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html 可以通过一个三角阅读全文

posted @ 2018-03-09 13:20 空気力学の詩阅读(220) 评论(1) 推荐(0) 编辑

2018年3月8日

EZ 2018 02 28 NOIP2018 模拟赛（二）

摘要： a56爆大奖在线娱乐TM的终于改完了（其实都是SB题）题目链接：http://211.140.156.254:2333/contest/53 T1送分，T2前40%送分，还有骗分机制在里面，T3暴力50 a56爆大奖在线娱乐200应该有的吧（事后诸葛亮）但T2的第一问智障了，但是无解骗分（直接搞一个数再开个根）弄了38分，a56爆大奖在线娱乐R 阅读全文

posted @ 2018-03-08 18:48 空気力学の詩阅读(1718) 评论(1) 推荐(0) 编辑

2018年2月28日

树的重心以及直径算法

摘要：树是a56爆大奖在线娱乐很牛X的数据结构，性质有很多，比如（自行百度去）今天主要讲一下如何求树的重心和直径（在某些算法中要用到） 1.树的重心树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡（百度百科）树的重心在点分治中可以保阅读全文

posted @ 2018-02-28 10:58 空気力学の詩阅读(1286) 评论(0) 推荐(1) 编辑

2018年2月27日

POJ 1741

摘要：它这道题的分类是分治，但a56爆大奖在线娱乐还是觉得和树的关系更密切些。也算是完成了第一个最简单的部分——基本算法（更强大的在后面）。是近来打过的比较难的题目了，因为涉及到很多新的东西也花了挺长时间去学点分治和树的重心之类的东西。首先，O(n^2)的爆搜还是很容易想到的吧，可惜过不了。考虑无根树转有根阅读全文

posted @ 2018-02-27 16:31 空気力学の詩阅读(157) 评论(0) 推荐(0) 编辑

POJ 1789&&2485&&1258&&3026

摘要：这个真的太水了——MST专辑。如果不会MST的两种算法的同学可以出门右转了。大致讲一下，第一题a56爆大奖在线娱乐是用Prim+堆优化的（毕竟点比较多），后面三题用的是Kruskal（习惯打，而且并查集常数实在小）前三题是裸题，最后一题要BFS预处理图上两点间的最短距离再跑Kruskal，稍微麻烦了点按顺序贴阅读全文

posted @ 2018-02-27 16:04 空気力学の詩阅读(147) 评论(0) 推荐(0) 编辑

2018年2月26日

HDU 2586

摘要：一道LCA的练手题。题目大意，在一个树中给出每两点之间的距离，然后让你求�a56爆大奖在线娱乐饬降慵涞木嗬搿� 很明显这可以用树剖（但是a56爆大奖在线娱乐不会），但是因为这里没有涉及到修改，a56爆大奖在线娱乐们可以巧妙的利用LCA来解决这个问题记一个点x到树根的距离为dis[x]，另一个店y到树根的距离为dis[y]，运用一下简单的容斥原理就可以阅读全文

posted @ 2018-02-26 16:30 空気力学の詩阅读(141) 评论(0) 推荐(0) 编辑

POJ 1094

摘要：一道拓扑的经典题，但理解题目让a56爆大奖在线娱乐很伤。大意是说给出关于n个字母的偏序关系，让你判断是否有唯一序列或有环（输出当前是第几步，如果有唯一序列还有输出），如果都读完了还不能确定，就输出另a56爆大奖在线娱乐情况。按照题意，每读入一步就走一遍topo来判断。有一个坑点：就算中间找到并退出了还是要把剩下的读完。具体看阅读全文

posted @ 2018-02-26 16:08 空気力学の詩阅读(188) 评论(0) 推荐(0) 编辑

EZ 2018 02 26 NOIP2018 模拟赛（一）

摘要：这次是校内OJ（HHHOJ）线上比赛，网址：http://211.140.156.254:2333/contest/51 （a56爆大奖在线娱乐去刚刚快写完了手贱关掉了）这次总体难度也不高，T1&&T2都是TG难度的题（可能还更低），T3要用到主席树（这个以后再说）大力切，但60分的暴力还是很好水的。 a56爆大奖在线娱乐 100 阅读全文

posted @ 2018-02-26 15:04 空気力学の詩阅读(266) 评论(0) 推荐(0) 编辑

Luogu P1558 色板游戏

摘要：（此题与POJ2777重题）为了加深对线段树的记忆，然后开始搞这道题。 TM的WA了一下午就是发现x可能大于y（然而题目里说的还很清楚，a56爆大奖在线娱乐TM没看见）这道题只需要在线段树的板子上改一些地方就可以了： 1.存储时不是存储颜色，而是将它状压成一个整数（如序号为3的颜色存为1<<3=8） 2.回溯时不阅读全文

posted @ 2018-02-26 13:58 空気力学の詩阅读(270) 评论(0) 推荐(0) 编辑

hl666

公告