浅念づ昔夜's Blog

传送门

Solution

设 $f_1(x)=a_1x+b_1$，$f_2(x)=a_2x+b_2$。若 $f_1(f_2(x))<f_2(f_1(x))$，则 $a_1b_2+a_1<a_2b_1+b_2$。又因为 $b_1,b_2>0$，移项得$\dfrac{a_1-1}{b_1}<\dfrac{a_2-1}{b_2}$。

传送门

Solution

朴素算法

遍历所有点来选择询问点，每次删点后，暴力更新每个点的 $w_{\delta}$。

时间复杂度 $O(mn^2)$，可通过 CCF 原数据。

传送门

Solution

设 $fib_i$ 为斐波那契数列的第 $i$ 项，$c_i$ 为第 $i$ 格的芯片数，那么当所有 $c_i$ 确定时，无论怎么操作，都能保证 $k=\sum fib_ic_i$ 不变。因此所有情况都可以变成在第一格上放置若干个芯片，其它格子上没有芯片。

传送门

Solution

有一个显然的事实：被删除的块的大小一定是 $k$ 的整数倍。因此我们不妨将原先的操作变成：挑选 $\lfloor \dfrac{n-1}{m} \rfloor$ 个不重复的，大小为 $k$ 的区间进行消除。

队伍配置

最低配置

芙宁娜 1+0，其余 0+0，共 5 金。

0 命芙不作推荐，不如胡行钟夜。

传送门

Solution

先用树状数组求逆序对，得出数组总共的逆序对数量 $tot$。设 $a_i$ 和它前面的数共组成 $inv_i$ 对逆序对。

手玩样例后不难理解，操作 $i$ 的本质，其实就是对所有 $j\le i$，若 $a_j$ 非零，则 $a_j-1$。设执行操作 $i$ 前有 $m$ 个 $a_j$ 非零，则执行操作后整个序列的逆序对数量减少 $m$。

传送门

Solution

小清新构造题。

把每一格初始化为 $-1$，接下来进行 $n$ 次操作。第 $i$ 次操作将第 $p_i$ 行为 $-1$ 的格子全部变成 $0$，然后将第 $q_{n-i+1}$ 列为 $-1$ 的格子全部变成 $1$。

传送门

Solution

设 $F_{i,len, d}$ 表示以 $a_i$ 结尾，长度为 $len$，公差为 $d$ 的等差数列数量。转移方程为

$F_{i,len,d}=\sum\limits_{j=1}^{i-1} F_{j,len-1,d}$

传送门

Solution

从 $1$ 到 $n$ 枚举数字，对于当前数字，若与栈顶元素相同，则弹出栈顶元素，否则压入当前数字。随后将当前栈的状态通过哈希映射到 map 数组中。map 数组负责统计该状态出现的次数。