月度归档: 2020年3月

16 篇文章

Luogu P1110 [ZJOI2007]报表统计 题解
Describe 题目链接 小 Q 的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小 Q 希望可以帮妈妈分担一些工作,作为她的生日礼物之一。 经过仔细观察,小 Q 发现统计一张报表实际上是维护一个非负整数数列,并且进行一些查询操作。 在最开始的时候,有一个长度为$ n$的整数序列$a$,并且有以下三种操作: INSERT i k…
钉钉群直播提取视频文件
[admonition title="Tips" color="red"]如果您打开yzxoi的网盘下载链接页面为白色,请检查浏览器是否使用chrome内核或者使用极速模式,建议使用Google Chrome浏览器[/admonition] 本教程仅供学习研究使用!!! 教程更新了若干次,2020->2021.04->2021.06,如果知友们发现…
Luogu P1514 引水入城 题解
题目链接 Describe 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个$N$行$\times M$列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的…
Luogu P3174 [HAOI2009]毛毛虫 题解
Describe 题目链接 对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。例如下图左边的树(图 $1$)抽出一部分就变成了右边的一个毛毛虫了(图 $2$)。 Solution 毛毛虫? 很明显,我们可以先预处理出每个点的入度。 显然最后的答案就是$\sum{a_i}-(s-1…
Luogu P1270 “访问”美术馆 题解
Describe 题目链接 经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer知道每个展室里藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要5秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多…
Luogu P3413 SAC#1 – 萌数 题解
Describe 题目链接 定义“萌数”: 存在长度至少为$2$的回文子串。 问$[L,R]$中共有多少个萌数字? 对于$100\%$的数据$0\leq L\leq R \leq {10}^{1000}$。 Solution 数位$dp$裸题。 $$DFS(x,las,lasqr,has,lim,st)$$ 分别表示第$x$位,上一个数字是$las…
Luogu P4127 [AHOI2009]同类分布 题解
Describe 题目链接 给出两个数$a,b$,求出$[a,b]$中各位数字之和能整除原数的数的个数。 Solution 数位dp。 $DFS(x,sum,dig,lim)$分别表示第$x$位,当前数位之和为$sum$,数字为$dig$,是否到达极限。 但是数据极大,$dig$会达到${10}^{18}$是不可能来记忆化的,所以考虑取模 那么模多…
Luogu P4124 [CQOI2016]手机号码 题解
Describe 题目链接 人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素,从号段中选取含有某些特征的号码单独出售。为了便于前期规划,运营商希望开发一个工具来自动统计号段中满足特征的号码数量。 工具需要检测的号码特征有两个:号码中要出现至少 $3$ 个相邻的…
Luogu P1801 黑匣子 题解
Describe 题目链接 Black Box是一种原始的数据库。它可以储存一个整数数组,还有一个特别的变量i。最开始的时候Black Box是空的.而i等于0。这个Black Box要处理一串命令。 命令只有两种: ADD(x):把x元素放进BlackBox; GET:i加1,然后输出Blackhox中第i小的数。 记住:第i小的数,就是Blac…
Luogu P1273 有线电视网 题解
Describe 题目链接 某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构,这棵树的根结点位于足球比赛的现场,树叶为各个用户终端,其他中转站为该树的内部节点。 从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的,一场转播的总费用等于传输信号的费用总和。 现在每个用户都准备了一笔费用想观看这场精彩的…
Luogu P2585 [ZJOI2006]三色二叉树 题解
Describe 题目链接 Solution $0-$绿色,$1-$红色,$2-$蓝色。 设$f[i][j]$表示$i$节点染成$j$这种颜色的最大值。 如果$i$节点的没有儿子,那么很明显$f[i][0]=1$。 如果$i$节点有一个儿子,那么$f[i][0]=max(f[to][1],f[to][2])+1,f[i][1]=max(f[to][…
Luogu P5060 旅行 题解
Describe 题目链接 给定一个 $N$ 个点, $M$ 条边的有向图,求从 $A$ 到 $B$ 的路径上边权和是 $P$ 的倍数的最短路径的长度及路径。 对于所有数据,$2\leq N \leq$$ 5\times $${10}^{4}$$,M\leq$$ 2 \times {10}^5$$ , 1\leq P $$\leq 50$。 Sol…
Luogu P2656 采蘑菇 题解
Describe 题目链接 在一个 $N$ 个点, $M$ 条边的有向图中,每条路可以走无数次,边权为 $w_i$ ,边的恢复系数为 $p_i$ 第二次走时,边权变为 $w_i \times {p_i} $ ,第三次走时,边权变为 $w_i \times {p_i} ^ 2$...第 $k$ 次走时,边权变为 $w_i \times {p_i}^{…
Luogu P2900 [USACO08MAR]Land Acquisition G 题解
Describe 题目链接 Farmer John 准备扩大他的农场,眼前他正在考虑购买 $N$ 块长方形的土地。 如果 FJ 单买一块土地,价格就是土地的面积。但他可以选择并购一组土地,并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 $3 \times 5$ 和一块 $5 \times 3$ 的土地,他只需要支付 $5 \tim…
Luogu P3648 [APIO2014]序列分割 题解
Describe 题目链接 你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块,你需要重复下面的操作 $k$ 次: 选择一个有超过一个元素的块(初始时你只有一块,即整个序列) 选择两个相邻元素把这个块从中间分开,得到两个非空的块。 每次操作后你将获得那两个新产生…
bzoj 4337 BJOI2015 树的同构
Description 树是一种很常见的数据结构。 我们把N个点,N-1条边的连通无向图称为树。 若将某个点作为根,从根开始遍历,则其它的点都有一个前驱,这个树就成为有根树。 对于两个树T1和T2,如果能够把树T1的所有点重新标号,使得树T1和树T2完全相 同,那么这两个树是同构的。也就是说,它们具有相同的形态。 现在,给你M个有根树,请你把它们按…