机器人跳跃问题

机器人正在玩一个古老的基于 DOS 的游戏。

游戏中有 N+1 座建筑——从 0到 N 编号，从左到右排列。

编号为 0 的建筑高度为 0个单位，编号为 i的建筑高度为 H(i) 个单位。

起初，机器人在编号为 0的建筑处。

每一步，它跳到下一个（右边）建筑。

假设机器人在第 k个建筑，且它现在的能量值是 E，下一步它将跳到第k+1 个建筑。

如果 H(k+1)>E，那么机器人就失去 H(k+1)−E 的能量值，否则它将得到E−H(k+1) 的能量值。

游戏目标是到达第 N 个建筑，在这个过程中能量值不能为负数个单位。

现在的问题是机器人至少以多少能量值开始游戏，才可以保证成功完成游戏？

输入格式

第一行输入整数 N。

第二行是 N个空格分隔的整数，H(1),H(2),…,H(N)代表建筑物的高度。

输出格式

输出一个整数，表示所需的最少单位的初始能量值上取整后的结果。

数据范围

1≤N,H(i)≤1e5,

输入样例1：

1
2

5
3 4 3 2 4

输出样例1：

1

4

输入样例2：

1
2

3
4 4 4

输出样例2：

1

4

输入样例3：

1
2

3
1 6 4

输出样例3：

1

3

分析

不论往高处跳和往低处跳，下一台阶机器人的能量都为2*E-H[i] 。可知 E越大 ，能量越大 ，可得出具有单调性 ，可以用二分做。

数据范围为1e5，n^2暴力算法将超时

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int h[N];
int n;
bool check(int x){
    for (int i = 0; i < n; i ++ ){
        x = 2*x-h[i];
        if(x<0){
            return false;
        }
        if(x>=1e5) return true;//重点，如不加此判断x将会溢出，溢出到负数小于0，走上个if逻辑，结果将会出错
    }
    return true;
}
int main()
{
    
    cin>>n;
    for (int i = 0; i < n; i ++ ){
        cin>>h[i];
    }
    int l =0,r=1e5;
    while(l<r){ //经典二分
        int mid = l+r>>1;
        if(check(mid)) r= mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}

有趣的数

我们把一个数称为有趣的，当且仅当：

  1. 它的数字只包含 0,1,2,3，且这四个数字都出现过至少一次。
  2. 所有的 0 都出现在所有的 1 之前，而所有的 2 都出现在所有的 3 之前。
  3. 最高位数字不为 0。

因此，符合我们定义的最小的有趣的数是 2013。

除此以外，4 位的有趣的数还有两个：2031 和 2301。

请计算恰好有 n 位的有趣的数的个数。

由于答案可能非常大，只需要输出答案除以 1e9+7 的余数。

输入格式

输入只有一行，包括恰好一个正整数 n。

输出格式

输出只有一行，包括恰好 n 位的整数中有趣的数的个数除以 1e9+7的余数。

数据范围

4≤n≤1000

输入样例：

1

4

输出样例：

1

3

分析

对于条件 2 把条件 2 划分为两类

0.1 设有 k 位 2.3 设有 n−k 位

由于最高位不是 0 ，所以0在1之前不可以在第一位

因为四个数字至少出现一次，所以 k 最多只能有 n−2 位 于是我们得到了 k 的范围 k≥2 and k≤n−2，所以2≤k≤n−2

对于条件 2 的每一类 我们再对 kk位的 0 1 数进行分类

设 0 的个数为 a 个，那么，1 的个数就是 k−a 个 由于每个数至少出现一次，所以 a的范围是 1≤a≤k−1 所以，k 位的 0 1 数总共有 k−1种选法 n−k 的 2 3 数同理，总共有 n−k−1 种选法 →→ 可以根据 0 1 数的选法获得

计算答案 对于每一个 k(2≤k≤n−2)分别计算答案

C[n - 1] [k] * (k - 1) * (n - k - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1005,MOD=1e9+7;
int c[N][N];
int main()
{
    cin>>n;
    for(int i = 0;i<=n;i++){
        for (int j = 0; j <=i; j ++ ){
            if(j==0) c[i][j]=1;
            else{
                c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
            }
        }
    }
    int res=0;
    for (int i = 2; i <= n-2; i ++ ){
        res=(res+(long long)c[n-1][i]*(i-1)%MOD*(n-i-1))%MOD;
    }
    cout<<res<<endl;
    return 0;
}