- 博客(28)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 洛谷 P3119 [USACO15JAN]草鉴定Grass Cownoisseur 题解
一、题目：NOI.AC二、思路：莫队模板题。理论上莫队只能过30分，但这道题由于数据太水，莫队+卡常数就能过去。同时也说明了莫队算法的优秀。在这里介绍一下莫队算法如何卡常数。普通排序：bool cmp(query a,query b){ return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;}（奇偶性）卡常数排序：（比普通...
2018-09-23 22:18:37
309
原创 洛谷 P1726 上白泽慧音 题解
一、题目：洛谷原题二、思路：闲扯句废话，从今开始我要刷洛谷试炼场了！那么言归正传，这道题明显是个有向图的tarjan好嘛。注意按照字典序输出，其他也没什么。三、代码：//自认为很优美的代码：#include<iostream>#include<cstdio>#include<vector>#include<algorithm>...
2018-09-21 20:44:58
207
原创 洛谷 P1858 多人背包 题解
一、题目：洛谷原题二、思路：在01背包的基础上加一维k，即f[i][j][k]f[i][j][k]f[i][j][k]表示前i件物品，体积为j的k次优解。那么我们考虑怎样转移。我们当前有两个序列，一列是不选当前物品，另一列是选当前物品，而且这两个序列是有序的。所以我们可以使用归并排序的思路，进行转移。可以省掉i那一维。口头说不太能说清楚，看代码就明白了。三、代码：#include...
2018-09-20 23:20:19
257
原创 洛谷 P3384 【模板】树链剖分 题解
一、题目：洛谷原题二、代码：//树链剖分模板，没啥思路可讲。#include<iostream>#include<cstdio>using namespace std;inline int read(void) { int x = 0, f = 1; char ch = getchar(); while (ch<'0' |...
2018-07-18 21:20:10
200
原创 Vijos 1448 校门外的树 题解
一、题目：Vijos原题二、思路：左右括号法。 对于每次操作[a,b][a,b][a,b]，将位于aaa的左括号个数加一，位于bbb的有括号个数加一。 对于每次查询[a,b][a,b][a,b]，定义XXX等于111到bbb的左括号个数，YYY等于111到a−1a−1a-1的有括号个数，答案即为X−YX−YX-Y。 当然可以用树状数组，但此题数据巨水，暴力枚举就过去了。...
2018-07-16 21:31:59
347
原创 浙江诸暨培训心得&总结
作者：岸芷汀兰day1今天是来到海亮教育园区的第一天，心情非常得开心和激动。迅速熟悉了环境之后，开始了紧张的学习和交流。上午：我的天！考试！考搜索！幸亏我的搜索功底还比较扎实，不至于爆零。用了两个小时时间写了第三题的暴力，用一个小时时间调试。蒟蒻的悲哀。不过令我欣慰的是，那道题我拿了最高分，得分的一共就两名学生，一位10分，而我30分。233下午：老师讲得非...
2018-07-05 09:52:45
634
2
原创 洛谷 P2296 寻找道路 题解
一、题目：洛谷原题二、思路：在上一篇中，我讲解了暴力做法，接下来讲正解。 首先，将图取反。 然后从终点开始BFS，标记终点可以到达的点（即原图中可以到达终点的点）。 接着枚举每一个没标记的点x，再枚举x点可以到达的点y（即原图中到达x点的点），如果y点已被标记，说明y点并不合法，删除。 最后SPFA（或BFS）求解。三、代码：#include&lt;iostre...
2018-06-25 13:08:36
247
原创 洛谷 P2296 寻找道路 题解
一、题目：洛谷原题二、思路：在上一篇中，我讲解了暴力做法，接下来讲正解。 首先，将图取反。 然后从终点开始BFS，标记终点可以到达的点（即原图中可以到达终点的点）。 接着枚举每一个没标记的点x，再枚举x点可以到达的点y（即原图中到达x点的点），如果y点已被标记，说明y点并不合法，删除。 最后SPFA（或BFS）求解。三、代码：#include<iostre...
2018-06-25 13:08:25
128
原创 【bf】洛谷 P2296 寻找道路 暴力
一、题目：洛谷原题二、思路：这是暴力做法，正解请看下一篇。 floyd（传递闭包）+ SPFA。 用传递闭包标记哪些点和终点联通，然后跑SPFA，在判断点是否入队是增加一条判断条件——是否与终点连通。 Tips：在这道题中，SPFA的实质是BFS，我习惯叫它为SPFA。注意起点的特判。 得分：60分。三、代码：#include&lt;iostream...
2018-06-25 13:01:00
174
原创 【bf】洛谷 P1850 换教室 暴力
一、题目：洛谷原题二、思路：爆搜。 暴力枚举要换的教室，计算期望值，不断更新答案。 我写了两个DFS函数。第一个用来枚举换的教室，第二个用来算期望值，写的很丑，望见谅。 得分：80分。233三、补充：补充一下递归实现指数型枚举的模板。 这等价于每个整数可以选或不选，所有可能的方案总数共有2n2n2^n种。vector<int>chos...
2018-06-16 12:50:21
289
原创 洛谷 P2827 蚯蚓 题解
作者：岸芷汀兰一、题目：洛谷原题二、思路：1. 80分做法优先队列 用priority_queue直接模拟即可。 需要注意的是，“其余蚯蚓的长度都会增加 q”的处理：其余增加q，两条不变，等价于两条减小q，其他不变。这样，每次分完一条蚯蚓后，将分成的两条蚯蚓的长度都减去q，同时更新删掉的总长度（del），那么原本的长度=优先队列中的长度+del。 代码：#incl...
2018-06-08 19:49:28
550
原创 洛谷 P3953 逛公园 题解
一、题目：洛谷原题二、思路：记忆化搜索。 首先，用SPFA预处理最短路。 设f[u][k]f[u][k]f[u][k]表示从起点到u节点比最短路长k的路径总数，则显然有f[u][k]=∑vv∈u的前驱f[v][dis[u]+k−w−dis[v]]f[u][k]=∑vv∈u的前驱f[v][dis[u]+k−w−dis[v]]f[u][k]=\sum_v^{v \in u的前驱} ...
2018-06-06 19:26:38
315
原创 洛谷 P4035 [JSOI2008]球形空间产生器 题解
作者:岸芷汀兰一、题目：洛谷原题二、思路：高斯消元。 求出一个点(x1,x2,...,xn)(x1,x2,...,xn)(x_1,x_2,...,x_n)，使得： ∑j=0n(ai,j−xj)2=C∑j=0n(ai,j−xj)2=C\sum_{j=0}^n(a_{i,j}-x_j)^2=C 把方程转化一下，变量放在左边，常数放在右边，然后高斯消元就可以了。 技巧：位运算...
2018-06-03 12:44:04
188
原创 洛谷 P3952 时间复杂度 题解
作者：岸芷汀兰一、题目：洛谷原题 二、思路：很显然是一道大模拟题，数据结构用栈。 但坑点比较多，先来看一下我的惨痛经历。 主要有以下坑点：字符串的读入；时间复杂度是取最大值；判错（包括变量的判重，我用了STL中的set）三、代码：#include<iostream>#include<cstdio>#include...
2018-06-03 12:35:24
489
原创 洛谷5月月赛 T2 偷上网 题解
作者：岸芷汀兰：一、题目:洛谷原题二、思路：暴力搜索出奇迹。 随机大法出奇迹。 这道题真的必须用随机。每次随机一个点，判断一下是否可行，限制一下循环次数，如果随机了1000次仍不行，输出GG。注意精度问题。三、代码：#include&lt;iostream&gt;#include&lt;cstdio&gt;#include&lt;cmath&gt...
2018-05-24 13:18:58
263
原创 洛谷 P1247 取火柴游戏 题解
作者：岸芷汀兰一、题目：洛谷原题二、思路：这可能是博弈论最简单的题了。 在这里，只简单的唠叨几句。 定理 NIM博弈先手必胜，当且仅当A1 xor A2 xor A3 xor … xor An ≠0。证明略。三、代码：//写得太丑#include&lt;iostream&gt;#include&lt;cstdio&gt;#incl...
2018-05-16 13:08:13
231
原创 洛谷 P1113 杂务 题解
作者：岸芷汀兰一、题目：洛谷原题二、思路：第一眼看题，立即想到拓扑排序。 再看一下标签——“递推”，真没看出和递推有何关系！ 言归正传，咳咳。入度为0的点的权值就是它的时间，入读不为0的点的权值是它的所有前驱的权值的最大值加上他的时间，遇到出度为0的点，计算完他的权值后，更新一下答案。（有点贪心的意思。） 上代码。三、代码：#include<iost...
2018-05-14 13:10:20
431
原创 洛谷 P4147 玉蟾宫 题解
作者：岸芷汀兰一、题目：题目链接二、思路：单调栈裸题。 预处理：s[i][j]表示(i,j)向上有几个连续的”F”。 需要用单调栈统计两个数组：l[i][j]表示s[i][j]的左边第一个比s[i][j]小的位置，r[i][j]表示s[i][j]的右边第一个比s[i][j]小的位置。 那么此时矩形的面积就是(r[i][j]-1-l[i][j])*s[i][j]。 具体细节看代码。 写得太丑
2018-05-06 10:09:14
311
原创 洛谷 P3391 【模板】文艺平衡树（Splay）
作者：岸芷汀兰一、题目洛谷原题二、思路类似线段树的维护标记。三、代码#include<iostream>#include<cstdio>using namespace std;inline int read(void) { int x = 0, f = 1; char ch = getchar(); while...
2018-04-19 13:12:01
250
3
原创 Vijos 1304 回文数 题解
题目Vijos原题思路这就是一道大模拟!其中涉及一些高精度运算。 所需函数：判断是不是回文数（judge）高精度相加（myplus）注意：字符串的运用进位逆序存储我的源代码//Vijos 1304#include<iostream>#include<cstdio>typedef long long ll;...
2017-12-05 13:07:41
339
原创 2017年NOIP普及组第三题“chess”题解
2017年NOIP普及组第三题“chess”题解作者：岸芷汀兰题目：链接：洛谷原题思路：很遗憾，这道题我没能在考场中写出来，在这里，向我的教练及朋友道歉，我让你们失望了。（QAQ）50分：普通的dfs。 80分：普通的bfs。 100分：记忆化搜索。 那么记忆化搜索有什么用呢？当前答案大于当前节点的最小花费时，continue。所以要记录每个节点的最小...
2017-11-18 18:40:56
664
原创 洛谷P1095守望者的逃离 题解
洛谷P1095守望者的逃离 题解——作者：岸芷汀兰一、题目：链接：洛谷原题二、思路：贪心加动规。 以时间为状态（以路程为状态不好做）。首先考虑闪烁法术，在魔法值够用的情况下尽可能的使用闪烁法术。当魔法值不够用时，停下休息。（第一个循环） 其次，考虑跑步。如果上一秒的路程加上17大于这一秒的路程，用这个路程更新答案。由于此题满足无后效性原则，因此这种方案是正确的。...
2017-10-30 13:00:34
660
原创 NOIP普及组2009年 细胞分裂 题解
NOIP普及组2009年 细胞分裂 题解——作者：岸芷汀兰一、题目链接：洛谷原题题目描述 Hanks 博士是 BT (Bio-Tech，生物技术) 领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。Hanks 博士手里现在有 N 种细胞，编号从 1~N，一个第 i 种细胞经过 1 秒钟可以分裂为Si个同种细胞（Si为正整数）。现在他需要选取某种细胞的...
2017-10-29 21:15:04
1593
原创 洛谷P1067多项式输出 题解
洛谷P1067多项式输出 题解——作者：岸芷汀兰一、题目题目描述一元 n 次多项式可用如下的表达式表示：其中，aixi称为 i 次项，ai 称为 i 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：多项式中自变量为 x，从左到右按照次数递减顺序给出多项式。多项式中只包含系数不为 0 的项。如果多项式 n 次项系数为...
2017-10-28 18:52:10
590
1
原创 NOIP2004普及组 花生采摘题解
——作者：岸芷汀兰前言：本道题坑极多，我提交了三次才通过了这道题，所以这道题给我的启示是：小心，小心，再小心！思路：贪心加模拟。运用贪心手段确定到花生地的第一步的位置，再用一个循环模拟摘花生，两个花生的最短距离：abs（x1-x2)+abs(y1-y2)，结束条件是时间用完了。最后输出answer就可以了。代码：//luogu P1086#include<iostream>#inc...
2017-10-13 21:10:34
1178
原创 洛谷P3931“tree”题解
洛谷P3931“tree”题解——作者：岸芷汀兰一、题目：题目背景冴月麟和魏潇承是好朋友。题目描述冴月麟为了守护幻想乡，而制造了幻想乡的倒影，将真实的幻想乡封印了。任何人都无法进入真实的幻想乡了，但是她给前来救她的魏潇承留了一个线索。她设置了一棵树（有根）。树的每一条边上具有割掉该边的代价。魏潇承需要计算出割开这棵树的最小代价，这就是冴月麟和魏潇承约...
2017-10-10 12:42:08
503
原创 洛谷P1842奶牛玩杂技 题解
一、题目题目背景Farmer John 养了N(1<=N<=50,000)头牛，她们已经按1~N依次编上了号。FJ所不知道的是，他的所有牛都梦想着从农场逃走，去参加马戏团的演出。可奶牛们很快发现她们那笨拙的蹄子根本无法在钢丝或晃动的的秋千上站稳（她们还尝试过把自己装在大炮里发射出去，但可想而知，结果是悲惨的） 。最终，她们决定练习一种最简单的杂技：把所有牛都摞在一起， 比如...
2017-10-05 14:32:03
995
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人