「CF623E」 Transforming Sequence
没想到非 Chinese Round 也会出这么毒瘤的题目......题目大意：对于正整数序列 $A$，定义序列 $B$： $B_1=A_1,B_i=B_{i-1}\ or\ A_i,i\in[2,n]B $ 其中 or 为位或运算。 每一个序列合法，满足对于$ \forall i\in[1,n]$，有 $A_i\in[1,2^k])$ 而且对于 $\forall i\in[2,n]$，有$...
没想到非 Chinese Round 也会出这么毒瘤的题目......题目大意：对于正整数序列 $A$，定义序列 $B$： $B_1=A_1,B_i=B_{i-1}\ or\ A_i,i\in[2,n]B $ 其中 or 为位或运算。 每一个序列合法，满足对于$ \forall i\in[1,n]$，有 $A_i\in[1,2^k])$ 而且对于 $\forall i\in[2,n]$，有$...
题目链接题解首先我们尝试把不能被车经过的边删掉，得到了一张新图。这个新图上每一个连通块的答案都相同。 所以 Dijkstra 是首先要跑的。然后我们发现如果可以离线的话我们可以把边和询问放在一起排序，用普通的并查集维护一下每个连通块到 $1$ 节点的最短距离就可以了。 但是这题目要求强制在线怎么办？我们可以使用可持久化并查集来维护这个东西。 可持久化并查集用可持久化线段树来实现，非常简单。代...
题目链接题目大意是对于每种物品被划分到不同的组里会产生不同的贡献，求一种最大的划分（这里的划分是连续一段划分到一起），并且要动态维护这个东西。我们首先考虑静态如何做这个东西，显然我们可以设出一个极为暴力的状态：$f(l,r,i,j)$ 表示燃料 $[l,r]$ 使用区间 $[i,j]$ 内的工作状态能得到的最大价值，直接 $O(4^3)$ 枚举中间点暴力转移一下就可以了。但是我们还要支持插入...
<h2>题目描述</h2>题目链接某天，Lostmonkey 发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置，每个装置设定初始弹力系数 $k_i$，当绵羊达到第 $i$ 个装置时，它会往后弹 $k_i$ 步，达到第 $i+k_i$ 个装置，若不存在第 $i+k_i$...
题目链接题目描述给定 $n$ 个点 $m$ 条边的连通点权无向图。 有 $q$ 个操作，要么修改一个点的点权，要么询问两点间经过一条从 $s$ 到 $t$ 的简单路径，路径上最小点权最小值是多少。 $ n,m,q \leq 10^5 $.题解问的是所有可能路径上的最小点权的最小值，那我们来考虑一下路径的性质。 首先我们可以发现，如果将这个图分成几个点双联通分量的话，路径一定是经过了从 $s$...