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

tag:
枚举，构造，动态规划

思路：
看了题解好像是可以用动态规划中的求最大子矩阵来做，但是这里用了很暴力的写法，加上前缀和优化也能过。这个做法本质上就是不断地枚举每一个矩形然后判断四条边是不是满足条件，然后再更新最大值就好了。

代码：

#include <iostream>
using namespace std;
const int N = 220;
int n, m;
int d[N][N], s[N][N], col[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            char c;
            cin >> c;
            if (c == '.') d[i][j] ++;
            s[i][j] = s[i][j - 1] + d[i][j];
            col[i][j] = col[i - 1][j] + d[i][j];
        }

    int res = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
        {
            for (int k = 1; k <= m; k ++)
            {
                for (int l = k; l <= m; l ++)
                {
                    if (
                            col[j][k] - col[i - 1][k] == j - i + 1
                            && col[j][l] - col[i - 1][l] == j - i + 1
                            && s[i][l] - s[i][k - 1]  == l - k + 1
                            && s[j][l] - s[j][k - 1] == l - k + 1)
                        res = max(res, (j - i + 1) * (l - k + 1));
                }
            }
        }
    cout << res << endl;
    return 0;
}

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

tag:
NOIP2012 提高组，贪心，高精度

思路：
用贪心的策略，将大臣按照左右手金币数量的乘积从小到大排序，贪心证明: https://www.luogu.com.cn/article/2xwnkq6p . 然后因为数据范围比较大又用到了乘除所以需要使用高精度，同时配合写一个比较函数。

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10;
int n;
typedef pair<int, int> PII;
vector<PII> d;
bool cmp(PII &a, PII &b)
{
    return a.first * a.second < b.first * b.second;
}
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++)
    {
        t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        C.push_back(t % 10);
        t /= 10;
    }
    while (!C.back() && C.size() != 1) C.pop_back();
    return C;
}
vector<int> div(vector<int> &A, int b)
{
    vector<int> C;
    reverse(A.begin(), A.end());
    int t = 0;
    for (int i = 0; i < A.size(); i ++)
    {
        t = t * 10 + A[i];
        C.push_back(t / b);
        t %= b;
    }
    reverse(C.begin(), C.end());
    while (!C.back() && C.size() > 1) C.pop_back();
    reverse(A.begin(), A.end());
    return C;
}
bool rescmp(vector<int> &A, vector<int> &B)
{
    if (A.size() != B.size()) return A.size() > B.size();
    else
    {
        for (int i = A.size() - 1; i >= 0; i ++)
        {
            if (A[i] == B[i]) continue;
            else return A[i] > B[i];
        }
    }
}
int main()
{
    cin >> n;
    PII king;
    cin >> king.first >> king.second;
    for (int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        d.push_back({a, b});
    }
    sort(d.begin(), d.end(),cmp);
    d.insert(d.begin(),king);
    vector<int> res(1, 0);
    vector<int> tmp(1, 1);
    for (int i = 1; i < d.size(); i ++)
    {
        tmp = mul(tmp,d[i - 1].first);
        auto tmmp = div(tmp, d[i].second);
        if (rescmp(tmmp, res)) res = tmmp;
    }
    for (int i = res.size() - 1; i >= 0; i --) cout << res[i];
    cout << endl;
    return 0;
}

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

tag:
差分

思路：
说是一道差分的题，但觉得更像是脑筋急转弯的那种感觉。为了求出最少的操作次数，可以依次求a(i) - a(i-1)，表示相邻两个数的差，然后将正的差和负的差分别求和，之后取这两个和的最大值就是最少的操作次数，因为对于差分来说，如果要对原数组的某一个区间加上1就是让这个区间的第一个数加1最后一个数的后一个数减一，所以加1和减1会有重叠，因此重叠的部分只需要算一次就好，然后剩下的不重叠的再单独算，所以最少的操作次数就是max(q, p)，而对于多少种情况来讲，其实看的是a(1)，因为最后数都一样的话，那么对于差分数组（代码没有）来说，第一个数会影响全部的数。所以只要把有可能会对第一个数产生影响的次数加在一块再加上本身一种情况就是最多可能的结果数。而这种会影响的次数其实就是不重叠的次数，也即max(p, q) - min(p, q)，（min(p, q)用来表示重叠的次数）。

代码：

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
long long a[N], b[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    long long p = 0, q = 0;
    for (int i = 2; i <= n; i ++)
    {

        long long tmp = a[i] - a[i - 1];
        if (tmp > 0) p += tmp;
        else q -= tmp;
    }
    cout << max(q, p) << '\n' << max(q, p) - min(q, p) + 1 << endl;
    return 0;
}

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

tag:
图论，最短路

思路：
这道题因为读入的时候，会有不同权值的相同的边，要求是如果有重复的就保留最长的那个，这种情况下用邻接链表不是很好做，所以可以用邻接矩阵来存比较方便。然后就是数据范围比较小，k是小于等于100，刚好floyd算法可以过，所以就用floyd来求最短路。

代码：

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

int main()
{
    int d[110][110];
    memset(d, 0x3f, sizeof d);
    int n, k;

    cin >> n >> k ;
    int c = 0;
    for (int i = 0; i < n; i ++)
    {
        int w;
        cin >> w;
        if (i == n - 1)
        {
            d[i][0] = d[0][i] = w;
        }
        else
        {
            d[i][i + 1] = d[i + 1][i] = w;
        }
    }
    for (int i = 0; i < k; i ++)
    {
        char a, b;
        int w;
        cin >> a >> b >> w;
        if (d[a - 'A'][b - 'A'] == 0x3f3f3f3f) d[a - 'A'][b - 'A'] = d[b - 'A'][a - 'A'] = w;
        else d[a - 'A'][b - 'A'] = d[b - 'A'][a - 'A'] = max(w, d[a - 'A'][b - 'A']);
    }
    for (int q = 0; q < n; q ++)
        for (int i = 0; i < n; i ++)
            for (int j = 0; j < n; j ++)
                d[i][j] = min(d[i][j], d[i][q] + d[q][j]);

    char s, t;
    cin >> s >> t;
    cout << d[s - 'A'][t - 'A'];
    return 0;

}

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

tag:
kruskal算法, 并查集

思路：
先按照边权排序，然后依次取出每条边，判断两个点是否联通（是否在一个集合）如果不连通就加一条边，然后更新下res = max(res, w) 然后边数++，最后判断边数是否为点个数-1，表示所有点都连上，如果没有则输出-1，否则输出res

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N];
struct edg {
    int x, y, t;
} Edg[N];
bool cmp(edg &a, edg &b)
{
    return a.t < b.t;
}
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
    {
        cin >> Edg[i].x >> Edg[i].y >> Edg[i].t;
    }
    sort(Edg + 1, Edg + m + 1, cmp);
    for (int i = 1; i <= n; i ++) p[i] = i;
    int res = 0, cnt = 0;
    for (int i = 1; i <= m; i ++)
    {
        int a = find(Edg[i].x), b = find(Edg[i].y), w = Edg[i].t;
        if (a != b)
        {
            p[a] = b;
            res = max(res, w);
            cnt ++;
        }
    }
    if (cnt < n - 1) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}