2 NOIAu

尚未进行身份认证

最后一天啦~

等级
TA的排名 1w+

一句话详细题解+优质题目及其博客(清真代码)链接 (持续更新)+知识点讲解汇总

CODEVSNOI2002贪吃的九头蛇codevs1746题解:树形DP,发现当”小头”大于等于2的时候,我们可以让小头们交替地去吃果子,比如son让小头A吃,可以让小头B吃father,让小头A吃grandfather,再让小头B吃grandgrandfather…所以我们发现其实只和”大头”吃那些点有关,所以我们定义dp[i][j][k]表示当前在位置i,i的子树里面大头吃j个,其中位置

2017-10-17 16:34:38

BZOJ 2427: [HAOI2010]软件安装 Tarjan缩点 + DP

TimeLimit:10SecMemoryLimit:128MBSubmit:1628Solved:635Description现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软

2017-10-13 22:14:30

BZOJ 2730: [HNOI2012]矿场搭建 割点 + 乘法原理

TimeLimit:10SecMemoryLimit:128MBSubmit:2362Solved:1093Description煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。请写一个

2017-10-13 20:34:40

HDU 4738 Caocao's Bridges 求桥 诸葛亮带着炸弹跑路了

DescriptionCaocaowasdefeatedbyZhugeLiangandZhouYuinthebattleofChibi.Buthewouldn’tgiveup.Caocao’sarmystillwasnotgoodatwaterbattles,sohecameupwithanotheridea.Hebuiltm

2017-10-13 18:58:59

POJ 1144 Network 裸割点

题意:给一个图,求割点个数#include<cstdio>#include<iostream>#include<cstring>usingnamespacestd;constintMAXN=110;intlow[MAXN],dfn[MAXN],head[MAXN],tail,cnt,timer,n;structLine{intto,nxt;}li

2017-10-13 14:19:59

BZOJ 1097: [POI2007]旅游景点atr 最短路 堆优Dijkstra 状压

TimeLimit:30SecMemoryLimit:357MBSubmit:2021Solved:515Description  FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景,品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的,比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山,而是希望去另外什么地方喝下午茶。幸

2017-10-13 12:20:12

BZOJ 1375: [Baltic2002]Bicriterial routing 双调路径 SPFA+DP思想

TimeLimit:5SecMemoryLimit:64MBSubmit:513Solved:189Description来越多,因此选择最佳路径是很现实的问题。城市的道路是双向的,每条道路有固定的旅行时间以及需要支付的费用。路径由连续的道路组成。总时间是各条道路旅行时间的和,总费用是各条道路所支付费用的总和。同样的出发地和目的地,如果路径A比路径B所需时间少且费用低,那

2017-10-13 10:13:05

POJ 3159 Candies 差分约束系统(这题卡SPFA的队列的双端队列)

DescriptionDuringthekindergartendays,flymousewasthemonitorofhisclass.Occasionallythehead-teacherbroughtthekidsofflymouse’sclassalargebagofcandiesandhadflymousedistributethe

2017-10-13 09:04:09

PoJ 2983 Is the Information Reliable? 差分约束系统

DescriptionThegalaxywarbetweentheEmpireDracoandtheCommonwealthofZibubrokeout3yearsago.DracoestablishedalineofdefensecalledGrot.GrotisastraightlinewithNdefensestations.

2017-10-12 22:18:00

POJ 1364 King 差分约束系统

DescriptionOnce,inonekingdom,therewasaqueenandthatqueenwasexpectingababy.Thequeenprayed:“Ifmychildwasasonandifonlyhewasasoundking.”Afterninemonthsherchildwasborn,

2017-10-12 19:04:36

POJ 1201 Intervals 差分约束系统

TimeLimit:2000MSMemoryLimit:65536KTotalSubmissions:27889Accepted:10743DescriptionYouaregivennclosed,integerintervals[ai,bi]andnintegersc1,…,cn.Writeaprogramth

2017-10-12 16:59:44

P1073 最优贸易 NOIP 2009 最短路

题目描述C国有n个大城市和m条道路,每条道路连接这n个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也计为1条。C国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价格不一定相同。但是,同一种商品在同一个城市的买入价和卖出价始终是相同的。商人阿龙来到

2017-10-12 14:48:57

BZOJ 4562: [Haoi2016]食物链 拓扑排序+DP(其实是递推)

TimeLimit:10SecMemoryLimit:128MBSubmit:744Solved:458Description如图所示为某生态系统的食物网示意图,据图回答第1小题现在给你n个物种和m条能量流动关系,求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1b1a2b2a3b3……am-1bm-1amb

2017-10-11 22:18:54

PoJ 1041 John's trip 神奇操作DFS

TimeLimit:1000MSMemoryLimit:65536KTotalSubmissions:9284Accepted:3116SpecialJudgeDescriptionLittleJohnnyhasgotanewcar.Hedecidedtodrivearoundthetowntovisithisf

2017-10-11 22:09:38

BZOJ 2064: 分裂 状压DP

TimeLimit:10SecMemoryLimit:64MBSubmit:540Solved:332Description背景:和久必分,分久必和。。。题目描述:中国历史上上分分和和次数非常多。。通读中国历史的WJMZBMR表示毫无压力。同时经常搞OI的他把这个变成了一个数学模型。假设中国的国土总和是不变的。每个国家都可以用他的国土面积代替,又两种可能,一

2017-10-11 21:40:47

BZOJ 4145: [AMPPZ2014]The Prices

TimeLimit:20SecMemoryLimit:256MBSubmit:468Solved:310Description你要购买m种物品各一件,一共有n家商店,你到第i家商店的路费为d[i],在第i家商店购买第j种物品的费用为c[i][j],求最小总费用。Input第一行包含两个正整数n,m(1<=n<=100,1<=m<=16),表示商店数和物品数。接下来

2017-10-11 21:18:27

欧拉回路 欧拉路径某些问题集合

后续会给出一些代码问题一:n个点,m个双向边,无重边,可能有自环,一条航线需要满足以下要求:从任意一个点出发,在任意一个点结束,经过m-2条边恰好2次,经过2条边恰好1次。求有多少本质不同的航线,两航线本质不同当且仅当存在1条边,在两航线中经过次数不同。N≤1e5,M≤1e5.首先这道题要判连通图,这个没问题然后这道题因为是无向图,而且可以有自环,所以我们的DP不是很好搞,于是

2017-10-11 16:31:46

浅谈Fleury(佛罗莱)算法 欧拉回路(及路径)

首先复习一下欧拉回路(及路径)的几个基础概念与定理FirstFirst欧拉回路:是指所有的边都只经过一次且仅一次,并且要走回到出发点的一条路径欧拉路径:表示一条不需要回到出发点,但是必须经过所有的边且都只经过一次的路径SecondSecond无向图存在欧拉回路的充要条件是所有的点的度数均为偶数无向图存在欧拉路径的充要条件是度数为奇数的点的数量为00个或者22个

2017-10-11 15:07:00

POJ 3254 Corn Fields 状压DP

TimeLimit:2000MSMemoryLimit:65536KTotalSubmissions:6321Accepted:3361DescriptionFarmerJohnhaspurchasedalushnewrectangularpasturecomposedofMbyN(1≤M≤12;1≤N≤12)s

2017-10-11 08:36:21

BZOJ 3566: [SHOI2014]概率充电器 期望DP + 树形DP

TimeLimit:40SecMemoryLimit:256MBSubmit:1276Solved:558Description著名的电子产品品牌SHOI刚刚发布了引领世界潮流的下一代电子产品——概率充电器:“采用全新纳米级加工技术,实现元件与导线能否通电完全由真随机数决定!SHOI概率充电器,您生活不可或缺的必需品!能充上电吗?现在就试试看吧!”SHO

2017-10-10 19:38:59

查看更多

勋章 我的勋章
    暂无奖章