Hawo11-CSDN博客

原创 NOIP 2017 复习计划

###离十一月份的全国青少年信息学联赛只有不到50天了。我的停课时间是从**九月二十五日**开始，一直延续到考试的前一段时间。由于集训队会在停课期间统一安排内容，所以我会顺应老师的安排，尽可能与大部队的复习情况吻合。（在自己的复习安排允许情况下）#背版子！！！####首先是数据结构。基础栈、队列、线段树与树状数组打几个模板题即可，然后是分块和CDQ分治。先理解，再刷题。主席树

2017-10-11 21:25:58 887

联赛。还有两天。这周到现在，已经有四次考试了。而且都是思维类型，不怎么考代码的。前两次的思维题目不难，也很对胃口。模拟啊递推啊什么的，至少是看到可以知道怎么做，并且可以实现。加上两天的T1都比较清真，所以心态也比较稳，成绩还不错。尽管Day2 T2写挂了80分，但是总体还是不错的。这里可以发现，对基础难度的题目我还是有一定能力解决掉，前提是不能挂掉！联赛注意！后两次测试更偏向思维层次，而且难度比之前

2017-11-09 07:17:59 565

原创停课总结（十）

咋感觉才写过一篇呢。。。两次考试，成绩都不靠前，但是还算稳定。主要是贯彻了“暴力骗分”的理念。T1还是比较稳，大多数都是拿到了分。但是由于担心不稳当，所以花了较多时间验证代码。接下来的时间要提高T1的做题效率。然后的T2呢。两天的得分率都不高。问题所在就是实现能力不够强。两次的算法都是想出来了，甚至是都在草稿纸上模拟出来了，但是因为各种细节，实际上实现的时候都出现了纰漏，导致或多或少有失分。当然就一

2017-11-06 19:00:10 509

原创停课总结（八）

哇，联赛要到了！这两天是和林荫的大佬一起考试。不得不说，这题目真的好难。。。我觉得要是联赛两天考这种东西，我就死了。DAY1的题目就开始不清真。T1是做过的原题，当时犯了错的所以这次没有犯顺利AC。但是T2这种很无语的字符串DP题目，我就只好DP各种到处转移大暴力骗分，骗了10分。然后T3是二分图的一些操作，但是我二分图很弱啊！！图论现有的只是想要骗点分啥的结果一分都没有。。。果然像朱闻笛这种讲过二

2017-11-03 22:06:07 485

原创停课总结（七）

没想到已经写过七篇总结啦。感觉时间过的好快。这周就基本没有什么专题了，主要是模拟测试。怎么说呢，感觉测试还是充分暴露了问题，当然也很大程度的让我了解自己并且提升了信心。首先的几次考试让我更加了解自己了。我发现自己比较擅长那种没有什么明确的算法的题目，比如上次和上上次的T3，一个是性质，一个是推公式，两道题都是A的。但是如果遇到像某次的T3还有上次的T2这种很明显的算法操作题目时候，应对能力下降了许多

2017-11-03 22:05:01 374

原创洛谷 1197 星球大战并查集解题报告

题目描述很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首

2017-11-03 21:59:37 616

原创洛谷 1650 赛马贪心解题报告

题目描述我国历史上有个著名的故事：那是在2300年以前。齐国的大将军田忌喜欢赛马。他经常和齐王赛马。他和齐王都有三匹马：常规马，上级马，超级马。一共赛三局，每局的胜者可以从负者这里取得200银币。每匹马只能用一次。齐王的马好，同等级的马，齐王的总是比田忌的要好一点。于是每次和齐王赛马，田忌总会输600银币。田忌很沮丧，直到他遇到了著名的军师――孙膑。田忌采用了孙膑的计策之后，三场比赛下来，轻松而优

2017-11-03 19:41:29 454

原创洛谷 1462 通往奥格瑞玛的道路

题目背景在艾泽拉斯大陆上有一位名叫歪嘴哦的神奇术士，他是部落的中坚力量有一天他醒来后发现自己居然到了联盟的主城暴风城在被众多联盟的士兵攻击后，他决定逃回自己的家乡奥格瑞玛题目描述在艾泽拉斯，有n个城市。编号为1,2,3,…,n。城市之间有m条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有

2017-11-03 17:27:40 389

原创浅谈多柱汉诺塔问题

众所周知，汉诺塔问题很经典。这里用DP可以解决nn个塔mm个柱子的移动次数问题当然想要输出步骤也可以我们回忆一下只有三根柱子的情况：先把n−1n−1个盘子移到第二根柱子上，再把剩下的那一个盘子移到第三根柱子，最后再把n−1n−1个盘子移到第三根柱子上。如果我们用FnFn来表示移动（三根柱子时）nn个盘子的最小步数，按照上面的叙述，则有： Fn=2×Fn−1+1Fn=2×Fn−1+

2017-11-03 15:07:06 1428 1

原创洛谷 1928 外星密码模拟？解题报告

题目描述有了防护伞，并不能完全避免 2012 的灾难。地球防卫小队决定去求助外星种族的帮助。经过很长时间的努力，小队终于收到了外星生命的回信。但是外星人发过来的却是一串密码。只有解开密码，才能知道外星人给的准确回复。解开密码的第一道工序就是解压缩密码，外星人对于连续的若干个相同的子串“X”会压缩为“[DX]”的形式（D 是一个整数且 1≤D≤99），比如说字符串“CBCBCBCB”就压缩为“

2017-11-03 07:53:08 654

原创洛谷 2285 打鼹鼠递推？ DP? 解题报告

题目描述鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏：在一个n∗nn*n的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网

2017-11-02 20:15:41 451

原创洛谷 1991 无线通讯网最小生成树解题报告

题目描述国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络；每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。任意两个配备了一条卫星电话线路的哨所（两边都ᤕ有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D，这是受收发器的功率限制。收发器的功率越高，通话距离 D 会更远，但同时价格也会更贵。收发器需要统一购买和安装，

2017-11-02 19:27:55 340

原创浅谈最大子矩阵

例题：奶牛沐场最大子矩阵面积，怎么求呢？可以想到的是，这个矩阵一定是极大子矩阵。（什么？你不知道什么是极大子矩阵？百度吧。。。）然后怎么求呢？这个子矩阵每一条边都不可以伸展了，也就是说他的边界上一定有障碍点或者是与边界重合了。算法一：直接想到的是，上下左右枚举四个边界，再看看是不是满足条件。复杂度？O(n5)O(n5)原因是什么？我们枚举了很多没有用的矩阵。很明显，我们不可以使用这个算法。算法二那么

2017-11-01 22:00:29 707

原创洛谷 1578 奶牛沐场最大子矩阵解题报告

题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内

2017-11-01 21:59:25 606

原创洛谷 1171 售货员的难题状压DP 解题报告

题目描述某乡有n个村庄(1输入输出格式输入格式：村庄数n和各村之间的路程(均是整数)。输出格式：最短的路程。输入输出样例输入样例#1：3 0 2 1 1 0 2 2 1 0输出样例#1：3 说明输入解释3 {村庄数}0 2 1 {村庄1到各村的路程}1 0 2 {村庄2到各村的路程}2 1 0 {村庄3到各村的路程}思路看到20想到状压。这里DP[i][j]DP[i][j]表示i情况下走

2017-11-01 19:56:39 483

原创洛谷 1318 积水面积模拟解题报告

题目描述一组正整数，分别表示由正方体迭起的柱子的高度。若某高度值为x，表示由x个正立方的方块迭起（如下图，0<=x<=5000）。找出所有可能积水的地方（图中蓝色部分），统计它们可能积水的面积总和（计算的是图中的横截面积。一个立方体的位置，为一个单位面积）。如图：柱子高度变化为 0 1 0 2 1 2 0 0 2 0图中蓝色部分为积水面积，共有6个单位面积积水。输入输出格式输入格式：两行，第一行

2017-11-01 17:13:39 1029

原创洛谷 2014 选课树形DP 解题报告

题目描述在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？输入输出格式输入格式：第一行有两个整数N,M用空格隔开

2017-11-01 16:41:06 543

原创洛谷 1429 平面最近点对贪心？解题报告

题目描述给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的输入输出格式输入格式：第一行：n；2≤n≤200000接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。输出格式：仅一行，一个实数，表示最短距离，精确到小数点后面4位。输入输出样例输入样例#1：复制3 1 1 1 2 2 2输出样例#1：1.0000说明0<=

2017-11-01 16:18:59 432

原创洛谷 2695 骑士的工作排序+贪心解题报告

题目背景你作为一个村的村长，保卫村庄是理所当然的了.今天，村庄里来了一只恶龙，他有n个头，恶龙到处杀人放火。你着急了。不过天无绝人之路，现在来了一个骑士团。里面有m位成员（往下看）题目描述每个人都可以砍掉一个大小不超过（<=）z的头，要money个金币，求最小花费。输入输出格式输入格式：第一行两个整数 n m下接n行，一个整数表示n个头的大小。下接m行，每个人可以砍的头大小或金币(金币==头的大小

2017-11-01 07:59:26 503

原创 bzoj 4565 字符合并 DP 解题报告

Description有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。Input第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。接下来2k行，每行一个字符ci和一个整数wi，ci 表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,

2017-10-31 22:05:22 514

原创 BZOJ 2142 礼物拓展Lucas 解题报告

Description一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E 心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你

2017-10-31 22:02:51 348

原创洛谷 1869 愚蠢的组合数 Lucas定理解题报告

题目描述最近老师教了狗狗怎么算组合数，狗狗又想到了一个问题。。。狗狗定义C(N,K)表示从N个元素中不重复地选取K个元素的方案数。狗狗想知道的是C(N,K)的奇偶性。当然，这个整天都老是用竖式算123456789*987654321=？的人不会让你那么让自己那么轻松，它说：“N和K都可能相当大。”但是狗狗也犯难了，所以它就找到了你，想请你帮他解决这个问题。输入输出格式输入格式：第1行：一个正整数t，

2017-10-31 21:59:25 608

原创洛谷 2330 繁忙的都市最小生成树解题报告

题目描述城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下

2017-10-31 20:46:20 446

原创洛谷 2737 麦香牛块最短路SPFA？解题报告

题目描述农夫布朗的奶牛们正在进行斗争，因为它们听说麦当劳正在考虑引进一种新产品：麦香牛块。奶牛们正在想尽一切办法让这种可怕的设想泡汤。奶牛们进行斗争的策略之一是“劣质的包装”。“看，”奶牛们说，“如果你只用一次能装3块、6块或者10块的三种包装盒包装麦香牛块，你就不可能满足一次只想买1、2、4、5、7、8、11、14或者17块麦香牛块的顾客了。劣质的包装意味着劣质的产品。”你的任务是帮助这些奶牛。给

2017-10-31 19:29:39 360

原创洛谷 1260 工程规划差分约束解题报告

题目描述造一幢大楼是一项艰巨的工程，它是由n个子任务构成的，给它们分别编号1，2，…，n(5≤n≤1000)。由于对一些任务的起始条件有着严格的限制，所以每个任务的起始时间T1，T2，…，Tn并不是很容易确定的(但这些起始时间都是非负整数，因为它们必须在整个工程开始后启动)。例如：挖掘完成后，紧接着就要打地基；但是混凝土浇筑完成后，却要等待一段时间再去掉模板。这种要求就可以用M(5≤m≤5000)个

2017-10-31 17:14:59 501

原创洛谷 1807 最长路 SPFA 解题报告

题目描述设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当为G中的一条边时有i < j。设w（i，j）为边的长度，请设计算法，计算图G中<1，n>间的最长路径。输入输出格式输入格式：输入文件longest.in的第一行有两个整数n和m,表示有n个顶点和m条边，接下来m行中每行输入3个整数a，b，v（表示从a点到b点有条边，边的长度为v）。输出格式：输出文件longest.out，一个整数，

2017-10-31 16:34:21 744

原创洛谷 1803 凌乱的yyy 贪心解题报告

题目背景快noip了，yyy很紧张！题目描述现在各大oj上有n个比赛，每个比赛的开始、结束的时间点是知道的。yyy认为，参加越多的比赛，noip就能考的越好（假的）所以，他想知道他最多能参加几个比赛。由于yyy是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加2个及以上的比赛。输入输出格式输入格式：第一行是一个整数n ，接下来n行每行是2个正整数ai,bi(ai输出格式：一个整数最多参加的比赛

2017-10-31 08:01:21 444

原创洛谷 1195 口袋的天空最小生成树解题报告

题目背景小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。题目描述给你云朵的个数N，再给你M个关系，表示哪些云朵可以连在一起。现在小杉要把所有云朵连成K个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。输入输出格式输入格式：每组测试数据的第一行有三个数N,M,K(1<=N<=1000,1<=M<=1000

2017-10-30 20:39:08 575

原创洛谷 1631 序列合并堆解题报告

题目描述有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2个和，求这N^2个和中最小的N个。输入输出格式输入格式：第一行一个正整数N；第二行N个整数Ai,满足Ai<=Ai+1且Ai<=10^9;第三行N个整数Bi, 满足Bi<=Bi+1且Bi<=10^9.输出格式：输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。【数据规模】对于50%的数据中，满足1<

2017-10-30 20:06:40 370

原创洛谷 1294 高手去散步搜索？图论？解题报告

题目背景高手最近谈恋爱了。不过是单相思。“即使是单相思，也是完整的爱情”，高手从未放弃对它的追求。今天，这个阳光明媚的早晨，太阳从西边缓缓升起。于是它找到高手，希望在晨读开始之前和高手一起在鳌头山上一起散步。高手当然不会放弃这次梦寐以求的机会，他已经准备好了一切。题目描述鳌头山上有n个观景点，观景点两两之间有游步道共m条。高手的那个它，不喜欢太刺激的过程，因此那些没有路的观景点高手是不会选择去的。另

2017-10-30 20:01:44 307

原创洛谷 1280 尼克的任务 DP 解题报告

题目描述尼克每天上班之前都连接上英特网，接收他的上司发来的邮件，这些邮件包含了尼克主管的部门当天要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。尼克的一个工作日为N分钟，从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完戍，尼克可以任选其中的一个来做，而其余的则由他的同事完成，反之如果只有一个任务，则该任务必需由尼克去完成，假如某些任务开始时刻尼克

2017-10-30 17:25:41 352

转载浅谈程序复杂度的常数优化

如果编译器没有开O2优化用库函数常数会凭空增加很多。。似乎NOIP考场不开O2 某些时候，如果你优化到无法再优化的时候尝试去自己重新实现库函数。比如isdigit() max()/min() unique()/lower_bound()/upper_bound() scanf()/printf() cin/cout getchar()/putchar()

2017-10-27 11:57:26 921 1

原创洛谷 1052 过河 DP 解题报告

题目描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当

2017-10-27 09:04:31 602 1

原创洛谷 1025 数的划分 DP 解题报告

题目描述将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5; 1，5，1; 5，1，1;问有多少种不同的分法。输入输出格式输入格式：n，k (6输出格式：一个整数，即不同的分法。输入输出样例输入样例#1：7 3输出样例#1：4说明四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;思路简单DP。代码#include

2017-10-26 12:03:46 403

原创洛谷 2814 家谱并查集解题报告

题目背景现代的人对于本家族血统越来越感兴趣。题目描述给出充足的父子关系，请你编写程序找到某个人的最早的祖先。输入输出格式输入格式：输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示

2017-10-26 11:47:57 533

原创洛谷 2708 硬币翻转特判？解题报告

题目背景难度系数：☆☆☆☆☆（如果你看懂了）题目描述从前有很多个硬币摆在一行，有正面朝上的，也有背面朝上的。正面朝上的用1表示，背面朝上的用0表示。现在要求从这行的第一个硬币开始，将n个硬币（1<=n<=硬币个数）一起翻面，问如果要将所有硬币翻到正面朝上，最少要进行这样的操作多少次？输入输出格式输入格式：一个字符串（当然不限长度，在字符串范围之内），有0和1组成输出格式：要翻转的最少次数输入输出样例

2017-10-25 21:58:41 1086

原创洛谷 1119 灾后重建生成树+Floyd 解题报告

题目背景B地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。题目描述给出B地区的村庄数N，村庄编号从0到N-1，和所有M条公路的长度，公路是双向的。并给出第i个村庄重建完成的时间t[i]，你可以认为是同时开始重建并在第t[i]天重建完

2017-10-25 21:29:11 379

原创洛谷 1441 砝码称重搜索+DP 解题报告

题目描述现有n个砝码，重量分别为a1，a2，a3，……，an，在去掉m个砝码后，问最多能称量出多少不同的重量（不包括0）。输入输出格式输入格式：输入文件weight.in的第1行为有两个整数n和m，用空格分隔第2行有n个正整数a1，a2，a3，……，an，表示每个砝码的重量。输出格式：输出文件weight.out仅包括1个整数，为最多能称量出的重量。输入输出样例输入样例#1： 3 1 1 2

2017-10-25 19:37:12 959

空空如也

空空如也