0918练习题解

A 青蛙赶路

有一只青蛙，每秒选择走1米或跳m米，青蛙体力不足，所以不能连续两秒都在跳。
青蛙将移动到[l,r]之间，它想知道有多少种不同的方式来实现其目标。
两种方式是不同的，当且仅当它们移动不同的米或花费不同的秒，或者是在一秒钟内，其中一个走而另一个跳。

Input

第一行输入包含2个整数n和m,n是查询数。（n <= 100000,2 <= m <= 100000）
对于下n行，每行包含两个整数l和r.（1 <= l <= r <= 100000）

Output

对于每个查询，输出到达的方案数，最后是模1000000007的答案。

Sample Input

4 4
4 4
1 4
1 5
1 6

Sample Output

2
5
8
12

题解：

这题的原理其实和我以前写的DP入门的博客里面的题非常相似，就是增加了不能二段跳这一限制，所以稍微改一下代码就行，记得使用前缀和哦

AC代码:

/*
* ===============================================
* Filename: A.cpp
* Description: 
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[100005];
const ll mod = 1000000007;
int main()
{
    int n, m;
    cin >> n >> m;
    dp[0] = 1;
    dp[1] = 1;
    dp[m] = 1;
    for (int i = 2; i <= 100000; i++)
    {
        dp[i] += dp[i - 1];
        if (i - m - 1 >= 0)
        {
            dp[i] += dp[i - m - 1]% mod;
        }
        dp[i] %= mod;
    }
    for (int i = 2; i <= 100000; i++)
    {    
        dp[i] += dp[i - 1];
        dp[i] %= mod;
    }
    dp[0]=0;
    while (n--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld\n", (dp[r] - dp[l - 1] + mod) % mod);
    }
    return 0;
}

---

B 贪吃蛇大作战

贪吃蛇大家一定都玩过吧，现在宋哥也要玩这个游戏，最初的时候贪吃蛇从屏幕的左下角出发，但是有一个非常不幸的事情，就是宋哥的游戏机的左键和下键坏掉了，这意味着什么？没错！他只能操控他的蛇向右或向上走了，假设屏幕被划分为10^9*10^9的格子，而贪吃蛇从坐标为(1,1)的格子出发，每次操作可以从坐标为(x,y)的格子前往坐标为(x+1,y)或(x,y+1)的格子，在所有格子中有一些格子中有一些食物，宋哥现在想知道，他的贪吃蛇最多能吃到多少食物呢？

Input

输入的第一行包含一个数字T(1<=T<=10)，代表数据组数，之后的每组数据的每一行包含一个数字n (1<=n<=1000)，代表有食物的格子数量，之后的n行每一行包含三个数字xi(1<=xi<=10^9),yi(1<=xi<=10^9),pi(1<=xi<=10^6)，分别代表格子的坐标和在这个格子里的食物数量。

Output

输出T行，第i行为第i组数据的答案。

Sample Input

2
3
1 1 1
2 2 2
3 3 3
3
1 3 1
2 2 2
3 1 3

Sample Output

6
3

题解

没啥说的，就是一个标准的DP，亏我当时还认为DP也会炸，（头没了）

AC代码

// 其实这题主要是问需要经过哪些点，而不是问路径如何
// 再结合本题的数据量，因此本题绝对是一道DP的题
// 不可能是搜索, 更不可能是单纯的贪心

/*
* ===============================================
* Filename: B.cpp
* Description: 代码嫖的jscblack(唯一真神)的
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

struct node
{
    int x, y;
    long long value;
}in[1005];
// DP 数组

bool cmp(node s1, node s2)
{
    if (s1.x == s2.x)
        return s1.y < s2.y;
    return s1.x < s2.x;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {

        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> in[i].x >> in[i].y >> in[i].value;
        }
        sort(in, in + n, cmp);
        // 将输入的点进行排序，（按照x和y升序）
        long long ans = 0;
        for (int i = 1; i < n; i++)
        {
            long long maxx = in[i].value;

            for (int j = i - 1; j >= 0; j-- )
            {
                if (in[i].x >= in[j].x && in[i].y >= in[j].y)
                {
                    // 满足移动条件（向上或者向右移动）
                    maxx = max(maxx, in[j].value + in[i].value);
                    // 寻找最大路径
                }
            }
            in[i].value = maxx;
            // 更新DP数组和答案
            ans = max(ans, in[i].value);
        }

        cout << ans << endl;
    }
    return 0;
}

---

C 小L的数列

小L有一串数字，他想将这串数字分为连续的三段，并且每一段数字的和都是相等的，即找到i，j使得sum[1,i-1]=sum[i,j]=sum[j+1,n]。
你能帮助小L得到这样的i，j有几对么？
注意：这三段中每一段必须有数字，不能出现一段为空的情况。

Input

输入有多组，不超过20组
第一行输入n，表示有n个数字。
第二行有n个数字，表示小L拥有的n个数字。
n的取值范围[1,5e5]
每个数字的范围[-1e9,1e9]

Output

一个数字，表示i，j的对数。

Sample Input

5
1 2 3 0 3
4
0 1 -1 0
2
4 1

Sample Output

2
1
0

题解：

这题其实是一道典型的前缀和，结果我因为好久都没写前缀和，导致当时没看出来就跳后面的题目去了

AC代码

/*
* ===============================================
* Filename: C.cpp
* Description: 
* Website: https://grimoire.cn
* Copyright (c) 2020 Mr.Sen. All rights reserved.
* ===============================================
*/

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int num[N], res[N];

int main()
{
    int n;
    while (cin >> n)
    {
        long long sum = 0;
        memset(res, 0, sizeof(res));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &num[i]);
            sum += num[i];
            // sum 是总和
            // num[i] 是输入的每一个数字
        }
        if (sum % 3 != 0)
        {
            printf("0\n");
            continue;
        }
        long long tt = 0;
        res[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            tt += num[i];
            if (tt == sum / 3 * 2 && i != 1 && i != n)
                // 这里寻找的其实是 j
                res[i] ++;
            res[i] += res[i - 1];
            // 前缀和处理
        }
        tt = 0;
        long long ans = 0;
        for (int i = 1; i <= n; i++)
        {
            tt += num[i];
            if (tt == sum / 3 && i != n)
            {
                ans += res[n] - res[i];
                // 从这里开始， 
                // 后面有res[n] - res[i]个j满足条件，所以增加j
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}