- 2024-06-17bzoj.org P07255 数字的拆分之二
Description将数字N进行拆分.拆分出来的数字可以重复使用.FormatInput每一行给出一个数字N,3<=N<=500.整个测试以0代表结束.Output拆分的种数.这道题,看似变态难写,实则。。。一道******题。(观众:哇。。。。。。)这题是个简简单单的dp!N就是背包容量,但是物品体积在哪捏???就
- 2024-04-15BZOJ 4403序列统计
BZOJ4403序列统计解析序列满足单调不降序列,所以每个数可以选多次,我们可以把不同位置的同一个数看成多个,这样把区间为\([L,R]\)中的每一个数加上\(i\),得到的区间大小为\([L+1,R+n]\),也就是从\(R-L+n\)个数中选\(n\)个。\[\begin{aligned}&{\sum^n_{i=1}C^{i
- 2024-04-13BZOJ 4403序列统计
假设存在一个满足条件的长度为i的不下降序列(显然是一定存在的)那么只需要从中选出i个数即可(不必在意选出具体数的大小,可以把满足条件的序列写下来,选几个数感受一下)。但是$n\choosem$里的\(m\)的是就是\((r-l+1)\)吗?乍一看是这样的,但是这样会出现一个问题,单调不下降子序
- 2024-01-26[Bzoj 3252] 攻略 题解
攻略题面\(n(\le2\cdot10^5)\)个点的有根树,\(k(\len)\)次从根走到叶子,每个点有权值,求经过的点的权值和的最大值.(同一个点只能算一次)Sol1我们设想一个叶子一个叶子加进去的过程。如果有两个从某个点到叶子的路径,我们可以如图把他分成两条路径。那么他满足贪心,也就是每次
- 2023-12-29【题解】BZOJ 4403序列统计
tg.BZOJ4403序列统计pj.BZOJ4403序列统计没啥用的题解\(QWQ\)——无脑思考首先要想怎么求单调不上升序列的个数,因为可能会有重复的数,所以不能直接用排列组合。那这道题怎么打呀?我不知道啊\(\dots\)\((~:\)因为原来是单调不下降序列,将第\(i\)位上的数加\(i\),于是
- 2023-10-28bzoj #4069. [Apio2015] 巴厘岛的雕塑
bzoj#4069二进制?按位考虑。或操作而且最小?按位贪心。从最高位往下贪,记录一个\(x\)表示当前最高位确定了哪些位可以为\(0\)(其中存在为\(0\)方案的位上值为\(1\))考虑dp处理对于第\(t\)位能否为\(0\):设计状态:设\(dp_{i,j}\)表示前\(i\)个数分成\(j\)个
- 2023-10-28bzoj #2863. 愤怒的元首
bzoj#2863设\(dp_i\)表示\(i\)个点的DAG个数。发现一个DAG删去出度为\(0\)的点后显然还是一个DAG,因此不妨枚举出度为\(0\)的点的个数:\(dp_i=\sum\limits_{j=1}^idp_{i-j}\binom{i}{j}2^{j(i-j)}\)这么干显然不太对,因为我们不能保证每次删除时都能把图中的所
- 2023-10-23P3565 [POI2014] HOT-Hotels
三倍经验:bzoj#3522P3565loj#2431加强版:bzoj#4543先看bzoj#3522这题。容易想到时间\(O(n^2)\),空间\(O(n^2)\)的树形dp。设\(dp_{1/2/3,u,i}\)表示以\(u\)为根的子树中所有以\(u\)为一端点,长度为\(i\)的路径中选\(1/2/3\)条路径的方案数(
- 2023-09-24BZOJ 生日礼物
题目背景翰翰18岁生日的时候,达达给她看了一个神奇的序列$A_1,A_2,\dots,A_n$。她被允许从中选择不超过$M$个连续的部分作为自己的生日礼物。翰翰想要知道选择元素之和的最大值。你能帮助她吗?解题思路可以先合并序列中连续的同为正或负的值,使原序列变为一个一正一
- 2023-09-19BZOJ 3509
题目链接description给定一个长度为\(n\)的数组\(a\),求有多少对\(i,j,k(1\leqi<j<k\leqn)\)满足\(a_k-a_j=a_j-a_i\)\(n\leq10^5\)值域大小3e4.solution三个数,看起来就不好用数据结构维护。\(2a_j=a_i+a_k\)可以当做多项式两项的指数相加得到指数为\(2a_j\)的
- 2023-09-15BZOJ 3451
题目链接description厉害题。给定一棵树,按照题面要求求一个错误点分治的期望执行次数。(不想描述题面了qwq)solution考虑拆开计算每个点期望几层点分治后被删除。这个期望值显然就是它对答案的贡献。我们不妨以这个点为根,那么相当于要求每次删除一个未被删除的点的子树,求删完
- 2023-08-09[BZOJ 4361] isn
简述题意给出一个长度为\(n\)的序列\(A(A_1,A_2,\dots,A_n)\)。如果序列\(A\)不是非降的,你必须从中删去一个数,并重复这一操作,直到\(A\)非降为止。求有多少种不同的操作方案,答案模\(10^9+7\)。题面转换
- 2023-07-18BZOJ 1461 题解
考虑设计一个哈希函数\(hash(x)=f(x)\timesbase^x\)。其中\(f(x)\)表示\(\sum_{j=1}^{i-1}[j<i]\)。然后类似于滑动窗口计算区间哈希值,加入一个数就计算贡献,减去一个数就计算这个数产生了贡献,两个东西都可以树状数组维护,那么愉快做完了。#include<bits/stdc++.h>#de
- 2023-07-14BZOJ #3784. 树上的路径
BZOJ#3784.树上的路径题意给一颗树,求所有路径长度中前\(k\)大。题解首先对于前\(k\)大,我们有一个常见的方法,二分。二分第\(k\)大的路径长度,然后使用点分治统计,点分治内部还要二分,所以时间复杂度\(O(nolg^3n)\)。二分显然是行不通了,想一下就会发现外层和内层的二分
- 2023-07-07BZOJ 2140: 稳定婚姻 tarjan
2140:稳定婚姻TimeLimit: 2Sec MemoryLimit: 259MBSubmit: 764 Solved: 355[Submit][Status][Discuss]Description我国的离婚率连续7年上升,今年的头两季,平均每天有近5000对夫妇离婚,大城市的离婚率上升最快,有研究婚姻问题的专家认为,是与简化离婚手续有关。25
- 2023-07-07BZOJ 2427: [HAOI2010]软件安装 树形背包
2427:[HAOI2010]软件安装TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 1275 Solved: 492[Submit][Status][Discuss]Description现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机
- 2023-07-07BZOJ 1042:[HAOI2008]硬币购物 容斥原理 背包dp
1042:[HAOI2008]硬币购物TimeLimit: 10Sec MemoryLimit: 162MBSubmit: 2505 Solved: 1505[Submit][Status][Discuss]Description硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次
- 2023-06-20bzoj 2839. 集合计数 二项式反演
集合计数设fi表示恰好交集为k的方案数。设gi表示交集至少为k的方案数。\(g_i=\sum_{j=i}^{n}C(j,i)f_j\)由二项式反演得:\(f_k=\sum_{i=k}^{n}(-1)^{i-k}C(i,k)g_i\)考虑\(g_i\)的求出,钦定\(i\)个数必选那么剩下\(n-i\)个数每个数可选可不选\(2^{n-i}\)但这道题我们选出的
- 2023-06-16【BZOJ 3156】防御准备 题解
原题令\(S_{i}=\sum_{j=1}^{i}j\),\(f_{i}\)为处理到第\(i\)个位置放置守卫塔的最小花费。观察题意,容易得到在\((1<=j<=i-1)\)时,有\(f_{i}=min\left\{f_{j}+\sum_{k=j+1}^{i-1}(i-k)+a_{i}\right\}\)①\(f_{i}=min\left\{f_{j}+\sum_{k=j+1}^{i-1}(i-k)\ri
- 2023-06-14 [BZOJ 2839] 集合计数
首先求一个集合的个数可由\(2\cdot2\cdot2\cdot2...\)得到,其中每个二表示选或者不选本个元素。即一个有\(n\)个元素的集合存在\(2^n\)个子集然后同理可得从\(2^n\)个子集中选交集的方案数为\(2\cdot2\cdot2\cdot2...\)(共包含\(2^n\)个\(2\))所以总数
- 2023-06-02bzoj 1007: [HNOI2008]水平可见直线(模拟栈)
http://www.lydsy.com/JudgeOnline/problem.php?id=10071007:[HNOI2008]水平可见直线TimeLimit: 1Sec MemoryLimit: 162MBSubmit: 7644 Solved: 2922[Submit][Status][Discuss]Description在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往
- 2023-04-13BZOJ 2038 小Z的袜子(hose) (莫队离线)
题目地址:BZOJ2038裸的莫队算法。代码如下:#include<iostream>#include<string.h>#include<math.h>#include<queue>#include<algorithm>#include<stdlib.h>#include<map>#include<set>#include<stdio.h>#incl
- 2023-04-04bzoj 4237 稻草人
4237:稻草人TimeLimit: 40Sec MemoryLimit: 256MBSubmit: 791 Solved: 353[Submit][Status][Discuss]DescriptionJOI村有一片荒地,上面竖着N个稻草人,村民们每年多次在稻草人们的周围举行祭典。有一次,JOI村的村长听到了稻草人们的启示,计划在荒
- 2023-04-04bzoj 3622 已经没有什么好害怕的了
3622:已经没有什么好害怕的了TimeLimit: 10Sec MemoryLimit: 256MBSubmit: 805 Solved: 377[Submit][Status][Discuss]DescriptionInputOutputSampleInput42535154540201030SampleOutput4HINT输入的2*n个数字保证全不相同。
- 2023-03-25bzoj 3669 魔法森林
3669:[Noi2014]魔法森林TimeLimit: 30Sec MemoryLimit: 512MBSubmit: 2690 Solved: 1667Submit][Status][Discuss]Description为了得到书法大家