2 rvlt1

尚未进行身份认证

暂无相关描述

等级
博文 82
排名 9w+

P1091 合唱队形 dp

题目描述NN位同学站成一排,音乐老师要请其中的(N-KN−K)位同学出列,使得剩下的KK位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2,…,K1,2,…,K,他们的身高分别为T1​,T2​,…,TK,则他们的身高满足T1​<...<Ti​>Ti+1​>…>TK​(1≤i≤K)。你的任务是,已知所有N位同学的身高,计算最...

2019-05-14 21:01:44

P1057 传球游戏 dp

题目描述上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。游戏规则是这样的:nn个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意),当老师再次吹哨子时,传球停止,此时,拿着球没有传出去的那个同学就是败者,要给大家表演一个节目。聪明的小蛮提出一个有趣的问题:有多少种不同...

2019-05-13 21:21:53

P1044 栈 卡特兰数

题目背景栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作,即poppop(从栈顶弹出一个元素)和pushpush(将一个元素进栈)。栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。题目描述宁宁考虑的是这样一个问题:一个...

2019-05-12 21:55:10

P1002 过河卒

题目描述棋盘上AA点有一个过河卒,需要走到目标BB点。卒行走的规则:可以向下、或者向右。同时在棋盘上CC点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示,AA点(0,0)(0,0)、BB点(n,m)(n,m)(nn,mm为不超过2020的整数),同样马的位置坐标是需要给出的。现在要求你计算出卒从AA点能够到达BB点的...

2019-05-10 21:45:56

nyoj1367 物流配送 最小费用流

题目描述:物流配送是物流活动中一种非单一的业务形式,它与物品流动、资金流动紧密结合。备货是配送的准备工作或基础工作,备货工作包括筹集货源、订货或购货、集货、进货及有关的质量检查、结算、交接等。配送的优势之一,就是可以集中用户的需求进行一定规模的备货。备货是决定配送成败的初期工作,如果备货成本太高,会大大降低配送的效益。配送中的储存有储备及暂存两种形态。配送储备是按一定时期的配送经营要求,形成的...

2019-05-04 21:20:00

最小费用流 用SPFA实现

/*(1)找到一条从源点到达汇点的“距离最短”的路径,“距离”使用该路径上的边的单位费用之和来衡量。(2)然后找出这条路径上的边的容量的最小值f,则当前最大流max_flow扩充f,同时当前最小费用min_cost扩充f*min_dist(s,t)。(3)将这条路径上的每条正向边的容量都减少f,每条反向边的容量都增加f。(4)重复(1)--(3)直到无法找到从源点到达汇点的路径。...

2019-05-04 21:08:39

nyoj15 括号配对2 区间dp

题目描述:给你一个字符串,里面只包含"(",")","[","]"四种符号,请问你需要至少添加多少个括号才能使这些括号匹配起来。如:[]是匹配的([])[]是匹配的((]是不匹配的([)]是不匹配的输入描述:第一行输入一个正整数N,表示测试数据组数(N<=10)每组测试数据都只有一行,是一个字符串S,S中只包含以上所说的四种字符,S的长度不超过100输出描述:...

2019-05-03 20:14:18

牛客网 被3整除的子序列 dp

时间限制:C/C++1秒,其他语言2秒空间限制:C/C++524288K,其他语言1048576K64bitIOFormat:%lld题目描述给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除答案对1e9+7取模输入描述:输入一个字符串,由数字构成,长度小于等于50输出描述:输出一个整数示例1输入132输出3...

2019-05-03 18:02:29

9-Prototypes analyze 二叉排序树

题目描述:ALphaCeilingManufacturers(ACM)isanalyzingthepropertiesofitsnewseriesofIncrediblyCollapse-ProofCeilings(ICPCs).AnICPCconsistsofnlayersofmaterial,eachwithadifferentv...

2019-04-21 21:37:22

计算几何 dls

实数比较#definedoubledbconstdbEPS=1e-9;intsign(dba){returna<-EPS?-1:a>EPS};intcmp(dba,dbb){returnsign(a-b)};点structP{ dbx,y; P(){} P(db_x,db_y):x(_x),y(_y){} Popera...

2019-04-18 12:22:01

poj1463 Strategic game 树形dp

TimeLimit:2000MS MemoryLimit:10000K TotalSubmissions:10111 Accepted:4761 DescriptionBobenjoysplayingcomputergames,especiallystrategicgames,butsometimeshecannot...

2019-04-16 16:00:22

Codeforces Round #398 (Div. 2) 767C 树形dfs

OnceatNewYearDimahadadreaminwhichhewaspresentedafairygarland.Agarlandisasetoflamps,somepairsofwhichareconnectedbywires.Dimarememberedthateachtwolampsinthegarland...

2019-04-16 09:26:06

桂林电子科技大学第三届ACM程序设计竞赛 二元 贪心

时间限制:C/C++1秒,其他语言2秒空间限制:C/C++262144K,其他语言524288K64bitIOFormat:%lld题目描述小猫在研究二元组。小猫在研究最大值。给定N个二元组(a1,b1),(a2,b2),…,(aN,bN),请你从中选出恰好K个,使得ai的最小值与bi的最小值之和最大。请输出ai的最小值与bi的最小值之和输入描述:第一行...

2019-04-15 21:21:36

桂林电子科技大学第三届ACM程序设计竞赛 点对 floyd

时间限制:C/C++1秒,其他语言2秒空间限制:C/C++262144K,其他语言524288K64bitIOFormat:%lld题目描述小猫在研究有向图。小猫在研究联通性。给定一张N个点,M条边的有向图,问有多少点对(u,v)(u<v),满足u能到达v且v也能到达u。输入描述:第一行两个正整数N,M,表示点数与边数。接下来M行,第i行两个正整数ui,v...

2019-04-14 17:17:53

double等浮点数比较问题,eps

https://blog.csdn.net/major_zhang/article/details/65449685

2019-04-11 21:23:40

poj2449 Remmarguts' Date 第K短路(A*算法)

求从s点到e点的第k条最短路。这里是最短路的典型变形之一:A*算法。A*算法是一种启发式搜索,不是纯粹的盲目搜索。A*算法中有个估值算法g(n),对于每个点而言,都有一个g(n)和h(n)来确定的f(n),实际上就是以f(n)为参考权值来确定搜索的方向,在这里,h(n)表示的是从s点出发到这个点现在走过的路径长度,而g(n)表示的是从n到e的最短长度的大小,那么就确定了搜索的优先性,这里的A*算法...

2019-04-10 22:32:02

邻接表的两种实现方法

1.用数组head[MAXN],next[MAXM];//head[v]记录表头节点v的第一条边的标号,next[u]标号为u的边的下一条边。structnode{ ints,e,w; node(ints,inte,intw){ this->s=s;this->e=e;this->w=w; } node(){}}t[MAXM];voida...

2019-04-09 12:38:05

poj1511 Invitation Cards SPFA

http://poj.org/problem?id=1511先一次用SPFA求早上从定点1到各点的最短路径和,再对其求反向图,用SPFA求一次顶点1到各顶点的最短路径和,这个值其实就是晚上各点回到顶点1的最短路径和了。#include<cstdio>#include<cstring>#include<algorithm>#include&...

2019-04-09 12:25:54

SPFA求最短路及判定负环

为什么能够判负环?根据原理,每个最短路都不会超过n-1条边,如果说超过了n-1条边的话,那么就说明走了重点,即走了环,因此就可以知道里面产生了负环,才使得这个最短路无解。SPFA对这个算法很好地进行了优化。优化的根源在于,能够改变最短路的路径都是之前成功松弛过的点,也就是说,如果一个点被成功地松弛了,那么这个点才有可能松弛其它边,没有被松弛的点,就说明这个点所记录的最短路径没有改变,那么以...

2019-04-08 21:52:41

dijkstra的邻接表实现和堆优化

时间复杂度O(eloge),在n的数量级>=1e5时必须采用这种堆优化+邻接表方式。intvis[MAXN];intpre[MAXN];//前驱节点intdis[MAXN];//距离源的长度structnode{ intvex,w;//节点和距离源点的最优距离 friendbooloperator<(nodea,nodeb){//重载运算符,使其...

2019-04-07 20:16:22
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周上午根据用户上周的博文发布情况由系统自动颁发。