本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-04 20:37:19

T1

显然的构造，考虑设 $g_i = i^2 - (i-1)^2$，那么对于偶数的 $b_i$ 一定可以表示成两个完全平方数的差，也即 $g$ 数组中的一段和。

设前 $i-2$ 个数（$i$ 为奇数）的和为 $x^2$。

所以我们可以双指针维护，对于当前的，从这个数前面的前缀组成的完全平方数之后往后扫，若扫不到和恰为 $b_i$ 的就输出 Impoissble 否则就考虑当前 $b_i = r^2 - l^2$，那么当前的前一个 $b_{i-1}$ 就是 $l^2 - x^2$，然后 $b_i + b_{i - 1}$ 就等于 $r^2$ 就是完全平方数了。

T2

很难不注意到，由于保证 $a_i \ge a_{i + 1}$，那么我们就可以从当前第一个能选的一直顺着选直到不能选，然后再跳一个连续的不能选的段，我们显然可以证明最多会减 $\log_2 n$ 次，因为每次减 $x$ 要么直接减半，要么就直接选到结束，否则就一定可以再选。

然后我们就直接线段树二分最长能选的和线段树二分下一个能选的即可。

当然由于 $[l,n]$ 这个限制有点烦，所以我们可以改成从 $[1,n]$ 让后让总价值 $x$ 加上 $\sum_{i=1}^{l-1} a_i$ 即可。

时间复杂度 $O(n \log^2 n)$。

T4

先枚举第 $i$ 个战舰，然后看这个战舰会有多少种方案有贡献。

那么看有没有贡献，就只需要看当前可以删掉的数能不能抵掉删除。

所以我们设 $f_{i,j}$ 表示前 $i$ 个数有 $j$ 个可以抵消的，共有多少钟方案数。

设当前在位置 $k$，那么枚举 $i,j$

• 1. 若 $i<k$，那么如果是加法，那么就看若 $a_{i} \le a_{k}$，那么 $f_{i,j+1}$ 就加上 $f_{i - 1,j}$，否则就让 $f_{i,j}$ 就加上 $f_{i - 1,j}$。若是减法，那么就让 $f_{i,\max(0,j-1)}+f_{i-1,j}$。
  2. 若 $i=k$，那么直接继承即可。
  3. 若 $i>k$，那么如果是加法，那么就看若 $a_{i} < a_{k}$，那么 $f_{i,j+1}$ 就加上 $f_{i - 1,j}$，否则就让 $f_{i,j}$ 就加上 $f_{i - 1,j}$。若是减法，并且 $j > 0$，那么就让 $f_{i,j}$ 加上 $f_{i-1,j}$。

最后再让 $f_{i,j}$ 加上 $f_{i-1, j}$。

T5

显然的，考虑分层图，由于是对边进行加操作，所以直接在 $u$ 或在 $v$ 之间建立层与层之间的联系都不行，于是可以考虑将 $u \to v$ 变成 $u \to tmp \to v$，然后对于每条边都有一个 $tmp$，然后层与层之间就让 $tmp$ 之间连边即可。

然后就是直接缩点求最长路即可。

时间复杂度 $O((n + m)k)$。

T1 std:

#include <bits\/stdc++.h>

#define int long long

using namespace std;

const int N = 100010;

int n;
int a[N], b[N], c[N];
int f[N], ans[N << 1], idx;

signed main() {
    for (int i = 1; i <= N; ++i)
        f[i] = i * i;
    for (int i = 1; i <= N; ++i)
        c[i] = f[i] - f[i - 1];

    scanf("%lld", &n);
    n \/= 2ll;
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &b[i]);

    int l = 1, r = 1, now = 0, tmp = 0, cnt;
    for (int i = 1; i <= n; ++i) {
        l = r = now + 2;
        cnt = c[l];

        while (cnt != b[i] && l <= r) {
            if (cnt < b[i]) {
                ++r;
                cnt += c[r];
            }
            if (cnt > b[i]) {
                cnt -= c[l];
                l++;
            }
        }

        if (l > r) {
            puts("Impoissble");
            return 0;
        }

        ans[++idx] = f[l - 1] - tmp;
        ans[++idx] = b[i];

        now = r;
        tmp = f[now];
    }

    for (int i = 1; i <= idx; ++i)
        printf("%lld ", ans[i]);

    return 0;
}

T2

#include <bits\/stdc++.h>

using namespace std;

#define int long long

const int N = 200010;

int n, q;
int a[N];
struct Node {
    int maxn, minn, sum;
    int tag;

    const Node operator+(Node b) {
        Node res = {0, 0, 0};
        res.maxn = max(maxn, b.maxn);
        res.minn = min(minn, b.minn);
        res.sum = sum + b.sum;

        return res;
    }
} tr[N << 2];

void pushdown(int u, int l, int r) {
    if (tr[u].tag == -114514) return;

    int mid = (l + r) >> 1;

    tr[u << 1].tag = tr[u << 1 | 1].tag =
    tr[u << 1].minn = tr[u << 1 | 1].minn =
    tr[u << 1].maxn = tr[u << 1 | 1].maxn =
    tr[u].tag;

    tr[u << 1].sum = tr[u].tag * (mid - l + 1);
    tr[u << 1 | 1].sum = tr[u].tag * (r - mid);
    tr[u].tag = -114514;
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u].tag = -114514;
        tr[u].minn = tr[u].maxn = tr[u].sum = a[l];
        return;
    }

    int mid = (l + r) >> 1;

    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);

    tr[u] = tr[u << 1] + tr[u << 1 | 1];
    tr[u].tag = -114514;
}

void modify(int u, int l, int r, int ql, int qr, int t) {
    if (l >= ql && r <= qr) {
        tr[u].minn = tr[u].maxn = tr[u].tag = t;
        tr[u].sum = t * (r - l + 1);
        return ;
    }

    pushdown(u, l, r);
    int mid = (l + r) >> 1;

    if (ql <= mid) modify(u << 1, l, mid, ql, qr, t);
    if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, t);
    
    int tmp = tr[u].tag;
    tr[u] = tr[u << 1] + tr[u << 1 | 1];
    tr[u].tag = tmp;
}

int query(int u, int l, int r, int ql, int qr, int y) {
    if (l == r) {
        if (tr[u].minn >= y) return -1;
        return l;
    }

    if (tr[u].minn >= y) return -1;
    if (r < ql) return -1;

    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    int res = query(u << 1, l, mid, ql, qr, y);
    if (res != -1) return res;

    return query(u << 1 | 1, mid + 1, r, ql, qr, y);
}

int query1(int u, int l, int r, int &y) {
    if (tr[u].sum <= y) {
        y -= tr[u].sum;
        return r - l + 1;
    }

    if (l == r)
        return 0;

    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    int ans = 0;
    if (tr[u << 1].minn <= y) ans += query1(u << 1, l, mid, y);
    if (tr[u << 1 | 1].minn <= y) ans += query1(u << 1 | 1, mid + 1, r, y);

    return ans;
}

Node query(int u, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return tr[u];

    pushdown(u, l, r);
    int mid = (l + r) >> 1;

    Node res;
    res.tag = -1;

    if (ql <= mid) res = query(u << 1, l, mid, ql, qr);
    if (qr > mid) {
        if (res.tag == -1) res = query(u << 1 | 1, mid + 1, r, ql, qr);
        else res = res + query(u << 1 | 1, mid + 1, r, ql, qr);
    }

    return res;
}

signed main() {
    \/\/ freopen("ys1.in", "r", stdin);
    \/\/ freopen("ys1.out", "w", stdout);
    scanf("%lld%lld", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);

    build(1, 1, n);

    for (int i = 1; i <= q; ++i) {
        int opt, x, y;
        scanf("%lld%lld%lld", &opt, &x, &y);

        if (opt == 1) {
            int l = query(1, 1, n, 1, x, y);

            if (l == -1) continue;
            modify(1, 1, n, l, x, y);
        } else {
            if (x != 1)
                y += query(1, 1, n, 1, x - 1).sum;

            printf("%lld\n", query1(1, 1, n, y) - x + 1);
        }
    }
    return 0;
}

T3

#include <bits\/stdc++.h>

using namespace std;

const int N = 2e5 + 2;

int n, q;
string s;
int ne[N];

int find(int x, int k) {
    if (ne[x] > k) {
        ne[x] = find(ne[x], k);
    }
    return ne[x];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cin >> s;
    s = " " + s;

    for (int i = 2, j = 0; i < s.size(); ++i) {
        while (j && s[i] != s[j + 1])
            j = ne[j];

        if (s[i] == s[j + 1])
            j++;

        ne[i] = j;
    }

    vector<int> res(n + 1);

    for (int i = n; i >= 1; --i) {
        int ans = 1;
        for (int j = i + i; j <= n;) {
            int k = find(j, i);
            if (k == i) {
                ans = ans + 1;
                j = j + i;
            } else
                j = j + i - k;
        }

        res[ans] = max(i, res[ans]);
    }

    for (int i = n - 1; i >= 1; --i)
        res[i] = max(res[i + 1], res[i]);

    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int x;
        cin >> x;
        cout << res[x] << "\n";
    }
    return 0;
}

T4

#include <bits\/stdc++.h>

using namespace std;

#define int long long
const int mod = 1e9 + 7;

int n;
int f[510][510];
int ans;
vector<pair<int, int>> opt;

signed main() {
    scanf("%lld", &n);
    opt.push_back({1, 1});
    for (int i = 1; i <= n; ++i) {
        int s, x;
        scanf("%lld", &s);

        if (s == 1) {
            scanf("%lld", &x);
            opt.push_back({1, x});
        } else {
            opt.push_back({2, -1});
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (opt[i].first == 2)
            continue;

        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int j = 1; j < i; ++j) {
            for (int k = 0; k <= j; ++k) {
                if (opt[j].first == 1) {
                    f[j][k + (opt[i].second >= opt[j].second)] += f[j - 1][k];

                    if (f[j][k + (opt[i].second >= opt[j].second)] >= mod)
                        f[j][k + (opt[i].second >= opt[j].second)] -= mod;
                } else {
                    f[j][max(0ll, k - 1)] += f[j - 1][k];

                    if (f[j][max(0ll, k - 1)] >= mod)
                        f[j][max(0ll, k - 1)] -= mod;
                }
                f[j][k] = (f[j][k] + f[j - 1][k]) % mod;
                if (f[j][k] >= mod)
                    f[j][k] -= mod;
            }
        }

        for (int k = 0; k <= i; ++k)
            f[i][k] = f[i - 1][k];

        for (int j = i + 1; j <= n; ++j) {
            for (int k = 0; k <= j; ++k) {
                if (opt[j].first == 1) {
                    f[j][k + (opt[i].second > opt[j].second)] += f[j - 1][k];
                    if (f[j][k + (opt[i].second > opt[j].second)] >= mod)
                        f[j][k + (opt[i].second > opt[j].second)] -= mod;
                } else if (k) {
                    f[j][k - 1] += f[j - 1][k];
                    if (f[j][k - 1] >= mod)
                        f[j][k - 1] -= mod;
                }
                f[j][k] = (f[j][k] + f[j - 1][k]) % mod;
                if (f[j][k] >= mod)
                    f[j][k] -= mod;
            }
        }

        for (int j = 0; j <= n; ++j) {
            ans += f[n][j] * opt[i].second % mod;

            if (ans >= mod)
                ans -= mod;
        }
    }

    printf("%lld\n", ans);

    return 0;
}

T5

#include <bits\/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100010, M = 40;

int n, m, k;
int s, t;
queue<int> q;
int in[N * M];
ll a[N], b[N];
int stk[N * M], idx, ld;
int id[N * M];
int len;
array<ll, 4> Edge[4 * N * M];
int dfn[N * M], low[N * M], dfn_idx;
int e[4 * N * M], e1[4 * N * M], ne[4 * N * M], h[N * M], edge_idx;
pair<ll, ll> W[4 * N * M];
pair<ll, ll> w[N * M];    \/\/ 每个 scc 的权值
int cnt[N * M], cnt_scc;  \/\/ 每个点所在 scc 编号
array<ll, 4>
    dist[N * M];  \/\/ 表示S+F最大的S和F，以及S+F最大的且(S!=0,F!=0)的S，F

void add(int a, int b, ll s, ll f, int e[]) {
    W[edge_idx] = {s, f}, e[edge_idx] = b, ne[edge_idx] = h[a],
    h[a] = edge_idx++;
}

void tarjan(int u) {  \/\/ tarjan板子
    dfn[u] = low[u] = ++dfn_idx;
    stk[++idx] = u;
    in[u] = 1;

    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        \/\/ cout << u << ' ' << v << endl;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in[v])
            low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u]) {
        ++cnt_scc;
        id[cnt_scc] = u;
        \/\/ cout << u << ' ' << cnt_scc << ":";
        while (true) {
            int t = stk[idx];
            --idx;
            in[t] = 0;
            cnt[t] = cnt_scc;
            if (t == u)
                break;
        }
        \/\/ cout << endl;
    }
}

signed main() {
    memset(h, -1, sizeof(h));
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; ++i)
        scanf("%lld", &a[i]);
    for (int i = 1; i <= m; ++i)
        scanf("%lld", &b[i]);
    ld = n * (k + 1) + 1;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        ll s, f;
        scanf("%d%d%lld%lld", &u, &v, &s, &f);
        add(u, ++ld, s, f, e);
        Edge[++len] = {u, ld, s, f};
        add(ld, v, 0, 0, e);
        Edge[++len] = {ld, v, 0, 0};
        for (int j = 1; j <= k; ++j) {
            add(u + j * n, ++ld, s, f, e);
            Edge[++len] = {u + j * n, ld, s, f};
            add(ld, v + j * n, 0, 0, e);
            Edge[++len] = {ld, v + j * n, 0, 0};

            add(ld - 1, ld, a[i], 0, e);
            Edge[++len] = {ld - 1, ld, a[i], 0};
            add(ld - 1, ld, 0, b[i], e);
            Edge[++len] = {ld - 1, ld, 0, b[i]};
        }
    }

    scanf("%d%d", &s, &t);

    for (int i = 1; i <= k; ++i) {
        add(t + (i - 1) * n, t + i * n, 0, 0, e);
        Edge[++len] = {t + (i - 1) * n, t + i * n, 0, 0};
        add(s + (i - 1) * n, s + i * n, 0, 0, e);
        Edge[++len] = {s + (i - 1) * n, s + i * n, 0, 0};
    }

    for (int i = 1; i <= ld; ++i) {
        if (!dfn[i]) {
            tarjan(i);
            \/\/ cout << i << endl;
        }
    }

    edge_idx = 0;
    memset(h, -1, sizeof(h));

    for (int i = 1; i <= len; ++i) {
        ll u = Edge[i][0], v = Edge[i][1], s = Edge[i][2], f = Edge[i][3];
        if (cnt[u] != cnt[v]) {
            add(cnt[u], cnt[v], s, f, e1);
            \/\/ cout << u << "->" << v << ' ' << cnt[u] << "->" << cnt[v] <<
            \/\/ endl;
            ++in[cnt[v]];
        } else {
            w[cnt[u]].first += s;
            w[cnt[u]].second += f;
        }
    }

    for (int i = 1; i <= cnt_scc; ++i) {
        if (!in[i] && i != cnt[s]) {
            q.push(i);
        }
    }

    int T = cnt[s];

    while (q.size()) {
        auto t = q.front();
        q.pop();
        for (int i = h[t]; ~i; i = ne[i]) {
            int v = e1[i];
            if (!(--in[v])) {
                if (v == T)
                    continue;
                q.push(v);
            }
        }
    }

    q.push(T);
    dist[T][0] = w[T].first;
    dist[T][1] = w[T].second;

    while (q.size()) {
        auto t = q.front();
        q.pop();
        \/\/ cout << id[t] << endl;
        for (int i = h[t]; ~i; i = ne[i]) {
            int v = e1[i], s = W[i].first, f = W[i].second;
            \/\/ cout << id[t] << ' ' << id[v] << ' ' << dist[t][0] << ' ' <<
            \/\/ dist[t][1] << ' ' << s << ' ' << f << endl;
            if (dist[t][0] + dist[t][1] + s + f > dist[v][0] + dist[v][1]) {
                dist[v][0] = dist[t][0] + s;
                dist[v][1] = dist[t][1] + f;
            }
            if (dist[t][0] + dist[t][1] + s + f > dist[v][2] + dist[v][3] &&
                dist[t][0] + s > 0 && dist[t][1] + f > 0) {
                dist[v][2] = dist[t][0] + s;
                dist[v][3] = dist[t][1] + f;
            }
            if (dist[t][2] + dist[t][3] + s + f > dist[v][2] + dist[v][3] &&
                dist[t][2] + s > 0 && dist[t][3] + f > 0) {
                dist[v][2] = dist[t][2] + s;
                dist[v][3] = dist[t][3] + f;
            }

            if (!--in[v])
                q.push(v);
        }
    }

    t = cnt[k * n + t];

    \/\/ cout << t << ' ' << dist[t][0] << ' ' << dist[t][1] << endl;

    if (!dist[t][0] || !dist[t][1]) {
        if (!dist[t][2] || !dist[t][3]) {
            if (!dist[t][0])
                puts("I WANT SLUG");
            else if (!dist[t][1])
                puts("I WANT FOOD");
        } else
            printf("%lld\n", dist[t][2] + dist[t][3]);
    } else
        printf("%lld\n", dist[t][0] + dist[t][1]);

    return 0;
}
\/*
6 7 2
1 2 1 1 1 1 1
1 2 1 1 1 1 1
1 2 1 1
1 3 1 1
3 4 1 1
2 4 1 1
2 5 1 1
4 6 1 1
5 6 1 1
1 6

6 7 1
1 2 1 1 1 1 1
1 2 1 1 1 1 1
1 2 1 1
1 3 1 1
3 4 1 1
2 4 1 1
2 5 1 1
4 6 1 1
5 6 1 1
1 6
*\/