[JSOI2016]飞机调度


JSOI 王国里有 $N$ 个机场,编号为 $1$ 到 $N$。从 $i$ 号机场到 $j$ 号机场需要飞行 $T_{i,j}$ 的时间。由于风向,地理位置和航空管制的因素,$T_{i,j}$ 和 $T_{j,i}$ 并不一定相同。 此外,由于飞机降落之后需要例行维修和加油。当一架飞机降落 $k$ 号机场时,需要花费 $P_k$​​ 的维护时间才能再次起飞。 JS Airways 一共运营 $M$ 条航线,其中第 $i$ 条直飞航线需要在 $D_i$ 时刻从 $X_i$ 机场起飞,不经停,飞往 $Y_i$ 机场。 为了简化问题,我们假设 JS Airway 可以在 $0$ 时刻在任意机场布置任意多架加油维护完毕的飞机;为了减少飞机的使用数,我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。 JYY 想知道,理论上 JS Airways 最少需要多少架飞机才能完成所有这 $M$ 个航班。

不定元任意范围的整数解个数


给出方程: $\sum_{i=1}^nx_i=s$ 其中 $f_i \le x_i \le g_i(1 \le i \le n)$。 求这个方程组的解的个数 $ans \% 1000000007$。

Pollard-Rho


问题

[HNOI2014]道路堵塞


题目描述题目传送门思路首先有一个结论:删除边后的最短路一定是在最短路上跑一段,然后跳出最短路,然后再跑一段。换言之,就是不在最短路上跑的路径一定是一段连续的路径,不会存在两段及以上(如果两段相等,假设选择原最短路上的路径)。证明:这个结论是我猜出来的,现在给出简要证明。记 dis⁡(i)\opera

同余


费马小定理 欧拉定理 扩展欧拉定理

选举预测


题目描述题目传送门思路看到 $n \le 10^6$,显然会有一些结论。结论1能打败人最多的人可能胜利。证明:假设打败人最多的人(称其为 Cms)不可能胜利,那必定有人(下文称其为石老板)可以打败他和他所有能打败的人,否则可能出现 Cms 打败的人干掉了石老板,然后 Cms 干掉了他,取得胜利。为了

【模板】扩展 KMP(Z 函数)


题目传送门思路对于一个字符串 $s$,$z_i := |\operatorname{LCP}(s,s[i:])|$,即 $s$ 从 $i$ 开始的后缀与 $s$ 的最大匹配。暴力计算 $z$ 函数是 $O(n^2)$ 的,考虑将计算的 $z$ 函数用起来。我们顺次计算 $z$ 函数,假设现在需要计

[POI2015] LAS


题目描述题目传送门思路这题黑是恶意评分吧考虑 dp,先想状态怎么设。很容易想到的第一种 dp,假设 $dp_{i,j}$($j \in \{1,2\}$),表示第 $i$ 个人吃了左边($j = 1$)或者 右边($j = 2$)的食物,可是这样似乎没有什么转移关系,所以做不了(~~或者我太菜了不会

复数


虚数我们定义 $i = \sqrt{-1}$ ,称 $i$ 为虚数单位。

CF797E Array Queries


题目描述题目传送门1题目传送门2给定长度为 $n$ 的序列 $a$。$m$ 次询问。每次询问给出 $p,k$。您要不断地执行操作 $p\gets p+a_p+k$,直到 $p>n$ 为止。询问的答案为操作次数。$1\le n,q\le 10^5$,$1\le a_i\le n$。思路Algor