#P8501. [NOI2022] 二次整数规划问题

[NOI2022] 二次整数规划问题

题目描述

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

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

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

  1. 一类约束是单个变量取值的约束:给出正整数 kk3k53 \leq k \leq 5)和 nn 个区间 [li,ri][l_i, r_i]1in1 \leq i \leq n),其中 1lirik1 \leq l_i \leq r_i \leq k,你给出的序列需要满足 1in\forall 1 \leq i \leq nlixiril_i \leq x_i \leq r_i
  2. 另一类约束是变量之间取值的约束:给出 mm 个三元组 (pi,qi,bi)(p_i, q_i, b_i),你给出的序列需要满足 1jm\forall 1 \leq j \leq mxpjxqjbj\lvert x_{p_j} - x_{q_j} \rvert \leq b_j

二次整数规划问题要有目标函数:在给出 k2k-2 个目标参数 v2,v3,,vk1v_2,v_3,\dots,v_{k-1}注意下标范围为 2\boldsymbol{2}k1\boldsymbol{k-1})的前提下,对于一个值域为 [1,k][1,k] 的整数数列 {p1,p2,,pn}\{p_1,p_2,\dots,p_n\},设 cic_i 为该序列中取值为 ii 的元素个数,GG 为满足 1i,jn1 \leq i,j \leq npipj1|p_i-p_j|\leq 1 的整数二元组 (i,j)(i, j) 个数,注意当 ij\boldsymbol{i \neq j} 时,(i,j)\boldsymbol{(i, j)}(j,i)\boldsymbol{(j, i)} 是不同的二元组。定义该序列的权值

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

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

二次整数规划问题不一定要有多组询问,但是我们会给出 qq 次询问,每次询问给出不同的权值参数 v2,v3,,vk1v_2, v_3, \ldots, v_{k-1},对于每组询问你需要找到满足约束的最大化权值的序列。为了减少输出量,你只需要输出这个序列的权值。

输入格式

本题有多组测试数据。 第一行一个非负整数和一个正整数 C,TC, T,分别表示测试点编号和测试数据数量。C=0C = 0 表示该组数据为样例。

对于每组测试数据,第一行四个整数 k,n,m,qk, n, m, q,描述序列值域、序列长度、变量之间约束的个数和询问次数。

接下来 nn 行每行两个整数 li,ril_i, r_i,描述序列中每个元素对应的取值区间。

接下来 mm 行每行三个整数 pj,qj,bjp_j, q_j, b_j,描述一个变量之间的约束。

接下来 qq 行每行 k2k - 2 个非负整数 v2,v3,,vk1v_2, v_3, \ldots, v_{k - 1} 描述一组询问的权值参数。

输出格式

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

提示

【样例 #1】

见附件中的 qip/qip1.inqip/qip1.ans

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


【样例解释 #1】

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


【样例 #2】

见附件中的 qip/qip2.inqip/qip2.ans

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


【样例解释 #2】

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


【样例 #3】

见附件中的 qip/qip3.inqip/qip3.ans

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


【样例解释 #3】

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


【样例 #4】

见附件中的 qip/qip4.inqip/qip4.ans

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


【样例 #5】

见附件中的 qip/qip5.inqip/qip5.ans

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


【样例 #6】

见附件中的 qip/qip6.inqip/qip6.ans

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


【样例 #7】

见附件中的 qip/qip7.inqip/qip7.ans

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


【样例 #8】

见附件中的 qip/qip8.inqip/qip8.ans

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


【数据范围】

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

  • 1T6001 \leq T \leq 600
  • ii1iT1 \le i \le T)个测试数据中,1nmax(Ti,2log2T)1 \leq n \leq \max(\frac{T}{i},2 \log_2 T)
  • 3k53 \leq k \leq 50m3n0 \leq m \leq 3n1q,q3×1051 \leq q,\sum q \leq 3 \times 10^5
  • 1lirik1 \leq l_i \leq r_i \leq k
  • 1pj,qjn1 \leq p_j,q_j \leq n0bj<k0 \leq b_j<k
  • 0v2,,vk110120 \leq v_2,\dots,v_{k-1} \leq 10^{12}
测试点编号 TT \leq k=k= q\sum q \leq 特殊性质 测试点分数
11 1010 33 200200 44
22 600600 3×1053 \times 10^5 66
33 1010 44 200200 44
44 600600 3×1053 \times 10^5 66
55 1010 55 300300 55
66 1515 500500 44
77 2525 750750
88 5050 10001000 66
99 8080 15001500
1010 120120 20002000 55
1111 200200 80008000 A 33
1212 400400 3×1043 \times 10^4 44
1313 600600 2×1052 \times 10^5 55
1414 200200 80008000 B 33
1515 400400 3×1043 \times 10^4 44
1616 600600 2×1052 \times 10^5
1717 120120 10510^5 C
1818 150150 2×1052 \times 10^5 55
1919 180180 3×1053 \times 10^5
2020 300300 5×1045 \times 10^4
2121 450450 10510^5 44
2222 600600 3×1053 \times 10^5

特殊性质 A:m=0m=0

特殊性质 B:m10m \leq 10,单个测试点中所有测试数据的 mm 的和不超过 200200

特殊性质 C:数据随机生成。具体地,生成测试点中每组测试数据时,给出参数 k,n,m,qk,n,m,q 以及 kk 个非负常数 p0,p1,p2,,pk1p_0,p_1,p_2,\dots,p_{k-1},保证 pk10p_{k-1} \neq 0,则按照如下规则生成该组数据:

  • 对于 1in1 \leq i \leq n,独立均匀生成 x,y[1,k]x,y \in [1,k],则 li=min(x,y),ri=max(x,y)l_i=\min(x,y),r_i=\max(x,y)
  • 不断按照如下方式生成三元组直至有 mm 个三元组:
    1. 独立均匀随机生成 u,v[1,n]u,v \in [1,n]
    2. pp 为权值随机生成 ww(对于 0ik10 \leq i \leq k-1w=iw=i 的概率为 pip0+p1++pk1\frac{p_i}{p_0+p_1+\dots+p_{k-1}});
    3. 若在原有三元组集合中加入 (u,v,w)(u,v,w) 后不存在序列 (x1,x2,,xn)(x_1,x_2,\dots,x_n) 满足所有限制,则舍弃当前三元组,否则加入当前三元组。
  • 每组询问的 v2,,vk1v_2, \ldots, v_{k-1}[0,1012][0,10^{12}] 内独立均匀随机生成。