也许是这几天以来最毒瘤的一场比赛

naive 的瓶子

题目描述

众所周知，小 naive 有 $n$ 个瓶子，它们在桌子上排成一排。第 $i$ 个瓶子的颜色为 $c_i$，每个瓶子都有灵性，每次操作可以选择两个相邻的瓶子，消耗他们颜色的数值乘积的代价将其中一个瓶子的颜色变成另一个瓶子的颜色。

现在 naive 要让所以瓶子的颜色都一样，操作次数不限，但要使得操作的总代价最小。

输入输出

输入文件为 colour.in。
一个测试点内多组数据。
第一行，一个正整数 $T$，表示数据组数。

每组数据内：
第一行一个整数 $n$，为瓶子的个数。
第二行共 $n$ 个整数，第 $i$ 个整数为第 $i$ 个瓶子的颜色 $c_i$。

输出文件为 colour.out。
共 $T $行，每行一个整数，为最小的总代价。

思路

不多说，直接 $O(n^3)$ 大力 DP，看代码。

代码

naive 的图

题目描述

众所周知，小 naive 有一张 $n$ 个点，$m$ 条边的带权无向图。第 $i$ 个点的颜色为 $c_i$。$d(s, t)$ 表示从点 $s$ 到点 $t$ 的权值最小的路径的权值，一条路径的权值定义为路径上权值最大的边的权值。

求所有满足 $u < v, |c_u − c_v| ≥ L$ 的点对 $(u, v)$ 的 $d(u, v)$ 之和。

输入输出

输入文件为 graph.in。
第一行，三个整数 $n, m, L$，表示点数，边数和参数 $L$。
第二行，$n$ 个整数，第 $i$ 个数为第 $i$ 个点的颜色 $c_i$。接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，描述了一条边。

输出文件为 graph.out。
共一行，一个整数，表示答案。

思路

可以发现原图的 $d(s, t)$ 等于最小生成树上的 $d(s, t)$，只有在最小生成树上的边才有贡献。我们按照长度递增将边加入生成树中，此时以这条边端点为根的两颗子树之间路径的权值就是这条边的长度。可以发现 $\sum \min(size(left \ child_i), size(right \ child_i)) = O(n\log_2 n)$，所以我们直接枚举更小的子树中的每个点，在另一个子树中询问满足题目要求的点的个数。发现这是个经典的双重限制查询，主席树可以很方便地解决这个问题。

代码

naive 的游戏

题目描述

众所周知，小 naive 有一个游戏。游戏地图是一个无限的一维数轴，游戏的目标是从起点s 到终点 t，除了起点其他每个点上都有小怪。有 n 条线段，每条线段上的相邻点之间有桥相连。

他有两种操作：

1. 走到相邻的有桥相连的点上，因为上面有小怪，所以要消耗 1 的代价；
2. 使用技能跳一跳，跳到距离为 L 的点上，由于把该点上的小怪踩死了，所以不消耗代价。

这个游戏有两种模式，简单和困难。

简单模式：任意点都为可停留点。
困难模式：只有在线段上出现过的点为可停留点，不可停留点不可到达。

现求从起点到终点所消耗的最小代价。

输入输出

输入文件为 game.in。
一个测试点内多组数据。
第一行，一个正整数 $T$，表示数据组数。
每组数据内：
第一行，五个整数 $type, n, L, s, t$，分别表示游戏模式，线段数，跳一跳的距离，起点坐标和终点坐标。$type = 0$ 表示为简单模式，$type = 1$ 表示为困难模式。
接下来 $n$ 行，每行两个正整数 $l_i, r_i$，表示线段 $[l_i, r_i]$。

输出文件为 game.out。
共 $T$ 行，每行为该组数据的答案。若不可达输出 $−1$。

思路

本题只适合口胡。

type = 0
把模 $L$ 意义下相同的点缩成一个点，那么就成了一个环。时间复杂度为 $O(nlog^2n)$。

type = 1
把模 $L$ 意义下相同的并且可达的点缩成一个点。有一个显然的结论，只有包含起点或终点或某条线段的端点的点在途中是具有决策意义的，也就是只保留这些点在图中即可。这样点数是 O(n) 的，边数也可以优化至 $O(n)$，跑最短路即可。

代码不放。整整 15k，好像没人愿意写，显然也包括我自己。