UOJ Logo Universal Online Judge

UOJ

#769. 【NOI2022】二次整数规划问题

附件下载 统计

本题中,你需要解决一个著名的 NP 问题——二次整数规划问题。

二次整数规划问题要有变量:你需要给出一个长度为 $n$ 的整数序列 $(x_1, x_2, \cdots, x_n)$,满足下文中的所有条件。

二次整数规划问题要有约束:你给出的整数序列需要满足以下两类约束:

  1. 一类约束是单个变量取值的约束:给出正整数 $k$($3 \le k \le 5$)和 $n$ 个区间 $[l_i, r_i]$($1 \le i \le n$),其中 $1 \le l_i \le r_i \le k$,你给出的序列需要满足 $\forall 1 \le i \le n$,$l_i \le x_i \le r_i$;
  2. 另一类约束是变量之间取值的约束:给出 $m$ 个三元组 $(p_i, q_i, b_i)$,你给出的序列需要满足 $\forall 1 \le j \le m$,$| x_{p_j} - x_{q_j} | \le b_j$。

二次整数规划问题要有目标函数:在给出 $k-2$ 个目标参数 $v_2,v_3,\cdots,v_{k-1}$(注意下标范围为 $2$ 至 $k-1$)的前提下,对于一个值域为 $[1, k]$ 的整数数列 $\{p_1, p_2, \cdots, p_n\}$,设 $c_i$ 为该序列中取值为 $i$ 的元素个数,$G$ 为满足 $1 \le i, j \le n$ 且 $|p_i-p_j|\leq 1$ 的整数二元组 $(i, j)$ 个数,注意当 $i \neq j$ 时,$(i, j)$ 与 $(j, i)$ 是不同的二元组。定义该序列的权值

$$ W(p_1, p_2, \cdots, p_n) = 10^6 G+\sum_{i=2}^{k-1} c_i v_i . $$

你的序列需要在满足以上两类约束的情况下,最大化其权值。

二次整数规划问题不一定要有多组询问,但是我们会给出 $q$ 次询问,每次询问给出不同的权值参数 $v_2, v_3, \cdots, 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, \cdots, v_{k - 1}$ 描述一组询问的权值参数。

数据保证在给定的约束条件下,至少存在一组满足所有约束的序列。

输出格式

对于每组数据的每组询问输出一行一个整数,表示序列权值的最大值。

样例一

见附件下载。

该样例满足数据范围中测试点 $1$ 的性质。

explanation

第一个测试数据中两组询问对应的最优序列均为 $(1, 2, 2, 1, 3)$,有 $c_2=2, G=21$。

样例二

见附件下载。

该样例满足数据范围中测试点 $3$ 的性质。

explanation

第一个测试数据中两组询问对应的一个最优序列分别为 $(4, 4, 3, 3)$ 和 $(4, 3, 2, 2)$。

样例三

见附件下载。

该样例满足数据范围中测试点 $5$ 的性质。

explanation

第一个测试数据中三组询问对应的一个最优序列分别为 $(3, 3, 3, 3, 3)$、$(2, 2, 3, 3, 2)$ 和 $(3, 2, 4, 4, 2)$。

样例四

见附件下载。

该样例满足数据范围中测试点 $2$ 的性质。

样例五

见附件下载。

该样例满足数据范围中测试点 $4$ 的性质。

样例六

见附件下载。

该样例满足数据范围中测试点 $8$ 的性质。

样例七

见附件下载。

该样例满足数据范围中测试点 $14$ 的性质。

样例八

见附件下载。

该样例满足数据范围中测试点 $17$ 的性质。

子任务

设 $\sum q$ 为单个测试点中所有测试数据的 $q$ 的和。对于所有测试点,

  • $1 \le T \le 600$,
  • 第 $i$ ($1 \le i \le T$) 个测试数据中,$1 \le n \le \max\left(\frac{T}{i},2 \log_2{T}\right)$,
  • $3 \le k \le 5$,$0 \le m \le 3n$,$1 \le q,\sum q \le 3 \times 10^5$,
  • $1 \le l_i \le r_i \le k$,
  • $1 \le p_j,q_j \le n$,$0 \le b_j < k$,
  • $0 \le v_2,\cdots,v_{k-1} \le {10}^{12}$。
测试点编号 $T \leq$ $k=$ $\sum q \leq$ 特殊性质 测试点分数
$1$ $10$ $3$ $200$ $4$
$2$ $600$ $3 \times 10^5$ $6$
$3$ $10$ $4$ $200$ $4$
$4$ $600$ $3 \times 10^5$ $6$
$5$ $10$ $5$ $300$ $5$
$6$ $15$ $500$ $4$
$7$ $25$ $750$ $4$
$8$ $50$ $1000$ $6$
$9$ $80$ $1500$ $6$
$10$ $120$ $2000$ $5$
$11$ $200$ $8000$ A $3$
$12$ $400$ $3 \times 10^4$ $4$
$13$ $600$ $2 \times 10^5$ $5$
$14$ $200$ $8000$ B $3$
$15$ $400$ $3 \times 10^4$ $4$
$16$ $600$ $2 \times 10^5$ $4$
$17$ $120$ $10^5$ C $4$
$18$ $150$ $2 \times 10^5$ $5$
$19$ $180$ $3 \times 10^5$ $5$
$20$ $300$ $5 \times 10^4$ $5$
$21$ $450$ $10^5$ $4$
$22$ $600$ $3 \times 10^5$ $4$
  • 特殊性质 A:$m=0$。
  • 特殊性质 B:$m \le 10$,单个测试点中所有测试数据的 $m$ 的和不超过 $200$。
  • 特殊性质 C:数据随机生成。具体地,生成测试点中每组测试数据时,给出参数 $k,n,m,q$ 以及 $k$ 个非负整数 $p_0, p_1, p_2, \cdots,p_{k-1}$,保证 $p_{k-1} \neq 0$,则按照如下规则生成该组数据:
    • 对于 $1 \le i \le 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 \le i \le k-1$,$w=i$ 的概率为 $\frac{p_i}{p_0 + p_1 + \cdots + p_{k-1}}$);
      3. 若在原有三元组集合中加入 $(u,v,w)$ 后不存在序列 $(x_1,x_2,\cdots,x_n)$ 满足所有限制,则舍弃当前三元组,否则加入当前三元组。
    • 每组询问的 $v_2, \cdots, v_{k-1}$ 在 $[0,10^{12}]$ 内独立均匀随机生成。

时间限制:2s$\texttt{3s}$

空间限制:$1\texttt{GB}$