字节跳动

ZJ1 附加题

存在n+1个房间，每个房间依次为房间1 2 3…i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略： A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1； B. 如果访问过当前房间 i 奇数次，那么移动到房间pi； 现在路人甲想知道移动到房间n+1一共需要多少次移动；

输入描述：

第一行包括一个数字n(30%数据1<=n<=100，100%数据 1<=n<=1000)，表示房间的数量，接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。

输出描述：

输出一行数字，表示最终移动的次数，最终结果需要对1000000007 (10e9 + 7) 取模。

示例1

输入：

1
2

2
1 2

输出：

1

4

说明：

1

开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。

分析：

https://blog.nowcoder.net/n/49cc621cec0a43ce8e9de0ad0d23246d

注意题目中提到的 pi(1 <= pi <= i)，这说明了策略B只可能是原地不动或后退。那么结合策略A让路人甲前进，假设dp[i] 为第一次到达i移动的次数，并且i前面的所有门都已经到达偶数次了。 所以dp[i] = dp[i-1] + x + 1; （x表示第二次到达i-1的步数）

第一次到达i-1门再走一步回到p[i-1]门（在i-1之前的门都经过偶数次），此时到达p[i-1]奇数次，其他所有门到达偶数次。这跟第一次到达p[i-1]门的情况完全相同。因此，从p[i-1]回到i-1门，需要dp[i-1] - dp[p[i-1]]次移动 （子问题），所以 x = dp[i-1] - dp[p[i-1]] + 1。

故dp[i] = dp[i-1] + dp[i-1] + dp[p[i-1]] + 1 + 1 = 2 * dp[i-1] - dp[p[i-1]] + 2;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n+1);
    for (int i=1; i<=n; i++) {
        cin >> p[i];
    }
    vector<int>dp(n+2);
    const int mod = 1e9 + 7;
    for (int i=2; i<=n+1; i++) {
        dp[i] = (2 * dp[i-1] % mod - dp[p[i-1]] + 2) % mod;
    }
    cout << dp[n+1] << endl;
    return 0;
}

ZJ2 编程题1

描述

有三只球队，每只球队编号分别为球队1，球队2，球队3，这三只球队一共需要进行 n 场比赛。现在已经踢完了k场比赛，每场比赛不能打平，踢赢一场比赛得一分，输了不得分不减分。已知球队1和球队2的比分相差d1分，球队2和球队3的比分相差d2分，每场比赛可以任意选择两只队伍进行。求如果打完最后的 (n-k) 场比赛，有没有可能三只球队的分数打平。



输入描述：

第一行包含一个数字 t (1 <= t <= 10) 接下来的t行每行包括四个数字 n, k, d1, d2(1 <= n <= 10^12; 0 <= k <= n, 0 <= d1, d2 <= k)

输出描述：

每行的比分数据，最终三只球队若能够打平，则输出“yes”，否则输出“no”

示例1

输入：

1
2
3

2
3 3 0 0
3 3 3 3

输出：

1
2

yes
no

说明：

1
2

case1: 球队1和球队2 差0分，球队2 和球队3也差0分，所以可能的赛得分是三只球队各得1分
case2: 球队1和球队2差3分，球队2和球队3差3分，所以可能的得分是 球队1得0分，球队2得3分, 球队3 得0分，比赛已经全部结束因此最终不能打平。

分析：假设 三个队的分数分别是，x+d1, x, x+d2。三个队的总分为k。则x * 3 + d1 + d2 = k。则三个队伍的分数可以计算出来。然后将剩余场次的分数补到分数低的队伍尽可能让他们分数相等。 60%

1

阿里

京东

JD1 年终奖

传送门

分析：二维DP模板

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

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        // dp[i][j]: 位于(i, j)获得的最大价值
        // dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + board[i][j];
        int n = 6, m = 6;
        vector<vector<int>> dp(n, vector<int>(m, 0));
        dp[0][0] = board[0][0];
        for (int i=1; i<n; i++) {
            dp[i][0] = dp[i-1][0] + board[i][0];
        }
        for (int j=1; j<m; j++) {
            dp[0][j] = dp[0][j-1] + board[0][j];
        }
        for (int i=1; i<n; i++) {
            for (int j=1; j<m; j++) {
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + board[i][j];
            }
        }
        return dp[n-1][m-1];
    }
};

JD3 小东分苹果

传送门

1
2
3
4
5
6
7

class Apples {
public:
    int getInitial(int n) {
        // write code here
        return long(pow(n, n) + 1 - n);
    }
};

专项