分类： QuestOJ 题解

Posted in: QuestOJ 题解

「QOJ2349」鸿鹄之志 bird

Written by Lu_Anlai 「QOJ2349」鸿鹄之志 bird有1条评论

题目

题目链接：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)$。

代码以后再放。

Back to Top