2018国庆雅礼集训

7/7

Day1

T1.养花

题目大意

给你一个长度为\(n\)的序列\(a_i\), 要求支持查询\([l_i,r_i]\)这个区间内的元素在膜\(k_i\)意义下的最大值

\(n \le 10^5, k_i \le 10^5, a_i \le 10^5\)

题解

\(20pts\) : 直接\(n \cdot q\)模拟就好了

\(40pts\) : 上一档分加上\(k \le 300\)的, 这种情况直接把询问搞出来然后对于每个\(k\)用线段树维护

复杂度\(O(k \cdot n + qlogn)\)

\(60pts\) : 对于\(k \le 300\)的暴力搞一搞, 对于大于\(k \ge 300\)的情况每次询问跳\(\frac{n}{k}\)次, 每一次用主席树查询一下前驱(貌似可以查前驱) , 复杂度\(O(300 \cdot n + q \cdot \frac{n}{300} \cdot logn)\), 假装它可以过\(5 \times 10^4\)

\(100pts:\) 考虑分块, 对于每一次查询膜\(k\)意义下的最大值, 相当于在若干个形如\([b \cdot k, b \cdot k + k)\)的区间内查询最大值

这样对于每一个块我们可以在\(O(n + nlogn)\)的时间内求出对于任意一个\(k\)的答案, 具体的 :

对于一个块内的元素, 我们把它丢在值域为\([0, 10^5]\)的数轴上, 对于任意一个\(k\)求最大值就是求 \[ max \{f[b \cdot k - 1] - (b - 1) \cdot k \ \ | \ \ b \cdot k \le 10^5 \} \] \(f[i]\)表示在数轴上小于\(i\)的并且离\(i\)最近的存在的数

这样的话, 我们设块的大小为\(B\), 那么总时间复杂度为 : \[ O(\frac{n}{B} \cdot (n + nlogn) + q \cdot (B + \frac{n}{B})) \] 因为\(q\)\(n\)同阶, 可以写成

\[ O(\frac{n}{B} \cdot (n + nlogn) + n \cdot (B + \frac{n}{B})) \]

化简得 : \[ O(\frac {2 \cdot n^2 + n^2logn}{B} + n \cdot B) \] 由均值不等式得 : \[ B = \sqrt{2 \cdot n + nlogn} \] 时最优, 最优复杂度为 : \[ O(n \cdot \sqrt{2 \cdot n + nlogn}) \] 由于常数很小并且开了\(O2\), 所以实际测评跑得飞快, 但实际上数据强度也不大, 以至于理论复杂度为\(O(\frac{n}{k} \cdot \sqrt{n} \cdot logn \cdot q)\)垃圾分块尽然能过????

实则是出题人没有精心构造数据

代码

Click Here

T2.折射

题目大意

给你\(n\)个点\((x_i,y_i)\),要求求出有多少不同的集合满足, 按照纵坐标从大到小的顺序加入集合并且满足

\[ \forall i, j \ \ y_i \ne y_j \\ \forall i \in (2, k], x_{j - 2} < x_j < x_{j - 1} \ \ or \ \ x_{j - 1} < x_j < x_{j - 2} \]

题解

关于部分分 : 除了那一档卡空间的以外, 并不知到其他的部分分存在的意义是什么, 很迷

考虑\(dp\), 首先我们要考虑一个问题, 我们要按照横坐标排序来转移, 因为按照纵坐标排序转移的话\(x\)有一个上界一个下界, 没办法优化, 所以按照横坐标排序

考虑设计状态\(f_{i,0/1}\)表示, 以第\(i\)个点为起始点的折线是往左下折或者往右下折的方案数

有转移如下 : \[ 1. \forall j \in [1, i), f_{j,1} \to f_{i,0} \vert \ \ y_j > y_i \\ 2. \forall j,k \in [1, i), f_{j,1} \to f_{i,0} \to f_{k,1} \vert\ \ y_j > y_k \ \ and \ \ x_j < x_k \] 上述式子说起来太抽象了, 不妨看一下这张图 :

第二种情况直接用前缀和转移一下就好了, 注意枚举顺序, 第二层\(j\)应该倒着枚举

复杂度\(O(n^2)\)

代码

Click Here

T3.作画

题目大意

给你一个\(r \times c\)\(01\)矩阵, 初始矩阵里都是\(0\)(代表白色, 反之代表黑色), 给定你一个目标状态, 问你最少需要多少步才能将初始状态转移到目标状态, 具体的每一步你可以将一个颜色相同的四联通块变成另一种颜色

题解

首先我们得知道一个结论, 将一个颜色相同的联通块的周围与其颜色不相同的联通块全部染成一种颜色, 总比将其其中一部分染色要优

知道这结论之后, 题目大概就做完了, 我们挑选一个初始联通块, 对于这种情况的答案就是这个矩阵被分为了多少黑白相间的块, 再次转化一下模型, 我们将颜色不同的块连上边权为\(1\)的边, 相同的连上边权为\(0\)的边, 然后枚举一下起点跑一下最短路就好了

注意到, 边权只有\(0\)或者\(1\), 那么直接\(01\)最短路就好了, \(01\)最短路的复杂度为\(O(V)\), \(V\)为点数

最终复杂度为\(O(n^4)\)

代码

Click Here

Day2

T1.施工

题目大意

你有一排建筑, 原高度为\(h_i\), 你可以将任意建筑升高任意高度, 设修改后的高度序列为\(b_i\)

求如下式子的最小值 \[ \sum_{i = 2} ^ {i \le n} (b_i - h_i)^2 + c \cdot |bi - b_{i - 1}| \]

题解

\(10pts\) : 直接\(O(n \cdot h^2)\)\(dp\)即可

\(30pts\) : 用堆维护一个升高一个高度最小差值, 复杂度\(O(\sum h \cdot logn)\)

\(53pts\) : 考虑\(f_i\)表示第\(i\)个建筑没有修改的最小花费

对于一次\(j \to i\)的转移, 我们只用考虑将\((j, i)\)这个开区间内的建筑都修改到相同高度\(t\)的最小花费

因为, 如果不相同我们将最高的那个降低一个高度一定不会更劣, 其次假如存在一种情况不是将这个区间内的建筑都修改到同一个高度, 并且比这个情况更优, 其中一定会有没有修改的, 会在\(k \to i\)的转移中考虑到

那么, 对于将这个区间中的建筑修改到同一高度\(t\)的花费是 \[ \sum_{k = j + 1} ^ {k < i} (t - h_i)^2 + c \cdot (h_j + h_i - 2 \cdot t) \] 将式子展开, 发现它是一个关于\(t\)的二次函数, 所以求一下对称轴就可以\(O(1)\)转移了

总复杂度\(O(n^2)\)

\(100pts\): 我们注意到任意一次合法的转移一定满足\(max\{h_k | k \in (j, i)\} \le min(h_i, h_j)\)

如果不满足的话, 这种情况一定没有把这个区间从中间最高的建筑拆成两段来考虑更优

所以我们维护一个关于高度的单调队列, 对于一个\(i\), 如果可以转移\(k\)次, 那么它会弹掉队尾的后\(k\)个元素

所以\(转移次数 = 队列中的元素总数\), 又因为每个建筑都只会入一次队列, 所以总转移次数是\(O(n)\)

总复杂度为\(O(n)\)

代码

Click Here

T2.蔬菜

题目大意

给定一个\(n \times m\)的矩阵, 有\(q\)次询问

对于一次询问, 要求输出询问的这个子矩阵中不同的数的出现次数的平方的和

题解

二维莫队版子题

复杂度\(O(?)\) (其实我也不会证复杂度)

代码

Click Here

T3.联盟

题目大意

给定一颗边权为\(1\)的树, 你可以任意删除一条边, 然后链接一条边(边权也为\(1\)), 要求求出重新连边后的树的直径的最小值, 并且输出所有可能删掉的边, 和一种删边连边的方案

题解

\(20pts:\) 枚举一条要删的边, 枚举两个要连接的点对, 然后\(O(n)\)求直径, 复杂度\(O(n^4)\)

\(60pts:\) 枚举一条要删的边, 然后原树变为两棵树记为\(T_1, T_2\), 分别求出他们的直径\(d_1, d_2\), 手玩可知最优合并后的直径最小值一定是\(max\{d_1, d_2, \lceil \frac{d_1}{2} \rceil + \lceil \frac{d_2}{2} \rceil + 1\}\)

\(100pts\) : 我们知道关于求直径有一种\(dp\)的做法, 延续这个思路, 求直径我们对于每个点记录它的子树当中的最长链和次长链, 这样向上转移的时候很方便, 但是从上向下转移就不太好做了, 我们考虑一种更通用的做法, 记录一下每个点的子树中最长链的两个端点, 每次合并两条链就枚举一下是哪两个端点组合在一起比较优, 合并是\(O(logn)\)的, 因为要求\(LCA\)

考虑删掉一条边后, 整个树会被分成两个子树, 如图我们删掉\(8\)号节点和其父亲所连的边 :

我们把整个树分成\(4\)个部分来考虑

  • 关于\(T2, T4\)我们维护一个关于每个点的子树的前缀最优答案, 和后缀最优答案
  • 关于\(T3\)就是我们\(dp\)预处理出来的东西
  • 最后关于\(T1\)我们直接在递归的时候合并一下当前节点的前缀答案, 后缀答案和当前已经处理出来的\(T1\)

总复杂度\(O(nlogn)\)

代码

Click Here

Day3

T1.u

题目大意

给定一个\(n \times n\)的矩阵\(A\), 有\(m\)次操作

每次将一个左上角坐标为\((x, y)\), 边长为\(L\)的三角形区域内的元素加上\(s\)

题解

\(1pts:\) 人口普查, 前提是交了程序

\(20pts:\) \(n^3\)暴力即可

$100pts : $ 直接高维差分 或者线段树维

高维差分不会

线段树的话直接维护每一列, 和每个斜线的差分值, 线段树区间加即可

复杂度\(O(qlogn + n^2logn)\)

代码

Click Here

T2.v

题目大意

\(n\)个球排成一列, 每个球的颜色只为黑或白, 有\(k\)次操作

对与第\(i\)次操作我们从区间\([1, n - i + 1]\)中等概率随机选择一个数\(x\)

你可以从左往右删除第\(i\)个, 或者从右往左删除第\(i\)个, 之后该球所有右侧的球的编号减1

给定每个球的颜色, 希望最大化移除的白球的数量

输出在最优策略下,期望的移除的白球的数量

题解 :

\(2pts:\)人口普查

\(22pts:\) \(n \le 5\), 暴搜所有情况

$75pts : $ 考虑状压\(dp\), 由于正着推不好做, 我们用记忆化搜索代替, 用一个数表示一个序列的状态, 然后按照最优策略搜就好了, 因为最后有很多重复的状态, 拿个\(map\)记录一下, 由于最后状态有很多重复的, 所以并跑不满, 但是由于空间问题, 最后会 \(MLE\)

\(100pts:\)我们知道\(map\)中的每一个元素其实是一个\(pair\), 这样其实很耗费空间而且\(map\)还自带一个\(log\), 我们考虑当序列长度小于等于\(24\)的时候直接开个数组存一下, 然后剩余的拿一个\(map\)存, 然后就卡过了

关于状态数的上界其实是\(\sum_{i = 0}^{n} min\{2^i, C_n^i\}\)

代码

Click Here

T3.w

题目大意

有一棵 \(n\) 个节点的树,每条边长度为\(1\),颜色为黑或白。 可以执行若干次如下操作:选择一条简单路径,反转路径上所有边的颜色。 对于某些边,要求在操作结束时为某一种颜色。 给定每条边的初始颜色,求最小操作数,以及满足操作数最小时,最小的操作路径长度和。

题解

\(13pts:\)保证对于所有的边均不是没有要求的边, 考虑一个显然的结论, 我们操作的任意一条链, 不会包括任意一条不需要修改的边, 因为如果包括对于操作次数一定不会更优, 并且会让操作路径长度变劣, 最后一棵树被不需要修改的边分成了几个联通块

然后我们发现对于一个边全部都要修改的联通块, 这个问题其实就是一个一笔画问题, 然后直接统计每个联通块中奇数度数的点整除\(2\)的和

复杂度\(O(n)\)

\(31pts:\) \(n \le 20\), 因为存在没有要求的边, 所以问题变得棘手了起来, 我们直接考虑枚举每一条没有要求的边到底是修改还是不修改, 然后剩下的按照上述作法做就可以了

复杂度\(O(n \cdot 2^n)\)

\(56pts:\)保证没有要求的边的个数不超过十, 直接暴力枚举一下就好了

复杂度\(O(n \cdot 2^{10})\)

\(100pts:\)我们考虑\(dp\), 设\(f_{i,0/1}\)表示第\(i\)个节点和它父亲节点之间的边是否翻转时\(i\)的子树中的最少奇数度数的点的个数和最短操作路径长度, 然后在\(dp\)时维护一个\(f0, f1\)表示, 当前节点的度数为偶数时的最优解, 为奇数时的最优解, 然后转移一下就好了

代码

Click Here

Day4

T1.x

题目大意

给定一个长度为\(n\)的正整数序列\(\{a_i\}\)

将这个序列成两个非空集合\(S, T\), 使得\(gcd(\prod_{i \in S}a_i, \prod_{i \in T}a_i) = 1\)

求划分方案数, 对\(10^9 + 7\)取膜

题解

\(20pts:\) \(O(2^n)\)枚举一下就好了

\(50pts:\) 直接暴力枚举一个点对\((a_i, a_j)\), 如果\(gcd(a_i, a_j) \ne 1\), 就把这两个数丢到一个集合里

最后答案就是\(2^{集合的个数} - 2\)

\(100pts:\) 考虑到两个数的最大公因数如果不为一, 说明这两个数一定有公共素因数, 所以最后的集合的个数一定小于等于\(\pi (值域)\)

那么直接暴力枚举每个数的素因子就好了

代码

Click Here

T2.y

题目大意

给定一个无向图,\(n\) 个点(从\(1\)开始编号), \(m\)条边(长度为\(1\)),每条边有一个权值 \(c\)(\(c \in \{0, 1\}\))。一条路径,可以表示为一个长度为经过边数的 \(01\) 串,串的第\(i\)位为经过的第\(i\)条边的权值。 两条路径相同,当且仅当表示其的\(01\)串相同。 求从\(1\)号点出发,长度为\(d\)的路径种数。

题解

\(20pts:\) \(n \le 30, d \le 4\), 直接暴搜就好了

\(60pts:\) \(n \le 70, d \le 13\)

做法一 :

考虑剪枝一下我们的暴搜

我们从低位向高位建一颗\(trie\)树, 考虑我们当前搜到的串为\(S\), 如果\(S\)\(trie\)树上代表的的节点的子树是满的, 就表示前缀为\(S\)的串不可能再对答案有贡献, 直接剪掉就好了

这种方法在随机图上跑得飞快, 但是如果\(01\)边权分布的不均匀就会被卡

做法二 :

考虑\(dp\), 设\(f_{i,L,S}\)表示从\(i\)点出发经过的串的长度为\(L\), 边集为\(S\), 可以到达的点的点集

然后直接暴力枚举一下集合中的点, 转移一下就好了

复杂度\(O(n^3 \cdot 2^d)\), 然后这个可以用\(bitset\)维护一下, 复杂度可以在除以一个\(64\)

\(100pts\): \(n \le 90, d \le 20\)

我们考虑优化一下上面的\(dp\), 发现这个东西其实可以\(meet \ \ in \ \ middle\)一下, 可以把复杂度开个根号, 然后就过了

复杂度\(O(2^d \cdot n + n^3 \cdot 2^{\frac{d}{2}})\)

代码

Click Here

T3.z

题目大意

在数轴上有一个线段,左端点在 \(0\),长度为 \(l\)。 现在需要按顺序完成 \(n\) 个任务,第 \(i\) 个任务可以用 \(x_i\) 表示:当线段接触到点 \(x_i\) 时,视为完成任务,也就是 \(x_i\) 在线段某一端点上, 或两端点之间。 你可以任意平移线段,求依次完成任务所需要的最短的平移总距离。 \(q\)次询问,每次给出一个\(l\)

题解

\(30pts:\) \(n \le 10^3, q \le 10^3\)

暴力模拟即可, 复杂度\(O(nq)\)

\(45pts:\)\(n \le 10^5, q \le 10^5\), 保证\(x_i\), 单调

二分一下一开始不移动时覆盖的任务的位置

然后因为是单调的, 只可能一直向左或者一直向右, 直接加上端点的距离当前点的距离就好了

复杂度\(O(qlogn)\)

\(65pts: n \le 10^5, q \le 10^5, i \in [1, n), |x_i| < |x_{i+1}|, x_i \cdot x_{i+1} < 0\)

同样一开始二分一下, 因为绝对值单调, 并且保证相邻的两个任务一正一负

设起始覆盖了的任务的个数为\(o\)

所以答案就是\(( \sum_{i = o + 1}^{n} |x_i - x_{i - 1}|) - (n - o) \cdot L_i\)

\(100pts:\) 并不会咕咕咕

代码

并没有写

Day5

T1.联

题目大意

有一个无限长的\(01\)序列, 初始全部为\(0\), 每次选择一个区间\([l, r]\)进行操作, 有三种操作 :

  • \(1 \ l \ r\), 将\([l, r]\)内的元素都变成\(1\)
  • \(2 \ l \ r\), 将\([l, r]\)内的元素都变成\(0\)
  • \(3 \ l \ r\), 将\([l, r]\)内的元素都异或\(1\)

每次操作后询问该序列最左边的\(0\)在哪个位置

题解

$20pts : $ \(max(r) \le 10^3, m \le 10^3\)

直接暴力模拟即可, 复杂度\(O(nm)\)

$45pts : $ \(max(r) \le 10^5, m \le 10^5\)

直接普通线段树, 复杂度\(O(nlogn)\)

$100pts : $ \(max(r) \le 10^{18}, m \le 10^5\)

做法一 :

离散一下所有询问的区间端点, 把\(l - 1, l, r, r + 1\)四个点都丢到线段树上

时间复杂度\(O(nlogn)\), 空间复杂度\(O(n)\)

做法二 :

动态开点线段树, 直接暴力插入, 然后每次动态开点

一开始我对于每个线段树上的节点维护了\(5\)个东西, 左右儿子的编号, 是否需要对区间异或, 赋值标记, 和这个区间中一的个数

发现这一共有\(3\)\(int\), \(1\)\(bool\), \(1\)\(long long\), 发现数组开不下啊

大概要开\(360MB\)

$PS : $ 在随机数据下大约要开\(1.8 \cdot 10^7\)个线段树节点

然后开始卡空间, 发现复制标记只有\(-1, 0, 1\), 把它开成\(char\), 发现我们并不关心这个区间内到底有多少个一, 只关心这个区间内有没有一和有没有被一填满, 所以它也可以开成\(char\)

然后这样的话, 空间就只需要\(188MB\)了, 成功卡了进去

代码

Click Here

T2.赛

题目大意

\(n\) 个物品,第 \(i\) 个物品的价格是 \(v_i\) ,有两个人,每个人都喜欢 \(n\) 个物品中的一些物 品。 要求选出正好 \(m\) 个物品,满足选出的物品中至少有 \(k\) 个物品被第一个人喜欢,\(k\) 个物 品被第二个人喜欢。并求出最小的价格和。

题解

\(20pts : n \le 20\)

直接暴力枚举每个物品选还是不选

复杂度\(O(2^n)\)

\(50pts : n \le 2 \cdot 10^5\), 保证没有一件物品同时被两个人喜欢

把每个人喜欢的物品集合都按权值\(sort\)一下, 然后分别选\(k\)个, 把第一个人喜欢的和第二个人喜欢的但没有选的物品和两个人都不喜欢的物品放在一起再次按权值\(sort\)一下, 把不够的物品选出来就好了

复杂度\(O(nlogn)\)

\(100pts : n \le 2 \cdot 10^5\), 没有任何限制

按照\(50pts\)的思路, 我们可以想到把物品分成四个集合, 二个人都喜欢的\(S_0\), 第一个人喜欢的\(S_1\), 第二个人喜欢的\(S_2\), 和两个人都不喜欢的\(S_3\)

然后枚举一下在\(S_0\)里选出的物品的个数, 知道了这个后, 我们可以确定要在\(S_1\)\(S_2\)当中应该选多少个

然后再从剩余没选的里面按照权值从小到大选出不够的

这个时候我们需要一个数据结构去维护一下这个东西, 显然值域线段树是一个很好的选择, 当我们从\(S_0\)当中的选的物品增加一个我们就动态的在线段树上删掉从\(S_0\)当中选出来的元素, 再动态的将\(S_1\)\(S_2\)当中永远不可能选到的加入线段树, 每次如果选出的元素不足\(m\)个, 就在线段树上选前几个将其补足就好了

\(PS: S_3\)当中的所有元素一开始就在值域线段树上

复杂度\(O(nlogn)\)

代码

Click Here

T3.题

题目大意

一开始有 \(n\) 个苹果,\(m\) 个人依次来吃苹果,第\(i\)个人会尝试吃\(u_i\)或\(v_i\)号苹果,具体 来说分三种情况。

  • 两个苹果都还在,那么这个人将随便选一个苹果吃了。
  • 只有一个苹果,那么这个人将吃掉这个苹果。
  • 都不在了,这个人吃不到苹果就走了。

请问有多少对苹果 \((i, j)(i < j)\)满足它们两个都幸存下来的概率 \(>0\)。

题解

不会部分分

考虑\(f_{i}(S)\)表示处理完前\(i\)个人, 集合\(S\)中的苹果全部存在的概率是否可能大于一

有以下转移

  • \(f_{i}(S) = 0, u_i, v_i \in S\)
  • \(f_{i}(S) = f_{i - 1}(S \cup \{v_i\} ), u_i \in S\)
  • \(f_{i}(S) = f_{i - 1}(S \cup \{u_i\}), v_i \in S\)
  • \(f_{i}(S) = f_{i - 1}{S}, v_i, u_i \not\in S\)

但是正着好像不太好推,发现最后剩下的集合越小,我们可以贪心一下, 只考虑最后只剩下一个的情况

设\(g_i\)表示最后只剩下\(i\)这个苹果我们从一开始需要保留的苹果的集合

直接按照前面所说的原则顺着向前推就好了

  • \(g_{i - 1} = g_i \cup \{u_i\}, v_i \in g_i\)
  • \(g_{i - 1} = g_i \cup \{v_{i}\}, u_i \in g_i\)

如果两个都属于\(g_i\), 那么表示\(i\)最终是不可能存活的

如果两个都不属于, 就不管

感性的理解一下:

如果某一个苹果\(j\)被纳入了集合, 就说留下\(i\)的代价是在此时此刻\(j\)需要为\(i\)牺牲, 并且只能在这个时刻牺牲

所以如果之后又需要\(j\)来为其牺牲, 那么这就是不成立的

所以最后直接枚举一下点对, 如果\(g_i \cap g_j = \varnothing\), 答案加一

因为一个苹果只能为一个苹果牺牲, 不可能同时为两个苹果牺牲

代码

Click Here

Day6

T1.Merchant

题目大意

有\(n\)个物品,第i个物品有两个属性\(k_i,b_i ,\)表示它在时刻\(x\)的价值为\(k_i \times x + b_i .\) 当前处于时刻\(0\),你可以选择不超过\(m\)个物品,使得存在某个整数时刻\(t, t \ge 0,\)你选择的 所有物品的总价值大于等于\(S\). 给出\(S\),求\(t\)的最小值。

题解

\(22pts: n \le 20\)

\(O(2^n)\)枚举

\(78pts: n \le 10^5\)

考虑二分一个\(t\), 求出每个物品在此时的价值, \(sort\)一下, 将前\(m\)个中大于\(0\)的选出来, 看和是否大于\(S\)

复杂度\(O(nlog^2n)\)

\(100pts : n \le 10^6\)

我们其实可以不用\(sort\), 直接用\(nth_element\), 可以在\(O(n)\)的复杂度内将前\(m\)个选出来

复杂度\(O(nlogn)\)

最后我们考虑一下二分的正确性, 我们分情况讨论一下

  • 如果直线的斜率都小于零, 这个是单调的, 可以二分
  • 如果存在直线的斜率大于零, 说明在时间大于某个值\(t_0\)后, 函数一定是单调递增的, 但考虑到在\(t_0\)之前有可能是单调递减的, 所以我们只用贪心的\(check\)一下\(0\)这个位置, 如果不成立, 那么它也是满足二分的单调性的

代码

Click Here

T2.Equation

题目大意

有一棵\(n\)个点的以\(1\)为根的树, 以及\(n\)个整数变量\(x_i\) 。树上\(i\)的父亲是\(f_i\) ,每条边\((i, f_i )\)有一个权值\(w_i\) ,表示一个方程\(x_i + x_{f_i} = w_i\) ,这\(n − 1\)个方程构成了一个方程组。 现在给出\(q\)个操作,有两种类型:

  • \(1 u  v  s,\)表示询问加上\(x_u + x_v = s\)这个方程后,整个方程组的解的情况。具体来说, 如果方程有唯一解,输出此时\(x_1\) 的值;如果有无限多个解,输出\(inf\);如果无解,输 出none. 注意每个询问是独立的.
  • \(2  u  w,\)表示将\(w_u\) 修改为\(w.\)

题解

\(3pts : q = 0\)人口普查

\(21pts : n \le 2\) 就两个点, 随便搞一下

\(86pts : n \le 10^5, q \le 10^5\)

我们手玩一下可以发现, 每个点的权值\(x_i\)都可以用\(x_1\)表示, 然后我们设\(1\)号节点的深度为\(1\)可以得到

\[ x_i = \sum_{j}w_j[LCA(i, j) = j][deep_j \&1 = t] - \sum_jw_j[LCA(i, j) = j][deep_j \&1 \ne t] (+ w_1) or (- w_1) \]

\(t = deep_i \& 1\)

这个就相当于每次查一下该点到根节点的路径上的边权和

然后暴力树链剖分维护一下就好了

复杂度\(O(nlog^2n)\)

\(100pts : n \le 10^6, q \le 10 ^ 6\)

正解, 好像是用树状数组维护一个差分值吧

复杂度是\(O(nlogn)\)的

但是我觉得卡一下常数, \(O(nlog^2n)\)还是能卡进去的

代码

Click Here

T3.Rectangle

题目大意

平面上有\(n\)个点,第\(i\)个点的坐标为\(X_i , Y_i\) 。对于其中的一个非空点集\(S\),定义\(f(S)\)为一个 最小矩形,满足:

  • 覆盖\(S\)中所有的点(在边界上也算覆盖);
  • 边与坐标轴平行。 求所有不同的\(f(S)\)的面积和对\(10^9 + 7\)取模的结果。两个矩形被认为是不同的,当且仅当 它们顶点坐标不同。

题解

\(13pts : n \le 18\) 暴力枚举一下点集

\(47 pts : n \le 300\)

考虑两个点, 并且用这两个点作为左边界, 和右边界

然后在枚举一个点以其作为下边界边界, 然后用树状数组维护一下这个下边界上有多少个点, 和他们点的纵坐标的和

复杂度\(O(n^3log(max\{X_i, Y_i\}))\)

\(100pts : n \le 10^4\)

设\(m = max\{X_i, Y_i\}\)

考虑优化一下上面那个过程, 随着\(n\)的增大, 我们考虑直接枚举左右边界的坐标\(x_0, x_1\)

考虑一个合法的矩阵, 那么它的上边界至下边界中一定要存在一个点在\(x = x_0\)上, 存在一个点在\(x = x_1\)上,

我们直接枚举一个在\(x = x_0\)上的点\(a\), 一个在\(x = x_1\)上的点\(b\), 并且使得\(y \in [min(y_a, y_b), max(y_a, y_b)]\)这个区间内没有点在$ x = x_0$ 或 $ x = x_1$上

然后发现纵坐标坐标大于等于\(max(y_a, y_b)\)并且横坐标属于\(x_0, x_1\)的点可以和任意纵坐标小于等于\(min(y_a, y_b)\)并且横坐标属于 \(x_0, x_1\)的点构成合法的矩形, 但是如果直接这样算会算重复, 如图所示 :

每次我们只用计算\(P1\)区域和\(P2\)区域的点组成的不同的上下边界, 这样可以很好的避免算重复

然后拿一个\(BIT\)维护一下就好了

总复杂度\(O(nmlogm)\)

代码

Click Here

Day7

T1.Reverse

题目大意

小\(G\)有一个长度为\(n\)的\(01\)串\(T\) ,其中只有\(T_S = 1,\)其余位置都是\(0\)。现在小\(G\)可以进行若干 次以下操作:

  • 选择一个长度为\(K\)的连续子串(\(K\)是给定的常数),翻转这个子串。

对于每个\(i, i \in [1, n],\)小\(G\)想知道最少要进行多少次操作使得\(T_i = 1\). 特别的,有\(m\)个“禁止位置”,你需要保证在操作过程中\(1\)始终不在任何一个禁止位置上。

题解

$46pts : $这个东西相当于, 对于每一个点向一段区间内的任意一点都连上边, 最后直接\(01BFS\)

由于边的个数可能是\(O(n^2)\)的, 最终复杂度\(O(n^2)\)

$100pts : $ 考虑到是向一个区间内的所有点连边, 这个可以用线段树来优化一下建图, 把一段区间在线段树上只会被分成\(logn\)个区间, 最终总复杂度为\(O(nlogn)\)

代码

Click Here