shiyongyang-CSDN博客

原创 51 nod 1775 LIS Counting

1775 LIS Counting 基准时间限制：1.5 秒空间限制：262144 KB 分值: 640 难度：8级算法题输入一个数列a[1..n]，其中1<=a[i]<=n，且a[i]≠a[j] (i≠j)，也就是说a是1~n的一个排列。a的子序列是从a中删除若干个元素后，剩下的元素按照原来顺序组成的序列。显然，a有2^n个子序列（包括空序列

2018-02-07 15:28:13 339

原创ＢＺＯＪ　４５５４

题目描述在2016年，佳缘姐姐喜欢上了一款游戏，叫做泡泡堂。简单的说，这个游戏就是在一张地图上放上若干个炸弹，看是否能炸到对手，或者躲开对手的炸弹。在玩游戏的过程中，小H想到了这样一个问题：当给定一张地图，在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头，但是不能穿透硬石头。给定一张n*m的网格地图:其中

2017-11-07 20:34:36 356

原创 HDU 5283

题目大意池塘里有一些鱼和一个渔网，池塘可以看成一个二维的平面，而渔网可以看成一个与坐标轴平行的矩形。每条鱼都被给予了一个标号，分别从1到n标号，n表示池塘里鱼的总数。鱼的游动可以概括为两个动作： 1 l r d : 表示标号在[l，r]这个区间内的鱼向x轴正方向游动了d个单位长度。 2 l r d：表示标号在[l，r]这个区间内的鱼向y轴正方向游动了d个单位长度。还有

2017-10-25 15:36:49 315

原创 BZOJ 2653

Description一个长度为n的序列a，设其排过序之后为b，其中位数定义为b[n/2]，其中a,b从0开始标号,除法取下整。给你一个长度为n的序列s。回答Q个这样的询问：s的左端点在[a,b]之间,右端点在[c,d]之间的子序列中，最大的中位数。其中aInput第一行序列长度n。接下来n行按顺序给出a中的数。接下来一行Q。然后Q行每行a,b,c,d，

2017-10-25 15:35:23 217

原创高精度四则运算模板

高精度乘法 #include #include #include #include #include #define N 300000using namespace std;char aa[N],bb[N];int lena,lenb,a[N],b[N],ans[N],len,nxt,tmp;int main(){ scanf("%s%s",aa+1,bb+1);lena=

2017-10-25 15:33:56 341

原创小W走迷宫

小W 走迷宫【问题描述】小W 被小M 困在了一个方格矩阵迷宫里，矩阵边界在无穷远处，我们做出如下的假设：a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b. 走过的格子立即塌陷无法再走第二次；c. 只能向北、东、西三个方向走。小W 走了没多久就累坏了，他很想知道如果允许在方格矩阵上走 N 步，共有多少种不同的方案。（开始时小W 就在方格矩阵上的任意

2017-10-25 15:31:54 276

原创 BZOJ 2669

题意有一个 n×m 的矩阵，其中每个数都是 [1,n×m] 中的一个，不会重复。有一些地方的值比周围的8个位置都小（如果有的话）。给出这些位置，求这样的矩阵有多少个。n≤4,m≤7 。/*状态压缩好题。对于局部最小值的位置一定不会超过8个，对于这种情况可以直接状态压缩，用最多8个二进制1来表示那些位置已经放了数。由于有些位置不受任何限制，所以将那些不受限制的点变成局部最小值位

2017-10-25 15:30:33 211

原创洛谷 P1848

题目描述：当农夫约翰闲的没事干的时候，他喜欢坐下来看书。多年过去，他已经收集了 N 本书 (1 每本书 i 都有宽度 W(i) 和高度 H(i)。书需要按顺序添加到一组书架上；比如说，第一层架子应该包含书籍1 ... k，第二层架子应该以第k + 1本书开始，以下如此。每层架子的总宽度最大为L（1≤L≤1,000,000,000）。每层的高度等于该层上最高的书的高度，并且整个书架的高度是所

2017-10-25 15:27:30 292

原创洛谷P1856

题目描述：给出n个矩形的左下角和右上角坐标，求n个矩形组合成的新图形的周长（有重叠）（-----扫描线-------模板）题解：扫描线模板/*对于矩形有长和宽两个属性，那就将这两个属性分开看，因为对答案的贡献是独立的。当啷个矩形有重合时，必然存在连续至少两个下边，一个下边对应一个上边，一个+1一个-1，判断区间是否哦为1/0，是即为有贡献。之一排序的时候是按照横纵坐标和上下边分

2017-10-25 15:24:55 252

转载斜率优化入门超经典，简单快乐入门

真是佩服大米饼：http://www.cnblogs.com/Paul-Guderian/p/7259491.html 值得一看的博客[1]玩具装箱（详细阐述）【LINK】步骤一：列出DP方程式:设f[i]表示分组完前i件物品的最小花费,为方便计算，设sum[i]表示是前i件物品的长度和。 f[i]=Min(f[j]+(sum[i]-su

2017-10-20 21:57:26 6301 2

原创 BZOJ 1907 树的路径覆盖

题目描述输入输出样例输入171 22 32 44 65 66 7样例输出3题解：比较裸的树形dp。对于任意节点x，只有三种情况，x单独成链，x与子树中的其中一条链成一条链，x与子树中的两条链成一条链。#include #include #include #define N 1001

2017-10-20 16:16:49 267

原创【bzoj3522】[Poi2014]Hotel 树形dp

题目描述有一个树形结构的宾馆，n个房间，n-1条无向边，每条边的长度相同，任意两个房间可以相互到达。吉丽要给他的三个妹子各开（一个）房（间）。三个妹子住的房间要互不相同（否则要打起来了），为了让吉丽满意，你需要让三个房间两两距离相同。有多少种方案能让吉丽满意？输入第一行一个数n。接下来n-1行，每行两个数x,y，表示x和y之间有一条边相连。输出让吉丽

2017-10-19 21:55:25 310

转载高斯消元集合

//高斯消元法解异或方程组，返回方程解得个数。 const int N = 30; int A[N][N];//关系矩阵 int Gauss(int equ,int var){//返回解得个数。 int row,col; for(row=0,col=0;row int max_r=row;//默认最大为本行 fo

2017-10-19 17:32:12 500

原创【bzoj4872】[Shoi2017]分手是祝愿数论+期望dp

题目描述Zeit und Raum trennen dich und mich.时空将你我分开。B 君在玩一个游戏，这个游戏由 n 个灯和 n 个开关组成，给定这 n 个灯的初始状态，下标为从 1 到 n 的正整数。每个灯有两个状态亮和灭，我们用 1 来表示这个灯是亮的，用 0 表示这个灯是灭的，游戏的目标是使所有灯都灭掉。但是当操作第 i 个开关时，所有编号为 i 的约数

2017-10-19 15:49:27 316

原创【bzoj4318】OSU! 期望dp

题目描述osu 是一款群众喜闻乐见的休闲软件。我们可以把osu的规则简化与改编成以下的样子: 一共有n次操作，每次操作只有成功与失败之分，成功对应1，失败对应0，n次操作对应为1个长度为n的01串。在这个串中连续的 X个1可以贡献X^3 的分数，这x个1不能被其他连续的1所包含（也就是极长的一串1，具体见样例解释）现在给出n，以及每个操作的成功率，请你输出期望分

2017-10-19 11:33:24 260

原创【bzoj3036】绿豆蛙的归宿期望dp

题目描述随着新版百度空间的下线，Blog宠物绿豆蛙完成了它的使命，去寻找它新的归宿。给出一个有向无环的连通图，起点为1终点为N，每条边都有一个长度。绿豆蛙从起点出发，走向终点。到达每一个顶点时，如果有K条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？输入第

2017-10-19 10:16:37 285

原创【bzoj2318】Spoj4060 game with probability Problem 概率dp

题目描述Alice和Bob在玩一个游戏。有n个石子在这里，Alice和Bob轮流投掷硬币，如果正面朝上，则从n个石子中取出一个石子，否则不做任何事。取到最后一颗石子的人胜利。Alice在投掷硬币时有p的概率投掷出他想投的一面，同样，Bob有q的概率投掷出他相投的一面。现在Alice先手投掷硬币，假设他们都想赢得游戏，问你Alice胜利的概率为多少。输入第一行一个正整

2017-10-19 09:17:00 348

转载 Collecting Bugs POJ 2096

Collecting BugsTime Limit: 10000MS Memory Limit: 64000KTotal Submissions: 2041 Accepted: 974Case Time Limit: 2000MS Special JudgeDescriptionIvan

2017-10-19 08:31:29 227

原创礼物期望dp

Description夏川的生日就要到了。作为夏川形式上的男朋友，季堂打算给夏川买一些生日礼物。商店里一共有种礼物。夏川每得到一种礼物，就会获得相应喜悦值Wi（每种礼物的喜悦值不能重复获得）。每次，店员会按照一定的概率Pi（或者不拿出礼物），将第i种礼物拿出来。季堂每次都会将店员拿出来的礼物买下来。众所周知，白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。

2017-10-19 08:22:33 314

转载收集邮票

题目描述有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k张邮票需要支付k元钱。现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。输入一行,一个数字N N输出要付出多少钱. 保

2017-10-18 21:22:42 400

原创【bzoj3450】Tyvj1952 Easy 期望dp

题目描述某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠运气:(我们来简化一下这个游戏的规则有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，连续a个comb就有a*a分，comb就是极大的连续o。比如ooxxxxooooxxx，分数就是2*2+4*4=4+16=20。Sevenkplus闲的慌就看他打了一盘，有些地方跟运气无关要么是o要

2017-10-18 20:19:34 265

转载【poj2096】Collecting Bugs 期望dp

题意有s个系统，n种bug，小明每天找出一个bug，可能是任意一个系统的，可能是任意一种bug，即是某一系统的bug概率是1/s，是某一种bug概率是1/n。求他找到s个系统的bug，n种bug，需要的天数的期望。分析计算期望E=∑所有可能需要的天数*概率找到s个系统n种bug，需要最少max（s，n）天，而可能的天数是无穷的，这样计算很复杂，复杂到算不了。所以考虑dp，期

2017-10-18 19:54:00 186

原创【bzoj2213】[Poi2011]Difference dp

题目描述已知一个长度为n的由小写字母组成的字符串，求其中连续的一段，满足该段中出现最多的字母出现的个数减去该段中出现最少的字母出现的个数最大。求这个个数。输入第一行，n第二行，该字符串1输出一行，表示结果样例输入10aabbaaabab样例输出3题解dp令sum[i][j]sum[i

2017-10-17 20:42:38 423

原创 merge

2.石子合并加强版(merge)【问题描述】还记得经典题石子合并吗？现在小Y将题目加强啦！在一个圆形操场的四周摆放着n堆石子，现要将石子有次序地合并成一堆。规定每次只能选取相邻的三堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，读入石子堆数n及每堆的石子数。选择一种合并石子的方案,使得做(n-1)/2次合并,得分的总和最小；【输入格式】第1行1个数，表

2017-10-17 19:15:28 198

原创错排问题组合数学+容斥原理

3.错排问题(problem)【题目描述】n本不同的书放在书架上。其中m本书已经重新摆放好，将剩下的n-m 本书也重新摆放，使每本书都不在原来放的位置。求有几种摆法。【输入数据】第1行两个数n,m；接下来m行，每行两个数xi,yi表示原来的第xi本书已经放到了第yi 个位置上数据保证任意两个x不相同，任意两个y不相同。【输出数据】输出方案数，对1000000007取

2017-10-17 17:58:33 1983

原创 NOI 嘉年华

题目描述NOI2011 在吉林大学开始啦！为了迎接来自全国各地最优秀的信息学选手，吉林大学决定举办两场盛大的 NOI 嘉年华活动，分在两个不同的地点举办。每个嘉年华可能包含很多个活动，而每个活动只能在一个嘉年华中举办。现在嘉年华活动的组织者小安一共收到了 n个活动的举办申请，其中第 i 个活动的起始时间为 Si，活动的持续时间为Ti。这些活动都可以安排到任意一个嘉年华的会场，也可以不安排。

2017-10-16 20:52:08 402

原创【bzoj3866】The Romantic Hero dp

题目描述给你n个数，从中选出两个不相交非空集合S和T，使得S中的每一个元素都在T集合的前面，并且S集合中的所有数的亦或等于T集合中的所有数的与，求方案数 mod 10^9+7。输入The first line contains an integer T, denoting the number of the test cases.For each test case

2017-10-16 20:44:08 213

转载 unique（）去重函数

unique()函数是一个去重函数，STL中unique的函数 unique的功能是去除相邻的重复元素(只保留一个),还有一个容易忽视的特性是它并不真正把重复的元素删除。他是c++中的函数，所以头文件要加#include，具体用法如下：int num[100];unique(num,mun+n)返回的是num去重后的尾地址，之所以说比不真正把重复的元素删除，其实是，该函数把重复的元素一到后

2017-10-16 11:41:48 624

原创【bzoj1190】[HNOI2007]梦幻岛宝珠分层背包dp

题目描述给你N颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过W，且总价值最大为，并输出最大的总价值。数据范围：N输入输入文件中包含多组数据。每组数据的格式如下：第一行是两个正整数n和W，1≤n≤100,1≤W≤2^30，分别表示宝石的数目和最多能带走的宝石重量。接下来的n行，每行有两个正整数weighti和valuei，1≤weighti≤2

2017-10-16 10:09:14 1195

原创洛谷 P2296 寻找道路

题目描述在有向图G 中，每条边的长度均为1 ，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：1 ．路径上的所有点的出边所指向的点都直接或间接与终点连通。2 ．在满足条件1 的情况下使路径最短。注意：图G 中可能存在重边和自环，题目保证终点没有出边。请你输出符合条件的路径的长度。输入输出格式输入格式：输入文件名为road .in。第一行

2017-10-13 22:03:45 241

原创洛谷 P2038 无线网络发射器选址

题目描述随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。假设该城市的布局为由严格平行的129 条东西向街道和129 条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值 1 。东西向街道从北到南依次编号为0,1,2…128 , 南北向街道从西到东依次编号为0,1,2…128 。东西向街道和南北向街道相交形成路口，规定编号为x 的

2017-10-13 19:26:13 461 1

转载指针

指针的概念指针是一个特殊的变量，它里面存储的数值被解释成为内存里的一个地址。要搞清一个指针需要搞清指针的四方面的内容：指针的类型，指针所指向的类型，指针的值或者叫指针所指向的内存区，还有指针本身所占据的内存区。让我们分别说明。先声明几个指针放着做例子：例一： int *ptr; char *ptr; int **ptr; int (*pt

2017-10-13 07:10:00 160

原创自然数线段树

3.自然数(mex.cpp)【问题描述】有一年，有道题目叫mex,Fanvree三秒钟就切了，所以今天，他要把题目改良，出到NOIP上。我们定义mex(i,j)为序列中第i项到第j项所没有出现的最小自然数。Fanvree的题目是，给你一个序列，求Σ1【输入格式】第一行一个整数n，表示序列大小。接下来一行，n个整数，描述序列【输出格式】只含一个整数，表示Σ1【

2017-10-12 20:13:09 542

原创钱仓最大字段和+贪心+模拟

1.钱仓(barn.cpp)【问题描述】Fanvree家有n个钱仓，他们以构成一个环，从1到n顺时针方向分布，也就是说第i个钱仓会和第i-1个和第i+1个相邻，特别地，第n个钱仓和第1个钱仓相邻。众所周知，Fanvree是个极其聪明的人，所以，他不会把钱全部放在同一个钱仓，他会平均分配，每个钱仓放1mol的钱。在开始时，每个钱仓会有ci mol的钱，保证Σci=n, Fanvree会推

2017-10-12 17:43:44 802

原创 noip 2015 T5 子串字符串dp

2．子串 (substring.cpp/c/pas) 【问题描述】有两个仅包含小写英文字母的字符串A和B。现在要从字符串A中取出k个互不重叠的非空子串，然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字

2017-10-11 07:39:48 298 1

原创天上掉馅饼期望dp+状压dp

天上掉馅饼(bonus)题目描述小G进入了一个神奇的世界，在这个世界，天上会掉下一些馅饼。今天，天上会随机掉下k个馅饼。每次天上掉下馅饼，小G可以选择吃或者不吃（必须在下一个馅饼掉下来之前作出选择，并且现在决定不吃的话以后也不能吃）。馅饼有n种不同的馅，根据物理定律，天上掉下这n种馅饼的概率相同且相互独立。然而，每一种馅饼i都有一个前提馅饼集合Si。只有当 Si 中的馅饼都吃过

2017-10-10 18:02:16 571

原创未知

题意：给定一个n个数的序列，分成k部分，求每一部分不同值个数之和的最大值。题解：结论，对于第i个元素，若i~n分为1部分，前i-1个数分成k-1部分，那么前i-1分成k-1也一定是最大的，那么考虑dp，枚举i这个位置，找出最大值。dp【j】【i】表示前j个数分成i部分的最大值，对于第k个数date【k】，date【k】仅对date【k】最近一次出现的位置last【date【k】+1】~k这段区

2017-10-10 17:54:01 179

原创 exlcs

exLCS(lcs.cpp)题目描述：给出两个仅有小写字母组成的字符串str1和str2，试求出两个串的最长公共子序列。公共子序列定义如下：若有a12k和b12k，满足str1[ai]=str2[bi]，∀i∈{1,2,3,···,k},则称找到了一个长度为 k 的公共子序列。输入格式：第一行一个字符串str1。第二行一个字符串str2。输出格式：一行，

2017-10-08 22:05:33 257

原创魔方大模拟

魔方(cube.cpp)题目描述：给出一个二阶魔方，保证 N 步以内能够还原。“还原”被定义为每个面均为纯色。请给出，操作编号字典序最小，且不存在同类操作相邻，的还原方案。输入格式：第一行一个正整数N，表示最多步数。接下来24个整数，按上图的顺序依次给出Ci，Ci∈{1,2,3,4,5,6}。输出格式：一行，t个用空格隔开的正整数，表示复原的

2017-10-08 18:01:09 340

原创 51 nod 1378 夹克老爷的愤怒树形dp + 贪心

1378 夹克老爷的愤怒夹克老爷逢三抽一之后，由于采用了新师爷的策略，乡民们叫苦不堪，开始组织起来暴力抗租。夹克老爷很愤怒，他决定派家丁常驻村中进行镇压。诺德县有N个村庄，编号0至 N-1，这些村庄之间用N - 1条道路连接起来。家丁都是经过系统训练的暴力机器，每名家丁可以被派驻在一个村庄，并镇压当前村庄以及距离该村庄不超过K段道路的村庄。夹克老爷一贯奉行最小成本最大利润的

2017-10-06 20:48:40 274

空空如也

空空如也