NOIAu-CSDN博客

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

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

2017-10-17 16:34:38 1495

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

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

2017-10-13 22:14:30 787

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

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

2017-10-13 20:34:40 936

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

DescriptionCaocao was defeated by Zhuge Liang and Zhou Yu in the battle of Chibi. But he wouldn’t give up. Caocao’s army still was not good at water battles, so he came up with another idea. He built m

2017-10-13 18:58:59 819

原创 POJ 1144 Network 裸割点

题意：给一个图，求割点个数#include <cstdio>#include <iostream>#include <cstring>using namespace std;const int MAXN = 110;int low[MAXN], dfn[MAXN], head[MAXN], tail, cnt, timer, n;struct Line{ int to, nxt; }li

2017-10-13 14:19:59 552

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

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

2017-10-13 12:20:12 591

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

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

2017-10-13 10:13:05 789

原创 POJ 3159 Candies 差分约束系统（这题卡SPFA的队列的双端队列）

DescriptionDuring the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class a large bag of candies and had flymouse distribute the

2017-10-13 09:04:09 610

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

DescriptionThe galaxy war between the Empire Draco and the Commonwealth of Zibu broke out 3 years ago. Draco established a line of defense called Grot. Grot is a straight line with N defense stations.

2017-10-12 22:18:00 415

原创 POJ 1364 King 差分约束系统

DescriptionOnce, in one kingdom, there was a queen and that queen was expecting a baby. The queen prayed: “If my child was a son and if only he was a sound king.” After nine months her child was born,

2017-10-12 19:04:36 458

原创 POJ 1201 Intervals 差分约束系统

Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 27889 Accepted: 10743DescriptionYou are given n closed, integer intervals [ai, bi] and n integers c1, …, cn. Write a program th

2017-10-12 16:59:44 357

原创 P1073 最优贸易 NOIP 2009 最短路

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

2017-10-12 14:48:57 441

原创 BZOJ 4562: [Haoi2016]食物链拓扑排序+DP（其实是递推）

Time Limit: 10 Sec Memory Limit: 128 MB Submit: 744 Solved: 458Description如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号 M条能量流动关系形如 a1 b1 a2 b2 a3 b3 …… am-1 bm-1 am b

2017-10-11 22:18:54 578

原创 PoJ 1041 John's trip 神奇操作DFS

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 9284 Accepted: 3116 Special JudgeDescriptionLittle Johnny has got a new car. He decided to drive around the town to visit his f

2017-10-11 22:09:38 478

原创 BZOJ 2064: 分裂状压DP

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

2017-10-11 21:40:47 549

原创 BZOJ 4145: [AMPPZ2014]The Prices

Time Limit: 20 Sec Memory Limit: 256 MB Submit: 468 Solved: 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 378

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

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

2017-10-11 16:31:46 1025

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

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

2017-10-11 15:07:00 7995 12

原创 POJ 3254 Corn Fields 状压DP

Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 6321 Accepted: 3361DescriptionFarmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) s

2017-10-11 08:36:21 407

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

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

2017-10-10 19:38:59 708

原创 2017年 10 月 9 日机房模拟赛

T1是背包问题，但是我不知道正解（正解是状态巧妙的背包问题）#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int MAXN = 2000 + 100;int N, M, dp[ MAXN + 10 ], tail;struct P {

2017-10-09 21:51:07 442

原创 UVa 10529 Dumb Bones 期望DP

题目传送门dalao讲解其实其实比较水，我们只需要列出一个总式子就可以了，用dp[i]表示拼出长度为i的多米诺骨牌需要至少多少次，于是我们枚举一个中间点作为拼成i块多米诺的最后一块，于是我们用El表示拼好左边长度的期望最少次数，Er表示拼好右边长度的期望最少次数，则显然如果我现在不倒的话，有拼好i块长度为Ei 则 Ei = El + Er + 1 这点是显然的，然而无论倒不倒，左边倒或者右边倒

2017-10-09 20:29:32 925

原创 BZOJ 1529: [POI2005]ska Piggy banks 并查集

Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1415 Solved: 699DescriptionByteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破

2017-10-09 18:49:14 323

原创 BZOJ 1190: [HNOI2007]梦幻岛宝珠背包DP

Time Limit: 10 Sec Memory Limit: 162 MB Submit: 1049 Solved: 605Description给你N颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过W，且总价值最大为，并输出最大的总价值。数据范围：N<=100;W<=2^30,并且保证每颗宝石的重量符合a*2^b（a<=10;b<=30）Input输入文件中

2017-10-09 12:28:08 398

原创 BZOJ 4569: [Scoi2016]萌萌哒倍增思维并查集

Time Limit: 10 Sec Memory Limit: 256 MB Submit: 1110 Solved: 528Description一个长度为n的大数，用S1S2S3…Sn表示，其中Si表示数的第i位,S1是数的最高位，告诉你一些限制条件，每个条件表示为四个数，l1，r1，l2，r2，即两个长度相同的区间，表示子串Sl1Sl1+1Sl1+2…Sr1与Sl2Sl2+1Sl2

2017-10-09 11:59:48 409

原创 BZOJ 3343: 教主的魔法分块大暴力

Time Limit: 10 Sec Memory Limit: 256 MB Submit: 1703 Solved: 783Description教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L

2017-10-08 19:29:14 409

原创 BZOJ 2794: [Poi2012]Cloakroom 背包DP

Time Limit: 20 Sec Memory Limit: 128 MB Submit: 319 Solved: 202Description有n件物品，每件物品有三个属性a[i], b[i], c[i] (a[i]Input第一行一个正整数n (n<=1,000)，接下来n行每行三个正整数，分别表示c[i], a[i], b[i] (c[i]<=1,000, 1<=a[i]Output

2017-10-07 15:09:28 822

原创 BZOJ 1483: [HNOI2009]梦幻布丁链表+启发式合并

Time Limit: 10 Sec Memory Limit: 64 MB Submit: 3433 Solved: 1357DescriptionN个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色. 例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.Input第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,

2017-10-06 22:19:55 305

原创 BZOJ 4668: 冷战并查集

Time Limit: 10 Sec Memory Limit: 256 MB Submit: 440 Solved: 215Description1946 年 3 月 5 日，英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”，正式拉开了冷战序幕。美国和苏联同为世界上的“超级大国”，为了争夺世界霸权，两国及其盟国展开了数十年的斗争。在这段时期，虽然分歧和冲突严重，但双方都尽

2017-10-06 21:32:47 419

原创 BZOJ 1202: [HNOI2005]狡猾的商人带权并查集

Time Limit: 10 Sec Memory Limit: 162 MB Submit: 3960 Solved: 1909Description刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了n个月以来的收入情况，其中第i 个月的收入额为Ai(i=1,2,3…n-1,n)，。当 Ai大于0时表示这个月盈利Ai 元，当 Ai小于0时表示这个月亏损Ai

2017-10-06 20:27:48 1038

原创 BZOJ 2287【POJ Challenge】消失之物背包DP

Descriptionftiasch 有 N 个物品, 体积分别是 W1, W2, …, WN。由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N - 1 物品装满容积为 x 的背包，有几种方法呢？” – 这是经典的问题了。她把答案记为 Count(i, x) ，想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。Input第1行：两个整数 N (

2017-10-06 18:14:40 322

原创 BZOJ 1296: [SCOI2009]粉刷匠背包

Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2174 Solved: 1253Descriptionwindy有 N 条木板需要被粉刷。每条木板被分为 M 个格子。每个格子要被刷成红色或蓝色。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷 T 次，他最多能正

2017-10-06 17:22:29 310

原创 POJ 3093 Margaritas on the River Walk 背包DP

dalao讲解因此我们可以背包，按照枚举最小的一个不被选中的物品进行巧妙去重#include <cstdio>#include <iostream>#include <cstring>#include <algorithm> using namespace std;const int MAXN = 10000 + 10;int T, f[MAXN], n, m, sum[MAXN], w

2017-10-05 22:07:07 372

原创割点与桥模板及讲解

割点：就是一张图中割掉这个点之后联通块个数增加的点桥：也即割边，是一张图中割掉这条边之后联通块个数增加的边求这个东西我们需要用到dfs序，以及low数组，其中low数组和tarjan求强连通分量里的low数组是一个意思，于是我们显然可以得出几个比较显然的结论 ①：low[v] > dfn[u] ->is a cut_line ②：low[v] ≥ dfn[u]->is a c

2017-10-05 16:25:51 608

原创 hdu 3709 Balanced Number 数位DP

DescriptionA balanced number is a non-negative integer that can be balanced if a pivot is placed at some digit. More specifically, imagine each digit as a box with weight indicated by the digit. When a

2017-10-02 22:25:36 628

原创 PoJ 3252 Round Numbers 数位DP

DescriptionThe cows, as you know, have no fingers or thumbs and thus are unable to play Scissors, Paper, Stone’ (also known as ‘Rock, Paper, Scissors’, ‘Ro, Sham, Bo’, and a host of other names) in ord

2017-10-02 22:14:38 524

原创 hdu 4734 F（x）数位DP裸

DescriptionFor a decimal number x with n digits (A nA n-1A n-2 … A 2A 1), we define its weight as F(x) = A n * 2 n-1 + A n-1 * 2 n-2 + … + A 2 * 2 + A 1 * 1. Now you are given two numbers A and B, plea

2017-10-02 21:53:41 374

原创 HDU 2089 不要62

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。不吉利的数字为所有含有4或62的号码。例如： 62315 73418 88914 都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利

2017-10-02 15:18:35 735

原创 BZOJ 3790 神奇项链 manachar 树状数组

Description母亲节就要到了，小 H 准备送给她一个特殊的项链。这个项链可以看作一个用小写字母组成的字符串，每个小写字母表示一种颜色。为了制作这个项链，小 H 购买了两个机器。第一个机器可以生成所有形式的回文串，第二个机器可以把两个回文串连接起来，而且第二个机器还有一个特殊的性质：假如一个字符串的后缀和一个字符串的前缀是完全相同的，那么可以将这个重复部分重叠。例如：aba和aca连接起来

2017-10-02 08:32:39 635

原创 BZOJ 2299: [HAOI2011]向量

Time Limit: 10 Sec Memory Limit: 256 MB Submit: 1424 Solved: 661Description给你一对数a,b，你可以任意使用(a,b), (a,-b), (-a,b), (-a,-b), (b,a), (b,-a), (-b,a), (-b,-a)这些向量，问你能不能拼出另一个向量(x,y)。说明：这里的拼就是使得你选出的向量之和为(x

2017-10-02 08:20:25 663

空空如也

空空如也