3 _Apocrypha

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 13w+

博客搬家啦~~

如题。。博客搬到博客园去啦。。 新博客地址:newblogs

2018-08-07 16:32:45

知识点整理:斜率优化DP

前言概要知识点讲解单调性归纳证明基于单调性的转移优化例题AC代码练习题BZOJ1096 仓库建设解题思路AC代码BZOJ1911 特别行动队解题思路AC代码前言最近刷BZOJ的题目的时候,发现做到了很多题目都是用到了斜率优化,这个优化很早也接触过,但也没有仔细地去学。最近认真的去学了一下,就在这里做个整理概要斜率优化是基于单...

2018-08-01 19:28:37

知识点整理:FFT详解

前言前置知识知识点讲解概要多项式相乘的朴素算法系数表示法与点值表示法复数的引入单位复根DFT前言FFT其实在很早的时候就已经接触到了,但是那个时候学起来有点仙,感觉这东西离实际解题的距离有点远,不如那些其他的数据结构那么直接。但是半年多下来的做题,发现FFT其实应用的十分广泛,并且很多数学题推出公式之后就可以套用FFT进行计算。所以对于FFT的理解也不...

2018-07-27 15:32:58

BZOJ 3065 带插入区间K小值 (树套树、替罪羊树套线段树)

BZOJ3065 带插入区间K小值题意题外话题解AC代码:BZOJ3065 带插入区间K小值题意Description 从前有nnn只跳蚤排成一行做早操,每只跳蚤都有自己的一个弹跳力a[i]a[i]a[i]。跳蚤国王看着这些跳蚤国欣欣向荣的情景,感到非常高兴。这时跳蚤国王决定理性愉悦一下,查询区间kkk小值。他每次向它的随从伏特提出这样的问题: 从左往右...

2018-07-24 20:25:57

知识点整理:二叉(重量)平衡树——替罪羊树

知识点概要知识点详解平衡因子子树的重构基础操作复杂度分析关于替罪羊树代码(luogu3369 && BZOJ3224)知识点概要在各种二叉平衡树中,大多数的平衡树都是通过旋转来维护这棵二叉查找树的性质,并且尽量保证每次的查找的复杂度为logloglog的。然而说实话,各种情况的旋转很容易写挂,考场上一旦写挂掉就会心态爆炸,所以我们或许...

2018-07-24 08:18:41

NOI2018 Day2 屠龙勇士(扩展孙子定理+multiset)

NOI2018 Day2 dragon题解AC代码: NOI2018 Day2 dragon题解开场开了T3之后发现T3根本不可做,于是集中精力刚T1和T2,但是机房猝不及防的断电三次,神TM整整少了半个小时做题时间。T1只码了70分,T2 15分暴力还挂成了10分。 这题的做法还是比较清真的,部分分也很多,打了简单的60分暴力之后发现有10分的部分分都是...

2018-07-21 10:08:54

NOI2018 Day1 归程(Kruskal重构树)

题意:题解:题意:本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 n 个节点、m 条边的无向连通图(节点的编号从 1 至 n)。我们依次用 l,a 描述一条边的长度、海拔。 作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边。 我们用...

2018-07-21 09:49:09

codeforces DIV2 E. Garlands (离线、二维树状数组)

E. Garlands题意:解题过程:AC代码:E. Garlands题意:给出你一个n*m矩阵,矩阵中有一些灯泡,这些灯泡连成了k条互不重叠的链。每个灯泡都有一定的权值w,但是只有当灯泡打开的时候,才会产生贡献,刚开始所有的灯泡都是开着的。共有q次询问,有两种操作: ①“Switch i”——表示将编号为i的链所有的灯泡取反(即开变关,关变开)。 ...

2018-07-12 19:12:15

CQOI2018 Day1 社交网络

Cqoi2018 Day1 社交网络题目背景:题目描述:输入输出个数:分析:Code:Cqoi2018 Day1 社交网络题目背景:当今社会,在社交网络上看朋友的消息已经成为许多人生活的一部分。通常,一个用户在社交网络上发布一条消息(例如微博、状态、Tweet等)后,他的好友们也可以看见这条消息,并可能转发。转发的消息还可以继续被人转发,进而扩散到...

2018-04-17 19:59:51

CQOI2018 Day1 :破解D-H协议

CQOI Day1 :破解D-H协议题目背景:题目描述输入输出格式SAMPLE INPUT:SAMPLE OUTPUT:分析:Code:想了一想……emm……发现自己的博客又是好久没有更新了啊……那么既然现在机房里要求强制补题……emm,作为蒟蒻的我就顺便更新一下博客吧。CQOI Day1 :破解D-H协议题目背景:Diffie-Hellm...

2018-04-17 19:42:36

LIGHGTOJ 1094 Farthest Nodes in a Tree (树的直径,模板)

LIGHGTOJ 1094 Farthest Nodes in a Tree题意:解题过程:AC代码:LIGHGTOJ 1094 Farthest Nodes in a Tree题目传送门题意:给出你一棵树和每条边的边权,让你找出树上的两点,满足这两点之间的路径权值和最大。求这个权值和。解题过程:这题是一道模板题,就是让你求树的直径(...

2018-03-06 17:35:12

POJ 2424 Flo's Restaurant (模拟)

POJ 2424 Flo’s Restaurant题意:解题过程:AC代码:POJ 2424 Flo’s Restaurant题目传送门题意:你在开一个餐厅,共有三种桌子,第一种:只能坐1~2个人,第二种:只能坐3~4个人,第三种:只能做5~6个人,每种桌子分别有A、B、C张,有一些客人会来吃饭,但可能会出现客人会等待的情况。假设每桌都要吃半小时...

2018-03-05 22:25:22

POJ 2392 Space Elevator(多重背包,排序)

POJ 2392 Space Elevator题意:解题过程:AC代码:POJ 2392 Space Elevator题目传送门题意:你需要建一个高塔,材料总共有K种,每种材料有三个属性:高度,数量,限度。限度是指该种材料只能在低于该限度的高度下被使用。问你最高能够把这个高塔建到多高。解题过程:这题中材料有高度和数量,比较容易的想到这题是...

2018-03-05 22:19:56

POJ 2385 Apple Catching(DP)

POJ 2385 Apple Catching题意:解题过程:AC代码:POJ 2385 Apple Catching题目传送门题意:一头牛要接苹果,一共有两棵树,牛刚开始在第一棵树下,每次可以在两棵树之间移动,给出你T秒内下落苹果的树的编号(1或2),问你最多移动K次,能够接到最多的苹果是多少。解题过程:比较水的DP,本来想着用一维记录牛当前在...

2018-03-05 22:11:55

POJ 2356 Find a multiple (数学,前缀和)

POJ 2356 Find a multiple题意:解题过程:AC代码:POJ 2356 Find a multiple题目传送门题意:给出你n个数,问你能否从这n个数中取出任意数量的数,使这些数的和是n的倍数,不行则输出0,否则输出方案。解题过程:根据抽屉原理可知这题并不存在0的情况,因为我们设前i个数的和对n取模为Si,如果出现Si...

2018-03-05 21:54:58

POJ 2355 Railway tickets (DP)

POJ 2355 Railway tickets题意:解题过程:AC代码:POJ 2355 Railway tickets题目传送门题意:你需要从s点做车到t点,车在行驶距离不同时价格不同,如果距离比0大且比l1小,那么价格为c1如果距离比l1大且比l2小,那么价格为c2,如果距离比l2大且比l3小,那么价格为c3,但一辆车的行驶距离不能超过l3,一共有...

2018-03-05 11:27:02

POJ 2353 Ministry(DP,前缀)

POJ 2353 Ministry题意:解题过程:AC代码:POJ 2353 Ministry题目传送门题意:给你一个n*m的矩阵,每个矩阵有一个数,表示在位置(i,j)办理手续的费用,在(i,j)办理完手续之后,你可以到(i+1,j)或者(i,j+1)或者(i,j-1)的位置继续办理手续,办完所有的手续定义为从(1,j)开始,到(n,j’)结束的整个过...

2018-03-05 11:18:01

POJ 2346 Lucky tickets(DP,记忆化)

POJ 2346 Lucky tickets题意:解题过程:AC代码:POJ 2346 Lucky tickets题目传送门题意:定义一个位数为偶数的数为幸运数当且仅当这个数前一半的部分数字之和等于后一半的数字之和,给出一个n,求出有多少个位数小于n的数是幸运数。解题过程:我们可以比较容易的想到DP,然后我们会发现DP当中我们需要的只是前一半...

2018-03-04 21:11:45

POJ 2329 Nearest number - 2(搜索)

POJ 2329 Nearest number - 2题意:解题过程:AC代码:POJ 2329 Nearest number - 2题目传送门题意:你有一个n*n矩阵,每个点有一个数字,可能是0~1e9的任意一个数字,现在要求你对这个矩阵进行修改,对于所有的为0的数字,要求寻找到这个点曼哈顿距离最小的非0的一个数,并把这个点改为那个数的值,如果有...

2018-03-04 21:02:33

POJ 2192 Zipper (简单DP)

POJ 2192 Zipper题意:解题过程:AC代码:POJ 2192 Zipper题目传送门题意:给出你三个字符串,问你能否把前两个字符串混合成第三个字符串,使得每个字母在原字符串中的前后顺序不改变。解题过程:考虑DP,可以用f[i][j]表示第一个字符串枚举到第i位,第二个字符串枚举到第j位时,能否混合成前第三个字符串前i+j位。...

2018-03-04 20:53:21

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!