题目详情题解（0）讨论（0）提交记录（0）

A93156.「NOI2022」二次整数规划问题

NOI/NOI+/CTSC

NOI

通过率：0%

时间限制：2.00s

内存限制：1024MB

题目描述

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

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

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

  1. 一类约束是单个变量取值的约束：给出正整数 kk（3≤k≤53 \leq k \leq 5）和 nn 个区间 [li,ri][l_i, r_i]（1≤i≤n1 \leq i \leq n），其中 1≤li≤ri≤k1 \leq l_i \leq r_i \leq k，你给出的序列需要满足 ∀1≤i≤n\forall 1 \leq i \leq n，li≤xi≤ril_i \leq x_i \leq r_i；
  2. 另一类约束是变量之间取值的约束：给出 mm 个三元组 (pi,qi,bi)(p_i, q_i, b_i)，你给出的序列需要满足 ∀1≤j≤m\forall 1 \leq j \leq m，∣xpj−xqj∣≤bj\lvert x_{p_j} - x_{q_j} \rvert \leq b_j。

二次整数规划问题要有目标函数：在给出 k−2k-2 个目标参数 v2,v3,…,vk−1v_2,v_3,\dots,v_{k-1}（注意下标范围为 2\boldsymbol{2} 至 k−1\boldsymbol{k-1}）的前提下，对于一个值域为 [1,k][1,k] 的整数数列 {p1,p2,…,pn}\{p_1,p_2,\dots,p_n\}，设 cic_i 为该序列中取值为 ii 的元素个数，GG 为满足 1≤i,j≤n1 \leq i,j \leq n 且 ∣pi−pj∣≤1|p_i-p_j|\leq 1 的整数二元组 (i,j)(i, j) 个数，注意当 i≠j\boldsymbol{i \neq j} 时，(i,j)\boldsymbol{(i, j)} 与 (j,i)\boldsymbol{(j, i)} 是不同的二元组。定义该序列的权值为

W(p1,p2,…,pn)=106G+∑i=2k−1civi。W(p_1, p_2, \ldots, p_n) = 10^6 G+\sum_{i=2}^{k-1} c_i v_i \text{。}

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

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

输入格式

从文件 qip.in 中读入数据。

本题有多组测试数据。

第一行一个非负整数和一个正整数 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 行每行 k−2k - 2 个非负整数 v2,v3,…,vk−1v_2, v_3, \ldots, v_{k - 1} 描述一组询问的权值参数。

输出格式

输出到文件 qip.out 中。

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

说明/提示

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

  • 1≤T≤6001 \leq T \leq 600，
  • 第 ii（1≤i≤T1 \le i \le T）个测试数据中，1≤n≤max⁡(Ti,2log⁡2T)1 \leq n \leq \max(\frac{T}{i},2 \log_2 T)，
  • 3≤k≤53 \leq k \leq 5，0≤m≤3n0 \leq m \leq 3n，1≤q,∑q≤3×1051 \leq q,\sum q \leq 3 \times 10^5，
  • 1≤li≤ri≤k1 \leq l_i \leq r_i \leq k，
  • 1≤pj,qj≤n1 \leq p_j,q_j \leq n，0≤bj<k0 \leq b_j<k，
  • 0≤v2,…,vk−1≤10120 \leq v_2,\dots,v_{k-1} \leq 10^{12}。
测试点编号 T≤T \leq k=k= ∑q≤\sum q \leq 特殊性质 测试点分数
11 1010 33 200200 无 44
22 600600 33 3×1053 \times 10^5 无 66
33 1010 44 200200 无 44
44 600600 44 3×1053 \times 10^5 无 66
55 1010 55 300300 无 55
66 1515 55 500500 无 44
77 2525 55 750750 无 44
88 5050 55 10001000 无 66
99 8080 55 15001500 无 66
1010 120120 55 20002000 无 55
1111 200200 55 80008000 A 33
1212 400400 55 3×1043 \times 10^4 A 44
1313 600600 55 2×1052 \times 10^5 A 55
1414 200200 55 80008000 B 33
1515 400400 55 3×1043 \times 10^4 B 44
1616 600600 55 2×1052 \times 10^5 B 44
1717 120120 55 10510^5 C 44
1818 150150 55 2×1052 \times 10^5 C 55
1919 180180 55 3×1053 \times 10^5 C 55
2020 300300 55 5×1045 \times 10^4 无 55
2121 450450 55 10510^5 无 44
2222 600600 55 3×1053 \times 10^5 无 44

特殊性质 A：m=0m=0。

特殊性质 B：m≤10m \leq 10，单个测试点中所有测试数据的 mm 的和不超过 200200。

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

  • 对于 1≤i≤n1 \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（对于 0≤i≤k−10 \leq i \leq k-1，w=iw=i 的概率为 pip0+p1+⋯+pk−1\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,…,vk−1v_2, \ldots, v_{k-1} 在 [0,1012][0,10^{12}] 内独立均匀随机生成。
首页