玖的数学&算法录
0%

香港城市大学（东莞）2024新生排位赛

发表于
本文字数： 7.9k 阅读时长 ≈ 7 分钟

前言：你怎么知道我这场拿了一血，然后各种犯病代码到结束。

A. Automation Machine

题意：

假设有一个AC自动机（不是这个 AC自动机 ）,约定写代码大于x行就算AC，每次AC以后代码会自动清空。

有T次操作数，并且现在有以下两种操作：

1、写k行代码。

2、查询目前AC数量。

数据范围

$$1 \leq x \leq 10^{12},1\leq T\leq10^6$$

$$1 \leq k \leq 10^{12}$$

题解：模拟

按题意。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void JiuCherish(){
   i64 n,t;
   std::cin >> n >> t;
   i64 now = 0;
   i64 ans = 0;
   while(t--) {
      int op;
      std::cin >> op;
      if(now > n) {
         ans += 1;
         now = 0;
      }
      if(op == 1) {
         i64 w = 0;
         std::cin >> w;
         now += w;
      } else {
         std::cout << ans << endl;
      }
   }
}

B.Dihedral Angle

题意：

我们需要计算两个相交平面之间的二面角。给定四个点 A,B,C,D的三维坐标，我们需要找到二面角 A−BC−D 的度数。

数据范围

每个点坐标都满足：

$$-10^4 \leq x,y,z \leq 10^{4}$$

保证四个坐标不重合。

题解：计算几何

先算向量，再算法向量，计算二面角的余弦值，最后确认角度。

代码：
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
struct Vector3D {
    double x, y, z;
    Vector3D(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) {}
    Vector3D operator-(const Vector3D& v) const {
        return Vector3D(x - v.x, y - v.y, z - v.z);
    }
    double dot(const Vector3D& v) const {
        return x * v.x + y * v.y + z * v.z;
    }
    Vector3D cross(const Vector3D& v) const {
        return Vector3D(y * v.z - z * v.y, z * v.x - x * v.z, x * v.y - y * v.x);
    }
    double norm() const {
        return sqrt(x * x + y * y + z * z);
    }
};
 
 
void JiuCherish(){
    Vector3D A, B, C, D;
    cin >> A.x >> A.y >> A.z;
    cin >> B.x >> B.y >> B.z;
    cin >> C.x >> C.y >> C.z;
    cin >> D.x >> D.y >> D.z;
 
    Vector3D AB = B - A;
    Vector3D BC = C - B;
    Vector3D CD = D - C;
    
    Vector3D n_ABC = AB.cross(BC);
    Vector3D n_BCD = BC.cross(CD);
    double cos_angle = (n_ABC.dot(n_BCD) / (n_ABC.norm() * n_BCD.norm()));
    double angle = acos(cos_angle) * 180 / M_PI;
    int int_angle = static_cast<int>(angle);
    if (fmod(angle, 1) >= 0.5) {
        int_angle++;
    }
    std::cout << int_angle << endl;
}

C.[Love Game]

题意：

Alice和Bob在玩一个游戏

游戏开始时有 n 颗钻石，假设当前钻石数为 x，那么每位玩家在每个回合可以选择以下三种操作之一：

  • 如果 5 能整除 x 并且 x≥5，那么他/她可以选择移除 5 颗钻石。
  • 如果 2 能整除 x 并且 x≥2，那么他/她可以选择移除 2 颗钻石。
  • 如果 x≥1，那么他/她可以选择移除 1 颗钻石。

Alice先手，并且双方用最优策略进行游戏，问最终谁会赢。

数据范围

$$1 \leq T \leq 10^{4}$$

$$1 \leq n \leq 10^{9}$$

题解：博弈，Nim

通过手玩 < 10的数可以发现：

1
2
3
4
5
6
7
8
9
i:1 Alice
i:2 Alice
i:3 Bob
i:4 Alice
i:5 Alice
i:6 Bob
i:7 Alice
i:8 Alice
i:9 Bob

有以上规律。

以6为例，Alice先手，那么一定有他有两种操作：第一种是 -1，那么钻石到了5，由于5 % 5==0所以Bob拿走五个钻石就能获胜，第二种是 6 % 2 == 0，因此拿走2个，也就是来到4，由于有了前五种情况，当钻石数到了4并且是Alice的时候，此时的Alice是必胜的状态，但是此时是Bob的回合，Bob可以通过Alice在四个钻石时候获胜手段再次获胜，因此6是Alice的必败态。

通过以上规律我们进行Nim打表得出下面规律：

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
i:1 Alice
i:2 Alice
i:3 Bob
i:4 Alice
i:5 Alice
i:6 Bob
i:7 Alice
i:8 Alice
i:9 Bob
i:10 Alice
i:11 Bob
i:12 Alice
i:13 Bob
i:14 Alice
i:15 Bob
i:16 Alice
i:17 Bob
i:18 Alice
i:19 Bob
i:20 Alice
i:21 Bob
i:22 Alice
i:23 Bob
i:24 Alice
i:25 Bob
i:26 Alice
//篇幅有限

Nim打表代码：

1
2
3
4
5
6
7
8
9
10
11
12
unordered_map<int, int> memo;
 
int nim_value(int n) {
    if (n == 0) return 0; 
    if (memo.count(n)) return memo[n];
    int result = 0;
    if (n >= 5 && n % 5 == 0) result = nim_value(n - 5) ^ 1;
    if (n >= 2 && n % 2 == 0) result = max(result, nim_value(n - 2) ^ 1);
    result = max(result, nim_value(n - 1) ^ 1);
    memo[n] = result;
    return result;
}

结合以上规律得到最终代码

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void JiuCherish(){
    int n;
    cin >> n;
    if(n <= 9) {
        if(n % 3 == 0) {
            std::cout << "Bob" << endl;
        } else {
            std::cout << "Alice" << endl;
        }
    } else {
        if(n & 1) {
            std::cout << "Bob" << endl;
        } else {
            std::cout << "Alice" << endl;
        }
    }
}

D.Rubbidows’s Input

题意：

rubbidows 系统将在第 ti秒执行操作 pi（pi∈{1,2}），其中操作 1 是自动按 Home 键，操作 2 是自动按 End 键。

输入的起始时间是第 1 秒，每个字符的输入需要 1 秒。操作必须在字符输入后执行。换句话说，如果 ti=x，那么只有在 rubbidows 系统输入第 x 个字符后，系统才会自动按 Home 或 End 键。

由于 Yuangq 把所有的钱都花在了买礼物上，他没有足够的钱购买官方的 Rubbish&Windows 版本，所以 Yuangq 决定以不同的方式输入。他想知道他必须以什么顺序输入才能正确输入字符串。

关于 Home 和 End 键：

  • Home 键将光标移动到编辑或非编辑窗口的第一行的第一个单词。
  • End 键正好相反，光标将被定位在最后。

数据范围

$$0 \leq |S| \leq 2 \times10^6$$

$$1 \leq n \leq 5 \times 10^5$$

$$ 0 < t_i < |S|$$

$$p_i = {1 or 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
32
33
34
35
36
37
38
39
40
41
42
43
44
struct P {
    int time,op,len;
}a[MAXN];
void JiuCherish(){
    std::string s;
    std::cin >> s;
    int n;
    std::cin >> n;
    bool end = false;
    bool home = false;
    bool ok = false;
    a[0].time = 0;
    a[0].op = 1;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i].time >> a[i].op;
    }
    for(int i=0;i<n;i++)
        a[i].len = a[i + 1].time - a[i].time;
    a[n].len = s.length() - a[n].time;
    std::sort(a,a + n + 1,[&](P a,P b){
        if(a.op != b.op)return a.op < b.op;
        else if(a.op == 1)
        {
            return a.time > b.time;
        }
        else
        {
            return a.time < b.time;
        }
    });    
    std::vector<std::pair<int,char>> ans;
    for(int i=0;i<=n;i++) {
        for(int j=1;j<=a[i].len;j++) {
            ans.pb({a[i].time - 1 + j,'a'});
        }
    }
    for(int i=0;i<s.length();i++) {
        ans[i].se = s[i];
    }
    std::sort(ans.begin(),ans.end(),[&](std::pair<int,int> a,std::pair<int,int> b){
        return a.fi < b.fi;
    });
    for(auto [x,y] : ans) std::cout << y;
}

E.Selecting Majors

题意：

有四个专业的学生，人数分别为a,b,c,d,现在他们需要到相应的教室去上课，问最少需要安排几个教室？

教室需要满足如下情况：

1、每个教室只能容纳30人。

2、每个教室只能全都是相同专业的学生。

数据范围

$$1\leq T \leq10^4$$

$$1 \leq a,b,c,d \leq 10^{9}$$

题解：模拟

每个专业人数除30再看看%30 为不为0就好了。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void JiuCherish(){
    int a,b,c,d;
    i64 ans = 0;
    std::cin >> a >> b >> c >> d;
    ans += a / 30;
    ans += b / 30;
    ans += c / 30;
    ans += d / 30;
    ans += (a % 30 != 0);
    ans += (b % 30 != 0);
    ans += (c % 30 != 0);
    ans += (d % 30 != 0);
    std::cout << ans << endl;
}

F. Traveler’s Escape

题意：

旅行者刚偷走了 Furina 最喜欢的甜点，现在 Furina 正在疯狂地在整个 Fontaine 寻找这个该死的旅行者！

Fontaine 是一个由 n 行和 m列的网格组成的国家，行号为 1,2,3,…,n,列号为 1,2,3,…,m。我们可怜的旅行者现在在坐标 (1,1)的网格上，时间是 1，他期望到达坐标 (n,m) 的网格，以便从 Fontaine 逃脱。在每个时刻，旅行者只能向下或向右移动任意数量的网格。

为了抓住旅行者，Furina 召集了 q 名检查员，他们计划在时间 ti到达坐标 (xi,yi)来抓住旅行者，只要旅行者在 ti时到达、经过或离开 (xi,yi)，他就会被抓住！此外，Furina 将在时间 k 关闭 Fontaine 的大门，如果旅行者在此之前没有逃脱，他就永远无法逃脱！

然而，旅行者是一个数学爱好者，所以无论在什么危机情况下，只要没有被抓住，他就想找出他最快的逃脱方案，以及总共有多少种方案。

注释：不同的旅行方案是根据逃跑的方向和距离来区分的，不需要在每个时刻都是相同的。例如，即使路线相同，执行方式的不同仍然会导致不同的方案。

数据范围

$$2\leq n,m \leq 500$$

$$1 \leq q,k \leq 100$$

$$1 \leq x_i \leq n,1\leq y_i\leq m,1 \leq t_i \leq k$$

题解：前缀和优化dp

约定 dp({i,j,k}) 表示 到 坐标(i,j)所花的时间为k 的方案数，那么就有

$$dp[i][j][k] = 左边所有dp[点][k - 1]$$

$$dp[i][j][k] = 上面所有dp[点][k-1]$$

转移过来的。

由于暴力枚举 n * m * k * (m or 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
30
31
32
33
34
35
36
37
38
void JiuCherish(){
    int n, m, q, k;
    cin >> n >> m >> q >> k;
    memset(t, 0x3f, sizeof(t));   
    while (q--) {
        int x, y, z;
        cin >> x >> y >> z;
        t[x][y] = min(t[x][y], z);
    }
    int ret = 0, mn = 0x3f3f3f3f;
    memset(f, 0, sizeof(f));
    f[1][1] = 1;
    for (int u = 1; u <= k; u++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (t[i][j] <= u) r[i][j] = 0;
                else r[i][j] = (r[i][j - 1] + f[i][j]) % mod;
            }
        }
        for (int i = 1; i <= m; i++) {
            bool flag = true;
            for (int j = 1; j <= n; j++) {
                if (t[j][i] <= u) c[i][j] = 0;
                else c[i][j] = (c[i][j - 1] + f[j][i]) % mod;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (t[i][j] <= u) f[i][j] = 0;
                else f[i][j] = (r[i][j - 1] + c[j][i - 1]) % mod;
            }
        }
        ret = (ret + f[n][m]) % mod;
        if (f[n][m]) mn = min(mn, u);
    }
    if (!ret) cout << -1 << '\n';
    else cout << ret << ' ' << mn << '\n';
   }

G.Waylon Tritangle

题意：

建造了这样一个 n 层的Waylon三角墙，之后，Yuangq拿了数以百万计的同样大小的绿色卡片来覆盖墙壁，每张卡片正好覆盖2块。因为一旦绿色卡片被撕开就会看起来很糟糕，他希望没有一张绿色卡片被撕开，所以所有的绿色卡片必须正好覆盖2块。

由于Yuangq对数学有着非凡的热情，他也希望能够计算出他可以给Waylon三角墙涂上多少种不同的颜色。所以，你的任务是为他计算出来！

数据范围

$$1 \leq T \leq 10^3$$

$$1 \leq n \leq 10^5$$

题解：数学

如果考虑单层涂色，那么可以延续前一层的涂色方式。

如果考虑双层涂色，那么可以将i与i-1组合起来，因此有：

$$f[i] = f[i - 1] + f[i - 2]$$

从第1层到第i层的涂色方式的方案数为

$$g[i] = g[i - 1] * f[i]$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void init() {
    f[0] = 1;g[0] = 1;
    f[1] = 2;g[1] = 2;
    for(int i=2;i<=MAXN;i++) {
        f[i] = (f[i - 1] + f[i - 2]) % mod;
        g[i] = f[i] * g[i - 1];
        g[i] %= mod;
    }
}
void JiuCherish(){
    int n;
    std::cin >> n;
    std::cout << g[n - 1] % mod << endl;
}

H. Xor Perfect

题意：

首先我们定义一个大小为n，并且非递减没有负数 的数组 a称为优秀数组，同时规定 sum为a整个数组的异或值。问你是否能构造出这样的优秀数组同时满足 sum 是 n 的因子。

数据范围

$$1\leq T \leq10^4$$

$$1 \leq n \leq 2 \cdot 10^5$$

并且保证

$$n * T < 2 \cdot 10^5$$

题解：模拟

考虑到 1是所有数的因子，并且 我们知道 (a ^ a) = 0 和 (0 ^ a) = a

所以构造 000….1 或者 011…1（注意奇偶）即可。

代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void JiuCherish(){
    int n;
    std::cin >> n;
    if(n & 1) {
        for(int i=0;i<n;i++) {
            std::cout << 1 << ' ';
        }
        std::cout << endl;
    } else {
        std::cout << 0 << ' ';
        for(int i=1;i<n;i++) {
            std::cout << 1 << ' ';
        }
        std::cout << endl;
    }
}