本文章由 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
*\/

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-18 13:59:42

A

一开始尝试直接输出的时候使用 %.lf 来四舍五入，但是发现 0.5 的时候会输出 0，最后还是用 $\lfloor a+0.5 \rfloor$ 来实现的四舍五入。

B

考虑先按照长度排序，对与长度相同的，把第一个数作为第一关键字，第二个数作为第二关键字以此类推，这样相等的一定是连续一段直接统计即可。

C

显然可以从 $n$ 开始 dfs 一遍，然后若遇到访问过的，那么它以及他后边需要的一定全解锁了，直接返回 $0$，否则继续下去，如果是叶子就是 $t_i$。

D

由于 $1 \le n \le 500$，考虑枚举两个点，那么对与这两个点，设最小满足的为 $(a,b)$，那么其他满足的一定是当前的倍数，所以我们可以求出任意两对点之间最小的 $(a,b)$ 然后扔到 set 里，然后看有多少不同即可。

E

一开始没看到要求每个点恰好一个出边，还以为不可做。

若最后可以使每个点恰好有一个出边，那么整个图就是若干个环，而每个环有两种方案，所以答案就是 $2^{\text{环的个数}}$。

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

using namespace std;

namespace A {
	long double n;
	void main() {
	    scanf("%Lf", &n);
	    printf("%.0Lf", floor(n + 0.5));
	}
}

namespace B {
	int n;
	vector<vector<int>> v;
	void main() {
		scanf("%d", &n);
		v.push_back({});
		for (int i = 1; i <= n; ++i) {
			int l; scanf("%d", &l);
			v.push_back({});
			for (int j = 1; j <= l; ++j) {
				int a; scanf("%d", &a);
				v[i].push_back(a);
			}
		}
		
		sort(v.begin(), v.end(), [&](vector<int> a, vector<int> b) {
			if (a.size() != b.size()) return a.size() < b.size();
			return a < b;
		});
		
		int ans = n;
		for (int i = 2; i <= n; ++i) {
			if (v[i] == v[i - 1]) --ans;
		}
		
		printf("%d\n", ans);
	}
}

namespace C {
	typedef long long ll;
	int n;
	ll t[200010];
	vector<int> e[200010];
	bool st[200010];
	
	ll dfs(int u) {
		if (st[u]) return 0;
		st[u] = true;
		
		ll res = 0;
		for (auto t : e[u]) {
			res += dfs(t);
		}
		
		return res + t[u];
	}
	
	void main() {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			scanf("%lld", &t[i]);
			int l; scanf("%d", &l);
			for (int j = 1; j <= l; ++j) {
				int c; scanf("%d", &c);
				e[i].push_back(c);
			}
		}
		
		printf("%lld\n", dfs(n));
	}
}

namespace D {
	int n;
	pair<int, int> a[510];
	
	int gcd(int a, int b) {
		return !b ? a : gcd(b, a % b);
	}
	
	void main() {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			scanf("%d%d", &a[i].first, &a[i].second);
		}
		
		set<pair<int, int>> cnt;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				if (i != j) {
					int tx = a[i].first - a[j].first, ty = a[i].second - a[j].second;
					int t = abs(gcd(tx, ty));
					
					cnt.insert({tx \/ t, ty \/ t});
				}
			}
		}
		
		printf("%d\n", cnt.size());
	}
}

namespace E {
	const int mod = 998244353;
	int n, m;
	vector<int> e[200010];
	bool st[200010];
	int cntE, cntV;

	void dfs(int u) {
		st[u] = true;
		++cntV;
		cntE += e[u].size();

		for (auto v : e[u]) {
			if (!st[v]) {
				dfs(v);
			}
		}
	}
	
	void main() {
		int ans = 1;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; ++i) {
			int u, v; scanf("%d%d", &u, &v);
			e[u].push_back(v);
			e[v].push_back(u);
		}
		
		for (int i = 1; i <= n; ++i) {
			if (!st[i]) {
				cntE = cntV = 0;
				dfs(i);
				
				if (cntE != cntV * 2) ans = 0;
				else {
					ans *= 2;
					if (ans >= mod) ans -= mod;
				}
			}
		}
		
		printf("%d\n", ans);
	}
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-18 14:08:28

A

直接模拟即可

B

直接暴力预处理出所有在 $1 ... 1000$ 中可以被 $4ab + 3a + 3b$ 表示出的数即可。

C

直接暴力时间复杂度是正确的。

D

套路题，之前做过类似的。

二分之后将所有点与 $mid$ 取 $\min$，此时只要 $\sum a_i$ 是 $\ge mid \cdot k$ 的就合法否则不合法，因为对 $mid$ 取 $\min$ 就相当于限制了每个数选的次数。

E

考虑记搜，枚举所有排列其实可以每次把一个字符扔到前面来实现，而由于我们只关心最后状态是什么不关心中途是怎么换的，那么把某个字符扔到前面实际上只用选最前面的字符即可。

然后把字符串 $S$ 和剩余步数记录一下即可。

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

using namespace std;

namespace A{
	int n, k, a;
	void main() {
		scanf("%d%d%d", &n, &k, &a);
		for (int i = 1; i < k; ++i) {
			a = a % n + 1;
		}
		
		printf("%d\n", a);
	}
}

namespace B {
	int n, s;
	bool st[10100];
	
	void init() {
		for (int i = 1; i <= 1000; ++i) {
			for (int j = 1; j <= 1000; ++j) {
				if (4 * i * j + 3 * i + 3 * j > 1000) break;
				st[4 * i * j + 3 * i + 3 * j] = true;
			}
		}
	}
	
	void main() {
		init();
		int ans = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			int a;
			scanf("%d", &a);
			ans += !st[a];
		}
		
		printf("%d\n", ans);
	}
}

namespace C {
	typedef long long ll;
	
	ll n;
	
	void main() {
		scanf("%lld", &n);
		ll ans = 0;
		for (ll A = 1; A * A * A <= n; ++A) {
			for (ll B = A; A * B * B <= n; ++B) {
				ll C = n \/ (A * B) - B + 1;
				ans += C;
			}
		}
		
		printf("%lld\n", ans);
	}
}

namespace D {
	typedef long long ll;
	int n, k;
	ll a[200010];
	
	bool check(ll mid) {
		ll sum = 0;
		for (int i = 1; i <= n; ++i) {
			sum += min(a[i], mid);
		}
		
		return sum \/ k >= mid;
	}

	void main() {
		scanf("%d%d", &n, &k);
		for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
		
		ll l = 1, r = 200000000000000000;
		while (l < r) {
			ll mid = (l + r + 1) >> 1ll;
			if (check(mid)) l = mid;
			else r = mid - 1;
		}
		
		printf("%lld\n", l);
	}
}

namespace E {
	typedef long long ll;
	int k;
	string s;
	map<pair<string, int>, ll> ma;
	
	ll dfs(string s, int k) {
		if (k < 0) return 0;
		if (s.size() <= 1) return 1;
		if (ma.count({s, k})) return ma[{s, k}];
		
		ll res = 0;
		for (int i = 0; i < (int)s.size(); ++i) {
			if (s[i] == 'K') {
				string t;
				for (int j = 0; j < i; ++j) t += s[j];
				for (int j = i + 1; j < (int)s.size(); ++j) t += s[j];
				
				res += dfs(t, k - i);

				break;
			}
		}
		for (int i = 0; i < (int)s.size(); ++i) {
			if (s[i] == 'E') {
				string t;
				for (int j = 0; j < i; ++j) t += s[j];
				for (int j = i + 1; j < (int)s.size(); ++j) t += s[j];
				
				res += dfs(t, k - i);

				break;
			}
		}
		for (int i = 0; i < (int)s.size(); ++i) {
			if (s[i] == 'Y') {
				string t;
				for (int j = 0; j < i; ++j) t += s[j];
				for (int j = i + 1; j < (int)s.size(); ++j) t += s[j];
				
				res += dfs(t, k - i);

				break;
			}
		}
		
		return ma[{s, k}] = res;
	}
	
	void main() {
		cin >> s >> k;
		cout << dfs(s, k);
	}
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-04 18:33:02

T3 线段树

我是小丑

build(1, 0, n);
modify(1, 0, Maxn, 0, 0);

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-06 10:10:06

前置知识：

杨表

看到最长上升/下降子序列长度还有计数，考虑杨表。

然后有一个结论，就是杨表的第一行的长度就是这个序列的最长上升子序列的长度，第一列的长度就是这个序列的最长下降子序列的长度。

由于这道题固定了最长上升子序列和最长下降自序的长度，并且长度为 $AB - 1$，那么最后杨表一定是长这个样子的：

然后由于最后要加上 $n + 0.5$，并且数量不变，所以要把 $n + 0.5$ 扔到 $b_{1,A}$ 上，并且把所以 $b_{i, A} (1 \le i < B)$ 都一一放到 $b_{i, A} (2 \le i \le B)$ 上。

那么我们要满足：

$b_{i + 1, A - 1} < b_{i, A}$，因为这样才能让 $n + 0.5$ 插进去后所有的 $b_{i, A}$ 都到 $b_{i + 1, A}$ 上。

由于数据范围极小，那么我们可以考虑暴力 $DP$。

设 $f_{a_1,a_2, \dots, a_A}$ 表示杨表第 $i$ 列填了 $a_i$ 个数的序列个数。

那么这个直接暴力转移，枚举当前数填到哪里，只要 $a_i < a_{i - 1}$，那么就可以从 $a_1, a_2, \dots, a_i, \dots, a_A$ 转移到 $a_1, a_2, \dots, a_i + 1, \dots, a_A$。

再统计合法的杨表的数量，那么我们设 $f_{a_1, a_2, \dots, a_n}$ 表示满足的杨表个数。

那么我们考虑大部分转移和上一部分是一样的，不过对于 $a_A$，它必须 $< a_{A - 1} - 1$ 才能转移，因为如果是 $< a_{A - 1}$，那么当前这个数填到 $a_A$ 上后，若 $a_A = a_{A - 1}$ 并且 $a_{A - 1}$ 还未填，那么我们就会发现再填上一个数之后就有一个不满足 $b_{i + 1, A - 1} < b_{i, A}$。

然后就做完了。

Code

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

using namespace std;

int A, B, mod;
map<vector<int>, int> f;

int dp1() {
	f.clear();
	f[vector<int> (A, 0)] = 1;

	for (auto [u, v] : f) {
		vector<int> t = u;
		for (int i = 0; i < A; ++i) {
			int lim = (i == 0) ? (B) : (u[i - 1]);

			if (u[i] < lim) {
				++t[i];

				f[t] += v;
				if (f[t] >= mod) f[t] -= mod;

				--t[i];
			}
		}
	}

	vector<int> t(A, B);
	return f[t];
}

int dp2() {
	f.clear();
	f[vector<int> (A, 0)] = 1;

	for (auto [u, v] : f) {
		vector<int> t = u;
		for (int i = 0; i < A; ++i) {
			int lim = (i == 0) ? B : ((i == A - 1) ? (u[i - 1] - 1) : (u[i - 1]));

			if (t[i] < lim) {
				++t[i];

				f[t] += v;
				if (f[t] >= mod) f[t] -= mod;

				--t[i];
			}
		}
	}

	vector<int> t(A, B);
	t[A - 1] = B - 1;

	return f[t];
}

int main() {
	scanf("%d%d%d", &A, &B, &mod);

	int res1 = dp1();
	cout << res1 << endl;
	int res2 = dp2();

	printf("%d\n", 1ll * res1 * res2 % mod);

	return 0;
}

当然，我们也可以先在第 $A$ 列选一个（也就是 $n + 0.5$ 的位置），然后再填其他的，这样也是可以的。

这里只给出和上一个方法不同的地方。

Code:

int dp2() {
	f.clear();
	vector<int> a(A, 0);
	a.back() = 1;
	f[a] = 1;

	for (auto [u, v] : f) {
		vector<int> t = u;
		for (int i = 0; i < A; ++i) {
			int lim = (i == 0) ? B : (u[i - 1]);

			if (t[i] < lim) {
				++t[i];

				f[t] += v;
				if (f[t] >= mod) f[t] -= mod;

				--t[i];
			}
		}
	}

	vector<int> t(A, B);

	return f[t];
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-15 21:30:01

我们发现，这就是给你一个矩阵，第 $i$ 行第 $j$ 列的权值是 $\left | A_i - B_j \right |$，有 $k$ 个询问，每次问你矩阵里 $(1,1)$ 到 $(x,y)$ 的和。

然后我么发现每个矩阵都有一个 $(1, 1)$ 固定，只有 $(x,y)$ 在变，所以就直接类似一维莫队，然后维护两个权值线段树，一个维护当前扫到的所有 $B_j$，另一个维护当前扫到的所有 $A_i$。

然后考虑新加一个 $x + 1$，那么就是说多了 $\sum \left | A_{x + 1} - B_j \right |$，那么就把绝对值拆开，然后就是在维护 $B$ 的权值线段树上，查 $\le A_{x + 1}$ 的 $B_j$ 的和以及数量，以及 $> A_{x + 1}$ 的 $B_j$ 的和以及数量，然后删除和关于 $y$ 的类似，然后就做完了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-02 07:42:24

思路：

我们发现对于长度为 $6$ 的 $C$，对应的 $A, B$ 本质都是相同的。

即当 $C=\texttt{001001}$ 时 $A = \texttt{010101}$ 而 $B = \texttt{101010}$。

$A$ 与 $B$ 的区别就是把前三个和后三个交换了一下，但是由于 $C$ 每三个都是相同的，所以每六个 $A,B$ 的贡献是一样的。

然后由于长度为 $3^n$，所以一共有 $3^{n-1}$ 个 $3$。由于 $3^{n-1}$ 一定为奇数，所以一共有 $\frac{3^{n-1}-1}{2}$ 个 $6$ 以及一个 $3$。

那么每个 $6$ 的贡献一定是 $3$，所以考虑多余的一个 $3$ 贡献是多少。

那么一定是 $\texttt{010}$ 贡献最少为 $1$。

然后按照上边说的写即可。

Code:

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

using namespace std;

typedef long long ll;
int T;
ll n;

const int mod = 1e9 + 7;

ll power(ll a, ll b) {
	ll res = 1;
	for (; b; b >>= 1, a = a * a % mod)
		if (b & 1) res = res * a % mod;

	return res;
}

signed main(){
	scanf("%d", &T);
	while (T--) {
		scanf("%lld", &n);
		if (n == 1) printf("1\n");
		else {
			printf("%lld\n", ((power(3, n - 1) - 1 + mod) % mod) * power(2, mod - 2) % mod * 3ll % mod + 1);
		}
	}
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-06 12:58:21

思路：

首先有一个性质，就是我们选中一个颜色后，在选另一个颜色，最多能解锁 $3$ 个当前颜色，证明很简单，首先最多是四个，然后若是 $4$ 的的话那么说明那个颜色与当前块不连通，所以至多三个。

由于矩形很大，于是可以考虑横着构造，若不够则在两边再选即可。

复杂度 $O(Tn)$。

Code：

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

using namespace std;

int T;
int x, y;

int main() {
	scanf("%d", &T);

	while (T--) {
		scanf("%d%d", &x, &y);
		if (3 * x + 1 < y || 3 * y + 1 < x) puts("NO");
		else {
			puts("YES");
			if (x == y) {
				int X1 = 100000, Y1 = 100000;
				for (int i = 1; i <= y; ++i) {
					printf("%d %d\n", X1, Y1);
					printf("%d %d\n", X1, Y1 + 1);
					Y1 += 2;
				}
			} else if (x > y) {
				printf("%d %d\n", 100000, 100001);
				int X1 = 100000, Y1 = 100002;
				int tmp = max(0, x - y - 1);
				for (int i = 1; i <= y; ++i) {
					printf("%d %d\n", X1, Y1);
					printf("%d %d\n", X1, Y1 + 1);
					if (tmp) {
						printf("%d %d\n", X1 + 1, Y1);
						--tmp;
					}
					if (tmp) {
						printf("%d %d\n", X1 - 1, Y1);
						--tmp;
					}
					Y1 += 2;
				}
			} else {
				printf("%d %d\n", 100000, 100000);
				int X1 = 100000, Y1 = 100001;
				int tmp = max(0, y - x - 1);
				for (int i = 1; i <= x; ++i) {
					printf("%d %d\n", X1, Y1);
					printf("%d %d\n", X1, Y1 + 1);
					if (tmp) {
						printf("%d %d\n", X1 - 1, Y1);
						--tmp;
					}
					if (tmp) {
						printf("%d %d\n", X1 + 1, Y1);
						--tmp;
					}
					Y1 += 2;
				}
			}
		}
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-06 17:37:53

思路:

先考虑 $n=2$ 怎么做，以 $n=2,m=3$ 为例：

那么显然可以这么走：

也就是是两边是对称的，所以这些增量都是形如 $(x,y_1),(-x,y_1),\dots$，而每个 $x,-x$ 循环中 $y$ 都不同那么是合法的。

进一步总结得出：

设当前坐标为 $(x, y)$。

• 若当前在上方，那么下一次坐标就是 $(x+1,m-y+1)$
• 若当前在下方，那么下一次坐标就是 $(x+1,m-y)$

而当 $n > 2$ 时，依以 $m=3$ 为例：

有一种走法时这样的：

有没有发现什么规律？

首先对于 $(1,n),(2,n-1),\dots$ 这些行对之间仅有一条连边。

如图上 $(1,4)$ 与 $(2,3)$ 这两个行对之间仅有 $(4,1) \to (2,1)$ 这一条边。

然后在每个行对中按照上面总结的做即可。

若最后还剩一行的话，那么可以考虑 $x$ 不变 $y$ 是 $1 \to m \to 2 \to (m -2)\dots$。

然后就做完啦。

Code:

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

using namespace std;

int n, m;
bool st[1000010];

void dfs(int i, int j) {
	if (i > j) return;
	if (i == j) {
		for (int t1 = m, t2 = 1; t1 >= t2; --t1, ++t2) {
			if (t1 == t2) {
				printf("%d %d\n", i, t1);
			} else {
				printf("%d %d\n", i, t2);
				printf("%d %d\n", i, t1);
			}
		}
	} else {
		for (int dx = 1; dx <= m; ++dx) {
			if (dx == m) {
				printf("%d %d\n", j, m - dx + 1);
				if (i + 1 != j) {
					if (i + 1 != j - 1)
						printf("%d %d\n", i + 1, 1);
					dfs(i + 1, j - 1);
				}
				continue;
			}
			printf("%d %d\n", j, m - dx + 1);
			printf("%d %d\n", i, dx + 1);
		}
	}
}

int main() {
	scanf("%d%d", &n, &m);
	if (n != 1)
		printf("%d %d\n", 1, 1);
	dfs(1, n);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-07 13:21:54

思路：

显然可以考虑第一行放横着的，第二行放竖着的，然后用变量维护一下各自的 $y$ 坐标，看是否充满一行即可。

Code：

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

using namespace std;

string s;
int Y0 = 1, Y1 = 1;

int main() {
	cin >> s;

	for (int i = 0; i < (int)s.size(); ++i) {
		if (s[i] == '0') {
			printf("2 %d\n", Y1);

			Y1++;
			if (Y1 > 4) Y1 = 1;
		} else {
			printf("1 %d\n", Y0);

			Y0 += 2;
			if (Y0 > 4) Y0 = 1;
		}
	}

	return 0;
}