【题解】2021年7月16日BNDSOJ模拟测验

发表于 分类于 阅读次数： Valine：

比赛链接（BNDSOJ）

题目 T1 T2 T3 T4
得分  20  30  20  100

T1 那23个路口

题目链接（BNDSOJ）

题目大意

给出一个\(m \times n\)的矩阵，每个点上有权值，其中权值为\(-1\)的点不能通过。给定一个出发点，求走\(23\)步之后走过的点的最大权值和。

\(0<n,m<300\)

分析

暴力搜索复杂度为\(O(4^n)\)，不可用，想到动态规划。

设\(dp_{i,j,k}\)表示终点在坐标\((i,j)\)走了\(k\)步时的最大权值和，我们考虑一个点的四个方向即可得出转移方程： \[ dp_{i,j,k}=\max (dp_{i,j-1,k-1},dp_{i,j+1,k-1},dp_{i+1,j,k-1},dp_{i-1,j,k-1}) \] 另外，要先预处理出从起点到每个点的步数，在枚举步数的没有达到时不要转移。

要注意本题是\(m \times n\)的矩阵，即\(m\)行\(n\)列，本人就在读入上面丢了\(80\)分……

实现

附完整代码\((52ms,12332kb)\)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>

#define ll long long
const ll inf = 1e18;
using namespace std;
int n, m, sx, sy;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool book[302][302];
ll a[302][302], dp[302][302][24], pat[302][302];

ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;
}

inline bool check(int x, int y) {
    if (x < 0 || x > m || y < 0 || y > n) return false;
    else if (a[x][y] == -1) return false;
    else if (x == sx && y == sy) return false;
    else return true;
}

void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || nx > m || ny < 0 || ny > n) continue;
        if (book[nx][ny] || a[nx][ny] == -1 || a[nx][ny] == 0) continue;
        book[nx][ny] = true;
        dfs(nx, ny);
    }
}

int main() {
    n = read();
    m = read();
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = read();
            if (a[i][j] == -1) {
                for (int k = 0; k <= 23; k++) {
                    dp[i][j][k] = -inf;
                }
            } else if (a[i][j] == 0) {
                sx = i;
                sy = j;
                dp[i][j][0] = 0;
            }
        }
    }
    book[sx][sy] = true;
    dfs(sx, sy);
    for (int k = 1; k <= 23; k++) {
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (abs(i - sx) + abs(j - sy) > k) continue;
                if (!book[i][j]) continue;
                ll cnt = -inf;
                if (check(i, j - 1)) cnt = max(cnt, dp[i][j - 1][k - 1]);
                if (check(i, j + 1)) cnt = max(cnt, dp[i][j + 1][k - 1]);
                if (check(i + 1, j)) cnt = max(cnt, dp[i + 1][j][k - 1]);
                if (check(i - 1, j)) cnt = max(cnt, dp[i - 1][j][k - 1]);
                dp[i][j][k] = cnt + a[i][j];
            }
        }
    }
    ll ans = -inf;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            ans = max(dp[i][j][23], ans);
        }
    }
    cout << ans;
    return 0;
}

T2 我们的可可西里

题目链接（BNDSOJ）

题目大意

给出\(N\times N\)的方格，放进去\(N\)个点，每行每列只能有一个点且坐标为\((i,i),i \in [1,N]\)的格子上不能放点，求一共有多少种放的方法。

\(N\le 1000\)

分析

转化一下问题，每一个列都必须放一个点，且不能放在和自己点的编号相同的位置上，即点\((i,i)\)上，所以这是一个错排问题。

下面求错排的递推公式：

设\(f_i\)表示编号为\(1-i\)时总方案数，易得\(f_1=0,f_2=1\)。

现在求\(f_k\)，有两种情况：

  • 编号为\(k\)的球可以在\(1\)到\(k-1\)的球中选择一个交换，这样的总方案数是\((k-1)\times f_{k-2}\)；
  • 编号为k的球可以在\(1\)到\(k-1\)的位置中选择一个放，原来在这个位置的球不放在第k个位置，这样的总方案数是\((k-1)\times f_{k-1}\)；

将两种情况的方案数相加，我们可得递推公式： \[ f_k=(k-1)\times (f_{k-1}+f_{k-2}) \] 利用容斥原理也可推出错排公式： \[ f_n=n!\times \sum_{i=2}^n \frac{1}{i!}(-1)^i \] 因为数据范围较大，本题需要高精度加法。

实现

附完整代码\((323ms,42132kb)\)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<bits/stdc++.h>

const int N = 10005;
using namespace std;

struct bign {
    int d[N], len;

    void clean() {
        while (len > 1 && !d[len - 1]) len--;
    }

    bign() {
        memset(d, 0, sizeof d);
        len = 1;
    }

    bign(int num) {
        *this = num;
    }

    bign operator=(const char *num) {
        memset(d, 0, sizeof d);
        len = strlen(num);
        for (int i = 0; i < len; i++) d[i] = num[len - i - 1] - '0';
        clean();
        return *this;
    }

    bign operator=(int num) {
        char s[20];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }

    bign operator+(const bign &b) const {
        bign c = *this;
        int i;
        for (i = 0; i < b.len; i++) {
            c.d[i] += b.d[i];
            if (c.d[i] > 9) c.d[i] %= 10, c.d[i + 1]++;
        }
        c.len = max(c.len, b.len);
        if (c.d[i] && c.len <= i) c.len = i + 1;
        return c;
    }

    bign operator*(const bign &b) const {
        int i, j;
        bign c;
        c.len = len + b.len;
        for (j = 0; j < b.len; j++) {
            for (i = 0; i < len; i++) {
                c.d[i + j] += d[i] * b.d[j];
            }
        }
        for (i = 0; i < c.len - 1; i++) {
            c.d[i + 1] += c.d[i] / 10;
            c.d[i] %= 10;
        }
        c.clean();
        return c;
    }

    string str() const {
        char s[N] = {};
        for (int i = 0; i < len; i++) s[len - 1 - i] = d[i] + '0';
        return s;
    }

};

bign f[1005], m;

ostream &operator<<(ostream &out, const bign &x) {
    out << x.str();
}

int n;

int main() {
    cin >> n;
    f[1] = 0;
    f[2] = 1;
    f[3] = 2;
    for (int i = 3; i <= n; i++) {
        bign k = i - 1;
        f[i] = k * (f[i - 1] + f[i - 2]);
    }
    cout << f[n];
    return 0;
}

T3 斯迈利的赌注

题目链接（BNDSOJ）

题目大意

两个人\(A,B\)在玩报数游戏，开始的数\(K\)值为\(M\)，\(A\)和\(B\)每人轮流报一个数\(J\)，这个数是\(2,4,8,16,32\) 中的任意一个，并将\(K\)的值乘以\(J\)。如果某一次报数后\(K\)大于\(N\)，则最后报的人输。

给出\(M,N\)，判断有必胜策略的是先手还是后手，如果是先手输出第一个报的数。

\(1\le M \le 2^{31}-1,N>=M,\lg N\le150\)

分析

将游戏过程中的判断用公式表示出来即： \[ M\times J=M\times 2^i>N,i\in [1,5] \] 转化一下： \[ M\times 2^i>N~~2^i>\frac{N}{M}~~i>\log_2^{\frac{N}{M}} \] 所以，问题变成：每人报\(1,2,3,4,5\)中的一个数，谁先报到\(\log_2^{\frac{N}{M}}\)，于是可得必胜策略：与前面拿的个数和为\(6\)，这样如果\(\frac{N}{M} \equiv 1(\mod 6)\)，是必胜的，最后一个一定被对方拿完，于是走后手；否则走先手，把\(\frac{N}{M}\)取到\(\frac{N}{M} \equiv 1(\mod 6)\)即可。

本题依然需要高精度。

实现

附完整代码\((390ms,3560kb)\)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>

using namespace std;
const int N = 10005;

struct bign {
    int d[N], len;

    bign() {
        memset(d, 0, sizeof d);
        len = 1;
    }

    void clean() {
        while (len > 1 && !d[len - 1]) len--;
    }

    bign(int num) { *this = num; }

    bign(char *num) { *this = num; }

    bign operator=(const char *num) {
        memset(d, 0, sizeof(d));
        len = strlen(num);
        for (int i = 0; i < len; i++) d[i] = num[len - i - 1] - '0';
        clean();
        return *this;
    }

    bign operator=(int num) {
        char s[20];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }

    bign operator+(const bign &b) {
        bign c = *this;
        int i;
        for (int i = 0; i < b.len; i++) {
            c.d[i] += b.d[i];
            if (c.d[i] > 9) c.d[i++] %= 10, c.d[i + 1]++;
        }
        while (c.d[i] > 9) c.d[i++] %= 10, c.d[i]++;
        c.len = max(len, b.len);
        if (c.d[i] && c.len <= i) c.len = i + 1;
        return c;
    }

    bign operator-(const bign &b) {
        bign c = *this;
        int i;
        for (int i = 0; i < b.len; i++) {
            c.d[i] -= b.d[i];
            if (c.d[i] < 0) c.d[i] += 10, c.d[i + 1]--;
        }
        while (c.d[i] < 0) c.d[i++] += 10, c.d[i]--;
        clean();
        return c;
    }

    bign operator*(const bign &b) const {
        int i, j;
        bign c;
        c.len = len + b.len;
        for (j = 0; j < b.len; j++) {
            for (i = 0; i < len; i++) c.d[i + j] += d[i] * b.d[j];
        }
        for (i = 0; i < c.len - 1; i++) c.d[i + 1] += c.d[i] / 10, c.d[i] %= 10;
        c.clean();
        return c;
    }

    bign operator/(const bign &b) {
        int i, j;
        bign c = *this, a = 0;
        for (i = len - 1; i >= 0; i--) {
            a = a * 10 + d[i];
            for (j = 0; j < 10; j++) if (a < b * (j + 1)) break;
            c.d[i] = j;
            a = a - b * j;
        }
        c.clean();
        return c;
    }

    bool operator<(const bign &b) const {
        if (len != b.len) return len < b.len;
        for (int i = len - 1; i >= 0; i--) {
            if (d[i] != b.d[i]) return d[i] < b.d[i];
        }
        return false;
    }

    bool operator>(const bign &b) const {
        return b < *this;
    }

    string str() const {
        char s[N] = {};
        for (int i = 0; i < len; i++) s[len - i - 1] = d[i] + '0';
        return s;
    }

};

istream &operator>>(istream &in, bign &x) {
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream &operator<<(ostream &out, const bign &x) {
    out << x.str();
    return out;
}

int main() {
    //freopen("a.in","r",stdin);
    bign n, m;
    cin >> m >> n;
    n = n / m;
    int cnt = 0;
    while (!(n < 2)) {
        cnt++;
        n = n / 2;
        while (!(n < 8192)) {
            n = n / 8192;
            cnt += 13;
        }
    }
    cnt++;
    if (cnt % 6 == 1) printf("0");
    else {
        int ans = 1;
        int num = cnt % 6 - 1;
        if (num < 0) num += 6;
        for (int i = 1; i <= num; i++) {
            ans *= 2;
        }
        printf("%d", ans);
    }
    return 0;
}

T4 运输

题目链接（BNDSOJ）

题目大意

给出含有\(n\)个元素的数列\(w\)，每次从中取出两个数，将它们的和除以\(K\)再放回，直到只剩一个数，求这个数的最小值。

\(n\le 10000,k\le 10000\)

分析

一道典型的贪心题，用优先队列维护大根堆，每次取堆顶两元素合并。

实现

附完整代码\((40ms,2980kb)\)

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
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>

#define ll long long
using namespace std;
ll n, k;
ll w[100005];

ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + ch - '0';
        ch = getchar();
    }
    return s * w;

}

priority_queue<ll> q;

int main() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++) {
        w[i] = read();
        q.push(w[i]);
    }
    while (q.size() != 1) {
        ll a, b, c;
        a = q.top();
        q.pop();
        b = q.top();
        q.pop();
        c = (a + b) / k;
        q.push(c);
    }
    cout << q.top();
    return 0;
}