乱听课记录

关于树的分治问题&杂题选讲 张哲宇

边分治

（边分不是很鸡肋吗）

例题一

题目大意：给出两颗有正负边权的树，求出两个点\(u,v​\)使得两棵树中\((u,v)​\)距离的和最大。\(n \le 10^5​\).

点分治

例题二

题目大意：\(n\)个点的树，每个点有非负点权，求权值第\(k\)大的联通块。\(n,k \le 10^5\).

考虑点分治，对于每一个分治中心，进行的点分相当于多了一个“强制选该分治中心”的限制。

对于每一层的分治，我们dfs重标号，那么对于第\(i​\)个点有两种决策：选点\(i​\)，那就继续考虑dfs序为\(i+1​\)点的决策；不选点\(i​\)，则跳到dfs序为\(i​\)子树的后一个点。如上的转化相当于把一个连通块转化成了一条路径，因此第\(k​\)大连通块问题就变成了经典\(k​\)短路问题（但是并不清楚在每层分治都做这个\(k​\)短路的复杂度是怎样的）

例题三（例题一）

题目大意：参见例题一

突然，掉线。

听说点分做法“实质上”就是边分。

例题四

题目大意：给出\(n\)个点的有根树，每个节点上有一个一次多项式，求每个节点到根的多项式乘积的和。\(n \le 10^5\).

大致就是在一层层的点分中心上跳，感觉可能类似codechef Yet Another Tree Problem

全局平衡二叉树

zzy的全局平衡二叉树讲跟没讲一个样。

还是去看tls写的吧基于变换合并的树上动态DP的链分治算法和全局平衡二叉树学习笔记

例题五（例题四）

（这个用全局平衡二叉树怎么做？）

All Last

题目大意：给出一颗\(n​\)个点的有根树，\(q​\)次询问距离点\(p​\)距离\(\le d​\)且不在路径\(u-v​\)上的点权\(\max​\).\(n,q \le 10^5​\).

例题六

题目大意：一颗有根树，每个节点有二维坐标\((x,y)\)。动态加入一个叶子\(v\)，并询问\(v\)到根路径上，与\(v\)的\(dis \in [l,r]\)的所有节点形成的凸包与斜率为\(k\)的直线的切点。

怎么突然放b站鬼畜了？？？计算鸭海星

推销Marp

FJWC2019选讲

杂题一

题目大意：要求\(O(1)\)回答是否存在\(n\)个点允许有重边不能有自环且弱连通的流网络，满足流量平衡且流量为\(1\)的边有\(a\)条，流量为\(2\)的边有\(b\)条，不存在其他流量的边。\(n \ge 2\).

标算：分类讨论

杂题二

打表题，zzy直接跳了。

杂题三

题目大意：初始有一个根，强制在线加叶子，要求每次加叶子之后输出当前树的权值。定义一颗树的权值为交换两颗互不为祖先的子树后的最大直径。\(n \le 5\times10^5\).

mine：处理根的子树深度最大、次大、第三大的深度，每次把第三大的子树嫁接给次大的最后一个节点。

上面这个做法有点小问题，因为嫁接的第三大子树不一定要是根的直接子树，所以选择的应当是一个“三叉戟”的形态，使得选取的边数最多。

杂题四

题目大意：构造一个恰有\(k\)条直径的边权非负的树，使用点数\(\le 5000\)，\(k\le 5000000\).

先从若干个菊花相接的情形开始考虑。

杂题五

题目大意：有一颗\(n\)个点的树，每次可以删除一个度数在\([L,R]\)之间的点然后得到\(a_i\)的贡献，要求最大化贡献之和。

dp

杂题六

有\(10^4\)个栈，栈顶元素是\(s_i\)，要求和spj玩游戏：选手每次选择一个数\(x\)，spj返回一个操作$\le / \ge \(，并把所有满足\)s_i \text{ opt } x\(的栈顶元素弹出并返回新的\)s_i$。要求在\(50\)次内清空所有栈。

一种显然的想法是每次取中位数，但是这个做法非常容易卡。问题出在剩余元素不同的栈应当赋不同的优先值。

（然后我也不知道怎么就）对于大小为\(x\)的栈构造指数权函数\(w(x)=p^x\)，操作次数近似\(\frac{\ln(n\times p^k)}{\ln \frac{2p}{p+1}}\)。取\(p=4\)时最大操作次数为\(49\).

杂题七

题目来源：#2392. 「JOISC 2017 Day 1」烟花棒

这个题去年讲过的呀，怎么又搬出来讲……

等等我怎么还没做掉。

杂题八

题目大意：\(n\)个点，\(m\)条边的无向图，每个点有权值\(a_i\)，求一条\(1\)到\(n\)的路径，最小化路径权值从大到小排序后的字典序。\(n \le 10^5,m \le 5\times 10^5\).

排序之后字典序最小相当于比较权值的桶的字典序大小。

杂题九

（zzy说题目有点难。于是看完题直接跳了）

杂题十

题目大意：给定一个点仙人掌，边权为\(1\)，求最短路长度为\(i\)的点对个数。

树的情况应该是个经典点分FFT问题。

这里是缩点点分；然后对于点分中心为环的情况，再分治处理？

1/2杂题选讲 高嘉煊Samjia

Incremental Double Free Strings

题目大意：给出整数\(n\)满足\(1\le n\le 26\)，定义一个长度为\(n(n+1)\over 2\)的字符串是合法的，当且仅当满足以下三个条件：

1. 所有字符都是小写字符

2. 不存在两个相邻相同字符

3. 对\(i=1\cdots n\)，总存在一个字符\(c\)在串中出现了\(i\)次

给出\(n,k\)，求所有合法字符串中字典序第\(k\)小的。\(k \le 10^{18}\).

CHEFKC

题目大意：求带权有向图的第\(k\)小割。\(n \le 77,m,k\le 777\)

题目来源：Chef and Cut

依旧是k短路题，考虑一个状态\((i,p[])\)表示考虑前\(i\)个数，每个数在\(S\)集合内或\(T\)集合内的割大小。那么从初始状态\((0,[])\)开始拓展。

好像有一种比讲课人更优的做法。

以上这个做法每次拓展的步长为1，那么不仅时间效率低，空间开销也有相当多是不必要的。

考虑从每一个完整状态开始A*。首先不做任何限制，仅仅跑一趟最小割，然后以这个最小割的状态作为初始状态。对于每一次对最优状态\(\text{ sta }\)转移调整到\(\text{ nxt }\)，枚举一个\(len\)表示\(\text{ nxt }\)前\(len\)位完全固定，然后从\(\text{ sta }\)中继承前\(len-1\)位并将\(len\)取反。这个转移是为了确保不重不漏，且按照权值顺序经过所有状态。

这可能是算是一个A*的处理技巧吧，但是不一定通用。有些时候从完整状态为保证按权值顺序经过所有状态可能比较困难。

这里是写的题解：【A* 网络流】codechef Chef and Cut

Spoonerisms

题目大意：给出\(n​\)个字符串，要求选出其中四个记为\(A,B,C,D​\)，使得存在非空的字符串\(p,q,r,s​\)满足\(A=pq,B=rs,C=rq,D=ps​\)，其中\(r\not= p,q\not= s​\)。\(\sum |S | \le 500000​\).

（听说标算锅了？然后zzq神仙提供了\(O(n\sqrt n)\)的“标算”）

问题转为求四元环，但是复杂度是\(O(n\sqrt n)​\)的。

cf1146H Satanic Panic

题目来源：H. Satanic Panic

dp+计算几何

Chopping hands

水题选讲 钟子谦

Complete The Graph

题目来源：cf Round #372 1b 加强

题目大意：有一张\(n​\)个点\(m​\)条边的简单正权无向图，\(S​\)到\(T​\)的最短路为\(L​\)，现在有一些边的边权未知，请输出任意一种方案。\(n,m\le 500000​\).

对于每一条边权未定的边，把它的边权先设为1。然后考虑首先处理出\(dist_i\)表示在如上初始化的情况下，\(T\)到\(i\)的最短路距离。之后再从\(S\)开始做dij，设\(S\)到\(u\)的最短路为\(len_i\)，那么当前若以\(u\)增广一条边权未定的边\((u,v)\)，就将其边权设为\(\max\{1,L-len_u-dist_v\}\)。以上构造能够保证问题的完全转化。

更详细的可以看我题解【图论 思维】cf715B. Complete The Graph加强

One Third

题目来源：AGC032F

喂鸽子

题目来源：集训队作业2019加强

题目大意：有\(n\)只鸽子，每次等概率选取一只鸽子喂一粒玉米。每一只鸽子只有喂了\(k\)粒玉米才会饱。问\(n\)只鸽子都被喂饱的期望步数。

感觉好经典啊。然而不会

Mergesort Strikes Back

题目来源：Avito Cool Challenge 2018 cf1081G. Mergesort Strikes Back

Traffic Blights WF2019

题目来源：ICPC World Final 2019

Mouse

题目来源：Info(1) Cup 2019

题目大意：交互库有一个\(1,2,\cdots n\)的排列\({p_i}\)，每次可以询问一个排列\({q_n}\)，交互库会返回相同的位置个数。要求还原\({p_n}\).\(n \le 256\)，询问次数\(\le 2400\).

考虑首先随机一个完全不同于原排列的排列\(p_i\)，再从这个排列开始“试探”。

不清楚复杂度证明。

Keep clicking,keep flipping

题目来源：IPSC2011

考虑贪心并证明。

构造题选讲 杨帆

cf720c

题目大意：有一个\(n\times m\)的网格，求构造一个四连通块（每个格子通过四个方向的边连通），使其中大小为3的\(L\)形（可旋转）数目恰好为\(k\)，\(n\times m \le 10^5\)。

mine：考虑矩形\(a\times b\)，那么有\(4(a-1)(b-1)\)个合法的\(L\)形。我们找一个合法\(L\)形数量接近\(k\)的矩形：对于一个角元素，它有3的贡献；对于一个边元素，它有6的贡献，这样就解决了模4下的0,1,2,3的合法性。

cf453c

cf819e

题目大意：一张\(n\)个点的完全图，要求找到若干个三、四元环，覆盖每条边恰好\(2\)次。\(n\le 300\)

分奇偶讨论，考虑从\(n=3\)和\(n=4\)的情形加点。

cf933e

题目大意：有一个长度为\(n\)的序列，每次可以选择相邻两个数\(a,b\)将其同时减去\(\max\{a,b\}\).求操作到无法操作的最小代价。\(n \le 10^5\)

构造一个\(b_i\)表示\(i\)这个位置减去的代价。思维构造题。

cf317e

题目大意：有一无穷大的网格图，还有点\(A,B\)和一些障碍。每次可以选择一个方向，对于\(A,B\)如果该方向没有障碍则向这个方向移动一步。目标是使\(A,B\)重合，要求步数\(\le 10^6\).障碍不超过\(400\)个，坐标绝对值\(\le 100\)。

首先考虑障碍为1的情况，则将\(A\)靠在障碍上，再将\(B\)移到和\(A\)的同一直线上，接下去再将\(A,B\)靠拢即可。

mine：如果\(A,B\)不连通则无解；如果\(A,B\)都与无穷远处连通，那么就把\(A,B\)都移出来，再用边界障碍做障碍=1的情形；如果\(A,B\)被封闭在一个障碍块里，那么因为障碍块的最大面积是\(100\times 100\)，就随机\(10^4\)次，每次走\(10^2\)步。

std：找到\(A\)与\(B\)的最短路，并将\(A\)沿着这条路径移动。如果\(A,B\)之间的距离缩短那么重复这个过程。当不能操作时，那么就找一个边界上的障碍来做障碍=1的情况即可。

cf gym 100162e

好像是大力分类讨论？

cf804e

（怎么跳了啊）

cf1053e

杂题选讲 毛一琛

序列

题目大意：长度为\(n\)的序列\(A\)，求长度为\(n\)的排列\(B\)满足\(\min \{|A_{B_i}-A_{B_{i-1}}|\}\)最大，\(n \le 10^5,A_i \le 10^9\)

当\(n\)为偶数时，有上界\(\min\limits _{i=1}^{n\over 2}\{a_{i+{n\over 2}}-a_i\}\)。

买置换

题目来源：2014集训队互测

（bzoj怎么没数据啊）

打怪兽

贪心&dp&结论

BBQ加强

题目来源：AGC001E加强

考虑组合数意义，相当于是一个矩形的两个对点路径的方案数。

注意到这里所求的组合数意义的路径必定经过直线\(y=-x\)，那么就\(f[i][j]\)表示第三象限所有点走到

Rational-Sums

题目来源：hackerrank Ad Infinitum18

这是推式子的数学题吧。

似乎还要一些观察和多项式的性质。

Permanent

题目来源：cf468e

构造二分图。（接下去没懂）

Addition without carry

二进制给出长度为\(n​\)的数组\(a​\)，求一个长度同样为\(n​\)的数组\(b​\)满足：

1. \(b_i \ge a_i\)
2. \(b_1|b_2|\cdots b_n=\sum b_i\)

要求最小化\(\sum b_i\)，\(n \le 3\times 10^5,\sum|a_i| \le 3\times 10^5,\max\{|a_i|\} \le 3\times 10^5\).

题目来源：cf gym102154a

第二条件等价于\(b_i\)上的1互不重叠。

考虑如何暴力：贪心地从高到低位确定\(b_i​\)，首先假设若第\(i​\)位为0，那么使\(1\cdots i-1​\)位为1检查是否合法。

有趣的游戏

题目来源：51nod 1599

凑数题

题目大意：有一个\(n\)个点的竞赛图，其中\(k\)条边的方向已经确定，剩下边的方向等概率随机。求最小环的期望个数。\(n \le 5000\).

最小环一定是三元环。\(O(n^2)​\).

座位空了好多

水题选讲 不知名大爷

Rikka with an unnamed temple

Square Subsequences

题目大意：给定长度为\(n\)的字符串\(S\)，求最长的"平方子序列"(一个字符串被称为"平方串"是它可以被表示为\(AA\)的形式)。\(|S|\le 3000\).

枚举一个断点\(len\)，求\(S(1\cdots len)\)和\(S(len+1\cdots |S|)\)的最长公共子序列的长度。

然后标算是把求最长公共子序列的dp给压位，复杂度\(O({n^3\over{6w}})​\)……

Forests Fires

题目来源：cf1086f

芒果冰加了空气

题目来源：北大集训d1t3

题目大意：给出一颗\(n\)个点的树，每次点分随机选取连通块内一个点作为下一层点分中心。求带标号点分树种类数。

mine：首先会自然想到一种naive的递归子问题划分，但是容易发现

\(f[i][j]​\)表示对\(i​\)的子树点分，并且\(i​\)在点分树中的深度为\(j​\)的方案数。

\(f'[x][i]=\sum_{j=1}^i\sum_{k=i-j}^{size[y]} f[x][j]*f[y][k]* {i-1\choose j-1}\)

tree

题目大意：给出\(n\)个点的树，每条边有\(int\)范围内的边权，\(q\)次修改更改路径\((u,v)\)上的边权为\(w\)，并询问离\(1\)最远的点的距离。

动态点分？全局平衡二叉树？

Rikka with Data Structures

题目大意：要求维护操作

1. 区间加
2. 区间赋值
3. 区间询问\([L,R]\)内以\(x\)为左端点，最大值在左/右端点的区间个数。

类似楼房重建。

Epic Convolution

题目来源：cf1054h

二维fft

Diameter

题目大意：求\(n\)个点有标号直径为\(0,\cdots n-1\)的无根树方案数。\(n \le 500\).

很类似烷烃计数啊。

problem

题目大意：求\(n!\text{ mod } p\)，\(0 \le n < p \le 10^{12}\)。

【翻译向】阶乘模大质数

problem2

题目大意：自然数倒数和。\(n\le 10^{12}​\).

problem3

组合数 行求和。

Cutting Squares

题目来源：PE270

先dp跑出较小解，再观察发现性质。

powerful number 在求积性函数前缀和中的应用

powerful number：每一个质因数的次数都大于等于2的数。

求积性函数前缀：\(\sum f(i)\)，如果存在积性函数\(g(i)\)满足对于任意质数\(p\)有\(f(p)=g(p)\)，那么(据说)可以利用powerful number的性质快速求\(\sum f(i)\).

并没有理解。