- 博客(133)
- 收藏
- 关注
RSS订阅原创 P3379 【模板】最近公共祖先（LCA）
题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式： 第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。 输出格式...
2018-12-22 17:32:31
238
原创 P1468 派对灯 Party Lamps
题目描述在IOI98的节日宴会上，我们有N(10<=N<=100)盏彩色灯，他们分别从1到N被标上号码。 这些灯都连接到四个按钮：按钮1：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。按钮2：当按下此按钮，将改变所有奇数号的灯。按钮3：当按下此按钮，将改变所有偶数号的灯。按钮4：当按下此按钮，将改变所有序号是3*K+1(K>=0)的灯...
2018-12-22 08:30:48
316
原创 P3650 [USACO1.3]滑雪课程设计Ski Course Design
题目描述农民约翰的农场里有N座山峰(1<=N<=1000),每座山都有一个在0到100之间的整数的海拔高度。在冬天,因为山上有丰富的积雪,约翰经常开办滑雪训练营。不幸的是,约翰刚刚得知税法在滑雪训练营方面有新变化,明年开始实施。在仔细阅读法律后,他发现如果滑雪训练营的最高和最低的山峰海拔高度差大于17就要收税。因此,如果他改变山峰的高度（使最高与最低的山峰海拔高度差不超过17）...
2018-12-12 17:13:49
186
原创 P1207 [USACO1.2]双重回文数 Dual Palindromes
题目描述如果一个数从左往右读和从右往左读都是一样，那么这个数就叫做“回文数”。例如，12321就是一个回文数，而77778就不是。当然，回文数的首和尾都应是非零的，因此0220就不是回文数。事实上，有一些数（如21），在十进制时不是回文数，但在其它进制（如二进制时为10101）时就是回文数。编一个程序，从文件读入两个十进制数N (1 <= N <= 15)S (0 <...
2018-12-08 16:40:01
212
原创 P1214 [USACO1.4]等差数列 Arithmetic Progressions
题目描述一个等差数列是一个能表示成a, a+b, a+2b,..., a+nb (n=0,1,2,3,...)的数列。在这个问题中a是一个非负的整数，b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p的平方 + q的平方的数的集合,其中p和q为非负整数)S中长度为n的等差数列。输入输出格式输入格式： 第一行: N(3<= N<=25),要找...
2018-12-08 16:39:00
161
原创 P1215 [USACO1.4]母亲的牛奶 Mother's Milk
题目描述农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数， 最初，A和B桶都是空的，而C桶是装满牛奶的。有时，农民把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。写一个程序去帮助农民找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。输入输出格式输入格式： 单独的一行包括三个整数A,B...
2018-12-08 16:38:26
181
原创 P1217 [USACO1.5]回文质数 Prime Palindromes
题目描述因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的)，所以 151 是回文质数。写一个程序来找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数;输入输出格式输入格式： 第 1 行: 二个整数 a 和 b . 输出格式： 输出一个回文质数的列表，一行一个。 ...
2018-12-08 16:37:42
173
原创 P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib
题目描述农民约翰的母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数,举例来说: 7 3 3 1 全部肋骨上的数字 7331是质数;三根肋骨 733是质数;二根肋骨 73 是质数;当然,最后一根肋骨 7 也是质数。 7331 被叫做长度 4 的特殊质数。写...
2018-12-08 16:35:56
280
原创 a
#include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#include<vector>#include<queue>#define N 3009using namespace std;
2018-09-12 17:04:18
127
原创 剑与魔法(dragons
时间限制:1000MS内存限制:131000KB题目描述 万老师听说某大国很流行穿越，于是他就想写一个关于穿越的剧本。 闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般，所以老师从维娜艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类：战役事件（CASE）、穿越回去事件（END）。战役事件可以选择是否参加，参加了之后会获得一定的...
2018-09-08 16:23:10
268
原创 最短路(path)
时间限制:2000MS内存限制:256000KB题目描述 给定一个n个点m条边的有向图，有k个标记点，要求从规定的起点按任意顺序经过所有标记点到达规定的终点，问最短的距离是多少。输入第一行5个整数n、m、k、s、t，表示点个数、边条数、标记点个数、起点编号、终点编号。接下来m行每行3个整数x、y、z，表示有一条从x到y的长为z的有向边。接下来k行每行一个整数表示标记点...
2018-09-08 14:57:00
648
原创 LIS最长上升自序列
描述的数值序列一个我是有序的，如果一个1 < 一个2 <... < 一个Ñ。令给定数字序列（a 1，a 2，...，a N）的子序列为任何序列（a i 1，a i 2，...，a iK），其中1 <= i 1 < i 2 <... < i K <= N.。例如，序列（1,7,3,5,9,4,8）具有有序子序列，例如（1,7），（3,4,...
2018-09-07 20:50:45
291
原创 LIS最长不上升子序列
描述的数值序列一个我是有序的，如果一个1 < 一个2 <... < 一个Ñ。令给定数字序列（a 1，a 2，...，a N）的子序列为任何序列（a i 1，a i 2，...，a iK），其中1 <= i 1 < i 2 <... < i K <= N.。例如，序列（1,7,3,5,9,4,8）具有有序子序列，例如（1,7），（3,4,8）和...
2018-09-07 20:21:25
384
原创 supermarket
题目描述有一个商店有许多批货，每一批货又有N(0<=N<=10^4104 )个商品,同时每一样商品都有收益P_iPi ,和过期时间D_iDi (1<=Pi,DiPi,Di <=10^4104 )，一旦超过了过期时间，商品就不能再卖。你要做的就是求出每批货最多能得到多少收益。输入输出格式输入格式多组数据，每组先给出一个整数N，表示这批货的商品个数。...
2018-08-22 18:37:05
249
原创 CH1602/loj 10050 The XOR Largest Pair
描述 在给定的N个整数A1，A2……AN中选出两个进行xor运算，得到的结果最大是多少？输入格式 第一行一个整数N，第二行N个整数A1～AN。输出格式 一个整数表示答案。样例输入 3 1 2 3 样例输出 3数据范围与约定 对于100%的数据: N<=10^5, 0<=Ai<2^31。CODE#include<c...
2018-08-19 22:05:29
287
原创 家族
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。Input 第一行：三个整数n,m,p，（n<=50000,m<=50000,p<=50000），分别表示有n个人，m个亲戚关系...
2018-08-18 11:47:30
253
原创 合并果子（小根堆 手打）
题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省...
2018-08-17 17:10:23
339
原创 合并果子（huffman树 模版 STL priority_queue 伪小根堆）
题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省...
2018-08-17 16:18:38
410
原创 合并果子（huffman 模版 双队列实现）
题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1n−1 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省...
2018-08-17 15:44:11
437
原创 P2776 [SDOI2007]小组队列
题目背景嘛，这道非常简单的给大家提供信心的省选题洛谷居然没有！这么简单的题怎么可以没有！给大家提升士气是义不容辞的责任！所以我就来补一下啦..值得一提的是，标程是我自己做的..很渣，因为数据很水所以能AC..大神勿喷..题目描述有 m 个小组， n 个元素，每个元素属于且仅属于一个小组。支持以下操作：push x：使元素 x 进队，如果前边有 x 所属小...
2018-08-16 21:40:32
260
原创 Team Queue
DescriptionQueues and Priority Queues are data structures which are known to most computer scientists. The Team Queue, however, is not so well known, though it occurs often in everyday life. At lunc...
2018-08-16 21:37:00
191
原创 1201 最大子序和
描述输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。例如 1，-3,5,1，-2,3当m=4时，S=5+1-2+3=7 当m=2或m=3时，S=5+1=6输入格式第一行两个数n,m（n,m<=300000） 第二行有n个数，要求在n个数找到最大子序和输出格式一个数，数出他们的最大子序和样例输入6 4 1 -3 5 ...
2018-08-16 21:34:32
274
原创 Largest Rectangle in a Histogram POJ2559/洛谷SP1805
DescriptionA histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on th...
2018-08-15 21:51:23
192
原创 归并排序
就是个版#include<cstdio>#include<iostream>using namespace std;int a[1000000];int b[1000000];int n;inline void fenzhi(int l,int r){ int mid=(l+r)>>1; if(l!=r) ...
2018-08-15 14:58:06
143
原创 洛谷P1678 烦恼的高考志愿
题目背景计算机竞赛小组的神牛V神终于结束了万恶的高考，然而作为班长的他还不能闲下来，班主任老t给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是v神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。题目描述根据n位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），...
2018-08-14 08:58:25
417
原创 洛谷P1873 砍树
题目描述伐木工人米尔科需要砍倒M米长的木材。这是一个对米尔科来说很容易的工作，因为他有一个漂亮的新伐木机，可以像野火一样砍倒森林。不过，米尔科只被允许砍倒单行树木。米尔科的伐木机工作过程如下：米尔科设置一个高度参数H（米），伐木机升起一个巨大的锯片到高度H，并锯掉所有的树比H高的部分（当然，树木不高于H米的部分保持不变）。米尔科就行到树木被锯下的部分。例如，如果一行树的高度分别为20，...
2018-08-13 21:20:59
269
原创 洛谷P1182 数列分段`Section II`
题目描述对于给定的一个长度为N的正整数数列 A-iA−i ，现要将其分成 M(M≤N)M(M≤N) 段，并要求每段连续，且每段和的最大值最小。关于最大值最小：例如一数列 4 2 4 5 142451 要分成 33 段将其如下分段：[4 2][4 5][1][42][45][1]第一段和为 66 ，第 22 段和为 99 ，第 33 段和为 11 ，和最大值为 99 。将...
2018-08-13 16:09:20
265
原创 64位整数乘法 高精度
描述求 a 乘 b 对 p 取模的值，其中 1≤a,b,p≤10^18。输入格式第一行a，第二行b，第三行p。输出格式一个整数，表示a*b mod p的值。样例输入2 3 9 样例输出6one#include<cstdio>#include<iostream>#include<cmath>#includ...
2018-08-13 10:33:44
341
原创 历史 history
题目描述 历史学家小Ａ正在研究一个奇怪的王国的历史。当前阶段的任务是研究该国的交通。 根据这个奇怪的王国的史书记载，史书开始记载前这个王国有 n 个城市（城市从 0 开 始标号） ，但所有城市之间都没有道路相连。 每一年，在位的国王会修建一条 x 到 y 的双向道路，一条道路可能被修建多次，但不会 修建起点和终点为同一个城市的道路。 而在这之间，国王会计划进行若干次旅行。对...
2018-07-15 16:59:34
336
原创 2359. 【USACO FALL03】受欢迎的牛 (Standard IO)
Description 每头牛都有一个梦想：成为一个群体中最受欢迎的名牛！在一个有N(1<=N<=10,000)头牛的牛群中，给你M(1<=M<=50,000)个二元组(A,B),表示A认为B是受欢迎的。既然受欢迎是可传递的，那么如果A认为B受欢迎，B又认为C受欢迎,则A也会认为C是受欢迎的，哪怕这不是十分明确的规定。 你的任务是计算被所有其它的牛都喜欢的牛的个...
2018-07-15 07:42:06
516
原创 前辈给我们留下最宝贵的经验
序章看了一些学长的总结，发现一些其实我们忽略的东西。有些时候我们会往往忽视在竞赛过程中我们真正遇到的问题，会不敢面对那些我们不得不正视的东西，会不由自主忽略那些真正值得我们追求的、向往的。 其实竞赛并没有使我们高人一等，也并没有使我们从文科生直接转为理科生。它里面蕴含的哲理值得去学习与体会。不只是算法，竞赛的精神和理念也是我们应该去理解的。广东中山纪念中学姜碧野学长 我随便看了下...
2018-07-14 20:21:34
558
4
原创 tarjan模板
推荐一下前辈的博客 https://blog.csdn.net/qq_34374664/article/details/77488976 https://blog.csdn.net/mengxiang000000/article/details/51672725这是介绍强连通分量的 https://blog.csdn.net/qq_16234613/article/de...
2018-07-14 16:38:56
199
原创 线段树模板
总结了一下线段树的基本运用和操作，也方便日后知识的梳理和Ctrl C+V提高AC率代码#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<vector>#inclu...
2018-07-14 10:56:21
184
原创 P3375 【模板】KMP字符串匹配
题目描述如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。为了减少骗分的情况，接下来还要输出子串的前缀数组next。（如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。）输入输出格式输入格式： 第一行为一个字符串，即为s1第二行为一个字符串，即为s2输出格式： 若干行，每行包含一个整数，表示s2在s1中出现...
2018-07-14 07:28:44
285
原创 3386. 【NOIP2013模拟】守卫者的挑战 (Standard IO)
Description打开了黑魔法师Vani的大门，队员们在迷宫般的路上漫无目的地搜寻着关押applepi的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为K的包包。擂台赛一共有N项挑战，各项挑战依次进行。第i项挑战有一个属性ai，如果ai>=...
2018-07-13 21:56:13
233
原创 C++输入输出优化
输入输出有时会被卡时间，所以我们可以通过一些例如getchar这样极快输入的方式减小提升我们输入输出的时间。#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cctype>#include<cmath>u...
2018-07-13 21:40:16
412
原创 4274. 【NOIP2015模拟10.28B组】终章-剑之魂
Description【背景介绍】 古堡，暗鸦，斜阳，和深渊…… 等了三年，我独自一人，终于来到了这里…… “终焉的试炼吗？就在这里吗？”我自言自语道。 “终焉的试炼啊！就在这里啊！”我再一次自言自语道。 “这背后可能有那个东西吗？”我自言自语道。 “这背后一定有那个东西呢！”我又一次自言自语道。 我沉默着，踏上黑漆漆的索桥，小心翼翼地，拿出锋利的注入我灵魂的双剑…… “那么，...
2018-07-13 21:36:48
317
2
原创 4271. 【NOIP2015模拟10.27】魔法阵
Description帕秋莉·诺蕾姬，有着“不动的大图书馆” 的称号，擅长使用各种各样的属性魔法。 ——《东方求闻史记》 一如既往地，帕秋莉在图书馆中研究着魔法。今天，她在研究一本魔法书中的法阵。 这个法阵可以看成是按下面的规则生成一个规模为n(n 为非负整数) 的图形： 1. 在直角坐标系xOy 中，画4 条线段：[(0,0), (2^n,0)], [(0, 0), (��-2^n,...
2018-07-12 21:49:24
370
原创 4270. 【NOIP2015模拟10.27】魔道研究
Description“我希望能使用更多的魔法。不对，是预定能使用啦。最终我要被大家称呼为大魔法使。为此我决定不惜一切努力。” ——《The Grimoire of Marisa》雾雨魔理沙 魔理沙一如既往地去帕秋莉的大图书馆去借魔导书(Grimoire) 来学习魔道。 最开始的时候，魔理沙只是一本一本地进行研究。然而在符卡战中，魔理沙还是战不过帕秋莉。 好在魔理沙对自己的借还和研究结...
2018-07-12 21:47:49
257
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人