Solutions

题意 给一段程序： int qsort(int L, int R) { if (L >= R) return 0; int i = L, j = R; int x = Random.Next(); int x0 = A[x]; assert(L <= x && x <= R); while (i < j) { while (A[i] < …

Jayun 发布于 2023-11-01 07:20:17

00

题意 给定两个人的树上博弈规则。小 N 初始时在节点 $S$ ，小 Y 需要通过一些操作“强迫”小 N 最后到达节点 $T$ 。小 N 想要让小 Y 的操作尽量多，而小 Y 希望自己的操作尽量少。求解两人都采取最优决策时，小 Y 的操作次数。 每一轮中操作如下： 小 Y 可选的操作有：恢复一条小 N 删除的边 ；或者删除一条边；或者跳过这次操作（不计入答案）。 小 N 接下来执行：如果 …

Jayun 发布于 2023-10-31 21:21:25

00

题目描述 要求在平面直角坐标系下维护两个操作： 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$ 。 给定一个数 $k$ ，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。 强制在线。 题解 李超树板题。在点上维护线段。 代码 const int N = 100005; const int mod = 39989; const double …

Jayun 发布于 2023-10-31 15:59:30

00

Escape Through Leaf 题面 有一颗 $n$ 个节点的树（节点从 $1$ 到 $n$ 依次编号），根节点为 $1$ 。每个节点有两个权值，第 $i$ 个节点的权值为 $a_i,b_i$ 。 你可以从一个节点跳到它的子树内任意一个节点上。从节点 $x$ 跳到节点 $y$ 一次的花费为 $a_x\times b_y$ 。跳跃多次走过一条路径的总费用为每次跳 …

Jayun 发布于 2023-10-31 15:51:30

00

题面 法阵由从左至右 $n$ 道魔力屏障组成，每道屏障有一个临界值 $a_i$ ，如果它承受攻击的魔力值 $>a_i$ ，屏障将会破碎，它所承受的魔力攻击将在魔力值减半后（向下取整）继续向右移动，否则该攻击会被该屏障完全拦截，停留在屏障前，屏障的临界值不会减少。当两次攻击相遇时，两次攻击会叠加形成新的攻击，新的攻击的魔力值为两次攻击魔力值之和，新的攻击会继续向右移动。小 Z 可以在法 …

Jayun 发布于 2023-10-31 14:12:43

00

题意 在线进行 $n$ 个操作： 把向量 $(x,y)$ 插入到平面内； 给一个向量 $(x,y)$ ，问平面内第 $l$ 个到第 $r$ 个向量之间中的一个向量与该向量的点积最大值。 $n\leq 3\times10^5$ 。 口胡 挺酷炫的。考虑到查询操作的 $x,y$ 相当于给了个直线斜率。那么解肯定在 $[l,r]$ 的凸包上，那么线段树每个点维护一个凸包（ …

Jayun 发布于 2023-10-31 11:55:53

00

题解 这里用了 WQS 二分，二分队列做法。 const int N = 5e5 + 5; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c …

Jayun 发布于 2023-10-30 22:01:54

00

题意 一棵 $n$ 个节点的树，第 $i$ 个点值为 $a_i$ 。 $q$ 次操作，每次操作要么单点修改；要么给出 $k$ 个数，查询这 $k$ 个点中任意两点的简单路径上的所有点的点值总和。 $n,q\leq10^5,\sum k\leq10^6$ 口胡 询问先按 dfs 序排序，然后从第 1 个点往后合并（统计到 lca 的答案）。树剖维护。 然后看答案验证发现错了。 …

Jayun 发布于 2023-10-30 19:59:19

00

口胡 设 $f_{i,j}$ 表示 $i$ 是第 $j$ 个邮局，有 $$f_{i,j}=\min_{k<i,g\text{二分得到}}\left\{f_{k,j-1}+\sum_{h=k+1}^{g-1}(a_h-a_k)+\sum_{h=g}^{i-1}(a_i-a_h)\right\} $$ 后面那一串满足四边形不等式。

Jayun 发布于 2023-10-30 19:16:33

00

题意 $n$ 个数，每个数 $a_i$ ，选 $k$ 个数，一个选取方案的值是异或和。求所有选取方案值的和。 $n\leq10^5,a_i<2^{31}$ 。 题解 加法和异或本质相同。 考虑每一位的贡献，简单组合计数。 代码 const int N = 3e5 + 5, mod = 998244353; inline ll Read() { ll x = 0, f = 1; …

Jayun 发布于 2023-10-30 19:02:53

00