onepointo-CSDN博客

原创 NOIP 2017 考点总结及复习规划

一、数据结构初级数据结构1.链表，双向链表 2.队列，单调队列，双端队列，栈，单调栈 3.堆基础数据结构1.并查集与带权并查集 2.hash 表 3.树状数组，线段树，线段树合并 *4.主席树 **5.平衡树 *6.左偏树 *7.分块二、数学1.gcd，lcm，扩展欧几里得算法 2.筛法，快速幂，快速乘 *2.lucas定理 3.乘法逆元 4.矩阵乘法 **5.莫比乌斯反演

2017-09-23 07:57:50 2455

原创 HDU 5306 吉司机线段树解题报告

Gorgeous SequenceProblem DescriptionThere is a sequence a of length n. We use ai to denote the i-th element in this sequence. You should do the following three types of operations to this sequence...

2018-04-20 20:29:16 539

自己的OI生涯就此结束了。。。身败名裂啊，考完下来的成绩只有期望分数的一半。Day 0上午考了一场信心赛，然而自己在考场上的大模拟并没有写出来（flag），连暴力都挂了（flag）。下午调整心态去考场。一路上好紧张啊，一直在虚今年会变的更难（比如说不送分了），后来安慰自己100+60+60+100+60+60也有440，勉强不会退役吧，于是乎觉得自己没有上440就可以退役，就这么决定了。晚上心情一般

2017-12-01 22:20:06 2161

原创 HDU 1827&&3072 强连通分量解题报告

HDU 1827 真是巧啊代码如下：#include<cstdio>#include<cstring>#include<algorithm>#include<stack>using namespace std;#define N 10010#define M 100010 int n,m;int cnt=-1,head[N];struct Edge{int to,nxt;}

2017-11-07 19:54:37 367

原创 BZOJ4952 [Wf 2017] 二分答案解题报告

4952: [Wf2017]Need for SpeedDescriptionSheila 是一名学生,她开着一辆经典的学生车:一辆又老,又慢,又锈,还老是崩坏的车。最近,时速表盘的指针还掉了。她把指针粘了回去,但是她可能没有粘对角度。因此,当表盘读数为s时,她真实的速度可能是s+c,其中c为未知常数 (可能是负的) 。Sheila 在最近的行程中仔细地做了一些记录,并希望能用这些记录来计算出c的值

2017-11-04 17:16:57 595

原创 BZOJ4951 [Wf 2017] 分治解题报告

4951: [Wf2017]Money for NothingDescription在这道题种你需要解决一个全世界人类从存在起就在面临的最深刻的问题–如何发大财。你是一名零件交易市场的中介。你的工作是从零件生产公司那里买到零件,然后把它们卖给零件消费公司。每个零件消费公司在截止日期前每天都会对一个零件有一个开放式的需求,以及它愿意买下零件的价格。另一方面,每个零件生产公司在开始日期及以后都可以销售零

2017-11-03 22:01:45 399

原创 2017.11.3 树上期望DP 解题报告

题目描述梦游中的你来到了一棵N个节点的树上. 你一共做了Q个梦, 每个梦需要你从点u走到点v之后才能苏醒, 由于你正在梦游, 所以每到一个节点后,你会在它连出去的边中等概率地选择一条走过去, 为了确保第二天能够准时到校, 你要求出每个梦期望经过多少条边才能苏醒. 为了避免精度误差, 你要输出答案模109+7的结果.输入格式第一行两个整数分别代表N和Q. 接下来N-1行, 每行两个整数u, v代表树中

2017-11-03 16:32:27 572

原创 2017.11.3 N盘M柱汉诺塔问题通解 DP 解题报告

题目描述众所周知, 汉诺塔是一个古老又经典的游戏. 这个游戏是这样的, 你有N个大小不同的盘子和3根柱子, 一开始所有盘子都叠放在第1根柱子上, 你需要把N个盘子全都移动到第3根柱子上, 每次都可以选择某根柱子最上面的盘子移动到另一根柱子上, 但是任何时候都必须保证没有一个盘子上面放了一个比它大的盘子. 求最少的移动步数. 这个问题太简单了, 乐于寻找挑战的你想要求出当有N个盘子, M个柱子且其他

2017-11-03 15:30:10 2373

原创 2017.11.2 树上期望DP 解题报告

题目描述给你一棵包含个n点的有根树，点的标号是1…n，在t=1时（ t表示时间），你在1号点，接下来，你会随机跑到当前点相邻的点，然后继续这个过程，直到访问了所有的点，已从一个点到另一个点需要的时间是1秒，那么问题来了，请问在这个随机过程中，对于每个节点，冬雪第一次访问的期望时间是多少？输入数据：3 1 2 2 3输出数据：1.000 2.000 5.000【解题报告】代码如下：#i

2017-11-02 20:14:41 454

原创 2017.11.2 支配树上LCA 解题报告

题目描述给出一个无向图（n<=50000,m<=100000）,q个询问（q<=100000）,每次询问节点1到k个点的必经点的个数（k<=100000）.输入数据：4 3 2 1 2 2 3 2 4 2 3 4 2 2 4输出数据：2 2【解题报告】思路应该比较好想，构建出支配树后求着k个点的LCA，LCA的深度即为答案。然而我在考场上并不会支配树。。。代码如下：#include<

2017-11-02 20:03:19 285

原创 BZOJ 5044 [Lydsy 九月月赛] 构造解题报告

5044: [Lydsy九月月赛]岛屿生成Description小Q设计了一款2D游戏，它的地图建立在二维笛卡尔坐标系上。这个游戏最大的特色就是可以随机生成地图，但是岛屿生成却给小Q带来了巨大的麻烦。一个岛屿可以看成一个恰好有n个顶点的简单多边形，每个顶点的坐标都必须是整数，同时为了防止精度误差，每条边的长度也必须是整数。为了体现程序的随机性，任何一条边都不能与x轴或者y轴平行。当然，这个多边形不能

2017-11-01 21:38:08 329

转载学习一个支配树

http://blog.csdn.net/qq_35649707/article/details/64125918 http://blog.csdn.net/GEOTCBRL/article/details/57875070 http://blog.csdn.net/a710128/article/details/499135531、基本介绍支配树 DominatorTree　　对于一个流程图

2017-10-31 21:57:01 708

原创 BZOJ 5072 [Lydsy 十月月赛] 树DP 解题报告

Problem Statement小A 成为了一个园艺家！他有一棵n 个节点的树（如果你不知道树是什么，请看Hint 部分）。他不小心打翻了墨水瓶，使得树的一些节点被染黑了。小A 发现这棵染黑了的树很漂亮，于是想从树中取出一个x 个点的联通子图，使得这些点中恰有y 个黑点，他想知道他的愿望能否实现。可是他太小，不会算，请你帮帮他。【解题报告】考虑转化才成树上背包的形式，发现对于每一个x都有一个y

2017-10-31 19:33:10 289

原创 BZOJ 5071 [Lydsy 十月月赛] 排序解题报告

Description小A成为了一个数学家，他有一串数字A1,A2…An 每次可以进行如下操作，选择一个数字i,将(Ai-1,Ai,Ai+1) 变为(Ai-1 + Ai,-Ai,Ai+1 + Ai),特别地，若i=N,则(An-1,An)变为 (An-1 + An,-An).小A很好奇，能否通过若干次操作，得到他的幸运数列B1,B2…Bn.可是他太小，不会算，请你帮帮他【解题报告】(ai−1,

2017-10-30 21:51:01 448

原创 BZOJ 4881 [Lydsy2017年5月月赛] 二分图染色+线段树

4881: [Lydsy2017年5月月赛]线段游戏Descriptionquailty和tangjz正在玩一个关于线段的游戏。在平面上有n条线段，编号依次为1到n。其中第i条线段的两端点坐标分别为(0,i)和(1,p_i)，其中p_1,p_2,…,p_n构成了1到n的一个排列。quailty先手，他可以选择一些互不相交的线段，将它们拿走，当然他也可以一条线段也不选。然后tangjz必须拿走

2017-10-30 21:09:38 364

原创 Codeforces 24D 期望DP 解题报告

D. Broken robotYou received as a gift a very clever robot walking on a rectangular board. Unfortunately, you understood that it is broken and behaves rather strangely (randomly). The board consists of

2017-10-30 19:52:03 867

原创 BZOJ 2744 [HEOI 2012] 二分图最大独立集解题报告

2744: [HEOI2012]朋友圈Description在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。两个国家看成是AB两国，现在是两个国家的描述： 1.A国：每个人都有一个友善值，当两个A国人的友善值a、b，如果a xor b mod 2=1，那么

2017-10-30 17:09:35 457 1

原创 BZOJ 4102 [Usaco2015 Open] 图上DP 解题报告

4102: [Usaco2015 Open]BessieDescription为了庆祝贝茜的生日,FJ给她吃草的自由. N块草地,标号1到N(1<=N<=1000),草地有营养价值.当贝茜走到这个草地,可以获得等于这块草地的营养价值的能量. 每块草地最多有10条双向边,每走一条边,贝茜花费E的能量. 贝茜拿可以从任何地方出发,当她不能获得更多的能量的时候她就会停止. 然而因为贝茜挑食,她每次不会吃低

2017-10-29 14:48:50 306

原创 2017.10.28 Tarjan求无向图必经点解题报告

【题目描述】给出一个无向图，求从1号点到n号点的必经点【输入】第一行一个整数一个整数 T，表示共 T组数据。对于每组数据，第一行两个n，m表示有n个点，m条边。接下来m行，两个正整数 u,v，表示u和v个建筑物之间相连。建筑物之间相连。建筑物之间相连。建筑物之间相连。【输出】必经点个数和必经点编号【解题报告】一开始以为是支配树什么的，看了题解才发现Tarjan也可以做，不禁感慨自

2017-10-28 16:55:00 1340 2

原创 2017.10.27 数学期望（手把手教你推期望）解题报告

【题目描述】有nn个数字，每一个数字可能为1 m1~m中的任意一个值，现在进行(n−k+1)(n-k+1)次选择，第一次选择1 k1~k个数字，第二次选2 k+12~k+1个数字……现在给出每一个数值（1−−m）（1--m）对应的一个函数w（x）w（x），对于每一次选择，它的代价为k个数内最大的数mxmx的w（mx）w（mx），求在k次选择后，代价和的期望值是多少【输入格式】第一行，三个整数n, m

2017-10-28 16:46:49 3212

原创 Codeforces 711C 树DP 解题报告

C. Bear and Tree JumpsA tree is an undirected connected graph without cycles. The distance between two vertices is the number of edges in a simple path between them. Limak is a little polar bear. He l

2017-10-27 17:20:38 237

原创 BZOJ 1801 [Ahoi 2009] DP 解题报告

1801: [Ahoi2009]chess 中国象棋Description在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.Input一行包含两个整数N，M，中间用空格分开.Output输出所有的方案数，由于值比较大，输出其mod 9999973Sample Input1 3*Sample Output7HI

2017-10-26 16:41:01 176

原创 BZOJ 1419 DP 解题报告

1419: Red is goodDescription桌面上有R张红牌和B张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到1美元，黑牌则付出1美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。Input一行输入两个数R,B,其值在0到5000之间Output在最优策略下平均能得到多少钱。Sample Input5 1Sample Output4.166666HINT输出答案时

2017-10-26 15:19:13 194

原创 BZOJ 3107 [cqoi 2013] DP 解题报告

3107: [cqoi2013]二进制a+bDescription输入三个整数a, b, c，把它们写成无前导0的二进制整数。比如a=7, b=6, c=9，写成二进制为a=111, b=110, c=1001。接下来以位数最多的为基准，其他整数在前面添加前导0，使得a, b, c拥有相同的位数。比如在刚才的例子中，添加完前导0后为a=0111, b=0110, c=1001。最后，把a, b, c

2017-10-26 15:04:27 235

原创 2017.10.25 DP 解题报告

眼镜(glasses.c/cpp/pas)3.1 题目描述这只小动物找到了书中的力量，它几乎就要成功了，依据书中内容，它还缺一副眼镜。于是它找到了一个01串，想要从中找到制造眼镜的材料。它希望找到这个01串的最长的子序列串(即不要求连续)，这个子序列满足01交间的性质(01010…或10101…)。但是在寻找之前，它想测试一下目前拥有的力量，于是它选择了一段连续的区间，将这个区间中的0变成1

2017-10-26 14:53:47 236

原创 BZOJ 3193 [JLOI 2013] 计数DP 解题报告

3193: [JLOI2013]地形生成Description最近IK正在做关于地形建模的工作。其中一个工作阶段就是把一些山排列成一行。每座山都有各不相同的标号和高度。为了遵从一些设计上的要求，每座山都设置了一个关键数字，要求对于每座山，比它高且排列在它前面的其它山的数目必须少于它的关键数字。显然满足要求的排列会有很多个。对于每一个可能的排列，IK生成一个对应的标号序列和等高线序列。标号序列就

2017-10-25 21:27:15 190

原创 BZOJ 3688 树状数组优化DP 解题报告

3688: 折线统计Description二维平面上有n个点(xi, yi)，现在这些点中取若干点构成一个集合S，对它们按照x坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4部分，每部分连续上升、下降。现给定k，求满足f(S) = k的S集合个数。Input第一行两个整数n和

2017-10-25 21:06:21 419

原创 BZOJ 1598 [Usaco 2008 Mar] 启发式搜索解题报告

1598: [Usaco2008 Mar]牛跑步DescriptionBESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚. BESSIE也不想跑得太远,所以她想走最短的路经. 农场上一共有M (1 <= M <= 10,000)条路, 每条路连接两个用1..N(1 <= N <= 1000)标号的地点. 更方便的是,如果X>Y,则地点X的高度大

2017-10-24 21:06:38 251

原创 BZOJ 3993 [SDOI 2015] 网络流+二分答案解题报告

3993: [SDOI2015]星际战争Description3333年，在银河系的某星球上，X军团和Y军团正在激烈地作战。在战斗的某一阶段，Y军团一共派遣了N个巨型机器人进攻X军团的阵地，其中第i个巨型机器人的装甲值为Ai。当一个巨型机器人的装甲值减少到0或者以下时，这个巨型机器人就被摧毁了。X军团有M个激光武器，其中第i个激光武器每秒可以削减一个巨型机器人Bi的装甲值。激光武器的攻击是连续的。这

2017-10-22 21:47:51 248

原创 BZOJ 4198 [Noi 2015] Huffman树解题报告

4198: [Noi2015]荷马史诗Description追逐影子的人，自己就是影子。 ——荷马 Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。一部《荷马史诗》中有 n 种不同的单词，从 1 到 n 进

2017-10-22 11:18:14 264

原创 CodeVS 1183 SPFA+二分答案解题报告

1183 泥泞的道路题目描述 DescriptionCS有n个小区，并且任意小区之间都有两条单向道路（a到b，b到a）相连。因为最近下了很多暴雨，很多道路都被淹了，不同的道路泥泞程度不同。小A经过对近期天气和地形的科学分析，绘出了每条道路能顺利通过的时间以及这条路的长度。现在小A在小区1，他希望能够很顺利地到达目的地小区n，请帮助小明找出一条从小区1出发到达小区n的所有路线中（总路程/总时间）最

2017-10-22 10:59:51 234

原创 Codeforces 461B 树DP 解题报告

B. Appleman and TreeAppleman has a tree with n vertices. Some of the vertices (at least one) are colored black and other vertices are colored white. Consider a set consisting of k (0 ≤ k < n) edges of

2017-10-18 21:52:11 364

原创 Codeforces 459E 图上DP 解题报告

E. Pashmak and GraphPashmak’s homework is a problem about graphs. Although he always tries to do his homework completely, he can’t solve this problem. As you know, he’s really weak at graph theory; so

2017-10-18 20:57:06 362

原创 BZOJ 2131 数据结构优化DP 解题报告

2131: 免费的馅饼DescriptionInput第一行是用空格隔开的二个正整数，分别给出了舞台的宽度W（1到10^8之间）和馅饼的个数n（1到10^5）。　　接下来n行，每一行给出了一块馅饼的信息。由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻t[i]（1到10^8秒），掉到舞台上的格子的编号p[i]（1和w之间），以及分值v[i]（1到1000之间）。游戏开始时刻为0。输入文件中同一行

2017-10-18 16:17:45 542

原创 CodeVS 1090 [NOIP 2003] 区间DP 解题报告

题目描述 Description设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子

2017-10-18 08:47:41 277

原创 Codeforces 815 C 树形依赖背包解题报告

C. Karen and SupermarketOn the way home, Karen decided to stop by the supermarket to buy some groceries. She needs to buy a lot of goods, but since she is a student her budget is still quite limited.

2017-10-17 21:34:50 495

原创 CodeVS 3657 区间DP 解题报告

题目描述 Description我们用以下规则定义一个合法的括号序列：（1）空序列是合法的（2）假如S是一个合法的序列，则 (S) 和[S]都是合法的（3）假如A 和 B 都是合法的，那么AB和BA也是合法的例如以下是合法的括号序列： (), [], (()), ([]), ()[], ()[()]= 以下是不合法括号序列的： (, [, ], )(, ([]), ([()

2017-10-17 21:18:56 326

原创 CDOJ 1321 区间DP 解题报告

括号匹配 (parenthesis.pas/cpp/c)【题目描述】给出长度为N的括号序列（只包含(,),[,]），问有多少种方法删掉这些括号的一个子集，使得剩下的括号序列是合法的，请注意不能全部删完。【输入格式】输入的第一行是一个整数N，表示序列的长度。接下来一行N个字符，表示括号序列。【输出格式】一行，表示方案数模1000000007的结果。【样例输入】4 ()[]【样例输出】3 【

2017-10-17 19:27:06 245

原创 Codeforces 870E 并查集解题报告

Points, Lines and Ready-made TitlesYou are given n distinct points on a plane with integral coordinates. For each point you can either draw a vertical line through it, draw a horizontal line through it

2017-10-15 22:02:38 367

动态规划加速原理之四边形不等式

NOIP2009测试数据

空空如也