题目大意

定义函数 $f(x)$:给定 $f(1),f(2)$,当 $i > 2,f(i) = af(i - 2) + bf(i - 1) $ 。
现给定一个长度为 $n$ 的序列 $x_i$,一共有 $q$ 次操作。每次操作子序列 $[l,r]$,对于每个 $x_i(l \le i \le r)$, 增加 $f(i-l+1)$。求最终序列。
$(1 \le n, q \le 10^5, 1 \le f(1),f(2),a,b \le 10^9,0 \le x_i \le 10^9)$

阅读全文 »

题目大意

给定一个 $N$ 个点,$M$ 条边的有向图。现将选择 $4$ 个不同的点进行顺序访问(从第 $1$ 个点出发,在第 $4$ 个点结束),并满足点与点之间的最短路距离之和最大。输出符合条件的任意 $4$ 个点。注意可多次经过同一个点。
$(4 \le n \le 3000, 3 \le m \le 5000)$

阅读全文 »

题目大意

背景:曹操和袁绍在官渡决战。
现有 $N$ 个村庄, $M$ 个战场。对于村庄 $i$ ,曹操可以挑选一些人去给定的 $x_i$ 战场充军(曹操军队),每挑选一个人需要花费 $c_i$ 元。由于村子的人惧怕袁绍的报复,所以村庄会送相同数量的人去给定的 $y_i$ 战场充军(袁绍军队)。
每个战场都有一个重要性 $w_i$。为了保证曹操的胜利,重要性为 $2$ 的战场曹操军队士兵数量要严格多于袁绍,重要性为 $1$ 的战场曹操军队士兵数量不能少于袁绍,重要性为 $0$ 的战场则无所谓。一开始双方都没有军队,问为保证胜利,曹操需要花费的最小费用。无解输出 $-1$。
$(1 \leq N, M \leq 10^5,1 \leq x_i, y_i \leq 10^5,0 \leq c_i \leq 10^5,w_i \in {0, 1, 2})$ 时限 $3s$。

阅读全文 »

题目大意

给定一个 $N \times M$ 的矩阵 $A$ 和数字 $k$。你有一个零矩阵 $B$,每次可以将矩阵 $B$ 中任意两个相邻元素(上下或左右)同时加 $1$,可以任意操作多次,但元素最大值不能超过 $k$。
求以下表达式的最小值: $$S = \sum_{i-1}^{N}\sum_{j-1}^{M}(A_{ij} - B_{ij})^{2} $$
$(1 \leq N, M, K \leq 9 )$ 时限 $1s$。

阅读全文 »

题目大意

给定长度为 $N$ 的字符串 $A$ 和长度为 $M$ 的字符串 $B$。每次从左往右看,如果发现 $A$ 作为 $B$ 的 $substring$ 出现,那么在 $B$ 中删除 $A$。对新的字符串递归进行此操作。求最大删除次数。
$( N \leq 256, M \leq 512000)$

阅读全文 »

二分搜索法,是通过不断缩小解可能存在的范围,从而求得问题最优解的方法。在程序设计竞赛特别是ACM中,经常可以见到二分搜索法和其他算法结合的题目。

本文主要总结了二分的几种常用写法。

阅读全文 »

题目大意

给出一个 $n$ 个点 $m$ 条边的无向图 $G$,每次你可以选择一些边,从图中删掉。要求选出来的边构成的子图的每个连通块最多只有一个环。 问最少需要删几次才能把所有边都删掉。

$(1 \leq n \leq 2000, 0 \leq m \leq 2000)$

阅读全文 »