NOIP全题解

userId_undefined

AC是最好的

秩序白银

2025-12-29 21:54:57

发布于：福建

7阅读
0回复
0点赞

T1；糖果店（candy）

题干

P14635 [NOIP2025] 糖果店

题目描述

小 X 开了一家糖果店，售卖 nn 种糖果，每种糖果均有无限颗。对于不同种类的糖果，小 X 采用了不同的促销策略。具体地，对于第 ii (1≤i≤n1 \le i \le n) 种糖果，购买第一颗的价格为 xix_i 元，第二颗为 yiy_i 元，第三颗又变回 xix_i 元，第四颗则为 yiy_i 元，以此类推。

小 R 带了 mm 元钱买糖果。小 R 不关心糖果的种类，只想得到数量尽可能多的糖果。你需要帮助小 R 求出，mm 元钱能购买的糖果数量的最大值。

输入格式

输入的第一行包含两个正整数 n,mn, m，代表糖果的种类数和小 R 的钱数。

输入的第 i+1i+1 (1≤i≤n1 \le i \le n) 行包含两个正整数 xi,yix_i, y_i，分别表示购买第 ii 种糖果时第奇数颗的价格和第偶数颗的价格。

输出格式

输出一行一个非负整数，表示 mm 元钱能购买的糖果数量的最大值。

输入输出样例 #1

输入 #1

2 10
4 1
3 3

输出 #1

4

输入输出样例 #2

输入 #2

3 15
1 7
2 3
3 1

输出 #2

8

说明/提示

【样例 1 解释】

小 R 可以购买 4 颗第一种糖果，共花费 4+1+4+1=104 + 1 + 4 + 1 = 10 元。

【样例 2 解释】

小 R 可以购买 1 颗第一种糖果、1 颗第二种糖果与 6 颗第三种糖果，共花费 1+2+12=151 + 2 + 12 = 15 元。

【样例 3】

见选手目录下的 candy/candy3.in 与 candy/candy3.ans。

该样例满足测试点 66 的约束条件。

【样例 4】

见选手目录下的 candy/candy4.in 与 candy/candy4.ans。

该样例满足测试点 8,98,9 的约束条件。

【样例 5】

见选手目录下的 candy/candy5.in 与 candy/candy5.ans。

该样例满足测试点 11,1211,12 的约束条件。

【样例 6】

见选手目录下的 candy/candy6.in 与 candy/candy6.ans。

该样例满足测试点 1313 的约束条件。

【样例 7】

见选手目录下的 candy/candy7.in 与 candy/candy7.ans。

该样例满足测试点 17,1817,18 的约束条件。

【数据范围】

对于所有测试数据，均有：

  • 1≤n≤1051 \le n \le 10^5；
  • 1≤m≤10181 \le m \le 10^{18}；
  • 对于所有 1≤i≤n1 \le i \le n，均有 1≤xi,yi≤1091 \le x_i, y_i \le 10^9。

::cute-table{tuack}

测试点编号 n≤n \le m≤m \le 特殊性质
11 11 1010 无
2,32,3 22 2020 ^
4,54,5 1010 ^ ^
66 10210^2 10210^2 A
77 ^ ^ B
8,98,9 ^ ^ 无
1010 10310^3 10410^4 A
11,1211,12 ^ ^ B
1313 ^ ^ 无
1414 10510^5 10910^9 A
15,1615,16 ^ ^ B
17,1817,18 ^ ^ 无
19,2019,20 ^ 101810^{18} ^

特殊性质 A：对于所有 1≤i≤n1 \le i \le n，均有 xi=yix_i = y_i。

特殊性质 B：对于所有 1≤i≤n1 \le i \le n，均有 xi≥yix_i \ge y_i。

入口

洛谷入口：P14635 [NOIP2025] 糖果店

ACGO入口：A92615 [NOIP2025] 糖果店

解析

记所有糖果中 xi+yix_i + y_i 最小的糖果为 tt，最终选择的结果可看作选取 2k2k 个糖果 tt 与其余若干糖果各一个，需满足 2kt+xp1+xp2+…+xpc≤m2kt + x_{p_1} + x_{p_2} + \ldots + x_{p_c} \leq m。由于仅买一个的糖果应选取 xx 最小的一部分，因此先将所有糖果按 xx 的大小排序，枚举购买 11 个的糖果数量，剩余钱用于成对购买糖果 tt（两个两个买），即可得到最大购买数量。

标程

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N 100100
using namespace std;

ll n,m,x[N],y[N];

int main()
{
    ll ans=0,mn=INF;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&x[i],&y[i]);
        mn=min(mn,x[i]+y[i]);//计算 xi+yi 最小的糖果
    }
    sort(x+1,x+n+1);
    ll s=0;
    for(int i=0;i<=n;i++)//枚举有多少糖果买了 1 个
    {
        s+=x[i];
        if(m<s) break;
        ans=max(ans,(m-s)/mn*2+i);//剩余的钱用于买最小的 xi+yi
    }
    cout<<ans;
}

T2：清仓甩卖（sale）

题干

P14636 [NOIP2025] 清仓甩卖

题目背景

额外提供了 0.5 秒的时限。

题目描述

小 X 的糖果促销策略很成功，现在糖果店只剩下了 nn 颗糖果，其中第 ii (1≤i≤n1 \le i \le n) 颗糖果的原价为 aia_i 元。小 X 计划将它们全部重新定价，清仓甩卖。具体地，小 X 会将每颗糖果的清仓价格分别定为 11 元或 22 元。设第 ii (1≤i≤n1 \le i \le n) 颗糖果的清仓价格为 wi∈{1,2}w_i \in \{1,2\} 元，则它的性价比被定义为原价与清仓价格的比值，即 aiwi\frac{a_i}{w_i}。

小 R 又带了 mm 元钱买糖果。这一次，小 R 希望他购买到的糖果的原价总和最大，于是他采用了以下购买策略：将所有糖果按照性价比从大到小排序，然后依次考虑每一颗糖果。具体地，若小 R 在考虑第 ii (1≤i≤n1 \le i \le n) 颗糖果时剩余的钱至少为 wiw_i 元，则他会购买这颗糖果；否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果的性价比相同，则小 R 会先考虑原价较高的糖果；若存在两颗糖果的性价比与原价均相同，则小 R 会先考虑编号较小的糖果。

例如，若小 X 的糖果商店剩余 33 颗糖果，原价分别为 a1=1a_1=1，a2=3a_2=3，a3=5a_3=5，而清仓价格分别为 w1=w2=1w_1=w_2=1，w3=2w_3=2，则性价比分别为 1,3,521, 3, \frac{5}{2}。因此小 R 会先考虑第 22 颗糖果，然后考虑第 33 颗糖果，最后考虑第 11 颗糖果。

小 R 想知道，在小 X 的所有 2n2^n 种定价方案中，有多少种定价方案使得他按照上述购买策略能购买到的糖果的原价总和最大。你需要帮助小 R 求出满足要求的定价方案的数量。由于答案可能较大，你只需要求出答案对 998,244,353998,244,353 取模后的结果。

输入格式

本题包含多组测试数据。

输入的第一行包含两个非负整数 c,tc, t，分别表示测试点编号与测试数据组数。c=0c=0 表示该测试点为样例。

接下来依次输入每组测试数据，对于每组测试数据：

  • 第一行包含两个正整数 n,mn, m，分别表示糖果的数量与小 R 的钱数；
  • 第二行包含 nn 个正整数 a1,a2,…,ana_1, a_2, \ldots, a_n，分别表示每颗糖果的原价。

输出格式

对于每组测试数据，输出一行一个非负整数，表示使得小 R 购买到的糖果的原价总和达到最大值的定价方案数对 998,244,353998,244,353 取模后的结果。

输入输出样例 #1

输入 #1

0 1
3 2
1 3 5

输出 #1

6

说明/提示

【样例 1 解释】

该样例即为【题目描述】中的例子。共有以下 66 种定价方案使得小 R 购买到的糖果原价总和最大，分别为：

  • w1=w2=w3=1w_1 = w_2 = w_3 = 1，小 R 购买到的糖果原价总和为 88；
  • w1=w3=1w_1 = w_3 = 1，w2=2w_2 = 2，小 R 购买到的糖果原价总和为 66；
  • w1=1w_1 = 1，w2=w3=2w_2 = w_3 = 2，小 R 购买到的糖果原价总和为 55；
  • w2=w3=1w_2 = w_3 = 1，w1=2w_1 = 2，小 R 购买到的糖果原价总和为 88；
  • w3=1w_3 = 1，w1=w2=2w_1 = w_2 = 2，小 R 购买到的糖果原价总和为 55；
  • w1=w2=w3=2w_1 = w_2 = w_3 = 2，小 R 购买到的糖果原价总和为 55。

注意：若 w1=w2=1w_1 = w_2 = 1，w3=2w_3 = 2，则小 R 会依次购买第 22 颗和第 11 颗糖果，原价总和为 44，但小 R 可以只购买第 33 颗糖果，原价总和为 55。因此该定价方案无法使小 R 购买到的糖果的原价总和达到最大值。

【样例 2】

见选手目录下的 sale/sale2.in 与 sale/sale2.ans。

该样例满足测试点 1∼31 \sim 3 的约束条件。

【样例 3】

见选手目录下的 sale/sale3.in 与 sale/sale3.ans。

该样例满足测试点 4,54,5 的约束条件。

【样例 4】

见选手目录下的 sale/sale4.in 与 sale/sale4.ans。

该样例满足测试点 7∼97 \sim 9 的约束条件。

【样例 5】

见选手目录下的 sale/sale5.in 与 sale/sale5.ans。

该样例满足测试点 10∼1210 \sim 12 的约束条件。

【样例 6】

见选手目录下的 sale/sale6.in 与 sale/sale6.ans。

该样例满足测试点 1313 的约束条件。

【样例 7】

见选手目录下的 sale/sale7.in 与 sale/sale7.ans。

该样例满足测试点 14,1514,15 的约束条件。

【样例 8】

见选手目录下的 sale/sale8.in 与 sale/sale8.ans。

该样例满足测试点 1717 的约束条件。

【样例 9】

见选手目录下的 sale/sale9.in 与 sale/sale9.ans。

该样例满足测试点 19,2019,20 的约束条件。

【样例 10】

见选手目录下的 sale/sale10.in 与 sale/sale10.ans。

该样例满足测试点 21∼2321 \sim 23 的约束条件。

【样例 11】

见选手目录下的 sale/sale11.in 与 sale/sale11.ans。

该样例满足测试点 24,2524,25 的约束条件。

【数据范围】

设 NN 为单个测试点内所有测试数据的 nn 的和。对于所有测试数据，均有：

  • 1≤t≤5×1041 \le t \le 5 \times 10^4；
  • 1≤n≤5,0001 \le n \le 5,000，N≤5×104N \le 5 \times 10^4，1≤m≤2n−11 \le m \le 2n - 1；
  • 对于所有 1≤i≤n1 \le i \le n，均有 1≤ai≤1091 \le a_i \le 10^9。

::cute-table{tuack}

测试点编号 n≤n \le N≤N \le mm 特殊性质
1∼31\sim 3 55 5,0005{,}000 ≤2n−1\le 2n - 1 无
4,54,5 1010 ^ ^ ^
66 4040 ^ ^ ^
7∼97\sim 9 300300 ^ =2=2 ^
10∼1210\sim 12 ^ ^ ≤2n−1\le 2n - 1 B
1313 ^ ^ ^ 无
14,1514,15 10310^3 10410^4 =2=2 ^
1616 ^ ^ =2n−1=2n - 1 ^
1717 ^ ^ =2n−2=2n - 2 ^
1818 ^ ^ ≤2n−1\le 2n - 1 A
19,2019,20 ^ ^ ^ B
21∼2321\sim 23 ^ ^ ^ 无
24,2524,25 5,0005{,}000 5×1045 \times 10^4 ^ ^

特殊性质 A：a1=a2=⋯=ana_1 = a_2 = \cdots = a_n。

特殊性质 B：对于所有 1≤i≤n1 \le i \le n，均有 ai>5×108a_i > 5 \times 10^8。

入口

洛谷：P14636 [NOIP2025] 清仓甩卖

ACGO：A92616.[NOIP2025] 清仓甩卖

解析

1. 不优方案的条件

当存在三种糖果 X,Y,ZX,Y,Z 满足

  • wX=wZ=1w_X = w_Z = 1，wY=2w_Y = 2
  • aX+aZ<aYa_X + a_Z < a_Y 且 aZ<12aY<aX<aYa_Z < \frac{1}{2}a_Y < a_X < a_Y贪心策略会因 XX 性价比较高而错选 X,ZX,Z，忽略总收益更高的 YY（ZZ 可不存在）。核心问题是考虑 YY 时仅剩 11 元，无法购买。

2. 方案数计算枚举糖果

  • X,YX,Y，将其他糖果分类：
  1. 原价大于 aYa_Y 的糖果(c1(c_1 个）：必被选中，消耗 11 或 22 元
    2.原价在 aX,aYa_X,a_Y 之间的糖果(c2(c_2 个)：出清价为 11 元时被选中，否则忽略
  • 不合法方案数为 Cc1+c2m−c1−2C_{c_1+c_2}^{m-c_1-2}（保证考虑 YY 时仅剩 $1￥ 元）考
  • 虑 ZZ 的取值方案（含不存在情况），总方案数为 2c3×Cc1+c2m−c1−22^{c_3} \times C_{c_1+c_2}^{m-c_1-2}，其中 c3c_3 为原价不低于 ZZ 的糖果数

标程

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
 
template<int P>
struct MInt {
    int x;
    MInt() : x{} {}
    MInt(i64 x) : x{norm(x % getMod())} {}
      
    static int Mod;
    static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    static void setMod(int Mod_) {
        Mod = Mod_;
    }
    int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    int val() const {
        return x;
    }
    explicit operator int() const {
        return x;
    }
    MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};
 
template<>
int MInt<0>::Mod = 1;
 
template<int V, int P>
MInt<P> CInv = MInt<P>(V).inv();
 
constexpr int P = 998244353;
using Z = MInt<P>;

struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

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

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());

    vector<Z> pw(n + 1);
    pw[0] = 1;
    for (int i = 0; i < n; i++) {
        pw[i + 1] = pw[i] * 2;
    }

    Z ans = 0;

    for (int i = 0; i < n; i++) {
        int p = n - 1;
        int A = 0, B = 0;
        bool flag = false;
        for (int j = 0; j < n && 2 * a[j] > a[i]; j++) {
            if (i == j) {
                flag = true;
                continue;
            }
            while (p > j && a[j] + a[p] < a[i]) {
                p--;
            }
            if (a[j] < a[i]) {
                ans += pw[n - p - 1] * comb.binom(A + B, 2 * A + B - m + 2);
            }
            if (flag) {
                B++;
            } else {
                A++;
            }
        }
    }

    cout << pw[n] - ans << '\n';
}

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

    int c, t;
    cin >> c >> t;

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

    return 0;
}

T3：树的价值（tree）

题干

P14637 [NOIP2025] 树的价值

题目描述

给定一棵 nn 个结点的有根树，其中结点 1 为根，结点 ii (2≤i≤n2 \le i \le n) 的父亲结点为结点 pip_i。

对于 1≤i≤n1 \le i \le n，定义结点 ii 的深度 did_i 为结点 1 到结点 ii 的简单路径的边数，也就是说，d1=0d_1 = 0，di=dpi+1d_i = d_{p_i} + 1 (2≤i≤n2 \le i \le n)。定义有根树的高度 hh 为所有结点的深度的最大值，即 h=max⁡i=1ndih = \max_{i=1}^{n} d_i。

给定高度的上界 mm。在本题中，给定的有根树的高度不超过 mm。

你需要给每个结点设置一个非负整数作为它的权值。对于 1≤i≤n1 \le i \le n，若结点 ii 的权值为 aia_i，令 SiS_i 表示结点 ii 的子树中结点权值构成的集合。对于每一种权值设置方案，定义树的价值为 ∑i=1nmex(Si)\sum_{i=1}^{n} \mathrm{mex}(S_i)，其中 mex(S)\mathrm{mex}(S) 表示不在集合 SS 中的最小非负整数。例如，在下图中，若设置 a1=3a_1 = 3，a2=2a_2 = 2，a3=a4=0a_3 = a_4 = 0，a5=1a_5 = 1，则 S1={0,1,2,3}S_1 = \{0,1,2,3\}，S2={0,1,2}S_2 = \{0,1,2\}，S3={0}S_3 = \{0\}，S4={0}S_4 = \{0\}，S5={1}S_5 = \{1\}，树的价值为 4+3+1+1+0=94 + 3 + 1 + 1 + 0 = 9。

你需要求出，在所有权值设置方案中，树的价值的最大值。

输入格式

本题包含多组测试数据。

输入的第一行包含一个正整数 tt，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

  • 第一行包含两个正整数 n,mn, m，分别表示结点数量与高度的上界。
  • 第二行包含 n−1n - 1 个正整数 p2,p3,…,pnp_2, p_3, \ldots, p_n，分别表示每个结点的父亲结点。

输出格式

对于每组测试数据，输出一行一个非负整数，表示树的价值的最大值。

输入输出样例 #1

输入 #1

2
5 2
1 1 2 2
7 2
1 1 2 2 2 3

输出 #1

9
13

说明/提示

【样例 1 解释】

该样例共包含两组测试数据。

对于第一组测试数据，可以设置 a1=3a_1 = 3，a2=2a_2 = 2，a3=a4=0a_3 = a_4 = 0，a5=1a_5 = 1，则树的价值为 4+3+1+1+0=94 + 3 + 1 + 1 + 0 = 9。

对于第二组测试数据，可以设置 a1=4a_1 = 4，a2=3a_2 = 3，a4=2a_4 = 2，a3=a6=1a_3 = a_6 = 1，a5=a7=0a_5 = a_7 = 0，则树的价值为 5+4+2+0+1+0+1=135 + 4 + 2 + 0 + 1 + 0 + 1 = 13。

【样例 2】

见选手目录下的 tree/tree2.in 与 tree/tree2.ans。

该样例满足测试点 3,43,4 的约束条件。

【样例 3】

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

该样例满足测试点 7,87,8 的约束条件。

【样例 4】

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

该样例满足测试点 13,1413,14 的约束条件。

【样例 5】

见选手目录下的 tree/tree5.in 与 tree/tree5.ans。

该样例满足测试点 18,1918,19 的约束条件。

【数据范围】

对于所有测试数据，均有：

  • 1≤t≤51 \le t \le 5；
  • 2≤n≤8,0002 \le n \le 8,000，1≤m≤min⁡(n−1,800)1 \le m \le \min(n - 1, 800)；
  • 对于所有 2≤i≤n2 \le i \le n，均有 1≤pi≤i−11 \le p_i \le i - 1；
  • 给定的有根树的高度不超过 mm。

::cute-table{tuack}

测试点编号 n≤n \le m≤m \le
1,21,2 77 n−1n-1
3,43,4 1313 ^
5,65,6 1818 ^
7,87,8 4040 ^
9,109,10 120120 ^
11,1211,12 360360 ^
13,1413,14 4,0004{,}000 22
15∼1715\sim 17 ^ 1010
18,1918,19 ^ 5050
20∼2520\sim 25 8,0008{,}000 800800

入口

ACGO入口：A92617.[NOIP2025] 树的价值

洛谷入口：P14637 [NOIP2025] 树的价值

解析

  1. 核心定义
  • 白点：不清空未分配权值节点，继承子树的 mex 值
  • 黑点：清空未分配权值节点，增大 mex 值
  • 状态定义：
    f[i][j][k]f[i][j][k]：白点i是树链第j个点，贡献为kk的最大价值
    g[i][j]g[i][j]：黑点i是树链第j个点的最大贡献2.
    优化思路
  • 性质：j≤kj \leq k（否则选黑点更优），k−jk-j 不超过子树最深深度用长链剖分优化 DP 转移，时间复杂度O(nm)O(nm)后缀加操作通过数据结构优化，最终时间复杂度O(nmlog⁡n)O(nm\log n)

标程

76pts

#include <bits/stdc++.h>

using namespace std;

constexpr int inf = 1E7;

template <typename T> struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) { init(n_); }

    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }

    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }

    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }

    T rangeSum(int l, int r) { return sum(r) - sum(l); }

    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

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

    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int x;
        cin >> x;
        x--;
        adj[x].push_back(i);
    }

    vector<int> d(n, 1), siz(n, 1);
    for (int i = n - 1; i >= 0; i--) {
        for (auto j : adj[i]) {
            d[i] = max(d[i], d[j] + 1);
            siz[i] += siz[j];
        }
        for (int j = 0; j < adj[i].size(); j++) {
            if (d[adj[i][j]] > d[adj[i][0]]) {
                swap(adj[i][j], adj[i][0]);
            }
        }
    }

    vector<int> dfn(n);
    {
        int k = 0;
        auto dfs = [&](auto &&self, int x) -> void {
            dfn[x] = k++;
            for (auto v : adj[x]) {
                self(self, v);
            }
        };
        dfs(dfs, 0);
    }

    m = d[0];
    vector<int> f(n, -inf);
    for (int k = m; k > 0; k--) {
        vector<int> nf(n);
        vector<int> g(n);
        Fenwick<int> h(n + 1);

        auto add = [&](int l, int r, int v) {
            if (l < r) {
                h.add(l, v);
                h.add(r, -v);
            }
        };

        auto G = [&](int x, int j) {
            if (j + d[x] - 1 < k) {
                return siz[x] * k;
            }
            return g[dfn[x] + k - j] + h.sum(dfn[x] + k - j + 1);
        };

        auto check = [&](int x) {
            auto H = h.sum(x + 1);
            g[x] += H;
            add(x, x + 1, -H);
        };

        for (int x = n - 1; x >= 0; x--) {
            if (adj[x].size()) {
                int max_val = -inf;
                for (auto v : adj[x]) {
                    auto temp = G(v, 1);
                    nf[x] += temp;
                    max_val = std::max(max_val, f[v] - temp);
                }
                nf[x] += max_val + k;
                g[dfn[x]] = nf[x];

                int D = 0;
                for (int i = 1; i < adj[x].size(); i++) {
                    D = std::max(D, d[adj[x][i]]);
                }
                auto temp = G(adj[x][0], 1);
                for (int i = 0; i < D; i++) {
                    check(dfn[x] + i + 1);
                    g[dfn[x] + i + 1] -= temp;
                    add(dfn[x] + i + 1, dfn[x] + i + 2, temp);
                }
                for (int i = 1; i < adj[x].size(); i++) {
                    int v = adj[x][i];
                    temp = G(v, 1);
                    for (int j = 0; j < d[v]; j++) {
                        g[dfn[x] + j + 1] = std::max(g[dfn[x] + j + 1], G(v, k - j) - temp);
                        add(dfn[x] + j + 1, dfn[x] + j + 2, temp);
                    }
                    add(dfn[x] + 1 + d[v], dfn[x] + d[x], G(v, k - d[v]));
                }
                add(dfn[x] + 1, dfn[x] + d[x], k);
            } else {
                nf[x] = k;
                g[dfn[x]] = k;
            }
        }

        f = move(nf);
    }
    cout << f[0] << '\n';
}

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

    int t;
    cin >> t;

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

    return 0;
}

序列询问（query）

题干

P14638 [NOIP2025] 序列询问

题目背景

额外提供了 1 秒的时限。

题目描述

给定一个长度为 nn 的整数序列 a1,a2,…,ana_1, a_2, \ldots, a_n。

有 qq 次询问，其中第 jj (1≤j≤q1 \le j \le q) 次询问将会给出 Lj,RjL_j, R_j (1≤Lj≤Rj≤n1 \le L_j \le R_j \le n)。定义区间 [l,r][l, r] (1≤l≤r≤n1 \le l \le r \le n) 是极好的，当且仅当区间 [l,r][l, r] 的长度在 [Lj,Rj][L_j, R_j] 内，即 Lj≤r−l+1≤RjL_j \le r - l + 1 \le R_j。定义区间 [l,r][l, r] (1≤l≤r≤n1 \le l \le r \le n) 的权值为 ∑i=lrai\sum_{i=l}^{r} a_i。对于所有 i=1,2,…,ni = 1, 2, \ldots, n，求出所有包含 ii 的极好区间的最大权值，即 max⁡1≤l≤i≤r≤n{∑i=lrai∣Lj≤r−l+1≤Rj}\max_{1 \le l \le i \le r \le n} \{ \sum_{i=l}^{r} a_i \mid L_j \le r - l + 1 \le R_j \}。

输入格式

输入的第一行包含一个正整数 nn，表示序列长度。

输入的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n。

输入的第三行包含一个正整数 qq，表示询问次数。

输入的第 j+3j + 3 (1≤j≤q1 \le j \le q) 行包含两个正整数 Lj,RjL_j, R_j，表示第 jj 次询问。

输出格式

对于每次询问，设包含 ii (1≤i≤n1 \le i \le n) 的极好区间的最大权值为 kik_i，输出一行一个非负整数，表示 ⨁i=1n((i×ki) mod 264)\bigoplus_{i=1}^{n} \left( (i \times k_i) \bmod 2^{64} \right)，其中 ⊕\oplus 表示二进制按位异或。注意：对于任意整数 xx，存在唯一的非负整数 x′x' 满足 x′≡x(mod264)x' \equiv x \pmod{2^{64}} 且 0≤x′≤264−10 \le x' \le 2^{64} - 1，则记 x mod 264=x′x \bmod 2^{64} = x'。

输入输出样例 #1

输入 #1

4
2 4 -5 1
3
1 2
3 4
1 4

输出 #1

18446744073709551603
8
4

说明/提示

【样例 1 解释】

对于第 11 次询问：

  • 包含 11 的极好区间为 [1,1][1,1] 和 [1,2][1,2]，权值分别为 2,62,6；
  • 包含 22 的极好区间为 [1,2][1,2]，[2,2][2,2] 和 [2,3][2,3]，权值分别为 6,4,−16,4,-1；
  • 包含 33 的极好区间为 [2,3][2,3]，[3,3][3,3] 和 [3,4][3,4]，权值分别为 −1,−5,−4-1,-5,-4；
  • 包含 44 的极好区间为 [3,4][3,4] 和 [4,4][4,4]，权值分别为 −4,1-4,1。

因此 k1=6k_1 = 6，k2=6k_2 = 6，k3=−1k_3 = -1，k4=1k_4 = 1。

对于第 2 次询问，k1=2k_1 = 2，k2=2k_2 = 2，k3=2k_3 = 2，k4=2k_4 = 2。

对于第 3 次询问，k1=6k_1 = 6，k2=6k_2 = 6，k3=2k_3 = 2，k4=2k_4 = 2。

【样例 2】

见选手目录下的 query/query2.in 与 query/query2.ans。

该样例满足测试点 2,32,3 的约束条件。

【样例 3】

见选手目录下的 query/query3.in 与 query/query3.ans。

该样例满足测试点 44 的约束条件。

【样例 4】

见选手目录下的 query/query4.in 与 query/query4.ans。

该样例满足测试点 6,76,7 的约束条件。

【样例 5】

见选手目录下的 query/query5.in 与 query/query5.ans。

该样例满足测试点 8∼108 \sim 10 的约束条件。

【样例 6】

见选手目录下的 query/query6.in 与 query/query6.ans。

该样例满足测试点 11,1211,12 的约束条件。

【样例 7】

见选手目录下的 query/query7.in 与 query/query7.ans。

该样例满足测试点 1313 的约束条件。

【样例 8】

见选手目录下的 query/query8.in 与 query/query8.ans。

该样例满足测试点 16∼2016 \sim 20 的约束条件。

【数据范围】

对于所有测试数据，均有：

  • 1≤n≤5×1041 \le n \le 5 \times 10^4，1≤q≤1,0241 \le q \le 1,024；
  • 对于所有 1≤i≤n1 \le i \le n，均有 ∣ai∣≤105|a_i| \le 10^5；
  • 对于所有 1≤j≤q1 \le j \le q，均有 1≤Lj≤Rj≤n1 \le L_j \le R_j \le n。

::cute-table{tuack}

测试点编号 n≤n \le q≤q \le 特殊性质
11 10310^3 11 无
2,32,3 3,0003{,}000 5050 ^
44 10410^4 128128 ^
55 3×1043 \times 10^4 512512 ^
6,76,7 5×1045 \times 10^4 1,0241{,}024 A
8∼108 \sim 10 ^ 512512 B
11,1211,12 ^ ^ C
1313 ^ 1,0241{,}024 D
14,1514,15 ^ ^ E
16∼2016 \sim 20 ^ ^ 无

特殊性质 A：对于所有 1≤j≤q1 \le j \le q，均有 Lj=RjL_j = R_j。

特殊性质 B：对于所有 1≤j≤q1 \le j \le q，均有 Rj≤32R_j \le 32。

特殊性质 C：对于所有 1≤j≤q1 \le j \le q，均有 Lj≤16L_j \le 16 且 Rj≥n−1000R_j \ge n - 1000。

特殊性质 D：对于所有 1≤j≤q1 \le j \le q，均有 Lj>n/2L_j > n/2。

特殊性质 E：对于所有 1≤j≤q1 \le j \le q，均有 Lj>n/4L_j > n/4。

入口

洛谷入口P14638 [NOIP2025] 序列询问

ACGO入口A92618.[NOIP2025] 序列询问

做法一：分块预处理
1.预处理区间 [ql,qr]=[2k,2k+1−1][q_l, q_r] = [2^k, 2^{k+1}-1] 的答案
2.询问时将区间拆分为整块（预处理结果）和散块（满足 2ql>qr）3.2q_l > q_r） 3.散块通过 O(1)O(1) RMQ 求解，总时间复杂度 O(nlog⁡n+nq)O(n \log n + nq)

做法二：二维区间拆分

  • 将可行区间拆分为两类三角形：
    包含 [l,r][l,r] 且长度 ≤ LL被 [l,r][l,r] 包含且长度 ≥ LL枚举边界区间，结合前缀 min / 后缀 max 和单调栈维护覆盖关系，总时间复杂度 O(n)O(n) per query
#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

template <class T, class Cmp = std::less<T>> struct RMQ {
    const Cmp cmp = Cmp();
    static constexpr unsigned B = 64;
    using u64 = unsigned long long;
    int n;
    std::vector<std::vector<T>> a;
    std::vector<T> pre, suf, ini;
    std::vector<u64> stk;
    RMQ() {}
    RMQ(const std::vector<T> &v) { init(v); }
    void init(const std::vector<T> &v) {
        n = v.size();
        pre = suf = ini = v;
        stk.resize(n);
        if (!n) {
            return;
        }
        const int M = (n - 1) / B + 1;
        const int lg = std::__lg(M);
        a.assign(lg + 1, std::vector<T>(M));
        for (int i = 0; i < M; i++) {
            a[0][i] = v[i * B];
            for (int j = 1; j < B && i * B + j < n; j++) {
                a[0][i] = std::min(a[0][i], v[i * B + j], cmp);
            }
        }
        for (int i = 1; i < n; i++) {
            if (i % B) {
                pre[i] = std::min(pre[i], pre[i - 1], cmp);
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (i % B != B - 1) {
                suf[i] = std::min(suf[i], suf[i + 1], cmp);
            }
        }
        for (int j = 0; j < lg; j++) {
            for (int i = 0; i + (2 << j) <= M; i++) {
                a[j + 1][i] = std::min(a[j][i], a[j][i + (1 << j)], cmp);
            }
        }
        for (int i = 0; i < M; i++) {
            const int l = i * B;
            const int r = std::min(1U * n, l + B);
            u64 s = 0;
            for (int j = l; j < r; j++) {
                while (s && cmp(v[j], v[std::__lg(s) + l])) {
                    s ^= 1ULL << std::__lg(s);
                }
                s |= 1ULL << (j - l);
                stk[j] = s;
            }
        }
    }
    T operator()(int l, int r) {
        if (l / B != (r - 1) / B) {
            T ans = std::min(suf[l], pre[r - 1], cmp);
            l = l / B + 1;
            r = r / B;
            if (l < r) {
                int k = std::__lg(r - l);
                ans = std::min({ans, a[k][l], a[k][r - (1 << k)]}, cmp);
            }
            return ans;
        } else {
            int x = B * (l / B);
            return ini[__builtin_ctzll(stk[r - 1] >> (l - x)) + l];
        }
    }
};

constexpr i64 inf = 1E18;

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

    int n;
    cin >> n;

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

    vector<i64> sum(n + 1);
    for (int i = 0; i < n; i++) {
        sum[i + 1] = sum[i] + a[i];
    }

    RMQ Less(sum);
    RMQ<i64, greater<i64>> Greater(sum);

    const int K = std::__lg(n) + 1;
    vector<vector<vector<i64>>> c(K, vector<vector<i64>>(K, vector<i64>(n, -inf)));
    auto solve = [&](int L, int R, vector<i64> &ans) {
        if (L >= R) {
            return;
        }
        vector<pair<int, i64>> q;
        int head = 0;
        for (int i = 0; i < n; i++) {
            if (i + L < n + 1) {
                i64 x = -sum[i] + Greater(i + L, min(n + 1, i + R));
                while (head < q.size() && q.back().second < x) {
                    q.pop_back();
                }
                q.emplace_back(i, x);
            }
            while (head < q.size() && i - q[head].first + 1 > L) {
                head++;
            }
            if (head < q.size()) {
                ans[i] = max(ans[i], q[head].second);
            }
        }
        q.clear();
        head = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (i + 2 - L > 0) {
                i64 x = sum[i + 1] - Less(max(0, i + 2 - R), i + 2 - L);
                while (head < q.size() && q.back().second < x) {
                    q.pop_back();
                }
                q.emplace_back(i, x);
            }
            while (head < q.size() && q[head].first - i + 1 > L) {
                head++;
            }
            if (head < q.size()) {
                ans[i] = max(ans[i], q[head].second);
            }
        }
    };
    for (int i = 0; i < K; i++) {
        int L = 1 << i;
        int R = L << 1;

        solve(L, R, c[i][i]);
    }

    for (int i = 0; i < K; i++) {
        for (int j = i + 1; j < K; j++) {
            for (int k = 0; k < n; k++) {
                c[i][j][k] = max(c[i][j - 1][k], c[j][j][k]);
            }
        }
    }

    int q;
    cin >> q;

    vector<i64> ans(n);

    while (q--) {
        int ql, qr;
        cin >> ql >> qr;
        qr++;

        int x = -1, y = -1;
        for (int i = 0; i < K; i++) {
            int L = 1 << i;
            int R = L << 1;
            if (ql <= L && R <= qr) {
                if (x == -1) {
                    x = i;
                }
                y = i;
            }
        }

        if (x != -1) {
            ans = c[x][y];
            solve(ql, 1 << x, ans);
            solve(2 << y, qr, ans);
        } else {
            fill(ans.begin(), ans.end(), -inf);
            while (2 * ql < qr) {
                solve(ql, 2 * ql, ans);
                ql *= 2;
            }
            solve(ql, qr, ans);
        }

        using u64 = unsigned long long;
        u64 out = 0;
        for (int i = 0; i < n; i++) {
            out ^= u64(i + 1) * ans[i];
        }
        cout << out << '\n';
    }

    return 0;
}

感悟


真的，难度是越来越大了，2026年难度不堪设想

userId_undefined
去预览
0/2000

全部评论 1

热门讨论