八月炊火-CSDN博客

原创邮局题解

题目这一题是一道很不错的题目，也是我很喜欢的一道题目，对于区间DP这一题可以好好看看。首先我们分析题目，对于这个题目应该会很有感觉，这就是区间DP，我们要做到以下几点：1、清楚状态转移方程的框架是什么？2、清楚操作是什么？3、计算出操作的花费4、完善状态转移方程（即定下完整的状态转移方程）。我们先解决第一点，框架是什么？首先解决状态定义的框架，我们肯定要以区间和操作次数来做为状态，...

2018-12-22 15:37:05 401

原创 noip 2018 day2 T2货币系统

题目知识点：背包DP讲解：这一题不算太难，可以说是送分题。我们考虑最多要选的肯定只有那n个嘛。然后我们继续考虑，一个货币不需要用当且仅当这个货币可以被已经选了的货币表示出来，这样这个就是完全背包了。我们定义dp[i]表示i这个货币能否被表示出来，1表示可以，0表示不可以。我们对于一个货币，如果它不能被任何一个货币表示出来，那么我们就必须要选它，而如果可以我们就不用选，假设我们的货币...

2018-11-17 15:04:38 469 1

原创 noip2018 day1 T3 赛道修建题解

题目知识点：二分、树、贪心讲解：对于这一题在考场上是一脸懵逼，先理解一下题目吧。给你一个数要求你从这个树上抠出m条链，要求：最小的链最长这个题目最大的困难是怎么抠？首先想到的就是二分，为什么？最小的链最长不就是二分的经典句子嘛。所以我们考虑二分最小链的长度，可是还是那个问题怎么抠？我们在没思路的时候我们可以看看可不可以拿部分分，说不定打着打着就有思路了（博主本人）。根据...

2018-11-17 11:57:36 1076 1

原创离散化解析

对于离散化一开始听了感觉很高大上，可是学了发现也不会太难。首先我们讲讲为什么要用离散化？对于有一些数据结构例如：并查集。就要以数字编号作为下标，可如果题目数字给的很大呢？凉凉。对于这种题目都会有个特点，数字很大，可数量不多，那么我们就可以重新对它进行编号，这个过程其实就是离散化。对于离散化我们比较重要的就是映射方程，也就是根据什么对它进行编号，比较常用而且好用的就是根据数量进行编号。所...

2018-11-06 21:32:09 444

原创组合数详解

概念：组合数我们用C（n，m）表示，它代表在n个数中取m个数的方案。（这个概念主要用于将问题抽象到组合数上）。公式：组合数的公式也不多，1、C（n，m）=C（n，n-m）。2、C（n，m）=C（n-1，m-1）+C（n-1，m）。这个很重要，因为这个和杨辉三角的递推公式一样的，所以我们经常把杨辉三角和组合数和起来看。典题3、C（0，n）+C（1，n）+C（2，n）+C（3，n）+…C（...

2018-11-01 11:08:09 7588

题目这一题真的是好题，floyd的经典好题。对于这一题我们只需要前置技能floyd就好了。我们先讲一下这一题好在哪吧。这一题好就好在这一题经典地利用了floyd的一个特征，首先我们回顾floyd，它是三重循环，其中最外层是枚举每个点k去更新别人嘛。所以我们再这一次更新后我们有个性质，那就是如果有一条最短路在经过这个点，那么肯定已经求出来的。而我们这个正是要利用这个性质。题目要求的是根据时间询...

2018-10-31 21:04:17 562 1

原创 Play the Dice 题解

题目知识点：数论、期望计算解析：这一题有点坑，scanf忘记加~，结果死循环，哭死。好了，不扯了。因为他们的概率是一样的，所以期望退化成了数值平均，说人话就是因为概率相同，所以数学期望就变成了可能值和的平均，我们用sum表示骰子上面分数的和，那么扔一次的数学期望是sum/n，而第二次就是sum/n*（m/n），第三次是sum/n*（m/n）*（m/n），第k次就是sum/n * （m...

2018-10-31 09:00:42 247

原创约数详解

约数这个还是数论比较热门的考点（这边是提高组，省选大佬出门右转）。首先约数是什么？听起来好高大上，其实就是因子，而对于约数要掌握的就是约数和以及约数个数，我们先看一下笼统的计算公式。对于一个数我们可以质因数分解，所以对于每个数n，我们可以分解成p1 ^ c1+p2 ^ c2+……+px ^ cx，这种形式，而约数个数也就是（c1+1） * （c2+1） * …… （cx+1），而约数和就是...

2018-10-31 07:53:27 1807

原创逆元

对于逆元其实说难不难，说简单也不简单。概念：对于a * x≡b（mod m）这个方程如果我们要求解的话其实是比较复杂的，可是如果我们可以求出a * y≡1（mod m）中的y的话，在上面那个方程上同乘以y就可以得到，x=b * y，是不是很神奇，我们也称y是a在mod m的条件下的逆元，写作x ^ -1求法：对于我们的逆元求法有四种，这四种各有千秋，我们要根据题目来决定采用哪种方法。...

2018-10-30 16:38:22 4156

原创拓展欧几里得算法

拓展欧几里得算法其实也不难，主要是要去记公式、代码、必要的话连推导也记下来。好了，不扯了，将正话。概念：要求解这样的方程：推导：对于这个我们其实就是利用辗转相除法，我们可以知道，我们辗转相除法的边界是a=d，b=0，（a和b为要求最大公约数的两个数，d为他们的公约数），此时我们可以知道a就是最大公约数，我们还可以知道，在这时，一定有个解是x=1，y=0，即a * 1+b * 0 =d...

2018-10-30 15:14:06 501

原创数列详解

对于数列这一个个人觉得很有可能会考（因为昨天刚考），结果今天才看，（哭死在厕所）好了，不扯了，首先我们讲讲什么是数列，其实就是一串数字，像我们的数组一样，只不过我们讨论的是数列中比较特殊的几个，分别是等差数列和等比数列。等差数列：其实就是对于数列相邻的两项他们的差值是一定的，举个栗子：1、3、5、7、9。这个数列就是等差数列，其中每相邻的两个数相差2，我们称2为差值，用d表示（下文的d均是差...

2018-10-29 10:55:16 2348

原创保送题解概率DP

题目背景：czk赫赫有名，为什么呢？因为他参加了超多竞赛，所以认识了无数OIer。而无数OIer也都认识他，为什么呢？因为czk实在是太牛了~ 所以我们经常可以听到OIer之间的典型谈话：小A：你知道czk吗？小B：当然认识啦，就是那个AK了XX竞赛的dadiao啊~ 小A：不止，他还AK了XX竞赛，XX竞赛，XX竞赛…… 那么，czk同学到底巨到什么地步呢？世界上总共有N门竞赛，czk同...

2018-10-28 11:50:52 185

原创 Eden的新背包问题题解

题目知识点：多重背包DP讲解：对于这一题其实就是多重背包的变式问题，我们发现就是在多重背包问题上加上了有一种不可以选，我们思考一下去掉这个物品不能选后会怎么改变，也就是把原本连续的一串物品分成了两块，而我们如果正常地做多重背包的话只能计算出前面一段，后面怎么办？再从后往前DP一遍不就好了，对就这么简单，只要想到了这里，那么问题就变成了多重背包版子题了。代码：#include<i...

2018-10-25 19:41:13 344 1

原创通天之分组背包题解

题目知识点：背包DP讲解：对于这一类题有个名字叫分组背包，是九大背包之一，而这一个也不会太难，我们现在来看看。这一题我们其实可以看做0/1背包，然后加一个每组只可以取1个的条件，我们发现如果加了这个条件，那么我们用0/1背包的做法就会有后效性，所有后效性都可以通过加状态维数来消除（个人认为，如果有反例欢迎留言），我们发现后效性和组别有关所以我们就可以这样，对于一组里面的每一个我们都枚举计...

2018-10-25 19:30:29 536

原创 bzoj 3195 奇怪的道路题解

题目知识点：状压DP讲解：这一题很有难度，是状压DP不错的提升题，为什么说他难呢？难就难在状态，对于这个状态我们很难定义出来。对于这一题首先想到的就是有两维，一维i是我们已经计算到了哪个点，还有j就是我们已经用了多少条边，可是我们发现，题目说每个点连的边必须是偶数个，所以我们再加一维，我们状压i-K（K是题目给的）到i+K这17个点的奇偶数的状态，我们用0表示为偶数，1表示奇数，这样我们...

2018-10-25 19:16:45 180

原创 poj 3311 和饼一起吃题解

题目链接知识点： floyd、状压DP讲解：对于这一题其实就是旅行商问题。我们很容易就想到首先我们要处理出每两个点之间的最短路，这就是floyd，处理完后我们就可以开始DP了，因为最多有10个送货点所以我们状压每个送货点是否送到，又因为我们最后是要回来的所以我们在定义状态时不可以单单只有每个点的状态，还要有现在到了哪个点，这样我们最后答案就是现在到了0这个点（回来了），并且全部送货地点都去过...

2018-10-25 13:44:19 168

原创小奇的矩阵题解

小奇的矩阵题目：题目背景：小奇总是在数学课上思考奇怪的问题。问题描述：给定一个n*m的矩阵，矩阵中的每个元素aij为正整数。接下来规定1.合法的路径初始从矩阵左上角出发，每次只能向右或向下走，终点为右下角。2.路径经过的n+m-1个格子中的元素为A1,A2…A(n+m-1)，Aavg为Ai的平均数，路径的V值为(n+m-1)*∑(Ai-Aavg) ^2 (1<=i<=n...

2018-10-19 22:05:30 545

原创找位置冲刺 noip

找位置代码测试区题目：Farmer John 想找一个最好的位置来建新农场，这样他每天可以少走些路。FJ 所在的区域，有N 个城镇(1 &amp;amp;lt;= N &amp;amp;lt;= 10,000)。城镇之间，有M(1 &amp;amp;lt;= M &amp;amp;lt;= 50,000)条双向路相连。所有城镇都可以借助一些路相互连接。FJ 需要你的帮助来选择最合适建新农场的城镇。K(1 &amp

2018-10-17 22:24:15 301

原创二分详解

引入：小明和小强玩一个游戏，小强在纸上写下一个数(在1到1000之内)，小明有十次询问的机会，每次询问小强只回答小明所说的数是大了还是小了或者等于，请问小明该怎么才能赢？解思：这个问题是二分的经典问题，由这个问题我们可以引出今天的主角——二分。对于这个问题我们先说小明改怎么办，如果听不同也没关系，后面会详细解释。小明一开始要猜的范围在1到1000我们询问1和1000的平均值也就是500如果...

2018-10-15 22:10:07 307

原创砍树枝冲刺noip

砍树枝题目：这天，CD 作为moreD 的宠物，又被残酷地训练爬树了，moreD 保证了这棵树满足从任意一个点出发，CD 都能走到所有的点，CD 每天都要爬过所有的点才能回家吃饭。经过一天又一天残酷的训练以后，CD 已经忍无可忍了，于是CD 会愤怒地误伤一条树枝，一条树枝被误伤以后就不可以再走了。当然，CD 不符合宠物法则的行动怎么会逃过moreD 的眼睛，moreD 决定，每当CD 误伤一条...

2018-10-10 21:50:46 261

原创冲刺noip2018 day1

今天的题目挺水的，先上题目：T1：题目描述：圆国是一个国家，它包含几个圆形地区。有些地区可能位于内其他地区，但其边界不相交或触摸。 Qatam是圆国的乡村居民。当他在两个地点之间旅行，他总是试图跨越过尽可能少的边界地区，因为跨越地区边界通常是费力的任务。输入输出格式：输入格式：第一行，包含一个整数Num，表示测试数据的个数。（1&lt;=Num&lt;=10）每组测试数据，第一行一个...

2018-10-08 16:47:01 699

原创长乐爆零之旅 day7 wzoi

二话不说上题目：题目描述：bleaves最近在wzoi上面做题。的题目有两种，一种是noip题，一种是省选题。 bleaves的做题方式很特别。每一天，她可能会看一道题目，这时她会选择题目种类，然后wzoi会在选定种类中随机扔给她一道她还没看过的题，她会把这道题看一遍，然后存在脑子里慢慢思考；她也有可能写题，这时她一定会写没写过的题中看的时间最迟的一题(如果不存在没写过的且没看过的题，她就...

2018-10-07 10:21:44 575

原创长乐爆零之旅 day6 rps

这一题好狗血，用递推空间炸了，0分,(哭死在厕所 )。题目：wzms今年举办了一场剪刀石头布大赛，bleavesbleaves被选为负责人。比赛共有2^n 个人参加，分为2n轮，在每轮中，第 1位选手和第 2位选手对战，胜者作为新的第 1位选手，第 3位和第 4位对战，胜者作为新的第 2位选手，以此类推。调查得知，每个人都有其偏爱决策，每个人在每一次对战中都会使用他的偏爱决策。如果一...

2018-10-06 17:33:47 266

原创长乐爆零之旅 day5 苹果树

这一题是书上差分和lca，可是没看出来，一开始直接暴力了。题目描述：小 B 是一个辛勤的农民，他家里种了一棵很大的苹果树。这棵苹果树可以看作一张 n 个点 n-1 条边的无向连通图，小 B 觉得这颗苹果树很脆弱，因为只要剪断任意一条边，苹果树就不连通了，于是他给苹果树新加了 m 条边。现在这颗苹果树就不像是一棵树了，成了一张 n 个点 n+m-1 条边的无向连通图，小 Q是小 B 的好朋友，...

2018-10-05 21:28:58 344

原创长乐爆零之旅第一天叉叉

本应是开心的国庆结果开心地爆零。先上题目：叉叉(cross,1s,128MB)【题目描述】现在有一个字符串，每个字母出现的次数均为偶数。接下来我们把第一次出现的字母a和第二次出现的a连一条线，第三次出现的和四次出现的字母a连一条线，第五次出现的和六次出现的字母a连一条线…对其他25个字母也做同样的操作。现在我们想知道有多少对连线交叉。交叉的定义为一个连线的端点在另外一个连线的内部，另外...

2018-10-03 08:22:50 304

原创树状数组 PK 线段树

这几天学树状数组，和之前的线段树比较发现树状数组虽然比线段树好实现，可是不支持区间查询和区间修改，那么树状数组就比不过线段树吗？想太多，之前有一些dalao吃饱了饭没事做于是就开始乱想，写过想出了超级树状数组，一个支持区间查询和区间修改的树状数组。我们之前做过区间查询和单点修改的树状数组和区间修改单点查询的树状数组（没看过的点这）那么有没有什么办法可以把它们和起来呢？答案是有的。推导：我们想一下...

2018-09-28 20:56:21 1056

原创树状数组算法详解

这几天扫描知识点，扫描到了树状数组就解决了。首先什么是树状数组？它其实就是支持单点修改和区间查询的数据结构，我会一步一步讲解这个树状数组到底是个什么东西，所以请跟上我的步骤，拿出纸笔跟我一起计算。首先我们要知道树状数组是怎么实现的，原理就是前缀和，如果我们可以快速地计算出前缀和，然后一减就得出了区间和了，可问题是如果用前缀和的话修改是要O（n）的，太大了，好了不扯了回归正题。然后我们要知道它...

2018-09-28 20:36:11 1264 1

原创 lca题目敌对势力题解

这是计蒜客noi模拟赛的day1第二题，现在写完了，发一波题解。先上题目：敌对势力这一题先想到的是暴力暴力出奇迹，后面只得了30分，然后后面老师说是lca我当场懵逼，为什么？原来是看错了，我以为是一个图，这当然不可以用lca，废话，后面才看到是无根树，眼瞎害死人。讲正事，看到无根树我们首先看看可不可以转成有根树，而这一题刚好可以，因为题目无特殊要求，所以我们可以随便选个点作为根，我们...

2018-09-23 13:51:57 296

原创拓扑排序建图模板题车站分级

超水题目在上面，这个是一个经典的拓扑排序和建图的模板，大家可以试试水，首先我们要理解题目，假设有一串编号1 3 5，这个就是1,5分别是起点和终点，而且只停靠3，所以2,4这两个车站必须要小于，1、3、5这三个，而其中三个关系是：1≤3≤5，本着贪心的原则：能等则等所以我们令他们相等，那么我们可以这样建图，如果2<3的话（注意没有等于），那么我们就添加一条从2通向3的边，这样我们只需要计...

2018-09-12 22:33:51 157

原创 sumdiv 题解

这个题目真的是大杂烩。先上题目：求A^B的所有约数之和mod9901（1&amp;amp;amp;lt;=A,B&amp;amp;amp;lt;=5*10^7）这个题目是经典数论，因为考的实在是太多了，先列举一下知识点：快速幂、等比数列、乘法逆元、分解质数、约数和。真的是太多了，下面我们一一讲一下，先快速幂，快速幂比较推荐的是一个非递归的，因为有些数据大了，递归会MLE。下面上代码：#include&amp;amp;amp;lt;io

2018-09-09 11:29:03 297

原创愤怒的小鸟题解

这一题太坑了，卡高精卡得好死。说正题，这一题除了卡高精就是状压了，当然也可以爆搜加剪枝在此我们就聊一下状压DP，当时看到这一题还无从入手想着只能暴力了，后面看到数据才18只猪^(*￣(oo)￣)^，不用说了，状压DP，我们可以用二进制来状压猪到底有没有被打掉，然后后面看了看也没什么状态可以定义了，于是我们确定状态dp[i]表示打掉i集合中的猪最少需要多少只鸟，下面我们讲一下集合，其实就是几只猪...

2018-09-08 13:11:48 404

原创 2018 08 22 总结

因为昨天一直在改题太坑了，好不容易才改对，哭死了好了开始补总结，今天的知识点分别是数位DP、树上二分、广搜，太刺激了，都不会。上题目：第1题幸运数【问题描述】 nyz!ysu!同学非常喜欢49，为什么呢？我也不知道。。。 nyz!ysu!同学认为49是幸运数字，同时含有49的数字也是幸...

2018-08-24 07:48:15 261

原创 2018 08 23 总结

今天是泉五之旅的最后一天，明天再上机一天就要开始上学了，可怕的英语又来了，唉。本来今天想好好考一下，没想到基本爆零，还被帅康dis了。话不多今天考的还好，主要是思维的转变，知识点分别是数论（其实就是自己找规律推）、广搜、DP 下面上题目：第1题点【问题描述】有N个二维坐标上的整数点(Xi,Yi)。现在请你选择一个整数点(X,Y)。最小化距离【输入文件】newb...

2018-08-23 18:43:10 194

原创 2018 08 21 学习总结

今天又刷了三道题，都还不错，知识点分别是最小堆、并查集和质数筛选、DFS爆搜首先上一下题目第1题 poker【问题描述】一副扑克牌有n张牌。一般你买的一副新扑克牌里除了这n张牌外还会有一些张特殊的牌，如果你不小心弄丢了n张牌中的某一张，就可以用特殊牌来代替，但是如果你弄丢两张的话就没有办法了，因为特殊牌上的图案是一样的。现在你得到了很多扑克牌，准确来说，n种牌你各有a...

2018-08-21 21:04:23 544

原创 2018 8 18 学习总结

今天去了泉州五中，感受了一下计算机的高难度题目，好难啊，太变态了，第一题是数论只能背代码，没办法，暴力也只有20分左右，第二题是DP，这一题就很有难度，一般情况下能拿到50分，可想要更高就难了，第三题是广搜，这一题一开始想了一个DP，只有80分，原来是有bug，正解是广搜，下面上一下题目，大家感受一下。 1.方程的解(equation.pas/c/cpp)【问题描述】佳佳碰到了一个难题，...

2018-08-21 19:43:33 426

原创线段树详解

首先要先知道线段树是什么？线段树其实就是一颗树，与其他树不一样的是正常的树节点信息是一个，而线段树顾名思义是一段所以它每个节点有三个信息分别是左端点、右端点、线段的信息，这三样中只有信息是可以很多，左右端点是惟一的。这是大概理念，听不懂没关系，下面上个经典图就知道了。这是普通的树这是线段树，而且是左闭右开区间，这里面还只有左右端点，区间信息还没有，不过已经很形象了。至于什么是左闭右...

2018-08-09 20:22:42 12789 3

原创平衡的阵容Balanced Lineup 题解线段树模板题

这一题还是比较简单的，有人说要用ST表，也可以，不过这类题最好是用线段树，因为这一题不用修改，所以可以用ST表，言归正传，怎么用线段树解决，首先要有一些基础，知道怎么用代码实现线段树的建树、修改、询问这三类，如果不清楚可以去看一下我关于讲线段树的博客。下面讲思路，这一题要通过维护一个线段树，叶子节点存两个信息，一个是这个区间的最大值与最小值，其他的和线段树没差了，下面上代码（代码有详细注释）。...

2018-08-08 19:34:36 613 1

原创乌龟棋 noip 2010

题目链接：https://www.luogu.org/problemnew/show/P1541 今天成功写过了这一题，我们是以这一题作为考试来写，一开始知道肯定是要DP的可是状态定义错了，一开始定义第几格为状态死活写不出来，又开始改状态，后面改成了卡牌数才AC了，一开始不敢这么定义，因为四重循环怕时间炸了，后面算了一下才发现四重循环看着吓人，实际上数字非常小，是可以过的。下面讲思路：首先定...

2018-08-07 20:19:25 175

空空如也

空空如也