发现题目中描述的配对条件可以理解为：\(pc_i-pc_j=1\)且\(a_i\bmoda_j=0\)，其中\(pc_i\)表示\(a_i\)的质因数个数。自然想到以\(pc\)奇偶性建立二分图，可以配对的点间连一条边。先不考虑费用，三种边为：\((s,i,b_i)\)，其中\(pc_i\bmod2=1\)。\((i,t,b_i)\)，其中\(pc_i\bm

视频链接：C120树剖+李超树P4069[SDOI2016]游戏_哔哩哔哩_bilibili    D12LuoguP3384【模板】轻重链剖分/树链剖分-董晓-博客园(cnblogs.com) LuoguP4069[SDOI2016]游戏//树剖+李超树O(nlognlognlogn)#include<iostream>#include<cstring>#in

题目描述我们要操作的是一条在树上的路径\(s\)->\(t\)。(1)查询\(s\)->\(t\)最大的数字。(2)在\(s\)->\(t\)上增加一个数字，输入\(a\)，\(b\),对于路径上的一个点\(u\)增加的数字是\(dis(s,u)\timesa+b\)。解题思路直接查询一条从\(s\)到\(t\)的路径是十分不方便的，所以我们

可以看出来出题人很想出一道把李超和别的什么东西凑起来的题目，于是给了这么一个缝合怪。https://www.luogu.com.cn/problem/P4069符号有点混乱。比如箭头又可以表示路径又可以表示赋值，代入语境应该还是好理解的。看到\(a\timesdis+b\)就应激反应出来是李超了，看到\(s\to

[SDOI2016]储能表-洛谷题目详情-[SDOI2016]储能表-BZOJbyHydroOJ一道很好的数位dp题不过这题有一个比较有意思的性质：当\(n,m\)为\(2^k\)的形式时，最终得到的数组对每一行排序后为\(0\simm-1\)的排列，如果有的话说不定可以作为一个部分分？遇到二进制运

传送门solution树剖后一段路径变成了若干链拼起来。自上而下和自下而上分别维护两棵李超线段树，每条链就是一段数轴，提前处理每个点两种方向上的在链内的横坐标。以最近公共祖先为界，把路径分成两段。从一个点向链的顶端跳就是区间加线段。每次跳完要把线段的截距增加一个横坐标偏

LLink显然的，答案就是\(C_n^m*D_{n-m}\)#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<stack>#include<set>#include<map>#include<ctime

原题\[\huge{\color{#ff0000}{\text{被XJK搏杀了，我tcl}}}\]我们先从\(n\)个数里选\(m\)个数钦定这些数满足\(a_i=i\)，因此原问题就等于让\(n-m\)个数的排列满足\(a_i\neqi\)的排列方案数先说一个错误的做法：设\(dp_i\)表示长为\(i\)的排列的方案数。我们每次枚举一个大小为\(

现在求有多少种长度为n的序列A，满足以下条件：1~n这n个数在序列中各出现了一次若第i个数A[i]的值为i，则称i是稳定的。序列恰好有m个数是稳定的满足条件的序列可能很多，序列数对10^9+7取模。输入第一行一个数T，表示有T组数据。接下来T行，每行两个整数n、

[SDOI2016]排列计数题目描述求有多少种\(1\)到\(n\)的排列\(a\)，满足序列恰好有\(m\)个位置\(i\)，使得\(a_i=i\)。答案对\(10^9+7\)取模。输入格式本题单测试点内有多组数据。输入的第一行是一个整数\(T\)，代表测试数据的整数。以下\(T\)行，每行描述一组测试

又来水博客了[SDOI2016]征途推一下柿子就会发现，我们要求最小值的部分是将整个序列分为来m段，然后每段和的平方相加最小。\(f[i][j]=f[k][j-1]+(s[i]-s[k])^2\),然后用滚动数组优化一下。\(g[i]=f[k]+s[i]^2-2s[i]s[k]+s[k]^2\)\(f[k]+s[k]^2=g[i]-s[i]^2+2s[i]s[k]\)将决策看

题目描述Alice和Bob在玩一个游戏。游戏在一棵有\(n\)个点的树上进行。最初，每个点上都只有一个数字，那个数字是\(123456789123456789\)。有时，Alice会选择一条从\(s\)到\(t\)的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点\(r\)，若\(r\)与\(s\)

传送门#include<iostream>#include<algorithm>#include<cstring>typedeflonglongll;typedefstd::pair<double,int>PDI;constintN=1e5,M=2e5+10;constllINF=123456789123456789;intn,m,cnt;inth[N],e[M],ne[M],

「SDOI2016」征途TJ题目传送门题目大意：有\(n\)个块，给出其块长，将其分为\(m\)组，使得每组内长度之和的方差最小。输出\(v\timesm^2\)，其中\(v\)是方差。思路：

[SDOI2016]储能表题目描述有一个n行m列的表格，行从0到n−1编号，列从0到m−1编号。每个格子都储存着能量。最初，第i行第j列的格子储存着(ixorj)点能量。