魔法少女LJJDescription:题目描述在森林中见过会动的树，在沙漠中见过会动的仙人掌过后，魔法少女LJJ已经觉得自己见过世界上的所有稀奇古怪的事情了LJJ感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味；小猴在枝头悠来荡去,好不自在；各式各样的鲜花争相开

前置芝士：kruskal求最小生成树，并查集原题链接：hydro思路我们将它建模成图论问题，相当于从\(i\)到\(j\)连一条长度为\(a_{i,j}\)的边，然后使得每个点都有一个入度，那么就是在求最小基环树森林。至于基环树森林怎么求呢？我们使用像kruskal的思想，按照边的长度的大小对边进行排

前几天我在和群里的一个人聊天，他NOIP2017只考了70分。我问他：“你没有什么理想吗？你有什么想做的事情？”他瞬间回复道：“我要学所有发明过的算法！”真没想到现在还有这种人。我问他这为什么能成为他的目标，他反问道：“你就没有这个想法吗？学一大堆别人听都没听说过的算法，出成题目让他

妙妙数数题key：数数题通常是，对于特定形式的计数，就盯着这个模式观察，看出一些充要条件、计数形式的转化，然后想办法维护。优化的本质就是把难算的变成好算的，把不好一起统计的（只能一个个数的）以某种角度、用某些数据结构，一起统计（多个多个数）。我觉得难点通常在于“盯出一些充要条件”，

缅怀zxc

Description将数字N进行拆分.拆分出来的数字可以重复使用.FormatInput每一行给出一个数字N,3<=N<=500.整个测试以0代表结束.Output拆分的种数.这道题，看似变态难写，实则。。。一道******题。(观众：哇。。。。。。）这题是个简简单单的dp!N就是背包容量，但是物品体积在哪捏？？？就

BZOJ4403序列统计解析序列满足单调不降序列，所以每个数可以选多次，我们可以把不同位置的同一个数看成多个，这样把区间为\([L,R]\)中的每一个数加上\(i\),得到的区间大小为\([L+1,R+n]\),也就是从\(R-L+n\)个数中选\(n\)个。\[\begin{aligned}&{\sum^n_{i=1}C^{i

假设存在一个满足条件的长度为i的不下降序列（显然是一定存在的）那么只需要从中选出i个数即可（不必在意选出具体数的大小，可以把满足条件的序列写下来，选几个数感受一下）。但是$n\choosem$里的\(m\)的是就是\((r-l+1)\)吗?乍一看是这样的，但是这样会出现一个问题，单调不下降子序

攻略题面\(n(\le2\cdot10^5)\)个点的有根树，\(k(\len)\)次从根走到叶子，每个点有权值，求经过的点的权值和的最大值.（同一个点只能算一次）Sol1我们设想一个叶子一个叶子加进去的过程。如果有两个从某个点到叶子的路径，我们可以如图把他分成两条路径。那么他满足贪心，也就是每次

tg.BZOJ4403序列统计pj.BZOJ4403序列统计没啥用的题解\(QWQ\)——无脑思考首先要想怎么求单调不上升序列的个数，因为可能会有重复的数，所以不能直接用排列组合。那这道题怎么打呀？我不知道啊\(\dots\)\((~:\)因为原来是单调不下降序列，将第\(i\)位上的数加\(i\)，于是

bzoj#4069二进制？按位考虑。或操作而且最小？按位贪心。从最高位往下贪，记录一个\(x\)表示当前最高位确定了哪些位可以为\(0\)(其中存在为\(0\)方案的位上值为\(1\))考虑dp处理对于第\(t\)位能否为\(0\)：设计状态：设\(dp_{i,j}\)表示前\(i\)个数分成\(j\)个

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)}\)这么干显然不太对，因为我们不能保证每次删除时都能把图中的所

三倍经验：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\)条路径的方案数（

题目背景翰翰18岁生日的时候，达达给她看了一个神奇的序列$A_1,A_2,\dots,A_n$。她被允许从中选择不超过$M$个连续的部分作为自己的生日礼物。翰翰想要知道选择元素之和的最大值。你能帮助她吗？解题思路可以先合并序列中连续的同为正或负的值，使原序列变为一个一正一

题目链接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\)的

题目链接description厉害题。给定一棵树，按照题面要求求一个错误点分治的期望执行次数。（不想描述题面了qwq）solution考虑拆开计算每个点期望几层点分治后被删除。这个期望值显然就是它对答案的贡献。我们不妨以这个点为根，那么相当于要求每次删除一个未被删除的点的子树，求删完

简述题意给出一个长度为\(n\)的序列\(A(A_1,A_2,\dots,A_n)\)。如果序列\(A\)不是非降的，你必须从中删去一个数，并重复这一操作，直到\(A\)非降为止。求有多少种不同的操作方案，答案模\(10^9+7\)。题面转换

考虑设计一个哈希函数\(hash(x)=f(x)\timesbase^x\)。其中\(f(x)\)表示\(\sum_{j=1}^{i-1}[j<i]\)。然后类似于滑动窗口计算区间哈希值，加入一个数就计算贡献，减去一个数就计算这个数产生了贡献，两个东西都可以树状数组维护，那么愉快做完了。#include<bits/stdc++.h>#de

BZOJ#3784.树上的路径题意给一颗树，求所有路径长度中前\(k\)大。题解首先对于前\(k\)大，我们有一个常见的方法，二分。二分第\(k\)大的路径长度，然后使用点分治统计，点分治内部还要二分，所以时间复杂度\(O(nolg^3n)\)。二分显然是行不通了，想一下就会发现外层和内层的二分

2140:稳定婚姻TimeLimit: 2Sec  MemoryLimit: 259MBSubmit: 764  Solved: 355[Submit][Status][Discuss]Description我国的离婚率连续7年上升，今年的头两季，平均每天有近5000对夫妇离婚，大城市的离婚率上升最快，有研究婚姻问题的专家认为，是与简化离婚手续有关。25