空気力学の詩

2018年2月24日

摘要：上课讲了下数据结构，因为暂时没找到分块的板子题，a56爆大奖在线娱乐做一下这道题加深一下对树状数组的理解。题意就是求逆序对，从逆序对的定义就可以看出，方法有两种：归并 or 树状数组。感觉树状数组更高级一点，写起来也比较容易（其实是不会归并）在这里由于a[i]太大（0~999999999），因此离散化一下，也阅读全文

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

EZ 2018 1 21 2018noip第五次膜你赛

摘要：这次分数普遍偏高，而且yu'ben'ao又AK了！但是最后一题莫名爆0让a56爆大奖在线娱乐很感伤啊（搓了1个多小时的20分暴力）！难度偏低，主要是T2没剪枝，炸了3个点。 T1 这种SB题恐怕是千年难遇了，PJ 的难度稍微观察一下就能发现ans=max{a[i]+i-1} 缅怀yekehe60分 CODE T 阅读全文

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

POJ 1068&&2632&&1573&&2993&&2996

摘要：这次的题目是著名的模拟（水逼）专题题目难度都不大，思维也不深，就是一个字——烦同时很多题目都有很多坑点 1608 题意是告诉你一个只有（）的字符串（且匹配正确），a56爆大奖在线娱乐）的左边有几个（，让你求每一对括号中包含了几对括号。思路很水，模拟出原字符串再开个栈做一次就行了。 CODE 2632 就是一堆阅读全文

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

2018年2月12日

POJ 3278&&2049&&3083

摘要：这次的题目叫图的深度&&广度优先遍历。然后等a56爆大奖在线娱乐做完了题发现这是DFS&&BFS爆搜专题。 3278：题目是经典的FJ，他要抓奶牛。他和牛（只有一头）在一条数轴上，他们都站在一个点上（坐标为0~1e5）。假设FJ的位置为x，他每次可以去x+1,x-1,x*2的地方。问他最少走几次才能抓到他的牛（牛不阅读全文

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

POJ 1328&&2109&&2586

摘要：这次是贪心（水笔贪心）专题。先看1328，一道经典的导弹拦截（或者是打击？不懂背景）。大意是说在一个坐标系中有一些点（或是导弹），你要在x轴上建一些东西，它们可以拦截半径为d的圆范围中的点。问最少修建的个数，不可能输出-1。经典问题了哈，主要是把二维的转成一维。对于a56爆大奖在线娱乐要拦截的点以d为半径画阅读全文

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

2018年2月10日

POJ 2965&&1753

摘要：最近由于复习备考（然而考得还是很炸），很久没打题目了。现在开始刷寒假作业，不得不搞POJ 话说没有中文真的好烦啊！先看1753 题目大意是说在一个4*4的格子中有黑白两色的棋子，你可以翻动其中的棋子但同时它四周（上下左右）的棋子也会被翻动，问你最少要翻几次才能翻成全黑或全白。首先要想到，一个棋子阅读全文

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

2018年1月18日

EZ 2018 01 14 2018noip第四次膜你赛

摘要：这次惨烈的炸了个精光（只有20），然后对a56爆大奖在线娱乐的OI想法造成了巨大的转折。（以上有点作，其实a56爆大奖在线娱乐只是再也不用vector存图了而已（用邻接表））难度很不均匀，而且题型很狗（还有结论题？？？） T1 坑人结论题，想出来100，没有就爆零 a56爆大奖在线娱乐和这道题杠了一个半小时，然后他们猥琐地告诉a56爆大奖在线娱乐结论——要么四边�a56爆大奖在线娱乐� 阅读全文

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

LCA的一些算法

摘要： LCA，就是求树上�a56爆大奖在线娱乐饬降愕淖罱沧嫦� （本题图片与代码均为Luogu3379）方法a56爆大奖在线娱乐好像讲过一个，这次把主要的三个一起讲一讲 <1> 倍增（O（n log n）） a56爆大奖在线娱乐们先考虑最基本的LCA，记录每一个点的父节点和深度。对于两个点x，y，先将它们调到同一高度（令dep[x]>dep[y]，即把阅读全文

posted @ 2018-01-18 19:15 空気力学の詩阅读(207) 评论(0) 推荐(0) 编辑

2018年1月13日

Luogo P2324 [SCOI2005]骑士精神

摘要：所有想练习A*的人都先来敲一下这道题吧。数据范围即便只有5*5，但朴素的爆搜还是会超时。因此考虑剪枝。对于这道题，肯定只要进行最优化剪枝，判断现在走的步数+剩下最少要走的步数，如果大于ans或者15就return；那么，估价函数怎么写？利用小学生的思想，将目前的图与目标状态对比一下，还有多阅读全文

posted @ 2018-01-13 12:10 空気力学の詩阅读(145) 评论(1) 推荐(0) 编辑

Luogu P2483 【模板】k短路（[SDOI2010]魔法猪学院）

摘要：说实话，看到这道题的洛谷评级a56爆大奖在线娱乐傻了（传说中的最高难度）然后看完题目才确定这真的是一道k短路的裸题。也就敲了个A*吧，15分钟竟然没有调试一遍过。欧洲玄学。看题目，主要是找几条从1走到n的路加起来小于等于给定的E即可。 a56爆大奖在线娱乐就是一道k短路。 A*和DJ很像，就是把堆的比较操作从当前路径长度+该阅读全文

posted @ 2018-01-13 10:59 空気力学の詩阅读(200) 评论(0) 推荐(0) 编辑

2018年1月11日

EZ 2017 01 07 t

摘要：这名字诡异（然而就是这样）这次主要是yekehe和yu‘ao都来了，a56爆大奖在线娱乐很开心的讨论（上了200）。但是，yu’ao dalao又AK了！（666666）不过总体难度也不高，主要是T3没思路。 T1 二分或桶 ·如果你不会这道题，出门右转找傅哥去。去年蒟蒻时期的噩梦啊。然而只是一道PJ的水题阅读全文

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

EZ 2017 12 30 2018noip第二次膜你赛

摘要：去年的比赛了，然而今天才改好。总体难度适中，有大佬AK。主要是自己SB第二题没想出来，然后又是可怜的100来分。 T1 一道二分+数学的题目。 a56爆大奖在线娱乐们可以二分叫的次数，然后用公式（等差数列，公差都是zi）算一个最大的可行的数目。最后把多余的加上去即可。注意当xi，yi都等于0的情况。 CODE 阅读全文

posted @ 2018-01-11 19:38 空気力学の詩阅读(218) 评论(1) 推荐(0) 编辑

2018年1月5日

Luogu P3379 【模板】最近公共祖先（LCA）

摘要：这就是一道很朴素的LCA题。算法应该主流的有三种：DFS序+RMQ；倍增；Tarjan；其中前面两个是在线算法，O（n log n），后一个是离线的，复杂度也是线性的O（n+q）。 a56爆大奖在线娱乐对于这道题n，q都偏大的情况下还是选择了Tarjan（后两种a56爆大奖在线娱乐不会）。简单说一下Tarjan的思想，对整个树阅读全文

posted @ 2018-01-05 13:20 空気力学の詩阅读(214) 评论(2) 推荐(0) 编辑

2018年1月4日

Luogu P1613 跑路

摘要： Luogu在博客里的第20题！这其实是一个想明白的就很简单的问题。首先，a56爆大奖在线娱乐们可以否决那些直接跑最短路然后看能拆出几个2^k次方的算法。其次，Floyd求最短路大家肯定都知道，但是求传递闭包的方法也是利用了Floyd。 a56爆大奖在线娱乐，这道题的大致思想就是Floyd两次！ a56爆大奖在线娱乐们可以先把题目中给定的点先连一阅读全文

posted @ 2018-01-04 18:34 空気力学の詩阅读(151) 评论(0) 推荐(0) 编辑

2018年1月2日

各类常见模板更新（不定期更新）

摘要：俗话说得好：模板敲得好，NOIP炸不了。因此为了防止比赛时想到了题解而敲不出来的情况，a56爆大奖在线娱乐们要坚持刷模板。（争取每次上线的话打1~2个吧）（排名顺序没有任�a56爆大奖在线娱乐庖澹氲绞裁葱词裁矗� SPFA（对应题目Luogu P3371 【模板】单源最短路径） Dijstra（堆优化）（对应题目Luogu P3 阅读全文

posted @ 2018-01-02 19:28 空気力学の詩阅读(436) 评论(4) 推荐(1) 编辑

Luogu P1196 [NOI2002]银河英雄传说

摘要：一年没写博客了（滑稽）。这道题很玄学，导致自己都有一个坑人的问题求解。如果有大佬有能力求帮助：https://www.luogu.org/discuss/show?postid=30231 再来讲一下a56爆大奖在线娱乐对这道题的理解吧。首先，对于判断两个数是否在同一列战舰中，a56爆大奖在线娱乐们只需要朴素的并查集就可以。但这阅读全文

posted @ 2018-01-02 18:42 空気力学の詩阅读(196) 评论(0) 推荐(0) 编辑

2017年12月28日

SCC的奇葩算法——Kosaraju

摘要：不会Tarjan，难道就不能与邪恶的SCC作斗争了吗？祭出Kosaraju。一些变量名的意义： a[N] 原图的vector存储 b[N] 原图的所有边反向vector存储 s dfs得出的拓扑序列栈 c[[N] a56爆大奖在线娱乐点的SCC编号算法框架： 1.将原图做一遍类似于拓扑的dfs，越早访问的顶点阅读全文

posted @ 2017-12-28 20:10 空気力学の詩阅读(1050) 评论(1) 推荐(0) 编辑

Luogu P1726 上白泽慧音

摘要：这显然是一道求强连通分量（SCC）的题目。只要你正常，都知道应该写Tarjan。然后（假装会写Tarjan），其实a56爆大奖在线娱乐当然不会。但是求SCC还有另一个算法。复杂度和Tarjan一样，只不过常数大了点而且不为人所知而已。蓝书和挑战程序竞赛上都有这个算法，好像叫Kosaraju。是不是很拽的感觉。阅读全文

posted @ 2017-12-28 19:54 空気力学の詩阅读(182) 评论(0) 推荐(0) 编辑

2017年12月26日

HW 2017 12 17可禾大佬神题

摘要：好不容易搞来的题目，不写一写怎么行呢。不过难度真心不高（一小时K掉），都是老题+暴力题，没有欧洲玄学。再说一句，这试卷是叶可禾出的吧。 T1 好老的题目，看到有多组数据a56爆大奖在线娱乐还怕了，以为有更流弊的算法。没想到减了数据范围。首先把边sort一遍，因为要求，max-min最小，a56爆大奖在线娱乐枚举最短边，然后向后阅读全文

posted @ 2017-12-26 18:58 空気力学の詩阅读(259) 评论(1) 推荐(0) 编辑

2017年12月24日

Luogu P1198 [JSOI2008]最大数

摘要： a56爆大奖在线娱乐会用高级（？？？）的单调栈来打这道题吗？线段树即可水过。假设这个数列刚开始所有数都是0，然后a56爆大奖在线娱乐们每次只要进行一个点的修改和区间求和即可。这不就是线段树大法。只要用一个len记录一下当前数列长度即可（刚开始智障把求最大数打成求和了，还过样例了） CODE 阅读全文

posted @ 2017-12-24 14:24 空気力学の詩阅读(185) 评论(1) 推荐(0) 编辑

Luogu P1525 关押罪犯

摘要：这又是一道坑题！思想进行了大幅转变，并查集炸了之后终于搞出了a56爆大奖在线娱乐奇葩的算法，终于卡时间A了。把思路按顺序理一理。先把边从大到小排序一下。 <1> 看完题目，a56爆大奖在线娱乐去这不是并查集模板么吗，马上敲了个裸并查集，判断两个点如果之前已经联通了，直接退出输出当前值即可。 CODE（WA）帅气得搞了50分· 阅读全文

posted @ 2017-12-24 09:55 空気力学の詩阅读(198) 评论(0) 推荐(0) 编辑

2017年12月22日

Luogu P1082 同余方程

摘要：怎么说呢，想通了就是一道模板题了。自己的数论也很烂，但竟然没有看题解搞了过去（奇迹）. 首先对于ax ≡ 1 (mod b)；观察数据范围可以发现b≥2，a56爆大奖在线娱乐转化成 ax mod b=1 从mod的定义中a56爆大奖在线娱乐们可以看出原方程就是ax-by=1（y是整数）因为一定有解，然后由裴蜀定理可以知道gcd 阅读全文

posted @ 2017-12-22 20:18 空気力学の詩阅读(132) 评论(1) 推荐(0) 编辑

EZ 2017 12 17初二初三第一次膜你赛

摘要：以后平时练习还是写一写吧。（题目搞来搞去太烦了，直接PDF存起来） T1 水题（???），主要是数据水，正解是设一个阙值，然而根本没人打。（暴力出奇迹） CODE T2 猥琐数学题（？？？）一定要想到，如果有解那么h[i]+l[j]≡k-a[i][j](mod k) 然后可以每次枚举第一列的数来当阅读全文

posted @ 2017-12-22 13:44 空気力学の詩阅读(254) 评论(1) 推荐(0) 编辑

2017年12月15日

BZOJ 1053: [HAOI2007]反素数ant

摘要：还以为是什么神坑数论题。看到题，第一眼想到φ，然后暴力。然后发现暴力其实是有可能的啦。一个数的因数个数=所有质因数的次数+1,然后乘起来。例如 60=2^2*3^1*5^1,so g(60)=(2+1)*(1+1)*(1+1)......（后面都是1）=12。然后a56爆大奖在线娱乐们就要构造（而不是枚举）阅读全文

posted @ 2017-12-15 19:48 空気力学の詩阅读(123) 评论(0) 推荐(0) 编辑

BZOJ 2208: [Jsoi2010]连通数

摘要： BZOJ的题目，就是高大上。然而是一道入门（稍微难一点）的水题。先读题，发现可以tarjan，对，这很适合tarjan。然后看数据范围，这不就是。。。暴力枚举+BFS找点。水题不做多解释。 CODE 阅读全文

posted @ 2017-12-15 13:34 空気力学の詩阅读(171) 评论(0) 推荐(0) 编辑

hl666

公告