A6724 | 「NOI2022」二次整数规划问题
来源NOI
时间限制2s
内存限制1024MB
通过 / 提交0/0
题目描述
本题中，你需要解决一个著名的 NP 问题——二次整数规划问题。
二次整数规划问题要有变量：你需要给出一个长度为 $n$ 的**整数**序列 $(x_1, x_2, \ldots, x_n)$，满足下文中的所有条件。
二次整数规划问题要有约束：你给出的整数序列需要满足以下两类约束：
1. 一类约束是单个变量取值的约束：给出正整数 $k$（$3 \leq k \leq 5$）和 $n$ 个区间 $[l_i, r_i]$（$1 \leq i \leq n$），其中 $1 \leq l_i \leq r_i \leq k$，你给出的序列需要满足 $\forall 1 \leq i \leq n$，$l_i \leq x_i \leq r_i$；
2. 另一类约束是变量之间取值的约束：给出 $m$ 个三元组 $(p_i, q_i, b_i)$，你给出的序列需要满足 $\forall 1 \leq j \leq m$，$\lvert x_{p_j} - x_{q_j} \rvert \leq b_j$。
二次整数规划问题要有目标函数：在给出 $k-2$ 个目标参数 $v_2,v_3,\dots,v_{k-1}$（**注意下标范围为 $\boldsymbol{2}$ 至 $\boldsymbol{k-1}$**）的前提下，对于一个值域为 $[1,k]$ 的整数数列 $\{p_1,p_2,\dots,p_n\}$，设 $c_i$ 为该序列中取值为 $i$ 的元素个数，$G$ 为满足 $1 \leq i,j \leq n$ 且 $|p_i-p_j|\leq 1$ 的整数二元组 $(i, j)$ 个数，**注意当 $\boldsymbol{i \neq j}$ 时，$\boldsymbol{(i, j)}$ 与 $\boldsymbol{(j, i)}$ 是不同的二元组**。定义该序列的**权值**为
$$ W(p_1, p_2, \ldots, p_n) = 10^6 G+\sum_{i=2}^{k-1} c_i v_i \text{。} $$
你的序列需要在满足以上两类约束的情况下，最大化其权值。在给出的约束下，保证存在满足约束的序列。
二次整数规划问题不一定要有多组询问，但是我们会给出 $q$ 次询问，每次询问给出不同的权值参数 $v_2, v_3, \ldots, v_{k-1}$，对于每组询问你需要找到满足约束的最大化权值的序列。为了减少输出量，你只需要输出这个序列的权值。
二次整数规划问题要有变量：你需要给出一个长度为 $n$ 的**整数**序列 $(x_1, x_2, \ldots, x_n)$，满足下文中的所有条件。
二次整数规划问题要有约束：你给出的整数序列需要满足以下两类约束：
1. 一类约束是单个变量取值的约束：给出正整数 $k$（$3 \leq k \leq 5$）和 $n$ 个区间 $[l_i, r_i]$（$1 \leq i \leq n$），其中 $1 \leq l_i \leq r_i \leq k$，你给出的序列需要满足 $\forall 1 \leq i \leq n$，$l_i \leq x_i \leq r_i$；
2. 另一类约束是变量之间取值的约束：给出 $m$ 个三元组 $(p_i, q_i, b_i)$，你给出的序列需要满足 $\forall 1 \leq j \leq m$，$\lvert x_{p_j} - x_{q_j} \rvert \leq b_j$。
二次整数规划问题要有目标函数：在给出 $k-2$ 个目标参数 $v_2,v_3,\dots,v_{k-1}$（**注意下标范围为 $\boldsymbol{2}$ 至 $\boldsymbol{k-1}$**）的前提下，对于一个值域为 $[1,k]$ 的整数数列 $\{p_1,p_2,\dots,p_n\}$，设 $c_i$ 为该序列中取值为 $i$ 的元素个数，$G$ 为满足 $1 \leq i,j \leq n$ 且 $|p_i-p_j|\leq 1$ 的整数二元组 $(i, j)$ 个数，**注意当 $\boldsymbol{i \neq j}$ 时，$\boldsymbol{(i, j)}$ 与 $\boldsymbol{(j, i)}$ 是不同的二元组**。定义该序列的**权值**为
$$ W(p_1, p_2, \ldots, p_n) = 10^6 G+\sum_{i=2}^{k-1} c_i v_i \text{。} $$
你的序列需要在满足以上两类约束的情况下，最大化其权值。在给出的约束下，保证存在满足约束的序列。
二次整数规划问题不一定要有多组询问，但是我们会给出 $q$ 次询问，每次询问给出不同的权值参数 $v_2, v_3, \ldots, v_{k-1}$，对于每组询问你需要找到满足约束的最大化权值的序列。为了减少输出量，你只需要输出这个序列的权值。
输入格式
从文件
**本题有多组测试数据。**
第一行一个非负整数和一个正整数 $C, T$，分别表示测试点编号和测试数据数量。$C = 0$ 表示该组数据为样例。
对于每组测试数据，第一行四个整数 $k, n, m, q$，描述序列值域、序列长度、变量之间约束的个数和询问次数。
接下来 $n$ 行每行两个整数 $l_i, r_i$，描述序列中每个元素对应的取值区间。
接下来 $m$ 行每行三个整数 $p_j, q_j, b_j$，描述一个变量之间的约束。
接下来 $q$ 行每行 $k - 2$ 个非负整数 $v_2, v_3, \ldots, v_{k - 1}$ 描述一组询问的权值参数。
qip.in 中读入数据。**本题有多组测试数据。**
第一行一个非负整数和一个正整数 $C, T$，分别表示测试点编号和测试数据数量。$C = 0$ 表示该组数据为样例。
对于每组测试数据，第一行四个整数 $k, n, m, q$，描述序列值域、序列长度、变量之间约束的个数和询问次数。
接下来 $n$ 行每行两个整数 $l_i, r_i$，描述序列中每个元素对应的取值区间。
接下来 $m$ 行每行三个整数 $p_j, q_j, b_j$，描述一个变量之间的约束。
接下来 $q$ 行每行 $k - 2$ 个非负整数 $v_2, v_3, \ldots, v_{k - 1}$ 描述一组询问的权值参数。
输出格式
输出到文件
对于每组数据的每组询问输出一行一个整数，表示序列权值的最大值。
qip.out 中。对于每组数据的每组询问输出一行一个整数，表示序列权值的最大值。
设 $\sum q$ 为单个测试点中所有测试数据的 $q$ 的和。对于所有测试点，
- $1 \leq T \leq 600$，
- 第 $i$（$1 \le i \le T$）个测试数据中，$1 \leq n \leq \max(\frac{T}{i},2 \log_2 T)$，
- $3 \leq k \leq 5$，$0 \leq m \leq 3n$，$1 \leq q,\sum q \leq 3 \times 10^5$，
- $1 \leq l_i \leq r_i \leq k$，
- $1 \leq p_j,q_j \leq n$，$0 \leq b_j<k$，
- $0 \leq v_2,\dots,v_{k-1} \leq 10^{12}$。
| 测试点编号 | $T \leq$ | $k=$ | $\sum q \leq$ | 特殊性质 | 测试点分数 |
|:-----:|:--------:|:----:|:---------------:|:------------:|:-----:|
| $1$ | $10$ | $3$ | $200$ | 无 | $4$ |
| $2$ | $600$ | $3$ | $3 \times 10^5$ | 无 | $6$ |
| $3$ | $10$ | $4$ | $200$ | 无 | $4$ |
| $4$ | $600$ | $4$ | $3 \times 10^5$ | 无 | $6$ |
| $5$ | $10$ | $5$ | $300$ | 无 | $5$ |
| $6$ | $15$ | $5$ | $500$ | 无 | $4$ |
| $7$ | $25$ | $5$ | $750$ | 无 | $4$ |
| $8$ | $50$ | $5$ | $1000$ | 无 | $6$ |
| $9$ | $80$ | $5$ | $1500$ | 无 | $6$ |
| $10$ | $120$ | $5$ | $2000$ | 无 | $5$ |
| $11$ | $200$ | $5$ | $8000$ | A | $3$ |
| $12$ | $400$ | $5$ | $3 \times 10^4$ | A | $4$ |
| $13$ | $600$ | $5$ | $2 \times 10^5$ | A | $5$ |
| $14$ | $200$ | $5$ | $8000$ | B | $3$ |
| $15$ | $400$ | $5$ | $3 \times 10^4$ | B | $4$ |
| $16$ | $600$ | $5$ | $2 \times 10^5$ | B | $4$ |
| $17$ | $120$ | $5$ | $10^5$ | C | $4$ |
| $18$ | $150$ | $5$ | $2 \times 10^5$ | C | $5$ |
| $19$ | $180$ | $5$ | $3 \times 10^5$ | C | $5$ |
| $20$ | $300$ | $5$ | $5 \times 10^4$ | 无 | $5$ |
| $21$ | $450$ | $5$ | $10^5$ | 无 | $4$ |
| $22$ | $600$ | $5$ | $3 \times 10^5$ | 无 | $4$ |
特殊性质 A：$m=0$。
特殊性质 B：$m \leq 10$，单个测试点中所有测试数据的 $m$ 的和不超过 $200$。
特殊性质 C：数据随机生成。具体地，生成测试点中每组测试数据时，给出参数 $k,n,m,q$ 以及 $k$ 个非负常数 $p_0,p_1,p_2,\dots,p_{k-1}$，保证 $p_{k-1} \neq 0$，则按照如下规则生成该组数据：
- 对于 $1 \leq i \leq n$，独立均匀生成 $x,y \in [1,k]$，则 $l_i=\min(x,y),r_i=\max(x,y)$；
- 不断按照如下方式生成三元组直至有 $m$ 个三元组：
1. 独立均匀随机生成 $u,v \in [1,n]$；
2. 以 $p$ 为权值随机生成 $w$（对于 $0 \leq i \leq k-1$，$w=i$ 的概率为 $\frac{p_i}{p_0+p_1+\dots+p_{k-1}}$）；
3. 若在原有三元组集合中加入 $(u,v,w)$ 后不存在序列 $(x_1,x_2,\dots,x_n)$ 满足所有限制，则舍弃当前三元组，否则加入当前三元组。
- 每组询问的 $v_2, \ldots, v_{k-1}$ 在 $[0,10^{12}]$ 内独立均匀随机生成。
- $1 \leq T \leq 600$，
- 第 $i$（$1 \le i \le T$）个测试数据中，$1 \leq n \leq \max(\frac{T}{i},2 \log_2 T)$，
- $3 \leq k \leq 5$，$0 \leq m \leq 3n$，$1 \leq q,\sum q \leq 3 \times 10^5$，
- $1 \leq l_i \leq r_i \leq k$，
- $1 \leq p_j,q_j \leq n$，$0 \leq b_j<k$，
- $0 \leq v_2,\dots,v_{k-1} \leq 10^{12}$。
| 测试点编号 | $T \leq$ | $k=$ | $\sum q \leq$ | 特殊性质 | 测试点分数 |
|:-----:|:--------:|:----:|:---------------:|:------------:|:-----:|
| $1$ | $10$ | $3$ | $200$ | 无 | $4$ |
| $2$ | $600$ | $3$ | $3 \times 10^5$ | 无 | $6$ |
| $3$ | $10$ | $4$ | $200$ | 无 | $4$ |
| $4$ | $600$ | $4$ | $3 \times 10^5$ | 无 | $6$ |
| $5$ | $10$ | $5$ | $300$ | 无 | $5$ |
| $6$ | $15$ | $5$ | $500$ | 无 | $4$ |
| $7$ | $25$ | $5$ | $750$ | 无 | $4$ |
| $8$ | $50$ | $5$ | $1000$ | 无 | $6$ |
| $9$ | $80$ | $5$ | $1500$ | 无 | $6$ |
| $10$ | $120$ | $5$ | $2000$ | 无 | $5$ |
| $11$ | $200$ | $5$ | $8000$ | A | $3$ |
| $12$ | $400$ | $5$ | $3 \times 10^4$ | A | $4$ |
| $13$ | $600$ | $5$ | $2 \times 10^5$ | A | $5$ |
| $14$ | $200$ | $5$ | $8000$ | B | $3$ |
| $15$ | $400$ | $5$ | $3 \times 10^4$ | B | $4$ |
| $16$ | $600$ | $5$ | $2 \times 10^5$ | B | $4$ |
| $17$ | $120$ | $5$ | $10^5$ | C | $4$ |
| $18$ | $150$ | $5$ | $2 \times 10^5$ | C | $5$ |
| $19$ | $180$ | $5$ | $3 \times 10^5$ | C | $5$ |
| $20$ | $300$ | $5$ | $5 \times 10^4$ | 无 | $5$ |
| $21$ | $450$ | $5$ | $10^5$ | 无 | $4$ |
| $22$ | $600$ | $5$ | $3 \times 10^5$ | 无 | $4$ |
特殊性质 A：$m=0$。
特殊性质 B：$m \leq 10$，单个测试点中所有测试数据的 $m$ 的和不超过 $200$。
特殊性质 C：数据随机生成。具体地，生成测试点中每组测试数据时，给出参数 $k,n,m,q$ 以及 $k$ 个非负常数 $p_0,p_1,p_2,\dots,p_{k-1}$，保证 $p_{k-1} \neq 0$，则按照如下规则生成该组数据：
- 对于 $1 \leq i \leq n$，独立均匀生成 $x,y \in [1,k]$，则 $l_i=\min(x,y),r_i=\max(x,y)$；
- 不断按照如下方式生成三元组直至有 $m$ 个三元组：
1. 独立均匀随机生成 $u,v \in [1,n]$；
2. 以 $p$ 为权值随机生成 $w$（对于 $0 \leq i \leq k-1$，$w=i$ 的概率为 $\frac{p_i}{p_0+p_1+\dots+p_{k-1}}$）；
3. 若在原有三元组集合中加入 $(u,v,w)$ 后不存在序列 $(x_1,x_2,\dots,x_n)$ 满足所有限制，则舍弃当前三元组，否则加入当前三元组。
- 每组询问的 $v_2, \ldots, v_{k-1}$ 在 $[0,10^{12}]$ 内独立均匀随机生成。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？