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

tag：
最大子数列，Kadane 算法，动态规划

思路：
使用动态规划得方法来求解，用两个变量currentSum，和maxSum，分别来维护以当前位置结尾的最大子段和以及全局的最大子段和。状态转移分别是currentSum = max(a, currentSum + a), maxSum = max(maxSum, currentSum).最后输出maxSum即可。细节：一开始可以先定义为最小值-0x3f3f3f3f这样可以避免漏掉负数，以及因为要求和所以最好开long long避免爆int。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int main()
{
    scanf("%d", &n);
    long long currentSum = -0x3f3f3f3f, maxSum = -0x3f3f3f3f;
    for (int i = 0; i < n; i ++)
    {
        long long a;
        scanf("%lld", &a);
        currentSum = max(a, currentSum + a);
        maxSum = max(maxSum, currentSum);
    }
    cout << maxSum << endl;
    return 0;
}

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

tag:
哈夫曼（Huffman）树 , 优先队列

思路：因为每次合并果子需要的体力值是两堆果子的重量之和，所以为了让总的体力值最小，可以使用贪心的策略，每次都只合并所有堆中重量最小的两堆。因此可以使用优先队列，每次取出两个头节点，res += 两个节点值的和，再将和的值插入到优先队列，重复这个过程直到队列中只有一个值，最后输出res即可。

代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    priority_queue<int, vector<int>, greater<int> > heap;
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++)
    {
        int a;
        cin >> a;
        heap.push(a);
    }
    long long res = 0;
    while(heap.size() > 1)
    {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    cout << res << endl;
    return 0;
}

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

tag:
二分

思路：
将每一个以1开头的片段当作一个整体ki，同时用ki表示当前片段数字的个数，那么若干个ki组合起来的片段的最后一个位置的坐标就是对ki求和Si。所以可以先用二分找到一个大于A的最小值，则A就在那个ki当中，然后求一下A距离上一个ki的偏移量，用A减去S(i - 1)，之后进行判断，如果 == 1则说明A处数字为1，否则就是0。

代码：

#include <iostream>  
#include <cstdio>  
using namespace std;  
int main()  
{  
    int n;  
    scanf("%d", &n);  
    while(n --)  
    {  
        int a;  
        scanf("%d", &a);  
        long long l = 0, r = 1e9;  
        while (l < r)  
        {  
            long long mid = (l + r) >> 1;  
            if (((mid * (mid + 1)) / 2) >= a) r = mid;  
            else l = mid + 1;  
        }  
        l --;  
        long long offset = a - (l * (l + 1)) / 2;  
        if (offset == 1) printf("%d\n", 1);  
        else printf("%d\n", 0);  
    }  
    return 0;  
}

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;
}