• 等级
  • 1580 访问
  • 38 原创
  • 0 转发
  • 222447 排名
  • 0 评论
  • 0 获赞

离散化解析

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

2018-11-06 21:32:09

组合数详解

概念: 组合数我们用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

灾后重建题解

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

2018-10-31 21:04:17

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

约数详解

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

2018-10-31 07:53:27

逆元

对于逆元其实说难不难,说简单也不简单。 概念: 对于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

拓展欧几里得算法

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

2018-10-30 15:14:06

数列详解

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

2018-10-29 10:55:16

保送 题解 概率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

Eden的新背包问题 题解

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

2018-10-25 19:41:13

通天之分组背包 题解

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

2018-10-25 19:30:29

bzoj 3195 奇怪的道路 题解

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

2018-10-25 19:16:45

poj 3311 和饼一起吃 题解

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

2018-10-25 13:44:19

小奇的矩阵 题解

小奇的矩阵 题目: 题目背景: 小奇总是在数学课上思考奇怪的问题。 问题描述: 给定一个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

小奇挖矿 2 题解

小奇挖矿 2 题目: 题目背景: 小奇飞船的钻头开启了无限耐久+精准采集模式!这次它要将原矿运到泛光之源的矿石交易市场,以便为飞船升级无限非概率引擎。 问题描述: 现在有m+1个星球,从左到右标号为0到m,小奇最初在0号星球。 有n处矿体,第i处矿体有ai单位原矿,在第bi个星球上。由于飞船使用的是老式的跳跃引擎,每次它只能从第x号星球移动到第x+4号星球或x+7号星球。每到一个星球,小奇会采走该...

2018-10-19 21:15:02

找位置 冲刺 noip

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

2018-10-17 22:24:15

二分详解

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

2018-10-15 22:10:07

砍树枝 冲刺noip

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

2018-10-10 21:50:46

冲刺noip2018 day1

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

2018-10-08 16:47:01

长乐爆零之旅 day7 wzoi

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

2018-10-07 10:21:44

八月炊火

纵星有坠,惟心不坠。
关注
  • 中国 福建省 泉州市
奖章
  • 持之以恒