T1

考虑序列中数的种类

若包含0或同时存在正负，答案就是\(\sum_{i=1}^{n} |a_i|\)

若仅正或仅负，答案就是\(\sum_{i=1}^{n}|a_i|-2*\min_{i=1}^{n}(|a_i|)\)

T2

枚举个矩形不选，然后求n-1个矩形的面积交-n个矩形的面积交，最后加上n个矩形的面积交

是一段连续的前后缀，可以\(O(n)\)或\(O(n\log_2 n)\)的 st 表

T3

枚举每种循环节，然后枚举循环了几次

复杂度\(O(n^2\ln n)\)

T4

直接爆枚主塔，然后枚举出边找到第二个主塔，然后在两塔的交集种选两个最大的就行了

代码

T1

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x7fffffff;
const int N = 2e6 + 11;
int n;
int a[N];
inline int min_(int a, int b) { return a < b ? a : b; }
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int main() {
    FILE* x = freopen("stone.in", "r", stdin);
    x = freopen("stone.out", "w", stdout);
    int t = read();
    bool jud0, judz, judf;
    int sum, minn;
    while (t--) {
        jud0 = judz = judf = 0;
        sum = 0;
        n = read();
        minn = inf;
        for (int i = 1; i <= n; ++i) {
            a[i] = read();
            jud0 |= (a[i] == 0);
            judz |= (a[i] > 0);
            judf |= (a[i] < 0);
            sum += a[i] < 0 ? -a[i] : a[i];
            minn = min_(minn, a[i] > 0 ? a[i] : -a[i]);
        }
        if (n == 1) {
            cout << a[1] << endl;
            continue;
        }
        if (jud0 && !(judz || judf))
            cout << 0 << endl;
        else if (judz && !(jud0 || judf))
            cout << sum - 2 * minn << endl;
        else if (judf && !(jud0 || judz))
            cout << sum - 2 * minn << endl;
        else
            cout << sum << endl;
    }
    return 0;
}

T2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 11;
const int inf = 0x7fffffff;
inline int max_(int a, int b) { return a > b ? a : b; }
inline int min_(int a, int b) { return a > b ? b : a; }
struct st_ {
    int xp, yp, xd, yd;
    friend st_ operator+(st_ a, st_ b) {
        a.xp = min_(a.xp, b.xp);
        a.yp = min_(a.yp, b.yp);
        a.xd = max_(a.xd, b.xd);
        a.yd = max_(a.yd, b.yd);
        return a;
    }
} f[20][N], now;
inline ll js(st_ x) {
    if (x.xp <= x.xd || x.yp <= x.yd)
        return -1ll;
    return 1ll * (x.xp - x.xd) * (x.yp - x.yd);
};
int q, p, n;
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}
void pre() {
    int logn = log2(n);
    for (int i = 1; i <= logn; ++i)
        for (int j = 1; j <= n; ++j) {
            if ((1 << i) + j - 1 > n)
                break;
            f[i][j].xp = min_(f[i - 1][j].xp, f[i - 1][j + (1 << i - 1)].xp);
            f[i][j].yp = min_(f[i - 1][j].yp, f[i - 1][j + (1 << i - 1)].yp);
            f[i][j].xd = max_(f[i - 1][j].xd, f[i - 1][j + (1 << i - 1)].xd);
            f[i][j].yd = max_(f[i - 1][j].yd, f[i - 1][j + (1 << i - 1)].yd);
        }
    return;
}
st_ get_st(int i, int j) {
    if (i > j)
        return (st_){ inf, inf, 0, 0 };
    int logn = log2(j - i + 1);
    return f[logn][i] + f[logn][j - (1 << logn) + 1];
}
int main() {
    FILE* h = freopen("carpet.in", "r", stdin);
    h = freopen("carpet.out", "w", stdout);
    int t = read();
    while (t--) {
        p = read(), q = read(), n = read();
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; ++i) {
            f[0][i].xd = read();
            f[0][i].yd = read();
            f[0][i].xp = read();
            f[0][i].yp = read();
        }
        if (n == 1) {
            cout << 1ll * (f[0][1].yp - f[0][1].yd) * (f[0][1].xp - f[0][1].xd);
            continue;
        }
        pre();
        int num = 0;
        ll sum = js(get_st(1, n));
        if (sum < 0)
            sum = 0;
        ll ans = sum;
        for (int i = 1; i <= n; ++i) {
            now = get_st(1, i - 1) + get_st(i + 1, n);
            if (js(now) > 0) {
                ++num;
                ans += js(now) - sum;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

T3

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 3e3 + 11;
const ull p = 131;
char tx[N];
int a, b, n;
ull hs[N][N];
inline int max_(int a, int b) { return a > b ? a : b; }
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    }
    return s;
}
int main() {
    FILE* x = freopen("melody.in", "r", stdin);
    x = freopen("melody.out", "w", stdout);
    a = read();
    b = read();
    cin >> (tx + 1);
    n = strlen(tx + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j) hs[i][j] = hs[i][j - 1] * p + tx[j] - 'a' + 1;
    int ans = 0;
    for (int len, ed, i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j) {
            len = j - i + 1;
            ed = 1;
            for (int k = 1; k <= (n - j) / len; ++k) {
                if (hs[j + (k - 1) * len + 1][j + k * len] != hs[i][j])
                    break;
                ++ed;
            }
            if (ed == 1)
                continue;
            ans = max_(ans, len * a + ed * b);
        }
    cout << ans << endl;
    return 0;
}

T4

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 11;
struct qxxx_ {
    int v, next;
} cc[2 * N];
bool jud[N];
int n, m;
int w[N];
int first[N], cnt;
vector<int> vct;
inline bool cmp(int a, int b) { return w[a] > w[b]; }
inline int max_(int a, int b) { return a > b ? a : b; }
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s;
}
void qxx(int u, int v) {
    cc[++cnt] = (qxxx_){ v, first[u] };
    first[u] = cnt;
    return;
}
int main() {
    FILE* p = freopen("station.in", "r", stdin);
    p = freopen("station.out", "w", stdout);
    n = read();
    m = read();
    for (int i = 1; i <= n; ++i) w[i] = read();
    for (int x, y, i = 1; i <= m; ++i) {
        x = read();
        y = read();
        qxx(x, y);
        qxx(y, x);
    }
    int ans = 0;
    for (int x, y, i = 1; i <= n; ++i) {
        for (int j = first[i]; j; j = cc[j].next) jud[cc[j].v] = 1;
        for (int j = first[i]; j; j = cc[j].next) {
            x = cc[j].v, vct.clear();
            for (int k = first[x]; k; k = cc[k].next) {
                y = cc[k].v;
                if (jud[y])
                    vct.push_back(y);
            }
            if (vct.size() > 1)
                sort(vct.begin(), vct.end(), cmp),
                    ans = max_(ans, (w[x] + 1) * (w[i] + 1) + w[vct[0]] * w[vct[1]]);
        }
        for (int j = first[i]; j; j = cc[j].next) jud[cc[j].v] = 0;
    }
    cout << ans << endl;
    return 0;
}