3 shiyongyang

尚未进行身份认证

暂无相关简介

等级
TA的排名 6w+

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

51 nod 1789 跑的比谁都快

1789 跑的比谁都快 基准时间限制:1.5 秒 空间限制:262144 KB 分值: 160 难度:6级算法题香港记者跑的比谁都快是众所周知的常识。现在,香港记者站在一颗有 n 个点的树的根结点上(即1号点),编号为 i 的点拥有权值 a[i] ,数据保证每个点的编号都小于它任意孩子结点的别号。我们假定这棵树的每个叶子结点都在发生一

2018-02-06 11:15:26

BZOJ 4554

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

2017-11-07 20:34:36

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

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

高精度四则运算模板

高精度乘法 #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

小W走迷宫

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

2017-10-25 15:31:54

BZOJ 2669

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

2017-10-25 15:30:33

洛谷 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

洛谷P1856

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

2017-10-25 15:24:55

斜率优化 入门超经典,简单快乐入门

真是佩服大米饼: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

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

【bzoj3522】[Poi2014]Hotel 树形dp

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

2017-10-19 21:55:25

高斯消元集合

//高斯消元法解异或方程组,返回方程解得个数。  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

【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

【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

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

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

2017-10-19 10:16:37

【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

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

礼物 期望dp

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

2017-10-19 08:22:33

查看更多

勋章 我的勋章
    暂无奖章