0103abc 的网站

（标题有含义） 比较困难的题，考察了大量点双的性质 考虑对于一个点双连通分量，其具有下面的性质： 无割点。 任意两个点 $a,b$ 均可存在一条简单路径连通。 递进于上一条，任意两个点 $a,b$ 都存在两条简单路径，使得这两条路径除了 $a,b$ 两个点以外其余点两两不相同。 对于任意两个点...

狗屎题。下面提供一个在原有时空限制（$\textbf{2s}\ /\ \textbf{500MB}$）下能通过的算法。 首先因为图是网格图，所以容易想到设 $f{i,j}$ 为从 $(1,1)$ 开始向下走到 $(i,j)$ 所需要的最小边权，转移容易。若此时无删除操作，则答案即为...

感觉这场题质量很高的说，但是 unr 了（ 考虑对于三个数 $x,y,z$，若其满足 $x\le y\le z<2x$，且现在需要组合这三个点，则此时组合 $(x,y),(y,z)$ 一定不会比组合 $(x,y),(x,z)$ 差。 因此这个题就做完了。对于每一个 $i$ 枚举其 $j$...

007. Hyperspace Highways 简单的。图为 semi-仙人掌，即把仙人掌中的环变为了连通子图。但是做法仍然是相似的。还是建立圆方树，这里把一个连通子图建立一个方点作为辅助，然后该子图中所有的点向这个方点连一条边权为 $1$ 的边，两个圆点之间连边权为 $2$ 的边。...

006. [COCI 2007/2008 #1] STAZA 题意是说给定一个仙人掌，求从 $1$ 号点到任意一个点 $x$ 的路径，使得其满足路径上没有重复的边的条件下，路径上边的数目最多。 很复杂，但是仍然可以看作【模板】仙人掌 dp（但是自己独立完成了，开心 考虑套路的建立狭义圆方树，然后考虑...

考虑什么时候图合法。很显然，当且仅当图有且仅有一个环构成时图合法。更确切的说，一个图合法当且仅当： 将所有的单向边扩展为双向边后图连通。 图中任意一个点 $u$ 的入度为 $1$。 因此首先特判掉图已经合法的情况，剩下的情况图是一个基环森林...

Sol $1$. 用 $O(\log n)$ 次询问计算答案。 首先肯定要询问一下 $0$，此时可以求得 $x+y$ 的值。然后对于每一个二进制位 $i$ 询问 $2^i$ 的值。此时设回答的值为 $o$，则： 若 $x+y=o$，则此时 $x,y$ 二进制第 $i$ 位都没有改变，那么 $x,y$...

好久没写题解了（ 很显然，一条连接 $(x1,y1)$ 和 $(x2,y2)$ 点的线段在平面直角坐标系上可以先把 $(x1,y1)$ 点平移到 $(0,0)$，那么就是考虑一条 $(0,0)$ 到 $(x,y)$ 的线段上是否没有其他的整点。 此时令 $d=\gcd(x,y)$，则： 若...

直接硬嗯是困难的，因此考虑正难则反计算有多少组不合法的方案数，然后用总方案数减去之。总方案数是容易计算的，显然就是 $10^n$。 考虑 dp 计算出不合法方案数。看到 $x+y+z\le 17$ 想到状压。设 $f_{i,j}$ 表示当前考虑了前 $i$ 个数，以第 $i$...

容易观察到若以聚会点 $x0$ 为自变量，$x0$ 所对应的所需时间 $y_0$ 为因变量，则该函数为没有连续相同值的单峰函数。因此考虑对答案三分，对于每一个三分到的值直接暴力 $O(n)$ 求解所需花费的时间即可。时间复杂度为 $O(n\log n)$ 可以通过。