算法题-白红宇

算法题

阅读量：3962 次

发布时间：2019-05-24

本文共 3636 字，大约阅读时间需要 12 分钟。

文章目录

不能超过

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

给出一个序列包含n个正整数的序列A，你可以从中删除若干个数，使得剩下的数字中的最大值和最小值之差不超过x，请问最少删除多少个数字。

输入

输入第一行仅包含两个正整数n和x，表示给出的序列的长度和给定的正整数。(1<=n<=1000,1<=x<=10000)

接下来一行有n个正整数，即这个序列，中间用空格隔开。(1<=a_i<=10000)

输出

输出仅包含一个正整数，表示最少删除的数字的数量。

样例输入

5 2

2 1 3 2 5

样例输出

提示

极端情况下，当删除到仅剩1个数时，最大值和最小值的差为0，故不会出现无解的情况。

空间回廊

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

有一款叫做空间回廊的游戏，游戏中有着n个房间依次相连，如图，1号房间可以走到2号房间，以此类推，n号房间可以走到1号房间。

在这里插入图片描述

这个游戏的最终目的是为了在这些房间中留下尽可能多的烙印，在每个房间里留下烙印所花费的法力值是不相同的，已知他共有m点法力值，这些法力是不可恢复的。

小明刚接触这款游戏，所以只会耿直的玩，所以他的每一个行动都是可以预料的：

一开始小明位于1号房间。

如果他剩余的法力能在当前的房间中留下一个烙印，那么他就会毫不犹豫的花费法力值。

无论是否留下了烙印，下一个时刻他都会进入下一个房间，如果当前位于i房间，则会进入i+1房间，如果在n号房间则会进入1号房间。

当重复经过某一个房间时，可以再次留下烙印。

很显然，这个游戏是会终止的，即剩余的法力值不能在任何房间留下烙印的时候，游戏终止。请问他共能留下多少个烙印。

输入

输入第一行有两个正整数n和m，分别代表房间数量和小明拥有的法力值。(1<=n<=100000,1<=m<=10^18)

输入第二行有n个正整数，分别代表1~n号房间留下烙印的法力值花费。(1<=a_i<=10^9)

输出

输出仅包含一个整数，即最多能留下的烙印。

样例输入

4 21

2 1 4 3

样例输出

提示

样例解释：

显然是所有房间都留下两个烙印，然后剩下1点法力值，仅能在2号房间再留下一个烙印.

小仓的射击练习4

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

小仓酷爱射击运动。今天的小仓想挑战自我。小仓有N颗子弹，接下来小仓每次会自由选择K颗子弹进行连续射击，全中靶心的概率为p[k]。如果成功小仓将获得a[k]的得分，并且可以使用余下子弹继续射击，否则今天的挑战结束。小仓想知道在最佳策略下，自己能得到的最高期望分数是多少。

输入

第一行一个数N，代表子弹数量。

第二行N个数p[]，第 i 个数代表p[i]。

第三行N个数a[]，第 i 个数代表a[i]。

1<=N<=5000 0<=p[i]<=1 0<=a[i]<=1000

输出

一个数表示最高期望得分，保留两位小数。

样例输入

0.80 0.50

1 2

样例输出

1.44

提示

样例1解释

选择用一颗子弹射击：如果命中则再用余下子弹射击（仅剩一颗子弹故只能选择一颗）：0.80 * 1 + 0.80 * 0.80 * 1= 1.44

选择用两颗子弹射击：0.5 * 2 = 1.00

此时最高期望得分为1.44

输入样例2

0.90 0.10 0.10

2 1 1

输出样例2

4.88

选择用一颗子弹射击：如果命中则再用一颗子弹进行射击，如果命中则再用一颗子弹进行射击（即3轮均使用了一颗子弹进行）：0.90 * 2 + 0.90 * 0.90 * 2+0.90 * 0.90 * 0.90 * 2= 4.878≈4.88 此种情况的期望得分最高，故为4.88

拆分

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

给定长度为n的串S，仅包含小写字母。定义

公式中，|A|代表字符串A的长度

也就是说如果子串是一个ABA型的字符串，且满足长度限制，则f(l,r)=1，否则等于0。（注意：形如“ababab”也可视为ABA型）

在这里插入图片描述

例如当n=2时，原式为f(1,1)+f(1,2)+f(2,2)。

输入

第一行一个字符串S

第二行一个数字k

输出

输出题目描述中式子的值

样例输入

abcabcabc

样例输出

提示

1<=n<=2000 , S[i]为小写字母

样例解释：

在这个字符串中，有f(1,5),f(1,8),f(1,9),f(2,6),f(2,9),f(3,7),f(4,8),f(5,9)的值为1，其他为0，故和为8。以f(1,5)为例，选择的子串是abcab，令A=“ab”，B=“c”,则|A|>=k且|B|>=1,因此f(1,5)等于1，以此类推。

max xor min

时间限制：C/C++语言 1000MS；其他语言 3000MS

内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述：

给你一个长度为n的序列a，请你求出对每一个1<=l<r<=n的区间中最大值和最小值的异或和的异或和。

例如序列为{1,3,5},不同的a(1,2)=1^3,a(1,3)=15,a(2,3)=(3^5),a(1,2)a(1,3)^a(2,3)=0，所以最后的答案是0。

输入

输入第一行仅包含一个正整数n，表示序列的长度。(1<=n<=10^5)

接下来一行有n个正整数a_i，表示序列a。(1<=a_i<=10^9)

输出

输出仅包含一个整数表示所求的答案。

样例输入

1 3 5

样例输出

括号匹配

题目描述

假设一:个数学表达式仅仅包含数字[0-9]，有限的运算符[+, -, ),]以及
左右圆括号([(，)。请编写一个程序，计算表达式中圆括号左右匹配的
对数和落单的左右括号个数。
输入描述:
输入为一个数学表达式，不要求表达式合法
输出描述:
输出三个用空格分隔数字分别代表左右匹配的括号对数，落单的左
括号数量，落单的右括号数量
示例1输入输出示例仅供调试，后台判题数据一般不包含示例
输入
12+(3+3))) (((

输出

1 3 2

N进制完美数之和的所有幂因子

题目描述

给定一-个整型值R，以及进制N，返回“種复幕因子的进制完美数之和的

所有幕因子，当环是“无重复幂因子的N进制完美数之和时，返回空

函数原型std::vector getPowerFactor( int R, int N);

定义解释:

N进制完美数: N 的M饮方为进制完美数(R=NAM则R为N

进制完美数)

因子: R=N^M中M为幕因子

重复因子的N进制完美数之和: R= SUM(R’), R’为进制完美数

(R"=N ^ MP),若求和中的因子M不重复，则R为无重复幕因子的N进制完

美数之和

示例1输入输出示例仅供调试，后台判题数据一般不包含示例

输入

39,3

输出

[1,2,3]

根据顾客属性计算出顾客排队顺序

■题目描述

|快钱源间:明多人都去唯饮餐，由于吃啪人很多，所0铁排7了卡的

队伍有。

从1到。标号，一开始，每个顾高主在伍当中的

队伍当中有n个倾客，

生ai和bi。

位置是i。每个顾客有两个属性

于站在他前面的

人与

i的乘积，加上站在他后面的人与。

每个顾客的不满意度

会了，那么它的不满意度等子. (3

B的强积。正式来说，假设顾客位于位

- bi*(n-5), .
  的则，你需要重鍁接每个顾睿的拉置，使得所
  作为食堂经理，本着顾喜至上
  有的频容的不满意的的总和
  最小。
  示鳓输入施出示收供同式后台数景敏不包会示例
  复制
  输入
  [8,9,7],[5,8,3]
  输出
  [3,1,2]
  说明
  顾客排队顺序为3，1，2，此时顾客的不满意度为7 * (1-1) + 3
  (3-1)+8(2-1)+5*(3-2)+9*(3-1)+8*(3-3)