- 博客(39)
- 收藏
- 关注
RSS订阅原创 牧场的安排 状态压缩动态规划模板题
牧场的安排Problem DescriptionFarmer John新买了一块长方形的牧场，这块牧场被划分成M列N行(1<=M<=12;1<=N<=12)，每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当的贫瘠，不能用来放牧。并且，奶牛们喜欢独占一块草地的感觉，于是FJ不会选择两块相邻的土地，也就是说，...
2019-02-13 21:19:46
573
原创 Hie with the Pie 动态规划的模板题
Hie with the PieProblem DescriptionThe Pizazz Pizzeria prides itself in delivering pizzas to its customers as fast as possible. Unfortunately,due to cutbacks, they can afford to hire only one driv...
2019-02-13 20:30:18
391
原创 石子合并 区间动态规划模板题
石子合并Problem Description在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.Input数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.Output输出共2...
2019-02-12 11:33:16
415
原创 门票 简单的循环
门票DescriptionRPK要带MSH去一个神秘的地方！RPK带着MSH穿过广场，在第1618块砖上按下了一个按钮，在一面墙上随即出现了一个把手。RPK握住把手，打开了一扇石质大门。他们穿过悠长而芬芳的小道，走到了一扇象征时间的大门——“the gate of time”。门上写着一个关于时间的谜题“承诺：____年”，RPK思考了一会，从容地用手指写下了1万，这时，门开始发出闪光，...
2018-12-02 10:09:42
599
原创 线段树 模板题
线段树Problem Description已知一个数列，你需要进行下面两种操作：1.将某区间每一个数加上x2.求出某区间每一个数的和Input第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个整数，表示一个操作，具体如下：操作1： 格式：1 x y k 含义：将区间...
2018-10-05 09:56:10
223
原创 Rainbow的信号 位运算的递推
Rainbow 的信号Freda 发明了传呼机之后，rainbow进一步改进了传呼机发送信息所使用的信号。由于现在是数字、信息时代，rainbow发明的信号用N个自然数表示。为了避免两个人的对话被大坏蛋Variant F偷听T_T，rainbow把对话分成A、B、C三部分，分别用a、b、c三个密码加密。现在Freda接到了rainbow的信息，她的首要工作就是解密。Freda了解到，这三部分的...
2018-09-27 18:23:50
666
原创 小猫爬山 枚举法
小猫爬山Problem DescriptionFreda和rainbow饲养了N只小猫，这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，...
2018-09-27 17:58:26
592
原创 Freda的队列 简单模拟
Freda的队列Problem DescriptionFreda有一个队列，最初它是空的。现在Freda接到了一系列指令，每个指令包含一个整数x。如果x>0，表示在队列开头加入一个数x。如果x=0，表示把队列复制一份，并接在现有队列的末尾。如果x=-1，表示弹出队列头部的数，并输出这个数值。但是指令实在是太多了，Freda实在是计算不过来每次要输出什么数值，请你帮帮她吧。I...
2018-09-27 17:47:42
824
原创 诸侯安置 简单的递推
诸侯安置Problem Description很久以前，有一个强大的帝国，它的国土呈正方形状（转45度看），如图所示。这个国家有若干诸侯。由于这些诸侯都曾立下赫赫战功，国王准备给他们每人一块封地（正方形中的一格）。但是，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，他们就会开战。如下图为n=3时的国土，阴影部分表示诸侯所处的位置。前两幅图中的诸侯可以互相攻击，第三幅则不可以。国王...
2018-09-26 22:16:39
478
原创 影像之结构化特征 广度优先搜索模板题
影像之结构化特征Problem Description在影像比对中，有一种方法是利用影像中的边缘(edge)资讯，计算每个边缘资讯中具有代表性的结构化特征，以作为比对两张影像是否相似的判断标准。Water-filling方法是从每个边缘图的一个端点开始，绕着相连的边缘点走并依序编号。若走到某一步时，遇到一个以上不同的连接点，则分成不同路径同时继续走，直到没有任何连接点为止。如果一个点和另一个...
2018-09-26 22:13:41
350
原创 小数化分数 模拟题
小数化分数Problem Description将给出的小数化为分数Input只有一行，为要转换的小数（正负均有）。注意：小数的格式有好几种。为了方便起见，循环部分均被括号括起来了。有前导0或后导0的例子：09.400（输出47/5）纯循环小数的例子：0.(3)（输出1/3）混循环小数的例子：0.5(142857)（输出18/35）输入数据都是正确的，不用判错。保证如果有循环节...
2018-09-26 22:11:39
1610
原创 逃离 单源最短路
逃离Problem Description遥远的delta星球上，第4次世界大战的战火迅速燃遍各地。X国前哨站的部队成功获取敌方的作战计划，得知敌方将对前哨战及周边的道路进行轰炸，部队必须立即撤回基地。由于空军很忙，部队只能从走陆路。前哨站与基地间有n个中转站和m条双向道路，已知敌军对每条路开始实行轰炸的时刻（若某条道路将在第x秒开始被轰炸，则部队在第x秒及x秒以后不能处在该道路上），以及...
2018-09-26 22:10:37
240
原创 阅览室 模拟题
阅览室Problem Description一个阅览室每天都要接待大批读者。阅览室开门时间是O，关门时间是T（T≤1000）。每位读者的到达时间都不一样，并且想要阅读的刊物不超过5本。每位读者心里对自己想看的刊物都有一个排位，到达之后他会先去找自己最想看的刊物，如果找不到则去找其次想看的刊物。如果找不到任何他想看的刊物，他会开始等待，直到有一本以上的他想看的刊物被人放回原处。当然，他会先去拿...
2018-09-26 22:09:13
909
原创 穿越丛林 选择结构与循环结构
穿越丛林Problem Descriptionljj是一位富有冒险心又很喜欢研究数学的孩纸，有一天，他到一个丛林冒险，这里的树长有像0、4、6、8、9这样形状的洞，他要想穿过丛林，必须从这些树洞里钻过去。这时他忽然萌生了一个特别的想法，统计穿越丛林道路的条数！现在他已经知道了要经过丛林道路所经过的n棵树的顺序，以及与每棵上的树洞的形状的数字。Input文件第一行一个整数n，表示丛林中有洞...
2018-09-26 22:08:24
1208
原创 【jzoj】省选模拟2018.8.23 a 简单的暴力
Description 给定一个n×m 的 01 矩阵，求包含[l,r]个 1 的子矩形个数。 Input 第一行，两个正整数n，m。 接下来n 行，每行一个长度为 m 的 01 串，表示给定的矩阵。接下来一行，两个自然数 l，r。 Output 第一行，一个整数代表答案。 Sample Input 2 3 100 011 2...
2018-08-23 12:40:20
546
原创 简单的序列 简单的动态规划
Description 从前有个括号序列 s，满足 |s| = m。你需要统计括号序列对 (p, q) 的数量。 其中 (p, q) 满足 |p| + |s| + |q| = n，且 p + s + q 是一个合法的括号序列。 Input 从文件 bracket.in 中读入数据。 第一行两个正整数 n, m。 第二行一个长度为 m 的括号序列，表示 s。...
2018-08-23 09:00:26
728
原创 可爱精灵宝贝 动态规划讲解
Description Branimirko是一个对可爱精灵宝贝十分痴迷的玩家。最近，他闲得没事组织了一场捉精灵的游戏。游戏在一条街道上举行，街道上一侧有一排房子，从左到右房子标号由1到n。 刚开始玩家在k号房子前。有m个精灵，第i只精灵在第A[i]栋房子前，分值是B[i]，以及它在T[i]秒内（含）存在，之后消失。Branimirko可以选择移动至相邻的房子，耗时1秒。抓住精灵...
2018-08-23 08:04:00
755
原创 把弹珠放在盒子里 简单的动态规划
Description 我们有n个相同的弹珠，k个相同的盒子。现在随机的将每个弹珠扔进盒子中，使得最终每个盒子非空，求出一共有多少种不同方案。两种方案不同当且仅当将盒子中的弹珠数最小表示后不同。由于方案数可能非常多，把答案模998244353输出即可。 Input 第一行输入两个正整数n,k。 Output 输出共一行，一个整数表示Ans mod 9982443...
2018-08-22 19:42:01
1479
原创 快速幂 模板题
题目描述 输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。 输入输出格式 输入格式： 三个整数b,p,k. 输出格式： 输出“b^p mod k=s” s为运算结果 输入输出样例 输入样例1： 2 10 9 输出样例1： 2^10 mod 9=7很显然，这是一道很明白的快速幂。 当然，...
2018-08-22 16:27:49
562
原创 点分治 模板题
题目描述 给定一棵有n个点的树 询问树上距离为k的点对是否存在。 输入输出格式 输入格式： n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径 接下来m行每行询问一个K 输出格式： 对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号) 输入输出样例 输入样例1： 2 1 1 2 ...
2018-08-22 15:36:57
358
原创 东风谷早苗 简单的水题
Description 在幻想乡，东风谷早苗是以高达控闻名的高中生宅巫女。某一天，早苗终于入手了最新款的钢达姆模型。作为最新的钢达姆，当然有了与以往不同的功能了，那就是它能够自动行走，厉害吧（好吧，我自重）。早苗的新模型可以按照输入的命令进行移动，命令包含’E’、’S’、’W’、’N’四种，分别对应四个不同的方向，依次为东、南、西、北。执行某个命令时，它会向着对应方向移动一个单位。作为...
2018-08-22 14:44:08
578
原创 aplusb 简单的水题
Description SillyHook要给小朋友出题了，他想，对于初学者，第一题肯定是a+b啊，但当他出完数据后神奇地发现.in不见了，只留下了一些.out，他想还原.in，但情况实在太多了，于是他想要使得[a,b] ([a,b] 表示a,b 的最小公倍数)尽可能大。 Input 输入文件的第一行一个整数T表示数据组数。 接下来T行每行一个整数n，表示.out中的...
2018-08-22 11:31:40
1354
原创 炮兵部队 状态压缩动态规划的模板题
Description 司令部的将军们打算在N×M的网格地图上部署他们的炮兵部队。 一个N×M的地图由N行M列组成，地图的每一格可能是山地（用”H”表示），也可能是平原（用”P”表示），如下图。 在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）。 一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮...
2018-08-22 11:03:44
365
原创 旅游路线 简单的暴力
Description GZOI队员们到X镇游玩。 X镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成m×n个区域，这些区域标从北到南、从西到东的坐标标识为从坐标 (1,1) 到坐标 (m,n) 。 GZOI队员们预先对这m×n个区域打分V(i,j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便游玩，队员们需要选定...
2018-08-22 09:56:10
459
原创 神在夏至祭降下了神谕 树状数组和动态规划的结合
夏至祭是一场迎接祖灵于夏季归来同时祈求丰收的庆典。村里的男人会在广场上演出冬之军跟夏之军的战争，夏之军会打倒冬之军的大将冬男，再放火将他连山车一起烧掉。 谢尔吉斯村长已经选好了N个人参加演出，其中一些人负责演夏之军，另一些人负责演冬之军。由于人数众多，谢尔吉斯想把这N个人分成若干个连续的段。为了保证演出的顺利进行，每段的夏之君人数与冬之军人数之差的绝对值不能超过K。 谢尔吉斯想知...
2018-08-22 09:00:02
466
原创 金色丝线将瞬间一分为二 树状数组的使用
Description 为了解开骑士木乃伊事件，久城一弥和布洛瓦警官来到了停尸间。停尸间里有N具遗体，每具遗体都有一个坐标(X,Y)。 由于停尸间的遗体摆放得横平竖直，我们认为两具遗体(Xi,Yi)和(Xj,Yj)得距离为|Xi-Xj|+|Yi-Yj|。 负责停尸间的工人由于需要经常搬运遗体，所以对任意两具遗体的距离之和特别有印象。 工人们已经记不得每具遗体对应的是什...
2018-08-22 07:55:15
415
原创 区间 分块的暴力做法
区间 Description 萌萌哒Salroey最近得到了一个长度为n的正整数数列Si，下标从1开始标号，她现在想让你对于一个给定正整数k，求出tj表示区间[j,j+k-1]中所有元素的乘积（1≤j≤n-k+1）。 为了方便输出，你只需要把所有tj对P取模之后，输出它们的异或和。 Input 第一行三个正整数n,k,P,分别表示序列长度，区间长度和模数。 ...
2018-08-12 09:58:12
804
原创 餐馆 树型动态规划模板题
餐馆 Description K妹的胡椒粉大卖，这辣味让食客们感到刺激，许多餐馆也买这位K妹的账。 有N家餐馆，有N-1条道路，这N家餐馆能相互到达。K妹从1号餐馆开始。每一个单位时间，K妹可以在所在餐馆卖完尽量多的胡椒粉，或者移动到有道路直接相连的隔壁餐馆。第i家餐馆最多需要A[i]瓶胡椒粉。K妹有M个单位的时间，问她最多能卖多少胡椒粉。 Input 第一行有...
2018-08-11 10:45:03
295
原创 词典 Trie字典树模板题
词典 Description 小C有n个字符串T1…Tn，给出n个询问 第i个询问给出一个字符串Si，对于每个询问，我们可以得到一个长度为n的bool数组a，其中ai=[Si是否为Ti的前缀] 例如，a=[0,0,1]表示Si是T3的前缀，但不是T1，T2的前缀。 对于每个询问给出的a数组，你的任务是求出它的最长全0子串长度 Input 第一行两个数...
2018-08-11 10:17:04
451
原创 旅行 关于SPFA的做法
旅行 Description 悠悠岁月，不知不觉，距那传说中的pppfish晋级泡泡帝已是过去数十年。数十年中，这颗泡泡树上，也是再度变得精彩，各种泡泡天才辈出，惊艳世人，然而，似乎不论后人如何的出彩，在他们的头顶之上，依然是有着一道身影而立。 泡泡帝，pppfish。现在，pppfish即将带着被自己收服的无数个泡泡怪前往下一个空间，而在前往下一个空间的道路上，有N个中...
2018-08-10 21:52:58
444
原创 关于字符串(zero)的特殊解法
字符串(zero) 给你一个只包含“0”与“1”的字符串S，你可以对这个字符串进行操作，每次操作将字符串中任意一个字符移动到字符串的任意位置，例如S=“0010”’，你可以将首位的0移动到末尾位置，使得S=“0100”。 现在有Q次询问，每次询问给出一个操作次数上限K，每次询问你需要回答在对字符串S进行不超过K次操作后，字符串最长连续“0”的长度。 输入 第一行一个01字符
2018-02-04 10:54:39
944
原创 重建 关于联通块的做法
重建 A国拥有N个城市编号为0~N-1，这N个城市由N条双向道路所连接形成了一个环。环上城市的编号沿顺时针方向递增（除第N-1号城市外）。 不幸的是，A国遭遇了一场地震，摧毁了所有N个城市的电力系统。在地震后的K天中，第i天会由城市Ci派出一支重建队伍，他们从第Ci个城市出发，找到顺时针方向上第一个电力系统未被修复的城市并修复它。在该城市电力系统被修复后，所有与它有联系的城市将会向
2018-02-03 10:20:06
466
原创 关于重建的模板题
重建 A国拥有N个城市编号为0~N-1，这N个城市由N条双向道路所连接形成了一个环。环上城市的编号沿顺时针方向递增（除第N-1号城市外）。 不幸的是，A国遭遇了一场地震，摧毁了所有N个城市的电力系统。在地震后的K天中，第i天会由城市Ci派出一支重建队伍，他们从第Ci个城市出发，找到顺时针方向上第一个电力系统未被修复的城市并修复它。在该城市电力系统被修复后，所有与它有联系的城市将会向它提
2018-02-02 11:43:18
240
原创 合并果子 关于排序的做法
题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要
2018-01-20 16:59:31
822
原创 合并果子 单调队列的模板题
题目描述 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要
2018-01-19 18:00:03
661
原创 放苹果 动态规划
放苹果 题目描述 把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分发（5,1,1和1,1,5是同一种方法） 输入输出格式 输入格式 第一行是测试数据的数目t（0 输出格式 对输入的每组数据M和N，用一行输出相应的K 输入输出样例 1 7 3 输出样例 8
2018-01-18 18:11:39
953
转载 欢迎使用CSDN-markdown编辑器
欢迎使用Markdown编辑器写博客本Markdown编辑器使用StackEdit修改而来，用它写博客，将会带来全新的体验哦：Markdown和扩展Markdown简洁的语法代码块高亮图片链接和图片上传LaTex数学公式UML序列图和流程图离线写博客导入导出Markdown文件丰富的快捷键快捷键加粗 Ctrl + B 斜体 Ctrl + I 引用 Ctrl
2017-10-27 18:10:43
156
原创 关于(最长链)的模板题
题目描述 Description 现给出一棵N个结点二叉树，问这棵二叉树中最长链的长度为多少，保证了1号结点为二叉树的根。 输入描述 Input Description 输入的第1行为包含了一个正整数N，为这棵二叉树的结点数，结点标号由1至N。 接下来N行，这N行中的第i行包含两个正整数l[i], r[i]，表示了结点i的左儿子与右儿子编号。如果l[i]为0，表示结点i没
2017-10-19 17:58:50
1076
原创 单调栈，关于（Bad Hair Day）的模板题
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。单调栈是一种单调递增或单调递减的栈，数据有序地储存在栈中，因此对于解决部分题目有着不错的效果。 题目如下： Bad Hair Day Some of Farmer John’s N
2017-10-02 21:07:45
480
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人