top显示当前进程的运行状况
文件名的第一个是.，代表隐藏文件，要ls -a才能看到
ls XXX -l会给出某个文件的详细信息，参数部分加上h，ls XXX -lh可以更人性化的输出，如将1024输出为1K
在某个文件夹内用ls -A，不同于-a，会不输出当前目录和上层目录，即.和..
ll等于ls -la
cd后什么都不加，直接返回家目录
cd -返回之前访问的目录
可以用\转义，如mkdir y\ c，会创建一个名称为y c的文件夹
mkdir a/b/c -p，可以在当前目录创建一个a文件夹，且a里有文件夹b，b里有文件夹c
history显示之前在命令行输入的指令
-r是指递归，如rm XXX -r就是删XXX文件夹，递归删XXX下的所有文件以及XXX本身
*为正则表达式，如rm *.txt就是删当前目录下所有非隐藏的txt文件
对rm命令，有些文件是受保护的删不了，可以加参数-f，如rm /* -rf，高危命令！！！

注：上图将绿化图看作A矩阵，藏宝图看作B矩阵。坐标系向上为x轴，向右为y轴。

此题的突破口在于，藏宝图的左下角一定是有一棵树，而西西艾弗岛绿化图中最多只有1000棵树，因此只需依次枚举藏宝图左下角的树对应于绿化图中的1000棵树的1000种情况。

#include<iostream>
using namespace std;

#define x first
#define y second

const int S = 55, N = 1010, INF = 1e9;
typedef pair<int , int> PII;

PII tree[N];
int b[S][S];
int n, l, s;

int main(){
    cin >> n >> l >> s;
    for(int i = 0; i < n; i ++){
        cin >> tree[i].x >> tree[i].y;
    }
    int cnt = 0;   //记录藏宝图中树的总数
    for(int i = s; i >= 0; i --){
        for(int j = 0; j <= s; j ++){
            cin >> b[i][j];
            cnt += b[i][j];
        }
    }
    //枚举绿化图中的所有树
    int res = 0;   //记录绿化图中有多少处坐标满足条件
    for(int i = 0; i < n; i ++){
        int sx = tree[i].x, sy = tree[i].y;    //将枚举到的绿化图中的树对应到藏宝图的左下角
        if(sx + s > l || sy + s > l) continue;   //若以绿化图中的某棵树作为藏宝图的左下角时，藏宝图会超出绿化图范围时，跳出该循环
        int tc = 0;   //记录绿化图中有多少棵树与藏宝图中的树对应，若最后tc==cnt，则res+=1
        for(int j = 0; j < n; j ++){
            int x = tree[j].x, y = tree[j].y;
            if(x >= sx && x - sx <= s && y >= sy && y - sy <= s){   //不判断范围则x-sx可能为负，数组越界。另外只有符合范围，绿化图中的树才可能与藏宝图中的树相对应
                if(!b[x - sx][y - sy]) tc = -INF;   //令tc为负无穷，则之后tc再怎么增加也仍是负数，不可能等于cnt
                else tc += 1;
            }
        }
        if(tc == cnt) res += 1;
    }
    cout << res << endl;

    return 0;
}

满分做法，差分

上图求解对于$t_{i}$时刻进入的某场所，我们在什么样的时间范围内做核酸才可以进入该场所。
进而求解出对于某一项出行计划，应该在什么样的时间范围内做核酸。

建立一个各元素为0的数组s[200010]，s[i]表示在i时刻做核酸可以满足多少个出行计划。因此对于给出的每一个出行计划，使$s[t_{i}-k-c_{i}+1]$到$s[t_{i}-k]$均加一。进而想到用差分来降低时间复杂度。

#include<iostream>
#include<algorithm>
using namespace std;

int n, m, k;
int a[200100] = {0};

int main(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++){
        int t, w;
        cin >> t >> w;
        int l = t - w - k + 1, r = t - k;
        if(r > 0){
            a[max(1, l)] ++, a[r + 1] --;
        }
    }
    for(int i = 1; i <= 200100; i ++) a[i] += a[i - 1];   
    //这里是算出每一个时刻做核酸可以满足的出行计划总数，而不能写成for(int i = 1; i <= n; i ++)
    for(int i = 0; i < m; i ++){
        int x;
        cin >> x;
        cout << a[x] << endl;
    }

    return 0;
}

我的做法（70分）

二分只优化了算法中的一部分的时间复杂度，但总时间复杂度仍为$n^{2}$

#include<iostream>
#include<algorithm>
using namespace std;

int n, m, k;
int a[100010], b[100010];

int main(){
    cin >> n >> m >> k;
    for(int i = 0; i < n; i ++){
        cin >> a[i] >> b[i];
    }

    int l = 0;
    for(int i = 0; i < m; i ++){
        int test;
        cin >> test;
        int get_result = test + k;

        //二分
        int r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(a[mid] < get_result) l = mid + 1;
            else r = mid;
        }

        if(a[l] >= get_result){
            int res = n - l;
            for(int j = l; j < n; j ++){
                if(a[j] - b[j] >= get_result) res --;
            }
            cout << res << endl;
        }else{
            cout << 0 << endl;
        }
        /*
        如果不进行特判，可能会出现以下情况，测试样例为：
        2 1 10
        1 24
        2 24
        1
        得结果为1，实际应为0
        */
    }

    return 0;
}

算法基础课的模板题中也有特判过程

①暴搜，递归(70分)

#include<iostream>
#include<algorithm>
using namespace std;

int n, x;
int a[35] = {0};
int res = 1e9;

int dfs(int u, int sum){
    if(u == n){                             //不可以if(u == n && sum >= x) res = min(res, sum);
        if(sum >= x) res = min(res, sum);
    }else{
        dfs(u + 1, sum);
        dfs(u + 1, sum + a[u]);
    }
    return res;
}

int main(){
    cin >> n >> x;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
    }

    cout << dfs(0, 0) << endl;

    return 0;
}

②用二进制数的每一位表示某本书买或是不买(70分)

#include<iostream>
#include<algorithm>
using namespace std;

int n, x;
int a[35] = {0};
int res = 1e9;

int main(){
    cin >> n >> x;
    for(int i = 0; i < n; i ++) cin >> a[i];

    for(int i = 0; i < (1 << n); i ++){
        int sum = 0;
        for(int j = 0; j < n; j ++){
            if((i >> j) & 1 == 1) sum += a[j];
            if(sum >= x && sum < res) res = sum;
        }
    }
    cout << res << endl;

    return 0;
}

③最优解，01背包(100分)

考查转化模型的能力。设总价格为sum，包邮最低价为x，则此题可转化为总体积为sum-x的01背包问题

朴素

#include<iostream>
using namespace std;

int n, x;
int w[33], v[33];
int f[33][300010];

int main(){
    cin >> n >> x;
    int sum = 0;
    for(int i = 1; i <= n; i ++){
        cin >> w[i];
        v[i] = w[i];
        sum += w[i];
    }
    int m = sum - x;

    for(int i = 1; i <= n; i ++){
        for(int j = 0; 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 << sum - f[n][m] << endl;

    return 0;
}

优化

#include<iostream>
using namespace std;

int n, x;
int w[33];
int f[300010];

int main(){
    cin >> n >> x;
    int sum = 0;
    for(int i = 1; i <= n; i ++){
        cin >> w[i];
        sum += w[i];
    }
    int m = sum - x;

    for(int i = 1; i <= n; i ++){
        for(int j = m; j >= 0; j --){
            f[j] = f[j];
            if(j >= w[i]) f[j] = max(f[j], f[j - w[i]] + w[i]);
        }
    }
    cout << sum - f[m] << endl;

    return 0;
}

#include<iostream>
using namespace std;

typedef long long LL;

int n;
LL m;                      //其实不会爆int，因为0≤m＜Cn，而Cn≤1e9

int main(){
    cin >> n >> m;
    int c_o = 1;
    for(int i = 0; i < n; i ++){
        int a;
        cin >> a;
        int c_c = c_o * a;
        cout << (m % c_c) / c_o << ' ';
        c_o = c_c;
    }

    return 0;
}

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

int n;
int a[1010];

int main(){
    cin >> n;
    int sum = 0;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        sum += a[i];
    }
    double mean = (double)sum / n;
    double d_sum;
    for(int i = 0; i < n; i ++){
        d_sum += pow((double)a[i] - mean, 2);
    }
    double d = d_sum / n;
    double standard_d = sqrt(d);
    for(int i = 0; i < n; i ++){
        printf("%f\n", (a[i] - mean) / standard_d);
    }

    return 0;
}

#include<iostream>
using namespace std;

int n, k;
bool s[100010] = {false};

int main(){
    cin >> n >> k;
    s[0] = true;
    int res = 0;
    for(int i = 0; i < k; i ++){
        int a, b;
        cin >> a >> b;
        if(s[b] == false) res ++;
        s[a] = true;
    }

    cout << res << endl;

    return 0;
}

暴力枚举

#include<iostream>
#include<cstring>
using namespace std;

int n, k;

int main(){
    cin >> n >> k;
    int res = 0;
    for(int i = 1; i <= n; i ++)
        for(auto c : to_string(i)){
            if(c - '0' == k) res ++;
        }
    cout << res << endl;

    return 0;
}

此题用到了算法基础课，贪心的排序不等式。当各元素查询次数和各元素值均取升序时，依次相乘再求和，即得最大值；当各元素查询次数取升序，但各元素值取降序时，依次相乘再求和，得最小值。

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
typedef long long LL;

int n, q;
LL s[N] = {0}; 
int a[N] = {0}, c[N] = {0};                //a数组存各元素值，c数组存储各元素的查询次数

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];                  //前缀和
    }
    cin >> q;
    LL inital_sum = 0;
    for(int i = 0; i < q; i ++){
        int l, r;
        cin >> l >> r;
        c[l] += 1;                               //差分
        c[r + 1] -= 1;
        inital_sum += s[r] - s[l - 1];
    }
    for(int i = 1; i <= n; i ++){
        c[i] += c[i - 1];                        //得到每个元素的查询次数
    }
    sort(a + 1, a + n + 1);
    sort(c + 1, c + n + 1);
    LL changed_sum = 0;
    for(int i = 1; i <= n; i ++){
        changed_sum += (LL)a[i] * c[i];
    }

    cout << changed_sum - inital_sum << endl;

    return 0;
}

Y总的代码与我略有不同，Y总没有用前缀和去求初始查询之和，而是直接将各元素的查询次数去乘以该元素值再求和，代码更简洁。

对每一头牛进行遍历，如果它是‘H’，则向左找到L个连续的‘G’，向右找到R个连续的‘G’；
如果它是‘G’，则向左找到L个连续的‘H’，向右找到R个连续的‘H’。

假设当前遍历到的牛为‘G’，则扔掉的所有照片中含有当前遍历到的牛‘G’的照片可能会出现三种情况：
①该牛的左边和右边都有连续的‘H’牛，共LR张
②仅在该‘G’牛的左边有连续的‘H’牛，共L-1张
③仅在该‘G’牛的右边有连续的‘H’牛，共R-1张

#include<iostream>
#include<algorithm>
using namespace std;

int n;
char a[500010];
int l[500010], r[500010];  //第i头牛左边和右边与第i头牛不同品种的牛有连续多少个

int main(){
    cin >> n;
    cin >> a;
    int g = 0, h = 0;
    //对第一次从左向右遍历，g(h)表示当前遍历到的牛的左边有多少头连续的g(h)牛
    for(int i = 0; i < n; i ++){
        if(a[i] == 'G'){
            g ++;
            l[i] = h;
            h = 0;
        }else{
            h ++;
            l[i] = g;
            g = 0;
        }
    }

    g = 0, h = 0;
    //对第二次从右向左遍历，g(h)表示当前遍历到的牛的右边有多少头连续的g(h)牛
    for(int i = n - 1; i >= 0; i --){
        if(a[i] == 'G'){
            g ++;
            r[i] = h;
            h = 0;
        }else{
            h ++;
            r[i] = g;
            g = 0;
        }
    }

    long long ans = 0;
    for(int i = 0; i < n; i ++){
        ans += (long long)l[i] * r[i];    //若改为(long long)(l[i] * r[i])，就错了
        ans += max(l[i] - 1, 0);         //此处容易错写为ans += l[i] - 1;
        ans += max(r[i] - 1, 0);
    }

    cout << ans << endl;

    return 0;
}