Chlience

【题解】CF 1054 Mail.Ru Cup 2018 Round 1
A Elevator or Stairs?Problem传送门 >ω<题目大意:是走楼梯 $x-y$ 快呢还是坐电...
扫描右侧二维码阅读全文
06
2018/11

【题解】CF 1054 Mail.Ru Cup 2018 Round 1

A Elevator or Stairs?

Problem

传送门 >ω<

题目大意:
是走楼梯 $x-y$ 快呢还是坐电梯 $x-y$ 快呢?

Solution

走楼梯花费的时间为 $abs(x - y) * t_1$
坐电梯花费的时间为 $abs(x - z) * t2 + t3 + t3 + abs(x - t ) * t2 + t3$
直接计算比较即可
(要我选肯定坐电梯好伐

B Appending Mex

Problem

传送门 >ω<

题目大意:
刚开始有一个空的数组,每次选择某个子集的 $mex$ 插入数组最后
$mex$ 指集合中最小没有出现的元素
给定序列,问是否有错误发生

Solution

因为是最小没有出现的元素,而且子集是任意选择,那么当前位置元素 $a[i]$ 能够出现当且仅当 $[0 , a[i] - 1]$ 已经出现过
用线段树/树状数组/...维护即可

C Candies Distribution

Problem

传送门 >ω<

题目大意:
有 $n$ 个排成一排的数 $a_i$
给定每个位置 $i$ 上的数比其左边的 $l_i$ 个位置的数要小
给定每个位置 $i$ 上的数比其左边的 $r_i$ 个位置的数要小
请给出最小的合法排列

Solution

  1. 从左到右扫,先以 $l_i$ 确定先后顺序,你会发现假设 $i , j$ 两个位置上的数都排在 $k$ 位置的后面,那么通过 $r_i$ 确定其排名即可
  2. 每个位置 $l_i+r_i$ 越大,显然排名就越高,所以按照 $l_i + r_i$ 排序然后检查即可

D Changing Array

Problem

传送门 >ω<

题目大意:
有 $n$ 个排成一排的数 $a_i$ , $0 \leq a_i \leq 2^k - 1$
现在可以将任意多的数 $\oplus 2^k - 1$ ,求最多能有多少个区间 $[l , r]$ 满足 $a_l \oplus a_{l + 1} \oplus \cdots \oplus a_r \neq 0$

Solution

先不考虑修改,可以将区间异或转化为两个前缀异或和的异或
设 $b_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i$
则 $a_l \oplus a_{l + 1} \oplus \cdots \oplus a_r = b_r \oplus b_{l - 1}$
那么题目转化为求 $b_i$ 中有多少对数异或为不为 $0$
这个非常简单,直接统计每个数相同的有多少再减去就行

那么如何处理修改呢?
发现每次修改其实可以做到只影响一个 $b_i$ ,即 $a_i \oplus 2^k - 1 , a_{i + 1} \oplus 2^k - 1$ ,那么 $b_i = b_i \oplus 2^k - 1$,其他不变
这样就很妙啊,于是乎本来每个数很多相等我们就可以将其分成一些不相等的,而且如果修改,则 $b_i \oplus 2^k - 1$ 的个数也会受到影响

设 $num[b_i]$ 为 $b$ 中为 $b_i$ 的值有多少个, $sum_i = num[i] + num[i \oplus (2^k - 1)]$ ,当区间个数取到最大值是,显然有 $sum_i$ 中一半选择 $i$ , 一般选择 $i \oplus (2^k - 1)$ ,即:

$$ ans = \frac{1}{2}\sum_{i = 1} sum_i * (n - sum_i) + \sum_{i = 1} sum_i * (sum_i - \lfloor \frac{sum}{2} \rfloor) $$

当然你在线每一位处理也是可以的,那么就只需要查询前面 $b_i$ 和 $b_i \oplus 2^k - 1$ 哪个多即可,用 $map$ 维护

Last modification:November 6th, 2018 at 10:40 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment