bzoj 3209 & Luogu P4317 花神的数论题 题解
题目链接:bzoj Luogu Description 求$1$到$n$每个数的$1$的个数之积。 对于$ 100\% $的数据,$n\leq 10^15$ Solution 数位$DP$。 可以先把$n$拆成二进制,然后$DFS$。 Code [crayon-5f08ba6710e84126101939/]
bzoj 1858. [Scoi2010]序列操作 题解
Description 题目链接:BZOJ1858 [Scoi2010]序列操作 给你长度为$n$的$01$串,现有$m$个操作。 区间赋值为$0$区间赋值为$1$区间反转(所有$0$变为$1$,所有$1$变为$0$)区间求和求区间最多有连续的几个$1$ 对于$100\%$的数据,$1\le n,m \le 100000$。 Solution 珂朵…
珂朵莉树 学习笔记
什么是珂朵莉树? 珂朵莉树,又称$ODT(Old Driver Tree)$,是一个基于$std::set$的暴力、玄学数据结构。 什么时候使用珂朵莉树? 如果有一题涉及到区间赋值(即把区间内所有的数全部赋值成同一个量)的操作,且数据随机,就可以考虑使用珂朵莉树。 下面以一道例题CF896来详解珂朵莉树。 Description 给你$n$个数,要…
bzoj1774. [Usaco2009 Dec]Toll 过路费 题解
Describe 一句话题意:给你一个有点权$n$与边权$m$的图,询问$q$次,问两个点间最短路长度。(最短路定义为路径上的边权和+路径上的点权的最大值) $1\leq n\leq 250,1\leq m\leq 10000,1\leq q\leq 10000$ Solution 考虑到点的数量小于$250$,所以可以$Floyed$求出任意两点…
小米稳定版刷root
[admonition title="警告" icon="flag" color="red"]刷机有风险,root需谨慎[/admonition] 序 由于去年入的Redmi7是入门机型,所以莫得开发版,窝就作死的刷了Magisk竟然还成功了QwQ。 过程 一、解BL锁 [admonition title="警告" icon="flag" colo…
bzoj3137 [Baltic2013]tracks 题解
Describe 给定一片长方形的草地,有2种动物:兔子和狐狸。兔子走过草地会留下R,狐狸走过草地会留下F。每只动物从左上角进入草地,从右下角走出草地。其间,它可以上下左右乱跳(可以重复),经过的格子会被覆盖上它的脚印。每次草地上最多只有一只动物。 给你地图,问最少有多少只动物走过了草地。 Solution 先将每一个边缘点加入$queue$,再每…
Luogu P4255 公主の#18文明游戏 题解
Describe 题目链接 这个游戏里有n个城市,标号1~n,有m条双向道路相连,编号1~m。 游戏里会系统会添加Ni个人到一个城市Xi,并给定这些人的信仰Ci 系统还会切断一条道路,并给定道路编号Xi 系统还会给定一个城市Xi,询问从Xi出发可以到达的所有城市中选择Ni个人,使得他们信仰都为Ci的概率为多少,对19260817取模。 Soluti…
Luogu P1879 [USACO06NOV]Corn Fields G 题解
Describe 题目链接 给一个$M\times N$的矩阵,矩阵每个位置为$0/1$,问选一些$1$使这些不相邻的方案数。 Solution 明显状压$DP$。 那么怎么$DP$呢? 设$f[i][j]$表示第$i$行状态为$j$的方案数。 那么转移就可以暴力枚举上一行的状态再判断可能性转移。 $$f[i][j]+=f[i-1][k]$$ 那么…
Luogu P1896 [SCOI2005]互不侵犯 题解
Describe 题目链接 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。 注:数据有加强(2018/4/25) 1 <=N <=9, 0 <= K <= N * N Solution 状压DP。 判断两个国王是否相互干扰…
Luogu P1110 [ZJOI2007]报表统计 题解
Describe 题目链接 小 Q 的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小 Q 希望可以帮妈妈分担一些工作,作为她的生日礼物之一。 经过仔细观察,小 Q 发现统计一张报表实际上是维护一个非负整数数列,并且进行一些查询操作。 在最开始的时候,有一个长度为$ n$的整数序列$a$,并且有以下三种操作: INSERT i k…