- 博客(62)
- 资源 (4)
- 收藏
- 关注
RSS订阅原创 洛谷P2730 魔板 Magic Squares
题目背景在成功地发明了魔方之后，鲁比克先生发明了它的二维版本，称作魔板。这是一张有8个大小相同的格子的魔板：1 2 3 48 7 6 5题目描述我们知道魔板的每一个方格都有一种颜色。这8种颜色用前8个正整数来表示。可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。对于上图的魔板状态，我们用序列（1，2，3，4，5，6，7，8...
2018-08-26 10:52:51
291
原创 UVA1347 Tour
John Doe, a skilled pilot, enjoys traveling. While on vacation, he rents a small plane and starts visitingbeautiful places. To save money, John must determine the shortest closed tour that connects hi...
2018-07-09 16:02:41
239
原创 洛谷 P3376 【模板】网络最大流
题目描述如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。输入输出格式输入格式：第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）输出格式：一行，包含一个正整数，即为该网络的最大流。输入输出样例输入样例#1： 复制4 5 4 34 2 ...
2018-06-23 18:11:01
309
原创 洛谷 P3063 [USACO12DEC]牛奶的路由Milk Routing
题目描述Farmer John's farm has anoutdated network of M pipes (1 <= M <= 500) for pumping milk from thebarn to his milk storage tank. He wants to remove and update most of these overthe next year, bu...
2018-06-18 16:25:55
495
原创 洛谷 P3116 [USACO15JAN]约会时间Meeting Time
题目描述Bessie and her sister Elsie want to travel from the barn to theirfavorite field, such that they leave at exactly the same time from the barn,and also arrive at exactly the same time at their favor...
2018-06-18 14:59:12
279
原创 洛谷 P2865 [USACO06NOV]路障Roadblocks
题目描述Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way....
2018-06-18 12:31:10
258
原创 洛谷 P3106 [USACO14OPEN]GPS的决斗Dueling GPS's
题目描述Farmer John has recently purchased a new car online, but in his haste heaccidentally clicked the "Submit" button twice when selecting extrafeatures for the car, and as a result the car ended up eq...
2018-06-18 11:14:54
313
原创 洛谷 P3115 [USACO15JAN]牛路线Cow Routing
题目描述Tired of the cold winter weather on her farm, Bessie the cow plans to fly to a warmer destination for vacation. Unfortunately, she discovers that only one airline, Air Bovinia, is willing to sell...
2018-06-17 22:10:21
451
原创 luogu P3096 [USACO13DEC]假期计划（黄金）Vacation Planning (gold)
题目描述Air Bovinia operates flights connecting the N farms that thecows live on (1 <= N <= 20,000). As with any airline, K of these farmshave been designated as hubs (1 <= K <= 200, K <= N...
2018-06-17 19:42:18
262
原创 luogu P1078 文化之旅 (NOIP 2012 普及组 第四题)
题目描述有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的...
2018-06-17 19:32:45
596
原创 洛谷 P3834 【模板】可持久化线段树 1（主席树）
题目背景这是个非常经典的主席树入门题——静态区间第K小数据已经过加强，请使用主席树。同时请注意常数优化题目描述如题，给定$N$个正整数构成的序列，将对于指定的闭区间查询其区间内的第$K$小值。输入输出格式输入格式： 第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。第二行包含N个正整数，表示这个序列各项的数字。接下来M行每行包含三个整数 l, ...
2018-06-10 21:51:57
275
原创 [USACO12MAR]园林绿化Landscaping
题目描述Farmer John is building a nicely-landscaped garden, and needs to move a large amount of dirt in the process.The garden consists of a sequence of N flowerbeds (1 <= N <= 100), where flowerbed...
2018-06-07 22:11:56
492
原创 洛谷P1351 NOIP 2014 联合权值
题目描述无向连通图 GG 有 nn 个点， n-1n−1 条边。点从 11 到 nn 依次编号,编号为 ii 的点的权值为 W_iWi ，每条边的长度均为 11 。图上两点 (u,v)(u,v) 的距离定义为 uu 点到 vv 点的最短距离。对于图 GG 上的点对 (u,v)(u,v) ，若它们的距离为 22 ，则它们之间会产生 W_v\times W_uWv×Wu的联合权值。请问图 GG ...
2018-06-06 22:01:52
225
原创 洛谷 P3052 USACO 摩天大楼里的奶牛Cows in a Skyscraper
题目描述A little known fact about Bessie and friends is that they lovestair climbing races. A better known fact is that cows really don't like goingdown stairs. So after the cows finish racing to the top ...
2018-06-03 19:51:31
327
原创 洛谷P3389 【模板】高斯消元法
题目背景Gauss消元题目描述给定一个线性方程组，对其求解输入输出格式输入格式：第一行，一个正整数 nn第二至 n+1n+1 行，每行 n+1n+1 个整数，为 a_1, a_2 \cdots a_na1,a2⋯an 和 bb ，代表一组方程。输出格式：共n行，每行一个数，第 ii 行为 x_ixi （保留2位小数）如果不存在唯一解，在第一行输出"No Solution".输入输出样例输入...
2018-06-01 21:35:34
206
原创 USACO 2011 March Silver Meeting Place
题目描述Bessie and Jonell are great friends. Since Farmer John scrambleswhere the cows graze every day, they are sometimes quite far from each otherand can't talk. The pastures and paths on FJ's farm form...
2018-05-27 20:47:18
213
原创 USACO 2004 February Green Distance Queries
题目描述Farmer John's cows refused to run in his marathon since he chose apath much too long for their leisurely lifestyle. He therefore wants to find apath of a more reasonable length. The input to this ...
2018-05-27 19:53:15
240
原创 USACO 2010 Holiday Gold 奶牛政坛
题目描述农夫约翰的奶牛住在N (2 <= N <= 200,000)片不同的草地上，标号为1到N。恰好有N-1条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合，详细说明了每个草地的父节点P_i (0 <= P_i <= N)。根节点的P_i ==0, 表示...
2018-05-27 19:05:19
232
原创 USACO 2008 OCT gold 牧草
题目描述有N (2 <= N <= 1,000)头奶牛，分别编号为1到N。还有N颗牧草分别编号为1到N。简单起见，第i头奶牛都盯着第i颗牧草。有几对牧草分别用一些小路连接了起来，总共有N-1条双向的小路，小路i连接了Ai及Bi颗牧草(1 <= Ai <= N; 1 <= Bi <= N)，小路的长度为Li (1 <= Li <= 10,000) 保证...
2018-05-26 21:23:57
200
原创 Luogu P3379 【模板】最近公共祖先（LCA）
题目描述如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。输入输出格式输入格式：第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。输出格式：输出包含M行，每行包含一个正整数，依次...
2018-05-24 22:02:14
186
原创 CODEVS 3243 区间翻转
题目描述给出N个数，要求做M次区间翻转（如1 2 3 4变成4 3 2 1），求出最后的序列输入描述第一行一个数N，下一行N个数表示原始序列，在下一行一个数M表示M次翻转，之后的M行每行两个数L，R表示将区间[L,R]翻转。输出描述 一行N个数，表示最终序列。样例输入41 2 3 421 23 4样例输出 2 1 4 3数据范围及提示对于30%的数据满足n<=100 , m <= 10...
2018-05-20 16:52:35
208
原创 CODEVS 2491 玉蟾宫
题目描述 有一天，小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。 这片土地被分成N*M个格子，每个格子里写着'R'或者'F'，R代表这块土地被赐予了rainbow，F代表这块土地被赐予了freda。 现在freda要在这里卖萌。。。它要找一块矩形土地，要求这片土地都标着'F'并且面积最大。 但是rainbow和freda的...
2018-05-19 21:25:28
178
原创 CODEVS 2492 上帝造题的七分钟 2
题目描述 XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。"第一分钟，X说，要有数列，于是便给定了一个正整数数列。 第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。 第三分钟，k说，要能查询，于是便有了求一段数的和的操作。 第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。 第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。 第六分钟...
2018-05-19 11:49:37
183
原创 CODEVS 3304 水果姐逛水果街Ⅰ
题目描述 水果姐今天心情不错，来到了水果街。水果街有n家水果店，呈直线结构，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。学过oi的水果姐迅速发现了一个赚钱的方法：在某家水果店买一个水果，再到另外一家店卖出去，赚差价。就在水果姐窃喜的时候，cgh突然出现，他为了为难水果姐，给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可...
2018-05-19 10:44:04
334
原创 CODEVS 2018 反病毒软件
题目描述 第一行为两个整数N，Q，以空格隔开。接下来Q行，每行代表一个事件。第i+1行代表第i个事件，这一行有三个整数Ci，Xi，Yi，其中Ci为1或2。如果Ci为1，表示在城市Xi又新发现了Yi个病例；如果Ci为2，表示询问从Xi到Yi，病例最多的城市与病例第二多的城市的病例数之差为多少。输出描述对于输入中的每一个Ci=2的事件，输出一行，即询问的结果。样例输入42 1 41 2 32 2 41...
2018-05-19 09:10:39
189
原创 CODEVS 1291 火车线路
题目描述 Description某列火车行使在C个城市之间(出发的城市编号为1，结束达到的城市的编号为C)，假设该列火车有S个座位，现在有R笔预订票的业务。现在想对这R笔业务进行处理，看哪些预定能满足，哪些不能满足。一笔预定由O、D、N三个整数组成，表示从起点站O到目标站D需要预定N个座位。一笔预定能满足是指该笔业务在行程范围内有能满足的空座位，否则就不能满足。一笔业务不能拆分，也就是起点和终点站...
2018-05-14 21:37:05
413
原创 CODEVS 1690 开关灯
题目描述 YYX家门前的街上有N(2<=N<=100000)盏路灯，在晚上六点之前，这些路灯全是关着的，六点之后，会有M(2<=m<=100000)个人陆续按下开关，这些开关可以改变从第i盏灯到第j盏灯的状态，现在YYX想知道，从第x盏灯到第y盏灯中有多少是亮着的(1<=i,j,x,y<=N)输入描述第 1 行: 用空格隔开的两个整数N和M第 2..M+...
2018-05-13 21:10:22
111
原创 CODEVS 1369 xth 砍树
题目描述 Description在一个凉爽的夏夜，xth 和 rabbit 来到花园里砍树。为啥米要砍树呢？是这样滴，小菜儿的儿子窄森要出生了。Xth这个做伯伯的自然要做点什么。于是他决定带着rabbit 去收集一些木材，给窄森做一个婴儿车……（xth 早就梦想着要天天打菜儿他儿窄森的小 pp，到时候在婴儿车里安装一个电子遥控手臂，轻轻一按，啪啪啪……“乌卡卡——”xth 邪恶滴笑了，“不要告诉 ...
2018-05-09 18:53:49
227
原创 洛谷P1083 借教室（NOIP提高2012第二天第二题）
题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tj，表示某租借者需要从第sj天到第tj天租借教室（...
2018-05-08 20:55:40
241
原创 CODEVS 1081 线段树练习 2
题目描述 给你N个数，有两种操作1：给区间[a,b]的所有数都增加X;2：询问第i个数是什么？输入描述 第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。输出描述 对于每个询问输出一行一个答案样例输入 3...
2018-05-06 21:24:40
143
原创 洛谷P1982 小朋友的数字
题目描述有 n 个小朋友排成一列。每个小朋友手上都有一个数字，这个数字可正可负。规定每个小朋友的特征值等于排在他前面（包括他本人）的小朋友中连续若干个（最少有一个）小朋友手上的数字之和的最大值。作为这些小朋友的老师，你需要给每个小朋友一个分数，分数是这样规定的：第一个小朋友的分数是他的特征值，其它小朋友的分数为排在他前面的所有小朋友中（不包括他本人），小朋友分数加上其特征值的最大值。请计算所有小朋...
2018-05-06 19:02:27
604
原创 CODE[VS]1191 数轴染色
题目描述 Description在一条数轴上有N个点，分别是1～N。一开始所有的点都被染成黑色。接着我们进行M次操作，第i次操作将[Li,Ri]这些点染成白色。请输出每个操作执行后剩余黑色点的个数。输入描述 Input Description输入一行为N和M。下面M行每行两个数Li、Ri输出描述 Output Description输出M行，为每次操作后剩余黑色点的个数。样例输入 Sample I...
2018-04-15 09:48:27
266
原创 种树
题目描述 校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作： K=1，读入l,r表示在l~r之间种上的一种树 K=2，读入l,r表示询问l~r之间能见到多少种树（l,r> 0） 输入 第一行n,m表示道路总长为n，共有m个操作接下来m行为m个操作 输出 对于...
2018-04-14 21:06:27
359
原创 洛谷 P1440 求m区间内的最小值
题目描述 一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。输入格式: 第一行两个数n，m。 第二行，n个正整数，为所给定的数列。输出格式： n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。输入样例 6 2 7 8 1 43 2输出样例 0...
2018-04-07 21:37:02
295
原创 洛谷P1816 忠诚
题目描述老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。输入输...
2018-04-04 18:43:02
360
原创 洛谷P2672 NOIP2015普及组第四题
题目描述 阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。 阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会...
2018-04-01 20:46:54
509
1
原创 洛谷P2671 NOIP2015普及组第三题 求和
题目描述一条狭长的纸带被均匀划分出了n个格子，格子编号从1到n。每个格子上都染了一种颜色color_i用[1，m]当中的一个整数表示），并且写了一个数字number_i。定义一种特殊的三元组：(x,y,z)，其中x，y，z都代表纸带上格子的编号，这里的三元组要求满足以下两个条件：1. xyz是整数,x<y<z，y-x=z-y2. colorx=colorz满足上述条件的三...
2018-04-01 19:05:04
1633
1
原创 洛谷 P3372 【模板】线段树 1
题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x2.求出某区间每一个数的和输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个整数，表示一个操作，具体如下：操作1： 格式：1x y k 含义：将区间[x,y]内每个数加上k操作2： 格式：2x y 含...
2018-03-28 21:05:13
179
原创 线段树模板（点修改 ，区间查询）
caiOJ1099题题目描述给出N个数，两种操作：1、C x y：修改第x个数的值为y；2、P x y：求第x到第y个的最大值，注：x未必比y小输入格式第一行输入N和M（0<N<=200000,0<M<5000），N表示有N个数，M表示有M个操作下来N个数然后是M个操作。输出格式遇到P操作的时候，输出结果。样例输入5 61 2 3 4 5P 1 5C 3 6P 3 4P 4...
2018-03-28 20:58:40
250
原创 POJ2185 【USACO】Milking Grid
题目描述 Every morning when they are milked, theFarmer John's cows form a rectangular grid that is R (1 <= R <= 10,000)rows by C (1 <= C <= 75) columns. As we all know, Farmer John is quite...
2018-03-28 18:43:23
283
2018NOIP普及组模拟试题（内涵试题、数据及满分代码）
2018-08-02
康托展开和康托展开的逆运算
2018-01-11
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人