标签 - 洛谷

? 解题记录 ? ? 洛谷 ? ? 博弈论 ? ? 动态规划 ? ? 搜索 ?    2019-01-30 17:26:26    885    0    0
题目描述菲菲和牛牛在一块n 行m 列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。 棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。 落子的规则是:一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。 棋盘的每个格子上,都写有两个非负整数,从上到下第i 行中从左到右第j 列的格 子上的两个整数记作Ai,j​ 、Bi,j​ 。在游戏结束后,菲菲和牛牛会分别计算自己的得分:菲菲的得分是所有有黑棋的格子上的Ai,j​ 之和,牛牛的得分是所有有白棋的格子上的Bi,j​的和。 菲菲和牛牛都希望,自己的得分减去对方的
? 解题记录 ? ? 洛谷 ? ? 网络流 ? ? 上下界网络流 ?    2018-12-05 23:08:48    336    0    0
题目描述滑雪场坐落在FJ省西北部的若干座山上。 从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向。 你的团队负责每周定时清理雪道。你们拥有一架直升飞机,每次飞行可以从总部带一个人降落到滑雪场的某个地点,然后再飞回总部。从降落的地点出发,这个人可以顺着斜坡向下滑行,并清理他所经过的雪道。 由于每次飞行的耗费是固定的,为了最小化耗费,你想知道如何用最少的飞行次数才能完成清理雪道的任务。 输入输出格式输入格式:   输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。 接下来的n行,描述1
? 解题记录 ? ? 洛谷 ? ? 半平面交 ?    2018-11-25 16:57:21    697    0    0
题目描述沫沫最近在玩一个二维的射箭游戏,如下图 1 所示,这个游戏中的 x 轴在地面,第一象限中有一些竖直线段作为靶子,任意两个靶子都没有公共部分,也不会接触坐标轴。 沫沫控制一个位于(0,0)的弓箭手,可以朝 0 至 90?中的任意角度(不包括 0度和 90度),以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力,并且光之箭没有箭身,箭的轨迹会是一条标准的抛物线,被轨迹穿过的所有靶子都认为被沫沫射中了,包括那些 只有端点被射中的靶子。 这个游戏有多种模式,其中沫沫最喜欢的是闯关模式。 在闯关模式中,第一关只有一个靶 子,射中这个靶子即可进入第二关,这时在第一关的基础上会出现另外
? 解题记录 ? ? 洛谷 ? ? 半平面交 ?    2018-11-25 16:53:54    719    0    0
题目描述这里有一辆赛车比赛正在进行,赛场上一共有N辆车,分别称为个g1,g2......gn。赛道是一条无限长的直线。最初,gi位于距离起跑线前进ki的位置。比赛开始后,车辆gi将会以vi单位每秒的恒定速度行驶。在这个比赛过程中,如果一辆赛车曾经处于领跑位置的话(即没有其他的赛车跑在他的前面),这辆赛车最后就可以得奖,而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度,你的任务就是算出那些赛车将会得奖。 输入输出格式输入格式:   第一行有一个正整数N表示赛车的个数。接下来一行给出N个整数,按顺序给出N辆赛车的起始位置。再接下来一行给出N个整数,按顺序给出N辆赛车的恒
? 解题记录 ? ? 洛谷 ? ? 搜索 ?    2018-11-13 10:10:52    506    0    0
题目描述Mayan puzzle是最近流行起来的一个游戏。游戏界面是一个7 行 5×5列的棋盘,上面堆放着一些方块,方块不能悬空堆放,即方块必须放在最下面一行,或者放在其他方块之上。游戏通关是指在规定的步数内消除所有的方块,消除方块的规则如下: 1 、每步移动可以且仅可以沿横向(即向左或向右)拖动某一方块一格:当拖动这一方块时,如果拖动后到达的位置(以下称目标位置)也有方块,那么这两个方块将交换位置(参见输入输出样例说明中的图6到图7 );如果目标位置上没有方块,那么被拖动的方块将从原来的竖列中抽出,并从目标位置上掉落(直到不悬空,参见下面图1 和图2); 2
? 解题记录 ? ? 强连通分量 ? ? 洛谷 ?    2018-11-13 10:01:47    469    0    0
题目描述在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的Alpaca L. Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天Henry Curtis故事的起点。Henry是一个爱财如命的贪婪家伙,而又非常聪明,他费尽心机谋划了这次盗窃行动,破解重重机关后来到这座地下宫殿前。 整座宫殿呈矩阵状,由R×C间矩形宫室组成,其中有N间宫室里埋藏着宝藏,称作藏宝宫室。宫殿里外、相邻宫室
? 解题记录 ? ? 洛谷 ? ? 最短路 ?    2018-11-13 09:12:52    406    0    0
题目描述小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面, 华容道是否根本就无法完成,如果能完成, 最少需要多少时间。 小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的: 在一个 n×m 棋盘上有n×m个格子,其中有且只有一个格子是空白的,其余n×m−1个格子上每个格子上有一个棋子,每个棋子的大小都是 1×1 的; 有些棋子是固定的,有些棋子则是可以移动的; 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。 游戏的目的是把某个指定位置可以
? 解题记录 ? ? 洛谷 ? ? 动态规划 ? ? 斜率优化 ? ? 凸包 ? ? stl ?    2018-11-04 15:44:33    675    0    0
Description 小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A纪念券(以下简称A券)和 B纪念券(以下 简称B券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动, 两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券 和 B券 的 价值分别为 AK 和 BK(元/单位金券)。为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法 。比例交易法分为两个方面:(a)卖出金券:顾客提供一个 [0,100] 内的实数 OP 作为卖出比例,其意义为:将  OP%
? 解题记录 ? ? 洛谷 ? ? 组合数 ? ? 筛法 ?    2018-11-04 15:28:51    674    0    0
2.1 题目描述 九条可怜是一个热爱游戏的女孩子,她经常在网上和一些网友们玩一款叫做《僵尸危机》 游戏。 在这款游戏中,玩家们会需要在成为僵尸之前与黑恶势力斗智斗勇,逃离被病毒感染的小 岛。但是黑恶势力不会让玩家轻易得逞,他会把一些玩家抓走改造成僵尸。变成僵尸的玩家会 攻击其他的玩家,被攻击的玩家会被” 感染”,成为病毒的潜在宿主。 具体来说,游戏开始时,所有的玩家会获得一个 l ∼ r 的编号 (如果一共有 r − l + 1 个玩 家),不同的玩家的编号不同。 游戏分轮次进行,在每一轮中一次会发生这样的事情。 • 如果所有当前所有的正常人都已经被感染,那么游戏结束。 •
? 解题记录 ? ? 洛谷 ? ? 搜索 ?    2018-11-04 15:25:33    549    0    0
题目描述小Z最近迷上了拼图游戏,然而智商有限,他总是无法拼出完整图案。游戏是这样的:首先小Z会得到一些拼图碎片,然后他试着重新排列这些碎片使得它们组成一个大小为4*4的正方形。如下图。注意小Z不能旋转或者翻转这些碎片。 小Z得到如图1的碎片,然后经过重新排列得到图2的正方形。 由于小Z实在太笨了,聪明的你请写一个程序帮助他来解决这个问题吧。 输入输出格式输入格式:   输入包含多组数据,请使用EOF 每组数据的的第一行包含一个正整数N,表示碎片的个数。接下来输入N个碎片。每个碎片的第一行是两个正整数r和c,表示这个碎片的行数和列数。接下来是r行,每一行包含c个字符'0'或'1','