Posted in: QuestOJ 题解

「QOJ2349」鸿鹄之志 bird

题目

题目链接:QOJ2349

题目限制

  • 时间限制:$1\texttt{s}$;
  • 空间限制:$512\texttt{MiB}$;
  • 输入文件:bird.in
  • 输出文件:bird.out

题目背景

你从小就励志,要当世界第一的猛汉王

题目描述

展现自我的时刻到了,现在你面前有 $n$ 位考官,每位考官都是多面手,具体地,每一位考官都有 $k$ 个属性值,其中第 $i$ 位考官的属性值分别为 $a_{i,0},a_{i,1},a_{i,2},\cdots,a_{i,k-1}$。

考官喜欢合伙刁难你,具体地,他们会对自己的各项属性进行线性组合,线性组合可以看做一个长度为 $k$ 的 $01$ 串,例如 $01000$。一个合法的线性组合集合 $\mathbb{S}$ 应该满足如下需求:

  1. 如果一个串 $a\in\mathbb{S}$ ,那么它的取反串 $a'\not\in\mathbb{S}$ ;
  2. 如果一个串 $a\in\mathbb{S}$,那么它应当满足 $\operatorname{cnt}(a)<\operatorname{cnt}(a')$ 或者 $\operatorname{cnt}(a)=\operatorname{cnt}(a')$ 的同时 $\operatorname{val}(a)< \operatorname{val}(a')$,其中 $\operatorname{cnt}(x)$ 表示 $x$ 中 $1$ 的个数,$\operatorname{val}(x)$ 表示 $x$ 的大小。

如果看不懂,你可以使用如下代码生成长度为 $n$ 的合法线性组合集合。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int n=4; //改变这里的值,即可得出不同长度的线性组合集合

int main(void){
    bitset<n> B;
    for(reg int i=0;i<(1<<n);++i){
        B=i;
        if(n&1){
            if(B.count()<=n/2)
                cout<<B<<endl;
        }
        else{
            if(B.count()<n/2)
                cout<<B<<endl;
            else if(B.count()==n/2&&i<(1<<(n-1)))
                cout<<B<<endl;
        }
    }
    return 0;
}

不难发现,长度为 $n$ 的线性组合集合 $\mathbb{S}$ 满足 $|\mathbb{S}|=2^{n-1}$。

定义一个考官的武德为一个 $2^{n-1}$ 元组,即上述线性组合集合中的每一个线性组合都对应一个武德值。具体地,对于一个线性组合 $s$,考官 $i$ 对应的武德值为 $\left(\sum\limits_{w=0}^{k-1}(-1)^{s_w}a_{i,w}\right)$。

与考官的武德相比,你总是有所不如,对于一个考官,你面对他的审查产生的尴尬值为两人武德差值绝对值的最大值,即 $\max\limits_{s_{j}\in\mathbb{S}}\left|A_j-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|$。

考官也喜欢不讲武德,总喜欢让你尴尬,他们会组织起来,对你进行多次审查,定义一次区间 $[l,r]$ 内考官审查你的尴尬值为 $\sum\limits_{i=l}^{r}\left(\max\limits_{s_{j}\in\mathbb{S}}\left|A_j-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|\right)$。

你可以在审查开始之前修炼自己的武德,即自由改变 $A_j$。请求出尴尬值的最小值。

输入格式

第一行,三个整数 $n,q,k$。

后 $n$ 行,每行 $k$ 个整数 $a_{i,0},a_{i,1},\cdots,a_{i,k-1}$。

后 $q$ 行,每行两个正整数 $l,r$ 表示询问区间。

输出格式

共 $q$ 行,表示每次询问尴尬值的最小值。

样例

样例输入

4 3 2
1 2
3 4
5 6
7 8
1 1
1 2
2 4

样例输出

0.000000
4.000000
8.000000

样例解释

$k=2$ 时,线性组合集合 $\mathbb{S}={[00],[01]}$。

第一次询问,考官属性为 ${[1,2]}$,对应的武德值为 ${(3,-1)}$,应选择 $A_0=3,A_1=-1$,尴尬值取最小为 $0$;

第二次询问,考官属性为 ${[1,2],[3,4]}$,对应武德值为 ${(3,-1),(7,-1)}$,应选择 $A_0\in[3,7]$,$A_1=-1$,尴尬值取最小为 $4$;

第三次询问,考官属性为 ${[3,4],[5,6],[7,8]}$,对应武德值为 ${(7,-1),(11,-1),(15,-1)}$,应选择 $A_0=11,A_1=-1$,尴尬值取最小为 $8$。

数据范围与提示

子任务编号 $n$ $q$ $k$ $a$ 分数
$1$ $\leq 10$ $0$ $=1$ $\lvert a\rvert\leq 10^9$ $5$
$2$ $\leq 100$ $\leq 100$ $=1$ $\lvert a\rvert\leq 10^3$ $10$
$3$ $\leq 100$ $\leq 100$ $=1$ $\lvert a\rvert\leq 10^5$ $5$
$4$ $\leq 100$ $\leq 100$ $=2$ $\lvert a\rvert\leq 10^3$ $5$
$5$ $\leq 10^5$ $\leq 10^5$ $=2$ $\lvert a\rvert\leq 10^9$ $20$
$6$ $\leq 100$ $\leq 100$ $\leq 10$ $\lvert a\rvert\leq 10^5$ $10$
$7$ $\leq 10^4$ $\leq 10^4$ $\leq 10$ $\lvert a\rvert\leq 10^5$ $45$

对于 $100\%$ 的数据,保证 $1\leq l\leq r\leq n$。

题解

下面我们直接说正解。

不难发现下面的规律,它表明各个属性之间对答案的影响无关。

如果我们设 $A_j=\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}x_{i,w}\right)$ 其中 $x$ 是我们任意选择,那么我们就对题目进行了恒等变换,不影响答案。

$$
\begin{aligned}
&\max\limits_{s_{j}\in\mathbb{S}}\left|A_j-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|\\\
=&\max\limits_{s_{j}\in\mathbb{S}}\left|\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}x_{i,w}\right)-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|\\
=&\max\limits_{s_{j}\in\mathbb{S}}\left|\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}\left(x_{i,w}-a_{i,w}\right)\right)\right|
\end{aligned}
$$

我们发现事实上线性组合就是一个幌子,如果我们将线性组合取反,由于上面式子绝对值的作用,我们得到的结果相同。也就是说如果我们把线性组合扩充到包含它与它的取反,结果不变。

这样的话,新的线性组合集合就包含了 $2^k$ 个元素,对应所有属性值之差乘上 $+1$ 或者 $-1$ 的自由组合,所以我们进一步转化,得到

$$
\begin{aligned}
&\max\limits_{s_{j}}\left|\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}\left(x_{i,w}-a_{i,w}\right)\right)\right|\\
=&\sum\limits_{w=0}^{k-1} \max\limits_{s_{j}}\left|(-1)^{s_{j,w}}\left(x_{i,w}-a_{i,w}\right)\right|\\
=&\sum\limits_{w=0}^{k-1} \max\limits_{s_{j}}\left|\left(x_{i,w}-a_{i,w}\right)\right|\\
=&\sum\limits_{w=0}^{k-1} \left|x_{i,w}-a_{i,w}\right|\\
\end{aligned}
$$

进一步地,我们得出答案其实就是 $k$ 维货仓选址。

我们选择运用主席树来解决区间中位数问题,时间复杂度为 $\Theta\left((k(n+q)\log_2n)\right)$。

代码以后再放。