url: https://www.luogu.com.cn/problem/P2280

tag：
前缀和

思路：
这是一道二维前缀和。根据题意可以知道边长为m的爆破正方形最多可以破坏 m m 个目标，所以题目就变成了找到地图范围内，大小为m m的子矩阵中总价值最大的值。地图的范围可以直接定义成边界5000 5000，也可以像代码中的一样，一开始为m m表示至少要有一个子矩阵，之后每次读入一个新的目标时通过目标的坐标来更新地图大小。遍历每一个子矩阵可以通过从x = m和y = m开始遍历每一个点作为子矩阵的右下端点然后通过计算得到左上端点然后再通过二维前缀和的公式计算求最大值即可。

代码：

#include <iostream>
#include <cstring>
using namespace std;
const int N = 5010;
int p[N][N];
int n, m;
int nx, my;
int main()
{
    scanf("%d%d", &n, &m);
    nx = my = m;
    // 读数
    for (int i = 0; i < n; i ++)
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x ++, y ++;
        nx = max(x, nx), my = max(y, my);
        p[x][y] += w;
    }
    // 计算前缀和
    for (int i = 1; i <= nx; i ++)
        for (int j = 1; j <= my;  j++)
        {
            p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i -1][j - 1];
        }
    // 求子矩阵中总价值最大的值
    int res =  -1;
    for (int i = m; i <= nx; i ++)
        for (int j = m; j <= my; j ++)
        {
            res = max(res, p[i][j] - p[i - m][j] - p[i][j - m] + p[i - m][j - m]);
        }
    cout << res <<endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/B3738

tag：
模拟，数学

思路：
数据范围比较小，可以用模拟的方式来通过这道题。比较难的部分应该是蛇形填充。这里可以先用一个数组来存放四个前进的方向。之后每次都判断一下前进之后的位置符不符合要求（不越界且当前位置没有被填充过），如果符合要求则前进，然后将数字放进矩阵，否则就换一个方向。

代码：

#include <iostream>
using namespace std;
int n, x, y;
const int N = 22;
int p[410], dp[N][N], d;
int dir[4][2] = {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0},
};
bool is_pr(int x)
{
    for (int i = 2; i * i <= x; i ++)
    {
        if (x % i == 0) return false;
    }
    return true;
}
int main()
{
    cin >> n >> x >> y;
    int k = 2;
    for (int i = 1; i <= n * n; i ++)
    {
        while (!is_pr(k++));
        p[i] = --k;
        k ++;
    }
    int nx = 0, ny = 0;
    dp[0][0] = p[1];
    for (int i = 2; i <= n * n; i ++)
    {
        int tmpx, tmpy;
        tmpx = nx + dir[d][0], tmpy = ny + dir[d][1];
        if (tmpx >= n || tmpx < 0 || tmpy >= n || tmpy < 0 || dp[tmpx][tmpy])
        {
            d = (d + 1) % 4;
            tmpx = nx + dir[d][0], tmpy = ny + dir[d][1];
        }
        nx = tmpx, ny = tmpy;
        dp[nx][ny] = p[i];
    }
    cout << dp[x - 1][y  - 1] << endl;
    return 0;
}

问题描述
小M想要通过查看往届游戏比赛的排名来确定自己比赛的目标分数。他希望找到往届比赛中排名第三的分数，作为自己的目标。具体规则如下：

如果分数中有三个或以上不同的分数，返回其中第三大的分数。
如果不同的分数只有两个或更少，那么小M将选择最大的分数作为他的目标。
请你帮小M根据给定的分数数组计算目标分数。

测试样例
样例1：

输入：n = 3,nums = [3, 2, 1]
输出：1

样例2：

输入：n = 2,nums = [1, 2]
输出：2

样例3：

输入：n = 4,nums = [2, 2, 3, 1]
输出：1

题解：

int solution(int n, std::vector<int> nums) {
    set<int> uniqueNums(nums.begin(), nums.end());
    if (uniqueNums.size() < 3) return *uniqueNums.rbegin();
    auto it = uniqueNums.rbegin();
    it ++;
    it ++;
    return *it;
}

这里主要用到了set的去重和排序。set是从小到大排，所以为了拿到最大值用来 rbegin() 这个反向迭代器。因为std::set 的迭代器是双向迭代器所以没有 += -= 这种操作。

双向迭代器：只支持单步的前进和后退操作，即使用 ++it 或 --it。它们不支持像 += 或 -= 这样的算术操作。

还有一个用法很有意思就是 set<int> uniqueNums(nums.begin(), nums.end()); 可以通过给set传一个范围（vector）来创建set。同样的用法在vector也有，例如：

std::vector<int> vec(uniqueNums.begin(), uniqueNums.end());
// 现在可以使用随机访问操作
return vec[vec.size() - 3];

在form第一个便签里加上 @submit 属性，后面跟上执行的函数，
例如：

<form @submit="login">
    <div class="mb-3">
      <label for="username" class="form-label">Username</label>
      <input v-model="username" type="text" class="form-control" id="username">
    </div>
    <div class="mb-3">
      <label for="password" class="form-label">Password</label>
      <input v-model="password" type="password" class="form-control" id="password">
    </div>
    <div class="error-message">{{ errorMessage }}</div>
    <button type="submit" class="btn btn-primary">Submit</button>
</form>

如果需要禁用掉默认事件可以用 @submit.prevent 例如：

<form @submit.prevent="login">
    <div class="mb-3">
      <label for="username" class="form-label">Username</label>
      <input v-model="username" type="text" class="form-control" id="username">
    </div>
    <div class="mb-3">
      <label for="password" class="form-label">Password</label>
      <input v-model="password" type="password" class="form-control" id="password">
    </div>
    <div class="error-message">{{ errorMessage }}</div>
    <button type="submit" class="btn btn-primary">Submit</button>
</form>

url : https://www.luogu.com.cn/problem/P2694

tag：
模拟

思路：
为了可以接到所有的金币，所以我们可以采取一个贪心的策略，每次都先去接高度距离自己最近的一个金币，之后判断在这个过程中是否存在接不到的情况，如果有就说明接不到所有的金币，否则就是可以接到所有的金币。
为了采取贪心的策略，我们需要对所有的金币按照高度排序。然后需要维护一个全局的掉落高度 ey 和自己的位置 fx ，之后按照高度遍历每一个金币，判断，当我走到这个金币的时候金币到我的高度，如果大于等于0则说明可以接到，否则接不到。如果可以接到，则更新一下ey和fx。
关于如何排序，可以利用pair的特性，即先按照first排序如果一样再按照second排序，来排。所以我们可以用pair来存每一个金币的位置，且将高度放到first。
关于如何判断，因为题目有给一个速度都是1，所以移动的距离（用绝对值表示）就是这一段时间，即从原来我的位置到要接的那个金币下面的时间，金币下降的高度。所以先让 ey += abs(fx - dp[i].second),之后再判断 dp[i].first - ey 的大小。如果大于0就可以接到，小于零就break掉。
当大于0时，为了可以接到，所以必须让金币的高度为0，因此就还要等一段时间，这段时间fx不会更新，但是ey需要再加上 dp[i].first - ey, 表示在等待的过程中全局的下降距离增加的距离。
ps：如果速度不为1可能反而会好理解一点。

代码：

#include <iostream>  
#include <algorithm>  
using namespace std;  
typedef pair<int, int> PII;  
PII dp[52];  
int main()  
{  
    int g;  
    cin >> g;  
    while(g--)  
    {  
        int n;  
        bool flag = true;  
        cin >> n;  
        int fx = 0, ey = 0;  
        for (int i = 0; i < n; i ++)  
        {  
            cin >> dp[i].second >> dp[i].first;  
        }  
        sort(dp, dp + n);  
        for (int i = 0; i < n; i ++)  
        {  
            ey += abs(fx - dp[i].second);  
            if (dp[i].first - ey >= 0)  
            {  
                ey += dp[i].first - ey;  
                fx = dp[i].second;  
            }  
            else  
            {  
                flag = false;  
                cout << "Notabletocatch\n";  
                break;  
            }  
        }  
        if (flag) cout << "Abletocatch\n";  
    }  
    return 0;  
}