题面我完全忘了，这里写的题面是我自己编的

关于代码里的一些习惯

我本地测试定义了 DEBUG 常量，#ifdef和#endif包裹的代码是用于进行文件流输入输出的，如果不想重复输入样例，可以新建一个input.in的纯文本文件，将样例打进去即可，控制台输出会输出至output.out文件内

若想使用文件流输入输出，需要在首部加入

1
#define DEBUG

Problem A 时间转换

Description

给出一个整数，表示从 1970 年 01 月 01 日 00 时 00 分 00 秒起至现在经过了多少毫秒，把它转换成HH:MM:SS的形式，使用 24 小时制，不足两位的时间补 0

Input

第一行一个整数 TT ，表示输入的字符串，表示从 1970 年 01 月 01 日 00 时 00 分 00 秒起至现在的总毫秒数

Output

对于输入数据，输出一行格式为HH:MM:SS的字符串代表转换后的时间，注意不足两位的时间需要补 0，其中 0<T<1090<T<10^9

Sample Input

1
1639634400000

Sample Output

1
06:00:00

Hint

样例数据代表的是北京时间2021-12-16 14:00:00所代表的的时间，其格林尼治时间为06:00:00

Solution

这个题也能算是经典题目了，这个东西实际上就是 UNIX 时间戳的一种变形

UNIX 时间，或称 POSIX 时间是 UNIX 或类 UNIX 系统使用的时间表示方式：从 UTC1970 年 1 月 1 日 0 时 0 分 0 秒起至现在的总秒数

当然一般来说规定的 UNIX 时间戳是以秒来计算的，这个题是用毫秒来输入的

但是这不是问题，因为我们输出的结果又不要我们给出毫秒数，我们可以直接对输入做个小处理，对整数做除 1000 的操作，丢掉后面三位，就是一个标准的 UNIX 时间戳了

那么对于这个时间戳的处理也很简单，首先我们不需要年月日，稍微心算一下，一天有 24×60×60=8640024\times60\times60=86400 秒，我们再对时间戳做取模运算，对其模 8640086400 ，这个时候剩下的值就是单纯的时分秒了，按顺序取出即可

拓展

有些人可能会苦恼未满两位补 0 怎么做，简单点的办法，C 语言可以写个 if，值小于 10 先输出一个 0 再输出数据

当然还有一种形式

1
printf("%02d:%02d:%02d", hour, minute, second);

其中的%02d表示输出宽度为 2，不满 2 的输出补 0

对于 C++的 cout，有如下函数选择

  • setw()：用于控制输出宽度，不足默认补空格

  • setfill()：用于更改默认填充的字符

剩下的可以直接看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    int hour = 0, minute = 0, second = 0;
    unsigned long long n;
    cin >> n;
    n /= 1000, n %= 86400;
    hour = n / 3600, n = n % 3600;
    minute = n / 60, n = n % 60;
    second = n;
    cout << setw(2) << setfill('0') << hour << ":"
         << setw(2) << setfill('0') << minute << ":"
         << setw(2) << setfill('0') << second;
    return 0;
}

Problem B 寻找第一个出现的位置

Description

给出一个整数和一个序列，求这个整数在这个序列中第一次出现的位置

Input

第一行一个整数 nn ，表示输入的序列长度，第二行 nn 个整数，表示输入序列，第三行一个 mm ，表示需要查找的值

Output

若找到该整数，则输出该整数在序列内的位置，若未找到该整数，则输出 −1-1

Sample Input

1
2
3
6
23 54 34 3 412 3
3

Sample Output

1
4

Hint

33 这个元素第一次出现在序列中的第 44 个位置，故输出 44

Solution

不好说，这个只要是学了循环应该就能做，纯纯签到题

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>
#define MAXN 10005
using namespace std;
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    int n, val, a[MAXN];
    cin >> n;
    for_each(a, a + n, [&](int &x)
             { cin >> x; });
    cin >> val;
    for (int i = 0; i < n; i++)
        if (a[i] == val)
        {
            cout << i + 1 << endl;
            return 0;
        }
    cout << -1 << endl;
    return 0;
}

Problem C 最大金币值

Description

给出一个 n∗nn*n大小的迷宫，每个格子内有 mm 个金币，从左上角开始，每次移动只能向下或者向右移动，问最多能拿到多少金币,答案对 109+710^9+7 取模

Input

第一行一个整数 n(0<n<1000)n(0<n<1000) ，表示矩阵大小，第 2∽n+12\backsim n+1 行有 nn 个整数，每个整数 k(0<k<108)k(0<k<10^8) 代表当前格内的金币数量

Output

输出一个整数，为最多能拿到金币的数量

Sample Input

1
2
3
4
5
6
5 5
23  434 23  123 32
234 52  32  43  13
43  56  898 656 77
346 775 223 56  23
2   556 7   8   9

Sample Output

1
2188

Solution

有两种解法

第一种是 DP(动态规划)写法，第二种是 DFS(深度优先搜索)写法

动态规划

考试的时候没想那么多，解法来自永远的神浩伟哥哥

假设我们已经知道了从 (1,1)(1,1) 走到 (n,n−1)(n,n-1) 和从 (1,1)(1,1) 走到 (n−1,n)(n-1,n) 能够获得的最多的金币量

显然，我们走到 (n,n)(n,n) 能够获得的最多的金币量就很容易求出来

如何知道走到 (n,n−1)(n,n-1) 能够获得的最多的金币量呢

只要知道 (n−1,n−1)(n-1,n-1) 和 (n,n−2)(n,n-2) 能够获得的最多的金币量就可以了

以此类推，我们只要知道起点位置的金币量就可以了

此问题的解是求 F(n,n)F(n,n) ，分析可得 F(n,n−1)F(n,n-1) 和 F(n−1,n)F(n-1,n) 是 F(n,n)F(n,n) 的子问题，由分治的思想，可以由子问题的最优解得到总问题的最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
#define MAXN 1000
using namespace std;
int n, m[MAXN][MAXN];
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> m[i][j];
            m[i][j] += max(m[i - 1][j], m[i][j - 1]);
        }
    cout << m[n][n];
    return 0;
}

深度优先搜索

首先写个边界条件，当跑到矩阵外面的时候返回

对于每一次 DFS，传入一对坐标，一个当前值val，给val加上当前坐标的值，判断是否还能继续走(是否撞墙)

如果撞墙且已经无路可走，将当前的val值与最大值ans比较，赋最大值给ans

然后分两个方向进行深搜，分别是向下和向右，这样的逻辑保证了不会走回头路，所以也不需要标记是否走过当前节点

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>
#define MAXN 1000
const int MOD = 1e9 + 7;
using namespace std;
int m[MAXN][MAXN];
int n, ans = 0;
void dfs(int x, int y, int val)
{
    val += m[x][y], val %= MOD;
    if (x > n || y > n)
    {
        ans = max(ans, val);
        return;
    }
    dfs(x + 1, y, val);
    dfs(x, y + 1, val);
}
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    cin >> n;
    for (int y = 1; y <= n; y++)
        for (int x = 1; x <= n; x++)
            cin >> m[y][x];
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}

Problem D 整数分解

Description

对于一个整数，我们可以对它进行两种操作

  • 减去 1

  • 减去 3

当它恰好等于 0 时，我们称这一串操作为一种方案，求对于一个整数 nn ，有多少种方案

Input

第一行一个整数 n(0<n<1000)n(0<n<1000)

Output

输出一个整数，为分解的方案数

Sample Input

1
3

Sample Output

1
2

Hint

第一种情况： 3=3−33=3-3 ，执行一次减 3 操作

第二种情况： 3=3−1−1−13=3-1-1-1 ，执行三次减 1 操作

共 22 种情况

Solution

深度优先搜索

首先写个边界条件，当前的值等于 0 的时候使方案数+1，当前值小于 0 的时候返回，但是不要做操作，因为它并不是答案，比如说对于 22 来说，减 3 操作并不是它的方案

接下来直接搜减 1 和减 3 操作即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int n, ans = 0;
void dfs(int val)
{
    if (val == 0) { ans++; return; }
    if (val < 0) return;
    dfs(val - 1);
    dfs(val - 3);
}
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    cin >> n;
    dfs(n);
    cout << ans;
    return 0;
}

动态规划

如果我们已知拆分 n−1n-1 的方法数量和拆分 n−3n-3 的方法数量，则吃 nn 个东西的方法总数等于 F(n−1)+F(n−3)F(n-1)+F(n-3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
#define MAXN 1000
using namespace std;
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    int a[MAXN] = {1, 1, 1, 2}, n;
    cin >> n;
    for (int i = 4; i <= n; i++)
        a[i] = a[i - 1] + a[i - 3];
    cout << a[n];
    return 0;
}

Problem E 资本家

Description

一个资本家有 nn 座店铺，他把每一天划分成 mm 个时间段

对于每一个时间段，每个店铺里有 AiA_i 个店员，当前时间段每个店铺会有 BiB_i 个顾客光临，而在每个时间段内每个店铺的人均消费额度为 CiC_i

现在资本家的商铺每天只能提供一个时间段的服务，并且一个服务员只能服务一位顾客，若一个顾客没有得到服务员服务将不会提供营业额，请问这种情况下，最大的营业额是多少？

Input

第一行两个整数 n,m(0<n,m<1000)n,m(0<n,m<1000)

之后是 33 个 n×mn\times m 的矩阵A,B,C

每个矩阵分别代表 nn 座店铺在 mm 个时间段内的店员数量，顾客数量和人均消费额

Output

输出一个整数，为最大营业额

Sample Input

1
2
3
4
5
6
7
2 3
1 2 3
3 2 1
3 2 1
1 2 3
4 5 2
3 1 6

Sample Output

1
16

Solution

阅读理解题

人都要看麻了

看完其实挺简单的，对 AB 矩阵的每一个元素取最小值，再与 C 矩阵的每一项相乘，取每家店铺乘积最大的时间段相加即可

因为对于顾客和服务员的关系，永远是两者取最小，毕竟是一一对应关系，最小的那个值才能创造营业额，那么把这个最小值跟人均消费额度相乘，就是当前时间段的营业额，把 n 家店铺每个时间段的最大值取出来相加，就是最大营业额了

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
#include <bits/stdc++.h>
#define MAXN 1000
#define FOR                      \
    for (int i = 1; i <= n; i++) \
        for (int y = 1; y <= m; y++)
using namespace std;
int n, m;
int A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];
int main()
{
#ifdef DEBUG
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif
    cin >> n >> m;
    int total = 0;
    FOR cin >> A[i][y];
    FOR cin >> B[i][y];
    FOR cin >> C[i][y];
    for (int i = 1; i <= n; i++)
    {
        int ans = 0;
        for (int j = 1; j <= m; j++)
            ans = max(min(A[i][j], B[i][j]) * C[i][j], ans);
        total += ans;
    }
    cout << total;
    return 0;
}