OI

萌宠菠菠乐园
2024-10-06 09:52

OI

关注

文章平均质量分 79

关注数：0 文章数：177 文章阅读量：313816 文章收藏量：82

作者: Whjpji

【动态规划】特别行动队【问题描述】你有一支由 n 名预备役士兵组成的部队，士兵从 1到n编号，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如(i, i + 1, …, i + k)的序列。编号为 i 的士兵的初始战斗力为 xi ，一支特别行动队的初始战斗力 x为队内士兵初始战斗力之和，即 x = xi + xi+1 + … + xi+k。通过长期的原创 2012-03-23 10:34:49 · 13516 阅读 · 0 评论【动态规划】玩具装箱 DescriptionP教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说原创 2012-03-23 11:11:21 · 1372 阅读 · 0 评论 ★☆【平衡二叉树】【倍增】会议中心 Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣，他们希望能够在里面举行会议。对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。会议中心的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。显然，有可能存在不止一种满足要求的策略。例如下面的例子。总共有4个公司。他们对租借会堂发出了请求，并提出了他们所需占用会堂的起止日期（如下表所示）。原创 2012-03-30 11:35:20 · 7426 阅读 · 3 评论 ★【STL】报表统计 Description小Q的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小Q希望可以帮妈妈分担一些工作，作为她的生日礼物之一。经过仔细观察，小Q发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作： INSERT i k 在原数列的第i个元素后面添加一个新元素k；如果原数列的第i个元素已经添加了若干原创 2012-04-18 08:40:56 · 1115 阅读 · 0 评论 ★【动态规划】【状态压缩】【容斥原理】【ZJOI2009】多米诺骨牌 Description　　有一个n×m的矩形表格，其中有一些位置有障碍。现在要在这个表格内放一些1×2或者2×1的多米诺骨牌，使得任何两个多米诺骨牌没有重叠部分，任何一个骨牌不能放到障碍上。并且满足任何相邻两行之间都有至少一个骨牌横跨，任何相邻两列之间也都至少有一个骨牌横跨。求有多少种不同的放置方法，注意你并不需要放满所有没有障碍的格子。Input　　第一行两个整数n;m。接下来n 行，每原创 2012-04-10 16:36:23 · 4576 阅读 · 0 评论【找规律】【ZJOI2009】函数这道题能做对，纯粹就是运气好……先来看两个图：可以简单得出以下规律：k│ │ │ │ │ │ │ │n│1│2│3│4│5│6│7│─┼-┼-┼-┼-┼-┼-┼-┤01│1│-│-│-│-│-│-│02│2│2│-│-│-│-│-│03│2│4│2│-│-│-│-│04│2│4│4│2│-│-│-│05│2│4│6│4│2│-│-│06│2│ 原创 2012-04-10 17:26:19 · 1764 阅读 · 0 评论【状态压缩】【动态规划】坑爹题【问题描述】呵呵，欧教又出了一套题，准备用来考察13 级众基友的OI 水平：“代码都是NOIP 难度，多琢磨一下。”虽然明知要被坑，但是众基友还是决定齐心合力来解决这套坑爹题。这套题一共有n 道，而停课的基友却只有8 个。对于一道题，它会完全占用某基友[a，b]区间的时间。当然，不是所有的基友会做这些题，比如小兽做BFS 不加边框，小蛋基本不会做题……作为基房的女王，神母牛小希想要知道是原创 2012-04-13 15:46:07 · 588 阅读 · 0 评论【筛选法】欧教发糖【问题描述】话说自从欧教给乐乐发了一个棒棒糖之后，机房的众基友就心理不平衡了。于是欧教不得不买了很多糖准备发给众基友。但是新的问题出现了：每个基友都想得到更多的糖，因此平均分配的原则在这里根本行不通。于是欧教又在网上找了一套呵呵难度的题并出了相当坑爹的数据，以考试的成绩来作为发糖的标准。当然，欧教的发糖标准也非常奇葩：对于基友A，如果在其他基友中有t 个人的得分是A 得分的因数，则就给A 原创 2012-04-13 15:14:21 · 571 阅读 · 0 评论【强连通分量】耍朋友【问题描述】春天来了，乐乐在某一天的中午做了一个奇怪而又温馨的梦，以下是梦境的描述：绵中21XX 级信奥班实现了男女人数平均，欧教本着“人人都有朋友耍，人人都有一等拿”的教学原则，准备为机房的每个同学牵红线。并且由于21XX 年世界男女比例对男生有利，所以只要一个男生喜欢一个女生，他们就可以耍朋友（耶~！）。现给出每个男生喜欢哪些女生（没错，是哪些，因为在乐乐的梦里一个男生喜欢N 个女原创 2012-04-13 17:23:31 · 820 阅读 · 0 评论 LCA向RMQ转化 1,最近公共祖先(LCA):对于有根树T的两个结点u、v，最近公共祖先LCA(T,u,v)表示一个结点x，满足x是u、v的祖先且x的深度尽可能大。2,LCA问题向RMQ问题的转化方法:(RMQ返回最值的下标)对树进行深度优先遍历，每当“进入”或回溯到某个结点时，将这个结点的深度存入数组dfsNum最后一位。同时记录结点i在数组中第一次出现的位置(事实上就是进入结点i时记录的位置)，记做转载 2012-04-15 10:37:51 · 544 阅读 · 0 评论 ★【动态规划】【线段树】基站选址【问题描述】有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。【输入格式】base.in输入文件的第一行包含两个整原创 2012-04-01 16:38:58 · 2930 阅读 · 3 评论【悬线法】糖果盒 Description一个被分为 n*m　个格子的糖果盒，第 i 行第 j 列位置的格子里面有 a [ i ][ j ] 颗糖。本来 tenshi 打算送这盒糖果给某 PPMM 的，但是就在要送出糖果盒的前一天晚上，一只极其可恶的老鼠夜袭糖果盒，有部分格子被洗劫并且穿了洞。tenshi 必须尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且 tenshi 希望保留在新糖果盒内的糖原创 2012-04-14 08:47:28 · 1293 阅读 · 0 评论【最近公共祖先】Tree A weighted tree is given. You must find the distance between two given nodes.InputThe first line contains the number of nodes of the treen (1 ≤ n ≤ 50000). The nodes are numbered from 0 to n 原创 2012-04-15 10:34:00 · 647 阅读 · 0 评论 ★【左偏树】Financial Fraud Bernard Madoff is an American former stock broker, investment adviser, non-executive chairman of theNASDAQ stock market, and the admitted operator of what has been described as the largest Ponzi sche 原创 2012-04-02 10:03:26 · 1106 阅读 · 0 评论【最小費用流】運輸問題问题描述： W 公司有 m个仓库和 n 个零售商店。第 i 个仓库有 ai 个单位的货物；第 j 个零售商店需要 bj 个单位的货物。货物供需平衡，即∑ai = ∑bj。从第 i 个仓库运送每单位货物到第 j 个零售商店的费用为 cij 。试设计一个将仓库中所有货物运送到零售商店的运输方案，使总运输费用最少。编程任务：对于给定的 m 个仓库和 n 个零售商店间运送货物的费用，计算最优运原创 2012-02-04 17:15:49 · 1065 阅读 · 0 评论【二分图最佳匹配】移动棋子在一个n*n的棋盘上有n枚棋子。每次可以把一枚棋子往上、下、左、右方向之一移动一格，最后排成一行、一列或者主、副对角线上（因此一共有2n+2条可能的目标状态），要求移动次数最小。棋盘上有一些位置是障碍，棋子在任何时候都不能经过。棋子的初始位置保证不在障碍物上。任两枚棋子不能在同时到达同一个格子。【输入文件】输入文件move.in第一行包含两个整数n, m，表示棋原创 2012-04-16 09:17:50 · 958 阅读 · 0 评论【悬线法】棋盘制作 Description国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。小Q找到了一张由N*M个正方形的格子组成的矩形原创 2012-04-16 14:51:46 · 993 阅读 · 0 评论【二分圖最佳匹配】糊塗的記者糊涂的记者（sign.pas/in/out）问题描述：　　在如今的信息社会中，时间-就是生命，对于记者们来说，如何以最快的速度传递消息就显得十分重要了，而为了尽快记录消息内容，速记也是必不可少的。速记就是用一些简单且特殊的符号表示一定的含义，具体如何对应依个人习惯而定，没有一种固定的表示方法。　　Tom是一名报社的新闻记者，常常马不停蹄的跟着新闻跑，有时只能随手记下采访的内容，让人送回原创 2012-02-02 08:19:18 · 1317 阅读 · 0 评论【费用流】Kaka's Matrix Travels DescriptionOn an N × N chessboard with a non-negative number in each grid, Kaka starts his matrix travelswith SUM = 0. For each travel, Kaka moves one rook from the left-upper grid to the right-bot 原创 2012-04-17 09:40:18 · 568 阅读 · 0 评论 ★☆【二分圖最佳匹配】丘比特的煩惱随着社会的不断发展，人与人之间的感情越来越功利化。最近，爱神丘比特发现，爱情也已不再是完全纯洁的了。这使得丘比特很是苦恼，他越来越难找到合适的男女，并向他们射去丘比特之箭。于是丘比特千里迢迢远赴中国，找到了掌管东方人爱情的神——月下老人，向他求教。　　月下老人告诉丘比特，纯洁的爱情并不是不存在，而是他没有找到。在东方，人们讲究的是缘分。月下老人只要做一男一女两个泥人，在他们之间连上一条红线，那么原创 2012-02-01 19:43:43 · 1777 阅读 · 0 评论【树的遍历】时态同步 Description小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到原创 2012-04-16 15:19:02 · 720 阅读 · 0 评论【并查集】Is it a tree？ A tree is a well-known data structure that is either empty (null, void, nothing) or is a set ofone or more nodes connected by directed edges between nodes satisfying the following properties.There 原创 2012-04-17 16:10:40 · 588 阅读 · 0 评论【并查集】食物链 Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是"1 X Y"，表示X和Y是同类。第二种说法是"2 X Y"，表示X吃Y。此人对N个动物，用上述两种说法，一句接一原创 2012-04-17 14:36:08 · 562 阅读 · 0 评论【并查集】Ubiquitou Religions DescriptionThere are so many different religions in the world today that it is difficult to keep trackof them all. You are interested in finding out how many different religions students in youru 原创 2012-04-17 16:43:32 · 744 阅读 · 0 评论【后缀数组】【SCOI2012】喵星球上的点名 Descriptiona180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。假设课堂上有N个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。然而，由于喵星人的字码过于古怪，以至于不能用ASCII码来表示。为了方便描述，a180285决定用数串来原创 2012-05-01 22:03:50 · 1721 阅读 · 2 评论 ★【求无向图割顶】Network DescriptionA Telephone Line Company (TLC) is establishing a new telephone cable network. They are connectingseveral places numbered by integers from 1 to N . No two places have the same number. The 原创 2012-04-18 21:43:12 · 1207 阅读 · 0 评论 ★【双连通分量】【奇环判定】Knights of the Round Table DescriptionBeing a knight is a very attractive career: searching for the Holy Grail, saving damsels indistress, and drinking with the other knights are fun things to do. Therefore, it is not verysu 原创 2012-04-19 11:07:13 · 1548 阅读 · 0 评论 ★【双连通分量】Redundant Paths DescriptionIn order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field,Bessie and the rest of the herd are forced to cross near the Tree of Rotten A 原创 2012-04-19 16:37:16 · 1093 阅读 · 0 评论【平衡二叉树】Who Gets the Most Candies? DescriptionN children are sitting in a circle to play a game.The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integeron it in his/her hand. The g 原创 2012-04-20 11:18:23 · 585 阅读 · 0 评论【平衡二叉树】Buy Tickets DescriptionRailway tickets were difficult to buy around the Lunar New Year in China, so we must get up early and join along queue…The Lunar New Year was approaching, but unluckily the Little Cat 原创 2012-04-19 21:13:02 · 537 阅读 · 0 评论【平衡二叉树】宠物收养所 Description最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被原创 2012-04-19 22:25:41 · 863 阅读 · 0 评论 ★【计算几何】凸多边形逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图：则相交部分的面积为5.233。【输入格式】输入文件polygon.in第一行有一个整数n，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数mi，表示多边形的边数，以下mi行每行两个整数，逆时针给出各个顶点的坐标。【输出格式】输出文件仅包含一原创 2012-04-15 19:40:03 · 1300 阅读 · 0 评论 ★【视野动态规划】【NOI2011】智能车比赛智能车比赛【问题描述】新一届智能车大赛在 JL 大学开始啦!比赛赛道可以看作是由 n 个矩形区域拼接而成(如下图所示),每个矩形的边都平行于坐标轴,第 i 个矩形区域的左下角和右上角坐标分别为(xi,1,yi,1)和(xi,2,yi,2)。题目保证:xi,1<xi,2=xi+1,1,且 yi,1< yi,2,相邻两个矩形一定有重叠在一起的边(如图中虚线所示),智能车可以通过这部分穿原创 2012-05-06 11:19:59 · 3672 阅读 · 0 评论 ★【AC自动机】【树状数组】【NOI2011】阿狸的打字机【问题描述】阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有 28 个按键,分别印有 26 个小写英文字母和'B'、'P'两个字母。经阿狸研究发现,这个打字机是这样工作的:输入小写字母,打字机的一个凹槽中会加入这个字母(按 P 前凹槽中至少有一个字母)。按一下印有'B'的按键,打字机凹槽中最后一个字母会消失。按一下印有'P'的按键,打字机会在纸上打印出凹槽中现有原创 2012-05-07 16:38:33 · 1754 阅读 · 0 评论 ★【最小树形图】Command Network DescriptionAfter a long lasting war on words, a war on arms finally breaks out between littleken’s andKnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered atotal 原创 2012-05-05 11:14:39 · 770 阅读 · 0 评论【树状数组】Mobile Phones DescriptionSuppose that the fourth generation mobile phone base stations in the Tampere area operate as follows.The area is divided into squares. The squares form an S * S matrix with the rows and 原创 2012-04-21 16:34:28 · 695 阅读 · 0 评论 ★【模拟退火】Texas Trip DescriptionAfter a day trip with his friend Dick, Harry noticed a strange pattern of tiny holes in the door of hisSUV. The local American Tire store sells fiberglass patching material only in squar 原创 2012-04-22 19:29:59 · 1345 阅读 · 1 评论 ★【二分图匹配】【博弈论】【NOI2011】兔兔和蛋蛋的游戏【问题描述】这些天,兔兔和蛋蛋喜欢上了一种新的棋类游戏。这个游戏是在一个 n 行 m 列的棋盘上进行的。游戏开始之前,棋盘上有一个格子是空的,其它的格子中都放置了一枚棋子,棋子或者是黑色,或者是白色。每一局游戏总是兔兔先操作,之后双方轮流操作,具体操作为: 兔兔每次操作时,选择一枚与空格相邻的白色棋子,将它移进空格。蛋蛋每次操作时,选择一枚与空格相邻的黑色棋子,将它移进空原创 2012-05-08 20:12:16 · 2927 阅读 · 1 评论 ★【动态规划】【斜率优化】【平衡树维护决策序列】【NOI2007】货币兑换问题描述小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A 纪念券(以下简称 A 券)和 B 纪念券(以下简称 B 券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A 券和 B 券的价值分别为 AK 和BK(元/单位金券)。为了方便顾客,金原创 2012-05-27 15:22:25 · 2610 阅读 · 0 评论 ★【划分树】K-th Number DescriptionYou are working for Macrohard company in data structures department. After failing yourprevious task about key insertion you were asked to write a new data structure that wouldbe able to 原创 2012-05-04 20:46:19 · 1245 阅读 · 0 评论 <12345>