2026“钉耙编程”暑期联赛（2）

1001. xyz 问题

2-SAT
强连通分量
构造

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
const int mod = 998244353;
const int INF = 1e18;
const int N = 30;

void init() {}
struct Tarjan {
    vector<vector<int>> graph;
    vector<int> dfn, low, scc, stk;
    vector<bool> instk;
    int n, cnt = 0, scc_cnt = 0;

    Tarjan(int n) : n(n) {
        graph.resize(n + 1);
        dfn.resize(n + 1);
        low.resize(n + 1);
        scc.resize(n + 1);
        instk.resize(n + 1);
    }

    void add_edge(int u, int v) {
        graph[u].push_back(v);
    }
    void dfs(int u) {
        dfn[u] = low[u] = ++cnt;
        stk.push_back(u);
        instk[u] = true;
        for (int v : graph[u]) {
            if (!dfn[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (instk[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            scc_cnt++;
            while (true) {
                int v = stk.back();
                stk.pop_back();
                instk[v] = false;
                scc[v] = scc_cnt;
                if (v == u) {
                    break;
                }
            }
        }
    }

    void work() {
        for (int i = 1; i <= n; i++) {
            if (dfn[i]) {
                continue;
            }
            dfs(i);
        }
    }
};

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    Tarjan tj(n * 2 + m * 4);
    auto getx = [&](int i, bool b) {
        return i + n * b;
    };
    auto getop = [&](int i, bool b, bool c) {
        return i + n * 2 + m * 2 * b + m * c;
    };
    for (int i = 1; i <= m; i++) {
        tj.add_edge(getop(i, 1, 1), getop(i, 0, 0));
        tj.add_edge(getop(i, 0, 1), getop(i, 1, 0));
    }
    for (int i = 1; i <= k; i++) {
        int x, op, y, z;
        cin >> x >> op >> y >> z;
        if (z == 1) {
            if (y == 1) {
                tj.add_edge(getx(x, 0), getop(op, 0, 0));
                tj.add_edge(getop(op, 0, 1), getx(x, 1));
                tj.add_edge(getop(op, 1, 1), getx(x, 0));
                tj.add_edge(getx(x, 1), getop(op, 1, 0));
            } else {
                tj.add_edge(getx(x, 0), getx(x, 1));
                tj.add_edge(getop(op, 0, 1), getop(op, 0, 0));
            }
        } else {
            if (y == 1) {
                tj.add_edge(getx(x, 1), getop(op, 1, 1));
                tj.add_edge(getop(op, 1, 0), getx(x, 0));
                tj.add_edge(getx(x, 0), getop(op, 0, 1));
                tj.add_edge(getop(op, 0, 0), getx(x, 1));
            } else {
                tj.add_edge(getx(x, 1), getop(op, 0, 1));
                tj.add_edge(getop(op, 0, 0), getx(x, 0));

            }
        }
    }
    tj.work();
    for (int i = 1; i <= n; i++) {
        if (tj.scc[getx(i, 0)] == tj.scc[getx(i, 1)]) {
            cout << "NO\n";
            return;
        }
    }
    for(int i = 1; i <= m; i++){
        if(tj.scc[getop(i, 0, 0)] == tj.scc[getop(i, 0, 1)]){
            cout << "NO\n";
            return;
        }
        if(tj.scc[getop(i, 1, 0)] == tj.scc[getop(i, 1, 1)]){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    string ans1, ans2;
    for(int i = 1; i <= n; i++){
        if(tj.scc[getx(i, 0)] > tj.scc[getx(i, 1)]){
            ans1 += '1';
        }else{
            ans1 += '0';
        }
    }
    for(int i = 1; i <= m; i++){
        int tg1= tj.scc[getop(i, 0, 0)]>tj.scc[getop(i, 0, 1)];
        int tg2= tj.scc[getop(i, 1, 0)]>tj.scc[getop(i, 1, 1)];
        if((!tg1)&&(!tg2)){
            ans2 += '|';
        }else if(tg1){
            ans2+='&';
        }else{
            ans2+='^';
        }
    }
    cout << ans1 << '\n' << ans2 << '\n';
}

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

1002. 表达式 2

快速傅里叶变换
分治
线性代数

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'

const int mod = 998244353;
const int INF = 1e18;

namespace FastPolyMat {

using u32 = uint32_t;
using u64 = uint64_t;
using i32 = int32_t;

static constexpr u32 MOD = 998244353;
static constexpr u32 G = 3;

u32 qpow(u32 a, u32 b) {
    u32 res = 1;
    while (b) {
        if (b & 1) res = (u64)res * a % MOD;
        a = (u64)a * a % MOD;
        b >>= 1;
    }
    return res;
}

static vector<u32> roots{0, 1};
static vector<vector<i32>> rev_cache(24);
static u32 inv_len[24];

void prepare_roots(i32 n) {
    if ((i32)roots.size() >= n) return;

    i32 k = __builtin_ctz((u32)roots.size());
    roots.resize(n);

    while ((1 << k) < n) {
        u32 e = qpow(G, (MOD - 1) >> (k + 1));

        for (i32 i = 1 << (k - 1); i < (1 << k); i++) {
            roots[i << 1] = roots[i];
            roots[i << 1 | 1] = (u64)roots[i] * e % MOD;
        }

        k++;
    }
}

const vector<i32>& get_rev(i32 n) {
    i32 lg = __builtin_ctz((u32)n);
    auto &rev = rev_cache[lg];

    if (!rev.empty()) return rev;

    rev.resize(n);

    for (i32 i = 1; i < n; i++) {
        rev[i] = (rev[i >> 1] >> 1)
               | ((i & 1) << (lg - 1));
    }

    inv_len[lg] = qpow((u32)n, MOD - 2);

    return rev;
}

void ntt(vector<u32> &a, bool invert = false) {
    i32 n = (i32)a.size();

    prepare_roots(n);
    const auto &rev = get_rev(n);

    for (i32 i = 0; i < n; i++) {
        if (i < rev[i]) {
            swap(a[i], a[rev[i]]);
        }
    }

    for (i32 len = 1; len < n; len <<= 1) {
        for (i32 i = 0; i < n; i += len << 1) {
            for (i32 j = 0; j < len; j++) {
                u32 u = a[i + j];
                u32 v = (u64)a[i + j + len]
                      * roots[len + j] % MOD;

                u32 x = u + v;
                if (x >= MOD) x -= MOD;

                u32 y = (u >= v ? u - v : u + MOD - v);

                a[i + j] = x;
                a[i + j + len] = y;
            }
        }
    }

    if (invert) {
        reverse(a.begin() + 1, a.end());

        u32 inv_n = inv_len[__builtin_ctz((u32)n)];

        for (u32 &x : a) {
            x = (u64)x * inv_n % MOD;
        }
    }
}

/*
a[0] = (0, 0)
a[1] = (0, 1)
a[2] = (1, 0)
a[3] = (1, 1)
*/
struct Mat {
    array<vector<u32>, 4> a;


    i32 cnt = 0;
};

Mat multiply(Mat A, Mat B) {
    i32 need = A.cnt + B.cnt + 1;

    Mat C;
    C.cnt = A.cnt + B.cnt;

    for (auto &v : C.a) {
        v.assign(need, 0);
    }


    if ((int64_t)(A.cnt + 1) * (B.cnt + 1) <= 512) {
        for (i32 i = 0; i <= A.cnt; i++) {
            for (i32 j = 0; j <= B.cnt; j++) {
                i32 k = i + j;

                C.a[0][k] = (
                    C.a[0][k]
                    + (u64)A.a[0][i] * B.a[0][j]
                    + (u64)A.a[1][i] * B.a[2][j]
                ) % MOD;

                C.a[1][k] = (
                    C.a[1][k]
                    + (u64)A.a[0][i] * B.a[1][j]
                    + (u64)A.a[1][i] * B.a[3][j]
                ) % MOD;

                C.a[2][k] = (
                    C.a[2][k]
                    + (u64)A.a[2][i] * B.a[0][j]
                    + (u64)A.a[3][i] * B.a[2][j]
                ) % MOD;

                C.a[3][k] = (
                    C.a[3][k]
                    + (u64)A.a[2][i] * B.a[1][j]
                    + (u64)A.a[3][i] * B.a[3][j]
                ) % MOD;
            }
        }

        return C;
    }

    i32 ntt_size = 1;
    while (ntt_size < need) {
        ntt_size <<= 1;
    }

    for (auto &v : A.a) v.resize(ntt_size);
    for (auto &v : B.a) v.resize(ntt_size);


    for (auto &v : A.a) ntt(v);
    for (auto &v : B.a) ntt(v);

    for (auto &v : C.a) {
        v.resize(ntt_size);
    }


    for (i32 i = 0; i < ntt_size; i++) {
        C.a[0][i] = (
            (u64)A.a[0][i] * B.a[0][i]
            + (u64)A.a[1][i] * B.a[2][i]
        ) % MOD;

        C.a[1][i] = (
            (u64)A.a[0][i] * B.a[1][i]
            + (u64)A.a[1][i] * B.a[3][i]
        ) % MOD;

        C.a[2][i] = (
            (u64)A.a[2][i] * B.a[0][i]
            + (u64)A.a[3][i] * B.a[2][i]
        ) % MOD;

        C.a[3][i] = (
            (u64)A.a[2][i] * B.a[1][i]
            + (u64)A.a[3][i] * B.a[3][i]
        ) % MOD;
    }

    for (auto &v : C.a) {
        ntt(v, true);
        v.resize(need);
    }

    return C;
}
Mat make_leaf(u32 d) {
    Mat M;

    M.cnt = 1;

    M.a[0] = {10, d};
    M.a[1] = {0, 1};
    M.a[2] = {d, 0};
    M.a[3] = {1, 0};

    return M;
}
Mat build(const string &str, i32 l, i32 r) {
    if (l == r) {
        return make_leaf((u32)(str[l] - '0'));
    }

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

    Mat L = build(str, l, mid);
    Mat R = build(str, mid + 1, r);


    return multiply(std::move(L), std::move(R));
}

vector<u32> work(const string &str) {
    i32 n = (i32)str.size();

    if (n == 1) {
        return {(u32)(str[0] - '0')};
    }

    // P = M_2 * M_3 * ... * M_n
    Mat P = build(str, 1, n - 1);

    vector<u32> ans(n);

    u32 d1 = str[0] - '0';

    /*
    [F_n, G_n] = [d_1, 1] * P

    F_n = d_1 * P00 + P10
    */
    for (i32 k = 0; k < n; k++) {
        ans[k] = (
            (u64)d1 * P.a[0][k]
            + P.a[2][k]
        ) % MOD;
    }

    return ans;
}

}
void init() {}

void solve() {
    int n;
    string s;

    cin >> n >> s;

    auto ans = FastPolyMat::work(s);

    for (int i = 0; i < n; i++) {
        cout << ans[i] << " \n"[i == n - 1];
    }
}

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

    init();

    int T;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

1003. 张力

字典树
动态规划
稀疏表

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'

const int mod = 998244353;
const int INF = 1LL << 62;
const int N = 2e5 + 5;

struct ST {
    int n, K;
    vvi st;
    vi lg;

    ST() {}

    // a 为 1-indexed
    ST(const vi& a) {
        init(a);
    }

    void init(const vi& a) {
        n = sz(a) - 1;

        lg.assign(n + 1, 0);
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i >> 1] + 1;
        }

        K = lg[n] + 1;
        st.assign(K, vi(n + 1, INF));
        st[0] = a;

        for (int k = 1; k < K; k++) {
            int len = 1LL << k;
            int half = len >> 1;

            for (int i = 1; i + len - 1 <= n; i++) {
                st[k][i] = min(
                    st[k - 1][i],
                    st[k - 1][i + half]
                );
            }
        }
    }

    int query(int l, int r) const {
        int k = lg[r - l + 1];

        return min(
            st[k][l],
            st[k][r - (1LL << k) + 1]
        );
    }
};

void init() {
}

void solve() {
    int n;
    cin >> n;

    vi a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int idx = 1;

    vector<array<int, 2>> g(50 * n + 5, {0, 0});
    vi cnt(50 * n + 5, 0);

    auto add = [&](int x) {
        int cur = 0;

        for (int dep = 0; dep < 50; dep++) {
            int b = (x >> dep) & 1LL;

            if (g[cur][b] == 0) {
                g[cur][b] = idx++;
            }

            cur = g[cur][b];
        }

        cnt[cur]++;
    };

    for (int x : a) {
        add(x);
    }

    auto dfs = [&](auto&& self, int u, int dep) -> pair<int, vi> {
        if (dep == 50) {
            int c = cnt[u];

            // c 个相同数字可以形成 1~c 个段，代价都是 0
            return {c, vi(c + 1, 0)};
        }

        pair<int, vi> l = {0, {}};
        pair<int, vi> r = {0, {}};

        if (g[u][0] != 0) {
            l = self(self, g[u][0], dep + 1);
        }

        if (g[u][1] != 0) {
            r = self(self, g[u][1], dep + 1);
        }

        if (l.f == 0) return r;
        if (r.f == 0) return l;

        // 枚举较小子树的段数
        if (l.f > r.f) {
            swap(l, r);
        }

        int ls = l.f;
        int rs = r.f;
        int w = 1LL << dep;

        // val[j] = f(R,j) + j*w
        vi val(rs + 1, INF);

        for (int j = 1; j <= rs; j++) {
            val[j] = r.s[j] + j * w;
        }

        ST st(val);

        vi dp(ls + rs + 1, INF);

        // k：合并后形成的段数
        for (int k = 1; k <= ls + rs; k++) {
            // i：左子树的段数
            for (int i = 1; i <= ls; i++) {
                // 合法右子树段数 j 的范围
                int ql = max(1LL, llabs(k - i));
                int qr = min(rs, k + i);

                if (ql > qr) continue;

                dp[k] = min(
                    dp[k],
                    l.s[i] + (i - k) * w
                    + st.query(ql, qr)
                );
            }
        }

        return {ls + rs, move(dp)};
    };

    cout << dfs(dfs, 0, 0).s[1] << endl;
}

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

    init();

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

1004. 坪厕鸡

线段树
优先队列
模拟

cpp

#include <iostream>
#include <queue>
#include <climits>
#include <tuple>

using namespace std;

typedef long long LL;
const int N = 200010;

struct Node {
    LL val, id, idx, len;
} tr[N * 4];
queue<tuple<int, int, int>> q[N];
LL res[N];

Node merge(Node a, Node b) {
    if (a.val < b.val) return a;
    else return b;
}

void modify(int u, int l, int r, int p, Node v) {
    if (l == r) tr[u] = v;
    else {
        int mid = l + r >> 1;
        if (p <= mid) modify(u << 1, l, mid, p, v);
        else modify(u << 1 | 1, mid + 1, r, p, v);
        tr[u] = merge(tr[u << 1], tr[u << 1 | 1]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // freopen("input", "r", stdin);
    int T;
    cin >> T;
    while (T--) {
        int n, m, k;
        cin >> n >> m >> k;
        for (int i = 1; i <= m; ++i) {
            int a, b, c;
            cin >> a >> b >> c;
            q[a].emplace(b, c, i); // time len idx
        }
        for (int i = 1; i <= n; ++i) {
            if (q[i].empty()) modify(1, 1, n, i, {LLONG_MAX, i});
            else {
                auto &[a, b, c] = q[i].front(); // time, len, idx
                modify(1, 1, n, i, {a, i, c, b}), q[i].pop();
            }
        }
        priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> pq;
        int cnt = m;
        LL cur = 0;
        while (cnt) {
            if ((pq.empty() || tr[1].val < pq.top().first) && pq.size() != k) {
                // cout << "starting" << endl;
                cur = max(cur, tr[1].val);
                res[tr[1].idx] = cur;
                cnt--;
                // cout << "time: " << cur << endl;
                // cout << "new test" << ' ' << tr[1].idx << endl;
                // cout << "emplacing " << cur + tr[1].len << ' ' << tr[1].id << endl;
                pq.emplace(cur + tr[1].len, tr[1].id);
                modify(1, 1, n, tr[1].id, {LLONG_MAX, tr[1].id});
            }
            else {
                // cout << "consuming" << endl;
                cur = max(cur, pq.top().first);
                // cout << "time: " << cur << endl;
                if (!pq.empty() && pq.top().first <= cur) {
                    auto [_, id] = pq.top();
                    // cout << "finished " << id << endl;
                    if (!q[id].empty()) {
                        auto &[a, b, c] = q[id].front();
                        // cout << "qwq " << id << endl;
                        modify(1, 1, n, id, {a, id, c, b});
                        q[id].pop();
                    }
                    pq.pop();
                }
            }
            // cout << endl;
        }
        // cout << pq.size() << endl;
        for (int i = 1; i <= m; ++i) cout << res[i] << ' ';
        // cout << '\n';
        cout << endl;
    }
    return 0;
}

1006. 合成大 hdu

构造
算术

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define debug(x) cout << #x << '=' << x << ' ';
#define DL cout << '\n';

void solve() {
	int n;
	cin >> n;

	string s;

	if (n <= 1500 * 1500) {
		int q = n / 1500;
		int r = n % 1500;
		if (r == 0) {
			s += string(1500, 'h');
			s += string(q, 'd');
			s += 'u';
		} else {
			s += string(r, 'h');
			s += 'd';
			s += string(1500 - r, 'h');
			s += string(q, 'd');
			s += 'u';
		}

	} else {
		int r = 1000 - n % 1000;
		int m = n - 999 * r;
		m /= 1000;
		int q = m / 999;
		int S = m % 999;
		//debug(r) debug(S) debug(q) DL
		s += string(r, 'h');
		s += 'd';
		s += string(1000-r, 'h');
		s += string(q, 'd');
		s += string(999 - S, 'u');
		if (S) s += 'd';
		s += string(S, 'u');
	}

	//cout << s.size() << '\n';
	cout << s << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t --) solve();
}

1007. 另一个 shu 论问题

莫比乌斯反演
启发式合并
树
深度优先搜索

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 2e5 + 5;
vi a[N];
std::vector<int> get_mu(int n) {
  std::vector<int> mu(n + 1), primes;
  std::vector<bool> not_prime(n + 1);
  primes.reserve(n);
  mu[1] = 1;
  for (int x = 2; x <= n; ++x) {
    if (!not_prime[x]) {
      primes.push_back(x);
      mu[x] = -1;
    }
    for (int p : primes) {
      if (x * p > n) break;
      not_prime[x * p] = true;
      if (x % p == 0) {
        mu[x * p] = 0;
        break;
      } else {
        mu[x * p] = -mu[x];
      }
    }
  }
  return mu;
}
vi mu=get_mu(N);
void init() {
    for(int i = 1; i < N; i++){
        for(int j = i; j <N; j+=i){
            a[j].pb(i);
        }
    }
}
void solve() {
    int n;
    cin >> n;
    vvi g(n+1);
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    vector<unordered_map<int, int>>m(n+1);
    for(int i = 1; i <= n; i++){
        for(auto x: a[i]){
            m[i][x]++;
        }
    }
    i64 ans = 0;
    auto dfs = [&](auto self, int u, int p) -> void {
        int res=0;
        for(auto v: g[u]){
            if(v == p) continue;
            self(self, v, u);
            if(sz(m[v]) > sz(m[u]))swap(m[u], m[v]);
            for(auto x: m[v]){
                if(m[u].count(x.f)&&x.f%u==0)ans+=(i64)x.s*m[u][x.f]*mu[x.f/u];
            }
            for(auto x: m[v]){
                m[u][x.f]+=x.s;
            }
            m[v].clear();
        }
    };
    dfs(dfs, 1, -1);
    cout << ans << endl;
}

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

1008. 最遥远的距离

构造
树

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 30;

void init() {}
void solve() {
    int n;
    cin >> n;
    vvi a(n + 1);
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        mx = max(mx, x);
        a[x].push_back(i);
    }
    int r = mx / 2 + 1;
    for (int i = 1; i < r; i++) {
        if (!a[i].empty()) {
            cout << "No\n";
            return;
        }
    }
    int cer = (mx % 2 == 0 ? 2 : 1);
    if ((int)a[r].size() != cer) {
        cout << "No\n";
        return;
    }
    for (int i = r + 1; i <= mx; i++) {
        if ((int)a[i].size() < 2) {
            cout << "No\n";
            return;
        }
    }
    auto pop = [&](int x) {
        int u = a[x].back();
        a[x].pop_back();
        return u;
    };
    vi cnt(n + 1);
    vpii ans;
    ans.reserve(n - 1);
    int cur = pop(mx);
    cnt[mx] = cur;
    for (int i = mx - 1; i >= r; i--) {
        int u = pop(i);
        ans.push_back({cur, u});
        cur = u;
        cnt[i] = u;
    }
    int start = (mx % 2 == 0 ? r : r + 1);

    for (int i = start; i <= mx; i++) {
        int u = pop(i);
        ans.push_back({cur, u});
        cur = u;
    }
    for (int i = r + 1; i <= mx; i++) {
        while (!a[i].empty()) {
            int u = pop(i);
            ans.push_back({u, cnt[i - 1]});
        }
    }

    cout << "Yes\n";
    for (auto [u, v] : ans) {
        cout << u << ' ' << v << '\n';
    }
}

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

1010. 幻灵战队 2

贪心
优先队列

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 30;

void init() {}
int get(int x){
    return x*20+5*(x+1)*x/2;
}
int get1(int x,int k){
    x-=k;
    int b=x/(k+1);
    int a=(k+1)*get(b);
    int c=(x-b*(k+1))*(20+5*(b+1));
    return a+c;
}
void solve() {
    int n,k;
    cin >> n>>k;
    string s;
    vpii a;
    cin >> s;
    int cnt = 0;
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == '0') cnt++;
        else{
            if(cnt){
                a.pb(mp(cnt, 0));
                ans += get(cnt);
                cnt = 0;
            }
        }
    }
    if(cnt){
        a.pb(mp(cnt, 0));
        ans += get(cnt);
        cnt = 0;
    }
    priority_queue<pair<int,pii>> q;
    for(auto i : a)q.push({get1(i.f,0)-get1(i.f,1),i});
    for(int i = 0; i < k; i++){
        if(q.empty())break;
        auto [x,y] = q.top();
        q.pop();
        y.s++;
        ans-=x;
        if(y.s!=y.f)q.push({get1(y.f,y.s)-get1(y.f,y.s+1),y});
    }
    cout<<ans<<endl;
}

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

1011. 键盘杀手

动态规划

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>
using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 30;

void init() {}
void solve() {
    int n;
    cin >> n;
    vi a(n+2);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vvi dp(n+1, vi(2));
    for(int i = 1; i <= n; i++){
        dp[i][0]=min(dp[i-1][0]+a[i+1],dp[i-1][1]+max(a[i-1],a[i+1]));
        dp[i][1]=min(dp[i-1][0],dp[i-1][1]+a[i-1]);
    }
    cout << min(dp[n][0],dp[n][1]) << endl;
}

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

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

1001. xyz 问题 ​

1002. 表达式 2 ​

1003. 张力 ​

1004. 坪厕鸡 ​

1006. 合成大 hdu ​

1007. 另一个 shu 论问题 ​

1008. 最遥远的距离 ​

1010. 幻灵战队 2 ​

1011. 键盘杀手 ​

1001. xyz 问题

1002. 表达式 2

1003. 张力

1004. 坪厕鸡

1006. 合成大 hdu

1007. 另一个 shu 论问题

1008. 最遥远的距离

1010. 幻灵战队 2

1011. 键盘杀手