Problem - Contest

Problem - Contest

A - 计算根

题目背景

特别提示：

1. 请使用 (int) cbrt(x + 0.5) 计算 $\lfloor \sqrt[3]{x}\rfloor$ 的值，否则可能会出现精度误差。
2. 本题包含两组针对时间复杂度为 $O(q\sqrt[3]{x})$ 的算法的 hack 数据（#11 和 #12）。

题目描述

小可可想计算所有不大于 $x$ 的正整数的立方根下取整之和，但是她不会做，你能帮帮她吗？

为了彻底帮小可可弄懂这个问题，你需要回答 $q$ 组询问，对于每组询问给定的一个正整数 $x_i$，输出：

$$\sum _{j=1}^{x_i}\lfloor j^{\frac{1}{3}}\rfloor$$

其中，$\lfloor x\rfloor$ 表示不大于 $x$ 的最大整数。

输入格式

第一行一个正整数 $q$。

接下来 $q$ 行，第 $i$ 行一个正整数 $x_i$。

保证给出的 ${\mathbf{x}}_1\sim {\mathbf{x}}_{\mathbf{q}}$ 单调不降。

输出格式

$q$ 行，每行一个正整数，表示该组询问的答案。

请注意答案的范围。

样例 #1

样例输入 #1

2
5
10

样例输出 #1

5
13

提示

样例 1 解释

$1\sim 10$ 的立方根下取整的结果是：$1,1,1,1,1,1,1,2,2,2$。

数据范围

对于 $20\%$ 的数据，$x_q,q\le 1000$。

对于另外 $20\%$ 的数据，$q=1$。

对于另外 $20\%$ 的数据，$q\le 5000$。

对于另外 $20\%$ 的数据，$q\le 10^5$，$x_q\le 10^6$。

对于 $100\%$ 的数据，$1\le q\le 2\times 10^5$，$1\le x_1\le x_2\le \dots \le x_q\le 10^{12}$。

B - 有趣的2

题目描述

派派最近学会了二进制数，他觉得太小的二进制数太没意思，于是他想对一个巨大二进制数做以下 $4$ 种基础运算：

运算 $1$：将整个二进制数加 $1$。

运算 $2$：将整个二进制数减 $1$。

运算 $3$：将整个二进制数乘 $2$。

运算 $4$：将整个二进制数整除 $2$。

派派很想知道运算后的结果，他只好向你求助。

（Ps：为了简化问题，数据保证 +，- 操作不会导致最高位的进位与退位）

输入格式

第一行两个正整数 $n,m$，表示原二进制数的长度以及运算数。

接下来一行 $n$ 个字符，分别为 0 或 1 表示这个二进制数。

第三行 $m$ 个字符，分别为 +，-，*，/，对应运算 $1,2,3,4$。

输出格式

一行若干个字符，表示经过运算后的二进制数。

样例 #1

样例输入 #1

4 10
1101
*/-*-*-/*/

样例输出 #1

10110

提示

对于 $30\%$ 的数据，$1\le n,m\le 1000$。

对于 $60\%$ 的数据，$1\le n,m\le 10^5$。

对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^6$。

C - 租借计划

题目描述

在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。

我们需要处理接下来 $n$ 天的借教室信息，其中第 $i$ 天学校有 $r_i$ 个教室可供租借。共有 $m$ 份订单，每份订单用三个正整数描述，分别为 $d_j,s_j,t_j$，表示某租借者需要从第 $s_j$ 天到第 $t_j$ 天租借教室（包括第 $s_j$ 天和第 $t_j$ 天），每天需要租借 $d_j$ 个教室。

我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供 $d_j$ 个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第 $s_j$ 天到第 $t_j$ 天中有至少一天剩余的教室数量不足 $d_j$ 个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

输入格式

第一行包含两个正整数 $n,m$，表示天数和订单的数量。

第二行包含 $n$ 个正整数，其中第 $i$ 个数为 $r_i$，表示第 $i$ 天可用于租借的教室数量。

接下来有 $m$ 行，每行包含三个正整数 $d_j,s_j,t_j$，表示租借的数量，租借开始、结束分别在第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从 $1$ 开始的整数编号。

输出格式

如果所有订单均可满足，则输出只有一行，包含一个整数 $0$。否则（订单无法完全满足）

输出两行，第一行输出一个负整数 $-1$，第二行输出需要修改订单的申请人编号。

样例 #1

样例输入 #1

4 3 
2 5 4 3 
2 1 3 
3 2 4 
4 2 4

样例输出 #1

-1 
2

提示

【输入输出样例说明】

第 $1$ 份订单满足后，$4$ 天剩余的教室数分别为 $0,3,2,3$。第 $2$ 份订单要求第 $2$ 天到第 $4$ 天每天提供 $ 3 $ 个教室，而第 $3$ 天剩余的教室数为$ 2$，因此无法满足。分配停止，通知第 $2$ 个申请人修改订单。

【数据范围】

对于10%的数据，有$1\le n,m\le 10$；

对于30%的数据，有$1\le n,m\le 1000$；

对于 70%的数据，有$1\le n,m\le 10^5$；

对于 100%的数据，有$1\le n,m\le 10^6,0\le r_i,d_j\le 10^9,1\le s_j\le t_j\le n$。

D - Poker

题目背景

所谓同花顺，就是指一些扑克牌，它们花色相同，并且数字连续。

题目描述

现在我手里有 $n$ 张扑克牌，但它们可能并不能凑成同花顺。我现在想知道，最少更换其中的多少张牌，我能让这 $n$ 张牌都凑成同花顺？

输入格式

第一行一个整数 $n$ ，表示扑克牌的张数。

接下来 $n$ 行，每行两个整数 $a_i$ 和 $b_i$。其中 $a_i$ 表示第 $i$ 张牌的花色，$b_i$ 表示第 $i$ 张牌的数字。

输出格式

一行一个整数，表示最少更换多少张牌可以达到目标。

样例 #1

样例输入 #1

5
1 1
1 2
1 3
1 4
1 5

样例输出 #1

0

样例 #2

样例输入 #2

5
1 9
1 10
2 11
2 12
2 13

样例输出 #2

2

提示

• 对于 $30\%$ 的数据，$n\le 10$；
• 对于 $60\%$ 的数据，$n\le 10^5$，$ 1 \le a_{i} \le 10^{5}$，$1\le b_i\le n$；
• 对于 $100\%$ 的数据，$n\le 10^5$，$1\le a_i,b_i\le 10^9$；

F - 有点挤

题目描述

宫老板有 $N(1\le N\le 50000)$ 匹马沿着一维的栅栏吃草，第 $i$ 匹马在目标点 $x_i$ ，它的身高是 $h_i(1\le x_i,h_i\le 10^9)$。

当一匹马左边 $D(1\le D\le 10^9)$ 距离内且右边 $D$ 距离内有身高至少是它的两倍的马，它就会觉得拥挤。

请计算觉得拥挤的马的数量。

输入格式

第一行两个整数 $N,D$。

接下来 $N$ ，每行两个整数 $x_i,h_i$。保证 $x_i$ 互不相同。

输出格式

一行一个整数，表示觉得拥挤的马的数量。

样例 #1

样例输入 #1

6 4 
10 3 
6 2 
5 3 
9 7 
3 6 
11 2

样例输出 #1

2