- 博客(104)
- 收藏
- 关注
RSS订阅
原创 NOI2016区间
传送门题解 Step 1 首先想如果知道了是哪些区间 怎么判断使得这 m个区间共同包含至少一个位置呢方法:区间打标记每次给一个区间，就把这个区间的值+1 如果有一个地方超过了m次，显然m个区间至少共同包含一个位置 这个时候就需要一个可以支持区间修改，查询区间最大值的数据结构那么就是线段树了 Step 2 如何知道选那些区间呢？首先对于每个区间 [L,R
2017-07-21 14:35:43
492
原创 洛谷P1210回文检测
题目描述据说如果你给无限只母牛和无限台巨型便携式电脑(有非常大的键盘),那么母牛们会制造出世上最棒的回文。你的工作就是去寻找这些牛制造的奇观(最棒的回文)。在寻找回文时不用理睬那些标点符号、空格(但应该保留下来以便做为答案输出),只用考虑字母’A’-‘Z’和’a’-‘z’。要你寻找的最长的回文的文章是一个不超过20,000个字符的字符串。我们将保证最长的回文不会超过2,000个字符(在除去标点符号、
2017-07-15 20:00:06
436
原创 Manacher算法
Manacher算法Manacher 算法 又名 ==马拉车算法==也是回文自动机此算法专门解决求回文串的问题求回文串的问题 首先有暴力做法1. Brute-force 解法枚举每一个子串 判断是否回文 此方法当然是最好想到的暴力但是时间复杂度显然是O(n^3)的 明显数据稍微大一点就不可过2. Brute-force 优化版此时枚举每个中点向左右扩展 奇数个和偶数个分开讨论此时的时间复杂度为O(
2017-07-15 19:59:44
387
原创 2017.7.15 NOIP模拟
全国信息学分区联赛模拟试题（七）【试题概览】试题名称 | 塔 | 圆 | 猴子 | 山| |—|—|—|—|—| 提交文件 | tower |circle| monkey |hill 输入文件 |tower.in |circle.in |monkey.in |hill.in 输出文件 |tower.out| circle.out| monkey.out |hill.out 时间限制 |1
2017-07-15 19:56:58
491
原创 2017.7 13 NOIP模拟赛
2017.7 13 模拟全国信息学分区联赛模拟试题（五）本人分数：190 (其实120 小小改动了一下才190)【试题概览】 试题名称 序列 矩形 锁 看守 提交文件 sequence rectangle lock jail 输入文件 sequence.in rectangle.in lock.in jail.in 输出文件 sequ
2017-07-14 20:32:37
428
原创 [笔记]: Tarjan算法求有向图的强连通分量
所谓Tarjan算法建议学习算法竞赛入门经典训练指南中的这一章对此的介绍因为我的解释需要中文十级才看的懂核心就是dfs中记录一个二元组一个叫dfn（就是算法训练入门经典中的pre）还有一个叫lowdfn就是在图中dfs时的时间戳low则是这个点能访问回到的点的dfn的最小值举个例子例如1->45此时的1 4 5 dfn值分别为123 当访问到5的时候lo
2017-07-07 21:12:16
358
原创 [bzoj1572]: [Usaco2009 Open]工作安排Job
1572: [Usaco2009 Open]工作安排JobTime Limit: 10 Sec Memory Limit: 64 MBSubmit: 1283 Solved: 590[Submit][Status][Discuss]DescriptionFarmer John 有太多的工作要做啊！！！！！！！！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位
2017-06-30 21:16:00
407
原创 [noip2002]: 均分纸牌
描述有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
2017-06-30 21:10:05
501
原创 [noip2010]：导弹拦截
描述经过11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0 时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。 某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦
2017-06-30 20:59:03
589
原创 [poj1830]: 开关问题
开关问题Time Limit: 1000MS Memory Limit: 30000KTotal Submissions: 8666 Accepted: 3405Description有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系
2017-06-30 20:50:02
572
原创 [笔记]: 高斯消元
高斯消元是个求解线性一元多次方程的好办法eg：求逆矩阵具体例子例如，考虑下面的矩阵为了找到这个矩阵的逆矩阵，扩充以下矩阵：通过计算，可以将增广矩阵转换为简化行阶梯形式，即把左边转化为单位矩阵：求得B为A的逆矩阵。像这个样子 把方程列成一个矩阵 矩阵的前n个元素是系数
2017-06-29 21:19:04
285
原创 [hdu5698]: 瞬间移动(两种方法求组合数)
welcome to my blog!!!瞬间移动Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1178 Accepted Submission(s): 583Problem Desc
2017-06-28 20:29:23
821
原创 [hdu1576]: A/b (扩展欧几里得)
A/BTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5900 Accepted Submission(s): 4620Problem Description要求(A
2017-06-28 10:40:26
252
原创 [bzoj2751]: [HAOI2012]容易题(easy)（快速幂）
2751: [HAOI2012]容易题(easy)Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2208 Solved: 931[Submit][Status][Discuss]Description为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下：有一个数列A已知对于所有的
2017-06-27 21:04:59
351
原创 [bzoj2186]: 莎拉公主的困惑（欧拉函数+乘法逆元）
2186: [Sdoi2008]沙拉公主的困惑Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 4233 Solved: 1476[Submit][Status][Discuss]Description 大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M
2017-06-27 20:56:13
471
原创 [笔记]: 欧拉函数线性筛法
和质数的线性筛法差不多 多加了几句话用到了几个定理 请自行百度这里求的欧拉函数 是指在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）1.如果这个数是质数 那么φ(i)=i-12.欧拉函数是积性函数 欧拉函数是积性函数——若m,n互质， 特殊性质：当n为奇数时， , 证明与上述类似。若n为质数则
2017-06-27 19:04:43
365
原创 [poj1061]: 青蛙的约会（扩展欧几里得）
青蛙的约会Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 115219 Accepted: 23709Description两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰
2017-06-26 19:25:50
327
原创 [noip2012]: 同余方程
首先转一下别人写的http://blog.csdn.net/zhjchengfeng5/article/details/7786595扩展欧几里德算法 谁是欧几里德？自己百度去 先介绍什么叫做欧几里德算法 有两个数 a b，现在，我们要求 a b 的最大公约数，怎么求？枚举他们的因子？不现实，当 a b 很大的时候，枚举显得那么的naïve ，那怎
2017-06-26 15:48:39
644
原创 [bzoj1934]: [Shoi2007]Vote 善意的投票
1934: [Shoi2007]Vote 善意的投票Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 2136 Solved: 1341[Submit][Status][Discuss]Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有
2017-06-26 10:14:02
226
原创 [bzoj1934]: [ZJOI2009]狼和羊的故事
1412: [ZJOI2009]狼和羊的故事Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3105 Solved: 1567[Submit][Status][Discuss]Description“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊
2017-06-26 09:46:00
270
原创 [bzoj3175] [Tjoi2013]攻击装置（最大独立集）
3175: [Tjoi2013]攻击装置Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1129 Solved: 551[Submit][Status][Discuss]Description给定一个01矩阵，其中你可以在0的位置放置攻击装置。每一个攻击装置（x,y）都可以按照“日”字攻击其周围的 8个位置（x-1,y-2）
2017-06-23 18:48:17
309
原创 [bzoj2150] 部落战争(二分图最小边覆盖)
2150: 部落战争Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 1021 Solved: 572[Submit][Status][Discuss]Descriptionlanzerb的部落在A国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。 A国是一个M*N的矩阵，其中某些地方是城镇，某些地方
2017-06-23 15:34:45
481
原创 [bzoj2424] 订货
2424: [HAOI2010]订货Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1080 Solved: 733[Submit][Status][Discuss]Description某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月
2017-06-23 10:45:16
321
原创 [bzoj1877][SDOI2009]晨跑
1877: [SDOI2009]晨跑Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 2340 Solved: 1255[Submit][Status][Discuss]DescriptionElaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他坚持下来的只有晨跑。 现在给出
2017-06-23 10:02:15
279
原创 [bzoj1221][HNOI2001] 软件开发
1221: [HNOI2001] 软件开发Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1705 Solved: 961[Submit][Status][Discuss]Description某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了
2017-06-23 09:56:48
255
原创 [bzoj1001][BeiJing2006]狼抓兔子
1001: [BeiJing2006]狼抓兔子Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 22620 Solved: 5695[Submit][Status][Discuss]Description现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，而且现在的兔子还比较笨，它们只有两个
2017-06-23 08:18:12
329
原创 [bzoj1834][ZJOI2010]network 网络扩容
1834: [ZJOI2010]network 网络扩容Time Limit: 3 Sec Memory Limit: 64 MBSubmit: 3194 Solved: 1654[Submit][Status][Discuss]Description给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况
2017-06-23 08:08:54
476
原创 [bzoj1202] 狡猾的商人
1202: [HNOI2005]狡猾的商人Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 3569 Solved: 1717[Submit][Status][Discuss]Description刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了n个月以来的收入情况，其中第i 个月的收入额为A
2017-06-22 21:06:22
238
原创 [笔记]: 差分约束
差分约束系统形如这个样子：X1 - X2 X1 - X5 X2 - X5 X3 - X1 X4 - X1 X4 - X3 X5 - X3 X5 - X4 比如要求满足此条件的 x1x2x3x4x5和的最小值怎么做呢? 此时 把式子传化一下 如 X4-X5>=3 (一定带等于) 再变成 X4>=X5+3如求最小值 就是大于等于 小于反之然
2017-06-22 21:00:47
234
原创 [bzoj1059]矩阵游戏
1059: [ZJOI2007]矩阵游戏Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 4731 Solved: 2255[Submit][Status][Discuss]Description 小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N*N黑白方阵进行（如同国际象棋
2017-06-21 16:42:02
291
原创 [笔记]:二分图最大匹配匈牙利算法
二分图最大匹配 km算法模板一个mat数组记录匹配的对象 一个flag数组记录对于当前点是否已经匹配flag数组记得每次清空 至于函数部分有个递归的过程//二分图最大匹配KM算法 /*8 5 51 11 22 12 23 34 34 55 5*/#include#include#include#include#include#include#in
2017-06-21 16:37:07
430
原创 [bzoj 1305&1433]最大流练习题
1305: [CQOI2009]dance跳舞Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 3330 Solved: 1409[Submit][Status][Discuss]Description一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲
2017-06-20 16:53:47
333
原创 [bzoj 1066][SCOI2007]蜥蜴
Description在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为1，蜥蜴的跳跃距离是d，即蜥蜴可以跳到平面距离不超过d的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减1（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为1，则蜥蜴离开后消失。以后其他蜥蜴不能
2017-06-20 08:10:15
212
原创 [笔记]: 网络流
详细介绍自行百度下面是两个模板都是poj1273模板题1.E_K 增广路算法//http://poj.org/status#include#include#include#include#include#include#includeusing namespace std;const int N=205;const int inf=1<<29;int n,
2017-06-19 16:45:52
214
原创 [bzoj 1614][Usaco2007 Jan]Telephone Lines架设电话线
1614: [Usaco2007 Jan]Telephone Lines架设电话线Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1703 Solved: 725[Submit][Status][Discuss]DescriptionFarmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ
2017-06-16 20:10:15
312
原创 [bzoj1295]: [SCOI2009]最长距离
1295: [SCOI2009]最长距离Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1576 Solved: 853[Submit][Status][Discuss]Descriptionwindy有一块矩形土地，被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B，那么两个格子的距离
2017-06-16 19:19:50
276
原创 [codevs1269] 匈牙利游戏
题解 借鉴了hzwer和网上的做法。。此题是个次短路的模板题分三种情况更新1.可以更新最短路 ：原最短路变为次短路 更新最短路2.可以更新次短路但不能更新最短路 ：更新次短路3.次段路也可以更新次段路：那么更新次短路#include#include#include#include#include#include#include#define N 20001#
2017-06-16 16:43:50
293
原创 [CF] Educational Codeforces Round 23
第一次打CF 有点小激动这场比赛是2017.6.15 晚上11.05开始的本人巨弱。。 瞬间被秒杀只A了第一个水题 第二题迷迷糊糊就错了花了好久都没改出来 以为自己方法错了 果断放弃 就睡了。。只好在第二天早上重新请教大犇 重新做一遍了（某大神：这些题很简单啊 我大概做个5。6题没问题吧） QwQA. Treasure Hunttime limit pe
2017-06-16 14:57:37
393
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人