做的跟shit一样，被虐爆了

F wiki数星星

题目背景

wiki正在一条直线上数星星，她想知道，哪里是离星星最近的地方呢？

题目描述

有一个函数 $ f(x) $，初始为常数函数 $ f(x) = 0 $。

接下来 $ Q $ 次操作：

• 更新 1 a b：给定整数 $ a, b $，令 $ g(x) = f(x) + |x - a| + b $，然后把 $ f(x) $ 替换为 $ g(x) $。

  例如：若当前 $ f(x) = 0 $，执行操作更新操作 1 2 1（即 $ a=2, b=1 $），则新的函数为 $ f(x) = |x-2| + 1 $；接着再执行操作 1 3 2（即 $ a=3, b=2 $），新的函数为
  $ f(x) = |x-2| + 1 + |x-3| + 2 $。

• 查询 2：输出使 $ f(x) $ 最小的整数 $ x $ 以及最小值 $ f(x) $。如果有多个使得最小的 $ x $，选择最小的那个整数。

例如：当 $ f(x) = |x - 2| + 1 $ 时，$ x = 2 $ 使得 $ f(x) $ 最小为 1。

已知询问时输出的值总是整数，请以整数格式输出。

阅读全文

软院大二上的算法课真是离谱，课上PPT几乎全是英文（怀疑完全是从算法导论原版书粘贴的），也听不懂。上机考试和上课讲的内容也没有关系，被纯纯虐杀，有的算法听都没听过...

第二章 算法基础

2.1 插入排序

基本算法：

​ 当选择循环下标j时，数组的A[1, j-1]已经排好序，剩余子数组为A[j+1, n]，将j下标的元素插入到前j-1个元素之中的合适位置：查找对应位置需要从j-1到1一个一个找到第一个小于等于A[j]的元素，找过的元素都往后移一位，A[j]放在停止的位置上。而循环下一次下标为j+1。

而当证明算法的正确性时，书中给出了需要证明的三条性质：

• 初始化： 循环的第一次迭代之前，它为真；
• 保持： 如果循环的某次迭代之前它为真，那么下次迭代之前它仍然为真；
• 终止： 在循环终止时，不变是为我们提供了一个有用的性质，该性质有助于证明算法是正确的。

阅读全文

A

题目描述

AndroidNeko 听说在计算复杂度的重要性刻进主题，想希望你以样写写一个程序来计算满足特定形式递归式的算法复杂度。

具体来说，给定正整数 $a, b, k$，所求递归式为：

$$ T(n) = aT\left(\frac{n}{b}\right) + O\left(n^k\right) $$

根据主定理，有：

$$ T(n) = \begin{cases} O\left(n^{\log_b a}\right), & \log_b a > k \\ O\left(n^k \log n\right), & \log_b a = k \\ O\left(n^k\right), & \log_b a < k \\ \end{cases} $$

输入格式

第一行一个正整数 $t$ $(1 \leq t \leq 2 \times 10^5)$，表示数据组数。

对于每组数据，一行三个正整数 $a, b, k$ $(1 \leq a, k \leq 10^9,\, 2 \leq b \leq 10^9)$，含义同题目描述。

输出格式

对于每组数据，输出一行：

• 若 $T(n)=O(n^{\log_b a})$，输出 n^{\log_ba}
• 若 $T(n)=O(n^k \log n)$，输出 n^klog n

• 若 $T(n)=O(n^k)$，输出 n^k

阅读全文

线性DP：递推方程有明显的线性的顺序。
考虑两个问题：如何状态表示（集合+属性）、如何状态计算（划分状态转移集合）
T1：

状态表示： 记录所有从起点走到(i,j)的路径中的路径数字之和的最大值。
状态计算：f[i,j] = max(f[i-1][j], f[i-1][j-1]) + a[i,j]
需要注意需要把f[i,j]初始化为极小值，避免算到三角形右边的元素。

T2：最长上升子序列

状态表示：使用一维数组，f[i]表示以第i个数结尾的上升子序列的长度的最大值。
状态计算：计算f[i]，去看倒数第二个数是哪个数，共i种可能，以编号1、2、3、……、i-1结尾或原本没有数（记为0）。每个循环先看是否满足上升的条件，若满足，则这个f[i]_j = f[j]+1，最后计算一个最大的f[i]_j就得出了f[i]的值。
时间复杂度计算：状态数量 × 转移的数量。此时是$n^2$。

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int a[N], f[N];

int main(){
    scanf(“%d”, &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++){
        f[i] = 1; //先全部赋值为1，只有a[i]一个数
        for(int j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, f[i]);
    printf("%d\n", res);
    return 0;
}

如何保存最长序列？
创建一个数组g[i]，存储每个转移是怎么转移过来的（记录上一个状态的id，也就是找f[i,j]最大值时找到的位置）。

阅读全文

本章主要介绍动态规划的常用思路，并介绍了背包问题里面的01背包、多重背包的解题思路和代码

01背包

01背包问题为：给定背包总体积，给N个物品，每个物品有一个体积和重量，只能用一次或不用，问最大重量是多少？
下面是思路，定义函数f(i,j)代表：仅包含前i个物品且总体积小于等于j的背包的最大价值是多少，故最终需要的结果是f(N,V)。
初始时把所有值都设为0，且i或j等于0的本身值就为0。
对于一个新的状态f(i,j)，可能的值有下面两种可能，如果包含i，则答案为f(i-1，j-vi) + wi；如果不包含i，则为f(i-1,j)。这两个值取最大值就可以算出f(i,j)。

代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for(int i=1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i=1; i <= n; i++)｛
        for(int j = 1; j <= m; j++){
            f[i][j] = f[i-1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    ｝
    cout << f[n][m] << endl;
}

阅读全文