山东省队集训题

以下题目来源LOJ

6059. 「2017 山东一轮集训 Day1」Sum

转移式子是

$f_{i,(j*10+c)\mod p,k}=\sum_k f_{i-1,j,k}*f_{1,c,t-k}$

其实就是矩阵乘法,但是矩乘只有60分

但是仔细观察这个第三维卷积形式很不错

所以我们考虑倍增NTT吧

怎么倍增呢,就是说我们使用一个p*n大小的数组记录p个多项式,然后从 $n->2n$ 的过程,就直接考虑枚举第二维的两个东西的取值,然后把对应两个多项式NTT卷起来

这样做复杂度就是 $p^2mlogm*logn$ ,毛估估一下是可以的

6061. 「2017 山东一轮集训 Day1」Sim

懒得做了,看全网没有题解发一篇吧

操作一一开始没看懂,其实他的意思就是从左到右拿出所有第一次出现的元素,然后把他们做一个类似找到所有三元组乘积然后求和

看见操作2,3,4,5,和下面那个 $n,q<=5e5$ 其实我思维定式就想树套树,但是说树套树并不practical啊QAQ怎么都要平衡树套线段树,搞不好还要写垃圾桶

所以对于插入和删除而且允许我们离线的操作可以暴力改成点亮和变暗

这个怎么做啊?首先你需要写一个set,然后考虑插入和删除操作都相当于在某个下标处直接模拟

然后记录序列的一个历史最大长度即可qwq

等等,好像我们的操作1和操作5也会跟着改/QAQ

所以要手写平衡树维护全局第k大这样子,因为我们下标要保证只扩展不收缩

于是插入和删除都变成了修改

最后我们要维护操作5和操作1,这个只能树状数组套主席树了

操作1的维护方式就是考虑一个单项和,乘积和,三项乘积和就好了

6060. 「2017 山东一轮集训 Day1 / SDWC2018 Day1」Set

.....有毒啊

首先显然的是,对于一位异或值为0的,我们一定是奇数个分给左边,奇数个分入右边,这样两位都能是1

然后异或值为奇数的,我们一定让 $x_2$ 尽可能拿奇数

同时你需要发现,异或值为0的,此时 $x_2$ 在这一位也应该尽量大!!

所以我们要让 $x_2$ 尽量在每一位都大!线性基!!

但是,这是在确保这个异或值的大前提的,这个大前提隐形说明了什么呢?

异或为1的条件2一定成立,即最后贡献无论如何分配只能是1
异或为0的条件1不一定成立,即最后贡献根据分配方案不同答案不同

这告诉我们,先让 $x_2$ 在这些为0的位上取到最大值,再在剩下的位取到最大值!

同时同一异或值的按照从高到底最大化

线性基魔改一下插入过程即可

6062. 「2017 山东一轮集训 Day2」Pair

怎么做呢?

考虑长度为m的连续子序列只有 $O(n-m)$ 个

所以可以考虑匹配过程,如何优化 $n^2$ 匹配

发现这个可以直接做,就是排序,然后让最大的匹配最小的

因为你发现这个一定满足单调性,不会说y不能匹配,比y小的元素x能匹配,然后交换x和y后合法了

于是我们需要一个set维护动态插入删除

但是说问题又来了,我们不知道原来一个不合法的状态变换过来会怎么办

那么这就是一个模拟费用流了QAQ

于是我们可以考虑Hall定理,就是完全匹配

你会发现Hall定理成立充分条件是右边任何一个点的子集都要和左边有大于点集个数的点连边

直接做是 $2^m$ CF还真有这样的神仙构造题

但是这道题有优化,就是考虑对于任何一个A的子集,都只会和排序后B的一个后缀连边

那么每次加入一个元素A,就可以二分,然后这些相当于对某个后缀来了新的边,然后区间加,然后查询 $v_i-i$ 是否都大于0即可

6065. 「2017 山东一轮集训 Day3」第一题

这题怎么都能做吧

2+2+1+1

考虑枚举二元组,木棍,然后把个数映射到值域上

然后考虑再去枚举二元组统计,对于一个二元组x+y,直接用 $n(n-1)/2$ 会计重

但是你发现计重只会计重 $x+y=x+z$ ,那么对于这个二元组很好统计有多少木棍为z qwq

3+1+1+1

考虑枚举其中一条单独木棍和三元组中一条木棍

三元组就变成了二元组

那么你就会发现二元组不能包括三元组那个边

但是由于和是一定的,所以直接减去就好了

6066. 「2017 山东一轮集训 Day3」第二题

我的思路很simple啊

这个树同构的前提条件就是所有点的括号序列都相同,就是说一个点可以被写成123111表示从根向他按那些顺序走过去的

然后我们把每个点的这个hash值求和作为点u的hash值

二分一个上界k,然后发现答案就是是否存在两个hash值一样的点

考虑怎么快速判断这个信息,就是考虑u子树向父亲扩展,相当于在路径头添加一个数,直接乘法原理乘上剩余点数放进去就好了

同时我们要删除掉某些点,考虑用一个线段树合并维护某个深度的点值的hash值,这个也很好维护吧

至于这个hash函数正确性就不知道了qwq

其实不难发现这个查询k级儿子的过程可以离线变为查询k级祖先,就不需要线段树合并了!

6067. 「2017 山东一轮集训 Day3」第三题

多项式多点求值模板题

直接上命没了,模数 $1e6+3$

于是考虑放弃

6068. 「2017 山东一轮集训 Day4」棋盘

网络流

你考虑怎么建图体现这个费用

首先不难把所有本质不同的行和列拿出来

然后如果存在(i,j)不是障碍就有i行j列的一条边

然后我们考虑更改一下由s向所有行点连边的边权,和t向所有列点连边的边权

不难发现就是我们流一个流量会带来已经流过流量的代价

那么我们把一个边拆成k条,每条流量为1,费用为[0~n-1]

于是就费用流即可,每次保证只增广一点流量

但是复杂度不太对,于是我们考虑每次增广后在残量网络上新加入几条边就能快许多

复杂度就是 $O(n^4)$

询问1e5组本质不同只有 $n^2$ 组

6069.「2017 山东一轮集训 Day4」塔

考试前本博客最后一题了/ll

考虑怎么设计dp状态,至少得到一个多项式算法

直接的想法是状压所有可能的case,就是铺满他们的方案数,再用空格插入得到总方案

但是不实际,我们可以想这个东西有什么性质,就是贡献之和大的元素有关

于是我们考虑把整个放入数的过程变成一个连通的过程,从小到大放入,让他们连通,然后在连通的过程计算答案

$f_{i,j,k}$ 表示考虑了前i个数,然后现在还有j个连通块,并且排列的长度为k

然后插入j,它只能插入在一个连通块的两端,并且决定这个连通块是否和周围的连通使得连通块数量减少

具体的,假设j=5

|1...|..2..|.3..|..4..|..5 |

那么我们有如上7个位置可以放入这个数

同时因为我们也可以新开一个连通块,但是此时必须保证剩下的数能够将所有的连通块连通才行!所以不能盲目新开

同时,如果我们不选择连通而是接在某个连通块左右时,也需要考虑能不能这样做,如果剩下空位正好就是剩下数字数,那你也没办法了

然后考虑实际上我们算出来的是没有可爱的空位的方案数

使用组合数解决最后一步就好了,就是插板法 $\binom{l-k-1+n}{n}$

6073. 「2017 山东一轮集训 Day5」距离

我们首先将问题简单转化,

$dis(x,y)=dep_x+dep_y-2dep_{lca}$

问题变成了些点的dep之和,一个点集的点和k的LCA的

第一个很简单,直接求和即可

然而第二个,我们需要考虑之前经典题的做法

我们是把所有点集里面的点把它到根的路径都加上了1,然后查询另一个点到根的点权和就是答案,这种思想相当于加权

然后我们这道题可以类似的,我们考虑从根到底实现一个可持久化线段树,每次修改操作是将点集中某个点加入导致的区间+

然后对于一次询问,我们相当于用四个主席树的结果凑出来区间查询的答案,这个区间查询时需要树剖

那要树剖就是 $O(nlog^2n)$

6074. 「2017 山东一轮集训 Day6」子序列

也是不错的点子啊

dp的第二维是10

$f_{i,j}$ 表示前i个点,然后最后一个位置是j的序列方案数

转移对于 $s_i=k$ ,有 $f_{i,k}=\sum f_{i,j}$

然后其他的是直接平移过去

这个dp的正确性在于任何子序列都在他最早匹配的位置出现并且匹配上

我们注意到区间查询,然后又是动态规划,因此可以用一个线段树维护dp数组

然鹅并不需要这样麻烦,线段树是在我们信息不可减的情况下才用的,而因为我们转移矩阵是可以写出逆矩阵的,因此还是可以求出来答案的

然后注意到本质不同的逆矩阵最多只有10个,所以可以快乐预处理

6079. 「2017 山东一轮集训 Day7」养猫

想到了最后一步,然后成功败在了建模上面/cy

我们拿到题其实有两个方向1. 动态规划2. 贪心

考虑动态规划,我们的转移需要记录前k位置有多少个ms,或者me,然后又发现我们每次移动需要减去左端点的猫的形态信息,这个确实不太现实

于是我们再去考虑每次最多减少一个猫的形态,可以考虑记录这个区间多几个0/1,比如这个区间是否至少达到下界i个吃饭喵,仔细思考发现状态对于转移真没啥用处,因为我们是最优化,而不是计数啊

那只剩下贪心,显然需要带反悔贪心

考虑网络流吧,第一步转换我就思考了好久呢QAQ

把每个区间限制看成一个点,每个点看成对于一个区间的影响,那么就会发现问题可以变成一个线段覆盖问题

首先都选上s,然后我们考虑换成e,然后最多一个位置能够换成n-ms个e最少是me个,似乎是不好做的qaq

换,对应 $(i,i+k,1,e_i-s_i)$

但是我们总有炫酷建图技巧,考虑用费用流把这个最少用流量最大的性质消掉,很简单,我们限制流量达到 $k-ms$ ,即建立虚点,然后S向虚连边限制流量恒为这个值

然后,我们从i向i+1连流量为 $k-ms-me,0$ 的边,这些边表示我们可以自由选择,然后跑最大费用流

分析一个剖面图,我们流量恒为 $k-ms$ ,然后对于 $i->i+1$ 最多有 $k-ms-me$ 流量,最少有0的流量,对应跨过他的边,最多有 $k-ms$ 的流量(几乎全换了),最少有me的流量

OK,正确的

6078. 「2017 山东一轮集训 Day7」重排

这题直接杀我真的是

没有自环,我的想法是每次计算走到一个点的期望最小代价时,应该考虑有多少条向他的相同的重边,然后这些重边可以自己排列出一个答案,这部分可以用一个简单计数解决,当没有重边时答案显然是 $sum/m$ ,有也不过是变化了几下而已

然后再想想怎么解决自环.翻了翻题解,发现好像自己萎了?

萎了的原因是,我们计算的方式不对,没有很好的体现这个最小值,我们计算只考虑了每个位置均摊的代价,也就是我们的转移只会走到一个点,然而没有考虑到有一些位置是可能在一些排列中成为答案的!

所以我们使用题解一个很巧妙的方法,好像是带权匹配,就是我们有 $O(d)$ 个边权(可以重权),同时有 $O(d)$ 个对应的点(可以有重复),因此我们有 $O(d^2)$ 种边*点的匹配方式

那么我们考虑一条边权方式能匹配哪些点,显然最优情况下是最小的那个,但是同时你会发现我们匹配最小的对于答案的贡献算完后应该去匹配次小的了,所以我们再放入这个匹配次小的,迭代处理下一层

考虑一种组合的概率咋算,要使用条件概率,就是我们现在有i匹配了前j个最小的点吧,然后i匹配j+1个点,那么那个点的信息就该是前面的都匹配失败了,然后这个点成功的概率

明天补坑

6100. 「2017 山东二轮集训 Day1」第一题

这种类型的题一般可以思考传递性对于区间性质的限制

就是我们再固定某一维信息后,因为限制具有无后效性(第i个元素受前i-1个元素限制),而且是必须要每个位置都满足,也就是二分性(可行性单调变化),所以只可能是从i出发向后的一段区间

比方说WC讲解中区间广义链,他的传递性可以认为是这个元素必须和前面元素构成链,而与此同时一旦构不成链,再向后延伸都不行

而无后效性主要用于递推,在本题中就是异或值不能变小,即新数的最高位对应的位置一定要为0,同时显然有单调性,我们对于L出发,有一个极长的R,那么对于一组询问包括L的,显然L出发的会对于其有 $min(r,R)-L+1$ 贡献,无疑这个好维护

所以我们可以考虑怎么做处理这个极长区间

答案是显然这样的极长区间数是 $O(n)$ 个的,所以只需要记录当前1~i中所有合法的极长区间的信息,然后加入第i个点的时候,考虑第i个点的最高位,对应信息中不是0的那些暴力删除掉,改掉他们的信息,然后将第i个插入即可

发现我们需要一个全局异或上一个数,查询某一位为0/1的是哪些的数据结构,额,好像直接用数组和一个变量维护,用延时删除标记就能做到 $O(nlogn)$ ....

最后还要考虑怎么回答答案,那个式子,显然我们可以用一个主席树数区间内R大于r的L的个数,,然其余直接求和后最后减去一个 $\sum L$ 即可

6101. 「2017 山东二轮集训 Day1」第二题

发呆,没想这个题,直接题解了...

我们考虑为什么不能刚好搭完,因为我们每次都只能向上或者向左向右搭所以就完蛋了

而观察样例我们能有一个看上去的最优的策略就是第一步先尽量铺满地下的第一层,第二层,第三层这样子

然后铺到我们不能铺为止,此时我们一定能够把区间分割成几个小区间,他们有一个性质,一旦我们选择在一个区间处选择铺砖,那么这次铺砖一定不能影响其他区间

然后我们根据这个可以分治新产生的区间了!

具体的,我们考虑记录 $l,r,x,p$ 表示当前分治到 $[l,r]$ 区间,然后已经有了x的基础,可以认为是所有数减去了x,然后有p点上次删除带来的影响

因为我们最后一次操作可能没能用完所有的砖块,所以我们要把这个剩下的信息,留给左边或者右边来用,就是p

看了题解觉得有点震撼啊!

首先对于这类问题我们可以建立笛卡尔树

笛卡尔树的构建我另写了博客

然后对于笛卡尔树上的节点,我们考虑从深的到浅的计算影响,每次只计算和父亲的差值

其中如果使用过多导致成为负数,一样传导父亲上,说明我们有过多的可以贡献出来

容易发现这个和之前我的做法是一样的东西,不过显然许多

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 7;
int n, k;
int a[MAXN], fa[MAXN], ls[MAXN], rs[MAXN], sz[MAXN], st[MAXN];
ll ans, sm[MAXN];
//有多少节点说明长度有多宽啊
inline void dfs(int u) {
	sm[u] = 0;
	sz[u] = 1;
	if(ls[u])dfs(ls[u]), sz[u] += sz[ls[u]], sm[u] += sm[ls[u]];
	if(rs[u])dfs(rs[u]), sz[u] += sz[rs[u]], sm[u] += sm[rs[u]];
	sm[u] += 1ll * (a[u] - a[fa[u]]) * sz[u]; //需要的
	if(sm[u] > 0) {
		ll x = (sm[u] - 1) / k + 1; //下取整啊
		ans += x;
		sm[u] -= x * k;//除掉
	}
}
int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	int top = 0;
	for(int i = 1; i <= n; ++i) {
		int k = top;
		while(k && a[st[k]] > a[i])--k;
		if(k)rs[st[k]] = i, fa[i] = st[k];
		if(k < top)ls[i] = st[k + 1], fa[st[k + 1]] = i;
		st[++k] = i;
		top = k;
	}
	dfs(st[1]);//总要有一个点
	printf("%lld\n", ans);
	return 0;
}

6102. 「2017 山东二轮集训 Day1」第三题

搞数学搞事情啊

这都是原题啊...qaq

看上去还真挺妙的

我们考虑有一个结论

$gcd(f_n,f_m)=f_{gcd(n,m)}$

证明:

考虑证明

$gcd(f_n,f_m)=gcd(f_n,f_{n-m})$

证明这个可以考虑再引理

$n|m,f_n|f_m$

再引理

$f_{n+m}=f_{n-1}f_m+f_nf_{m+1}$

或者我们有更优美的形式

$f_{n+m+1}=f_mf_n+f_{n+1}f_{m+1}$

这个可以很牛逼的数学归纳法证明!

首先假设对于所有m,前k个n是成立的,然后推导出第k+1个成立

首先当k=0的时候显然成立

那么现在有 $f_{k+m+1}=f_{m}f_{k}+f_{k}f_{m+1}$ 成立

f_{m}f_{k+1}+f_{k+1}f_{m+1}\\ f_mf_k+f_mf_{k-1}+f_{k}f_{m+1}+f_{k-1}f_{m+1}\\ f_{k}f_{m+2}+f_{k-1}f_{m+2}\\ =f_{k+1}f_{m+2}\\ =f_{k+1}f_{m}+f_{k+1}f_{m+1}\\ =f_{k+m+2}\\

我承认证的时候可能有点鬼畜...QAQ

然后证明这个结论

$f_{m+n}=f_{n-1}f_{m}+f_{n}f_{m+1}$

你别说,这个结论EI说这个可以用矩阵乘法简单证明...

好像你仔细一想如果我们分开结合律一下,还真的可以证明....

$gcd(f_{n+m},f_m)=gcd(f_{n-1}f_{m}+f_{n}f_{m+1},f_m)$

然后观察到我们有 $f_{m+1}$ 和 $f_m$ 是互质的,所以就可以解决了

$=gcd(f_{n},f_m)$

也就是说我们可以让第一个的下指标减去第二个的

根据欧拉定理显然就有 $gcd(f_n,f_m)=gcd(f_{d},f_d)$ ,就证明完了

然后我们还有一个没有证明的式子 $n|m,f_n|f_m$

考虑两个数的gcd,一定是n吧,然后我们又有f_n,f_m的gcd为f_n,然后就证完了...

然后我们又有一个lcm的显然的式子

$lcm S=\frac{\prod S}{gcd S}$

但是他不对,因为这个式子没有考虑多个数的时候,一个数就能让gcd变为1,但是根据lcm是所有质因子的指数取max定义来说,肯定不对啊/汗

所以是

$lcm S=\prod_{T\subset S,T != \empty}gcd(T)^{-1^{|T|+1}}$

考虑gcd相当于最小值,而我们要求的是最大值,所以就是一个类似于minmax容斥的形式,但是因为都要乘起来所以是这样子

然胡

lcm S=\prod_{T\subset S,T != \empty}f_{gcd(T)}^{(-1)^{|T|+1}}

还是不行,我们最好枚举这个gcd,但是这个又是一车连乘号和一个集合gcd.....,所以考虑莫反一下

$f_n=\prod_{d|n}g_d$

$lcmf_S=\prod_{T \subset S,T!=\empty}(\prod_{d|gcd(T)}g_d)^{|-1|^{|T|+1}}$

这个式子把下面放上去就好了

lcmf_S=\prod_{d}g_d^{\sum_{T \subset S,T!=\empty,d|T}|-1|^{|T|+1}}

$d|T$ 是d整除T中每一个元素的意思!

然后我们又有一步神仙转换,考虑这个容斥系数的实际含义,就是对于所有被整除的集合,他都会只会被算一次,也就是说,如果存在一个集合整除他,他就会被算一次

额,怎么发现可能只能打表了....qaq

进而

lcmf_S=\prod_{\exist a \in S,d|S}g_d

于是我们就可以照着这个式子,在值域上随便 $n\ln n$ 求解了

最后我们 $g_n$ 的算法是经典反演技巧,就是只保留第n项

6104. 「2017 山东二轮集训 Day2」第二题

这个有点神奇啊

不懂世事的我点开了第一篇题解

天哪,O(m)...

又是一个被贪心搞过去的题啊

考虑贪心咋做啊

首先我们有这样的贪心决策,从左向右考虑,对于这一行只保留最高的非0点,然后我们删除的时候,考虑优先做删掉两个的决策,然后到边界时候我们再去删掉一个

但是这样会萎掉,反例:(最高的非0点)

3,6

这个时候你发现我们会选择后面那个点操作3次更优秀,而不这样做我们会选择第一个操作两次,然后第二个操作两次

所以说我们要想个办法,把这一次修改的影响留到下一次,下一次可以替换操作

对应的就是,我们这一次操作还是照常进行,但是说,如果下一个位置能够用两次反过来的操作替换这一次正着的操作就替换

更具体的,我们一旦有一个正着的L,那么我们就给后面加势,使得后面位置有机会把正着的L变成两个倒着的L,而只花费额外1的代价

但是这样还是不行,反例

3,6,6

只需要5次

问题出在我们前两个柱子太贪心了,用了3次,但是没能最小化第三根柱子

解决这个问题我们可以考虑把这个从i-1位置向后伸的柱子改为i向前伸之后,再改为i+1向前伸,然后我们就能相对而言减少代价

你仔细想会发现这个东西是肯定可以的,因为后面的这个一定是只考虑充满部分,而前面也是一样,那么我们就会发现,只需要将之前的操作移动过来就好了....

但是这个代价又需要多算一遍,也就是说我们移动一次操作代价就会多算一遍,但是高度也会递增啊,所以每次会让高度增长一倍

就是说,我们考虑实际的决策有哪些情况

选择一些高度为2的铺下去,然后让下一个得到这个高度为2的
选择一个高度为1的,然后让下一个得到这个高度为2的,显然只需要偶数个
调整从上一列过来的高度为1的信息,对于一个高度为1的,可以变成两个高度为2的,然后向左伸,保证左边一行信息正确,这样我们花费1的代价使高度增加了3,注意这是在之前的方案上修改得到的结果
调整从上一列过来的高度为2向前伸展的信息,对于一个向前凑齐2的操作,他的形态一定是在第i列操作两次向前,就是类似于2,4的形态的操作,我们可以变成2,4,6,而只用多出两次操作,也就是说我们可以花费1的代价,使得高度增加3,同时能够多出两倍这样的操作类型

实现起来不是很困难,考虑记录这个位置能够有多少个3,4替换操作即可

    for (int i = 1; i <= m; i++) {
        chemx(h[i], 0);
        int t1 = min(a[i], h[i] / 3), t2, t3;
        // printf("%d\n", h[i]);
        h[i] -= t1 * 3;
        t2 = h[i] >> 1, t3 = h[i] & 1;
        h[i + 1] -= t2 + t3 * 2;
        a[i + 1] = t1 * 2 + t2;
        res += t1 + t2 + t3;
        // printf("%d %d %d %d %d %d\n", i, a[i], h[i], t1, t2, t3);
    }
答案就是res

6109. 「2017 山东二轮集训 Day4」增添

这我真找不到题解,但是这么简单一题有啥难的啊?

考虑只有2,3操作怎么做

建立可持久化线段树,然后一个区间推平的信息就记录在对应节点上,表示这个节点的信息和某个节点的信息应该完全相同,下传标记的时候同步递归即可

被随手插了/ll,这个东西首先是假的

因为如果我们带的区间也有信息,这样下传标记的时候还需要查询带标记的那个点是什么

于是我们就要不断的这样递归下去,复杂度就是 $O(n^2)$ 的了/ll

那么一个很好的做法就是考虑可持久化平衡树

因为这样的树支持将某个区间复制一遍然后粘到对应的区间上去

具体就是直接复制建立新版本,然后因为我们实现复制需要可持久化所以是可持久化平衡树

然后操作1直接实现一个标记永久化就好了,注意两个操作的兼容问题,就是推平的时候要把标记永久化信息挂到 $[l,l+t]$ 区间上

看了看题解使用这个帯修改标记的写法,这样的写法每次都要新建点,但是也是可以的吧?

可能相对而言更好些,因为我们不需要再重新给这个区间上标记了

6108. 「2017 山东二轮集训 Day3」第三题

咋做啊/kk

考虑二分答案吧

然后我们怎么判定呢??

每次找到一条最短路,然后考虑我们怎么通过所有人走最短路完成这个事情

应该是 $(dis+T-1)$ 的时间内完成所有人

出发顺序就是1第1s出发,然后2第2s出发,这样会尽可能的霸占整条道路

然后我们仔细思考发现可以通过更换下一条最短路从而减少许多时间!

再思考一下,我们更换最短路如果和之前的边有重边会怎么样?

首先那条重复的边一定在这两条路径上都处于同一位序,要不然就不是最短路了

那么他们就一定会导致走到其中那条边的时候,类似于一个长度为k的队伍一样,这一条边通过的人要有向后次序

所以就导致这个次短路还不好找啊

所以我们仔细想这个很像网络流的过程,可以走网络流

费用流!

冷静思考一下对于两次得到的路径咋分配过了多少人啊QAQ

再冷静思考一下我们是不是二分答案了啊....

所以这个就是二分到的 $dis+T-1=sum,T=sum-dis+1$ 这么多人吧

然后如果能保证在图没有增广完毕的情况下走光了所有人就是合法的

于是本题就做完了

6112. 「2017 山东二轮集训 Day5」分裂

最小化所有划分中最大子串

有个很显然的 $n^2$ 做法给每一个子串标号,然后 $f_{i,j}$ 表示前i个子串划分成j段的最大标号最小是什么

转移枚举第j段的转移,设 $cmax(i,j)$ 表示 $S_{i,j}$ 中最大子串编号,然后就是

$f_{i,j}=min(max(f_{k,j-1},cmax(k,i)))$

这个东西显然是凸的,就是在某个时间之前前面取到最大,某个时间后面取到最大,只需要找到这样的决策点即可

然后这样的决策点单调不减就做完了qwq

再去考虑变为 $polylog$

.....不太会了,感觉上不太能动态规划

一看题解全是sbsa/cy

然后开始跳题了/ll不会做啊

6115. 「2017 山东二轮集训 Day6」汇合

求最近公共祖先

看了下题解感觉不是,但是我也无语

再一交,不太对,空间限制4m?

卧槽.....lxl转世?这个链两个9e5的数组都开不下

打开第一篇题解...卧槽被震撼了

怎么做呢?

观察这个数据范围,考虑树分块

我们将整个树分为 $O(\sqrt n)$ 块

对于一次查询,如果他们不在同一块内就暴力跳到同一块,否则就小的向父亲跳直到跳到一起

如果能够保证每个连通块高度不超过 $\sqrt n$ 就可以做到 $O(m\sqrt n)$ 公共祖先

然后我们要意识到不能保证这个性质

所以我们随机设根

$rand$ x个位置,钦定他们为根,将树划分为 $n+1$ 个连通块

然后就做完了....但是为什么能过要抿一下

首先,我们尽可能让连通块数多一点,减少单个连通块过高的情况

然后...我们要实现一个严格n的空间的树分块

我们需要知道一个点属于那个块,以及这个点的具体哪个父亲

可以考虑压位 ,我们分4095块,这样用掉12位

然后剩下的二十位我们存储父亲是什么点即可

然后查询的时候不在一块内就跳到块的父亲处,然后不断跳下去

6118. 「2017 山东二轮集训 Day7」鬼牌

答案用期望的线性性,等于每种牌成为炸弹的概率乘上每种牌的期望成功次数

这个概率是 $siz/p$ 猜一猜就有了

然后期望操作次数可以考虑dp

$f_i$ 表示大小为i的牌成功的期望次数

然后转移向i+1和i-1转移,注意这个二元组顺序是定的所以不能随便乘法原理

分A选中它B选中它等4中情况分类讨论即可

这里有个很坑的地方是我们转移到 $f_0$ 是没有意义的,因为我们是知道这个牌必胜的!所以我们 $f_1$ 不能转移到 $f_0$

写完之后会发现这个应该是个三元矩阵高斯消元,可以 $O(n)$ 但是牌的个数实在太多了,也就是我们的瓶颈所在

翻一翻之前做过的题,我了个亲娘哎是2000的数据范围(((

等一等我一看啊,原来是最大牌数只有1e5的数据范围

但是好像这个还是1e9总牌数啊/ll

题解有很迷的东西,这个好像是模拟调和级数,但是据题解区说这个锅了

看了某位大佬的题解觉得很神啊

首先怎么说明这个概率是 $sz/p$ 啊

考虑 $f_0=0,f_n=1$

然后 $f_i=1/2(f_{i-1}+f_{i+1})$ 就是这个数减少或者增多的概率是一样的

$f_{i+1}=2f_i-f_{i-1}$

然后就是神仙操作

我们不需要递推,而是直接求解方程,因为我们只需要知道 $f_1$

这个就是假设 $f_0=x$ ,然后 $f_i=kx+b$ 递推即可,最后由 $f_n$ 求出

挂个博客

关于代码里的式子不一样

你考虑最后枚举n-j是什么

然后发现分子能提出一个i-1,然后分子有一个n,就做完了

谢谢EI哥哥教育我/ll/ll 我脑子真的瓦特了

#include<bits/stdc++.h>
using namespace std;
#define ldb double

const ldb C = 0.577215664901532860606512090082402431042159335;

ldb f[1000010];
int num[100010], n, m;

inline int rd() {
	int x = 0; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar());
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	return x;
}

inline ldb calc(int n) {
	return (n <= 1000000) ? f[n] : log(n) + C;
}

int main() {
	m = rd(); n = rd();
	for (int i = 1; i <= n; i++) num[i] = rd();
	for (int i = 1; i <= min(m, 1000000); i++)
		f[i] = f[i - 1] + (ldb)1.0 / i;
	ldb ans = 0;
	for (int i = 1; i <= n; i++)
		ans += (ldb)num[i] / m * (m - 1) * (m - 1) -
			   (ldb)(m - 1) * ((ldb)(num[i] - 1) -
							   (ldb)(m - num[i]) * (calc(m - 1) - calc(m - num[i])));
	printf("%.10lf\n", ans);
	return 0;
}

6119. 「2017 山东二轮集训 Day7」国王

考虑 $n^2$ 我们可以不枚举编号连续的某一段,而是考虑以树上的每一个点做根dfs,然后从这些点出发,找到所有满足条件的路径,然后把这些路径挂到区间上,就是这一段路径末尾编号和开头编号形成的区间右端点上.

然后再去枚举区间,对于一段区间,我们加入所有在这个编号连续区间内的ex路径,然后删除掉那些右端点在区间内左端点在区间外的路径即可.

考虑怎么加速这两部分,我们是加速枚举区间还是加速枚举所有路径啊/kk

瞄一眼题解,他写了点分治

考虑点分治,我们能够知道对于一个端点有多少个另一个端点是满足条件的

但是如果说我们对于一条路径,只在大编号处统计他的话,就是完全可以的....但是说这样我们就好二维数点了?

不太对啊,再想想办法

考虑这个编号连续的固定右端点的r区间如果合法,那一定存在一个极小的合法子区间,也就是说对于一个固定r,左端点向左移动是单调更优的!

而我们知道这个信息可以怎么办啊?

注意到有一个事实,就是一个点出发的所有exciting路径数是能统计得到,然后如果我们圈出的区间中所有出发的边数总和超过路径总数就一定可以的(因为我们实际上每个路径算了两遍啊)

然后你会发现我们可以推出一个式子

$sum_l+2sum_{lr}+sum_r=2S$

$sum_l>sum_r$

实际上只需要 $sum_l+sum_{lr}>S$

因为这样一定 $sum_r$ 小于S

然后我们每一个 $sum_{lr}$ 是配对区间外又有一个的

也就是说我们根本不用管!

....那么区间的sum只需要大于一半就好了

6130. 「2017 山东三轮集训 Day1」Fable

一看题解震撼了啊/ll

k轮排序之后,任意区间 $[i,i+k]$ 的最小值会被放到位置i上...

然后从1到n一路干过去,保留上一侧没有放的数

如果区间不完整就右端点和n取min

神仙啊!

首先思考冒泡排序的过程,我们其实就相当于每次把一个大数向后放,然后其他小的数都只能向前挪一步

也就是说,不管怎么排序,我们k轮之后,都只能让至多 $i+k$ 位置上的数到i上!

这也就是为什么这样写了!我们前面的数过来没有任何限制,但是这个位置只能有后至多i+k位置的数向前移动得到啊!

#include <cstdio>
#include <queue>

const int MAXN = 200000;

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    std::priority_queue<int, std::vector<int>, std::greater<int>> q;

    for (int l = 1, r = 0; l <= n; l++) {
        for (; r < l + k && r < n; r++) {
            int x;
            scanf("%d", &x);
            q.push(x);
        }

        printf("%d\n", q.top());
        q.pop();
    }
}

夏晓光(loveJY)的博客