比赛链接：

2024年大学生计算机大赛决赛-个人赛

比赛时间：2024.11.17

U503552 村庄的友谊

在一个遥远的村庄里，村民们的契合度是一个重要的特征。每个村民都有一个契合度，契合度的值为 $1$ 到 $n$ 之间的任意整数。村民们之间的友谊是基于他们的契合度：只有当两个村民的契合度相乘的结果是质数时，他们才能成为朋友，否则他们就是陌生人，即使他们可能有相同的朋友。

现在，村庄的长老希望了解村庄中有多少对不同的陌生人。请你帮助长老计算出来。

输入格式

  • 第一行输入一个整数 $n\ (1 ≤ n ≤ 5*10^5)$，表示村民的数量。
  • 第二行输入 $n$ 个整数，表示每个村民的契合度，契合度的值在 $1$ 到 $5*10^5$ 之间。

输出格式

输出一个整数，表示村庄中有多少对不同的陌生人。

数据范围

对于 $20%$ 的数据，$1 <= n <= 10$

对于 $40%$ 的数据，$1 <= n <= 1000$

对于 $100%$ 的数据，$1 <= n <= 500000$

题解：

一个质数只能被1和它本身整除。因此，如果两个村民的契合度相乘为质数，则其中一个村民的契合度必须为1，另一个村民的契合度必须为这个质数。契合度为1的村民与其他所有质数的村民都是朋友。

  1. 统计契合度为1的村民数量 countOnes。
  2. 统计契合度不为1的村民数量 countprime。
  3. 计算陌生人对数：陌生人对数 = 总对数 - 朋友对数。
  4. 总对数可以通过组合公式 C(n, 2) = n * (n - 1) / 2 计算。
  5. 朋友对数等于契合度为1的村民与其他所有非1的村民之间的配对数，即 count_ones * countprime。
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
#include <bits/stdc++.h>
using namespace std;

const long long MAXN = 500000; // 定义最大数字范围
bool prime[MAXN + 1]; // 用于标记数字是否为质数的数组

// 初始化质数数组的函数
void ai()
{
    // 使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来标记质数
    for (long long p = 2; p * p <= MAXN; p++) // 只需要遍历到sqrt(MAXN)
    {
        if (prime[p]) // 如果p是质数
        {
            for (long long i = p * p; i <= MAXN; i += p) // 将p的所有倍数标记为非质数
            {
                prime[i] = 0;
            }
        }
    }
}

// 计算陌生人数量的函数
long long solve(long long n, vector<long long> &person)
{
    long long cntOne = 0; // 记录数字1的数量
    long long cntprime = 0; // 记录质数的数量
    for (long long i : person) // 遍历每个人的数字
    {
        if (i == 1) // 如果数字是1
            cntOne++;
        else if (prime[i]) // 如果数字是质数
            cntprime++;
    }

    long long total = n * (n - 1) / 2; // 计算总的对数（即C(n, 2)）
    long long friends = cntOne * cntprime; // 计算朋友对的数量（1和质数组成的对）
    long long strangers = total - friends; // 计算陌生人的数量（剩下的对数）
    return strangers;
}

int main()
{
    long long n; // 人数
    cin >> n; // 输入人数
    fill(prime, prime + MAXN + 1, 1); // 初始化质数数组为1（假设所有数字都是质数）
    prime[0] = prime[1] = 0; // 0和1不是质数
    ai(); // 调用函数初始化质数数组

    vector<long long> person(n); // 存储每个人的数字
    for (long long i = 0; i < n; i++)
    {
        cin >> person[i]; // 输入每个人的数字
    }
    cout << solve(n, person); // 输出陌生人的数量
}

U504030 再多一些0

小T有一个数 $n$，现在他可以从 $[1,m]$ 中选一个数字 $k$，然后把 $n$ 变成 $kn$ ，由于小T非常喜欢数字0，所以他下意识的认为一个数的后缀0个数越多越好，请你找到一个最大的 $k$ ，使得 $kn$ 的后缀0个数最多。

后缀0个数：就是指一个数字末尾有多少个0，例如1992000这个数字末尾有3个0，所以它的后缀0个数就为3。

输入格式

输入两个正整数 $n,m$。

输出格式

输出一个整数，表示能选到的最大 $k$。

样例 #1

样例输入 #1

1
5 43

样例输出 #1

1
40

提示

样例解释

在本题中，当 $k=40$ 时得到 $5 \times 40 = 200$，此时后缀0数量最多且 $k$ 最大。

数据范围

对于$100%$的数据，$1 \le n,m \le 10^9$。

2和5相乘为10，每有一对2和5则多一个0。

若n中有a个2，b个5，则n中后缀0的数量为min(a, b)（a, b的较小值）。

因为m最大为10^9，枚举[1, m]中的每个数作为k显然会超时。

考虑枚举k中有多少个2和多少个5，因为在10^9内，一个数最多含有log_2 10^9个2或者log_5 10^9个5，数量不会很多，所以这样枚举不会超时。

如果当前枚举k中有c个2和d个5，k*n的后缀0个数为min(a+c, b+d)。

按题目要求保留取后缀0最多的，且最大的k即为答案。

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
#include <bits/stdc++.h>
using namespace std;

#define int long long

// 解决问题的函数
void solve() {
    int n, m;
    cin >> n >> m;

    // 计算n中2和5的因子个数
    int c2 = 0, c5 = 0;
    while (n % 2 == 0) {
        c2++;
        n /= 2;
    }
    while (n % 5 == 0) {
        c5++;
        n /= 5;
    }

    int k2 = 1;
    int ma = -1, ans = 1;

    // 枚举所有可能的2的幂次k2
    for (int i = 0; k2 <= m; i++) {
        int k5 = 1;
        // 枚举所有可能的5的幂次k5，使得k2*k5不超过m
        for (int j = 0; k2 * k5 <= m; j++) {
            int v2 = c2 + i;  // 当前2的因子总数
            int v5 = c5 + j;  // 当前5的因子总数
            int v10 = min(v2, v5);  // 10的因子数由较少的那个决定

            int now = k2 * k5;
            now = m / now * now;  // 计算当前值在m范围内的最大倍数值

            // 更新最大10的因子数和对应的答案
            if (v10 > ma) {
                ma = v10;
                ans = now;
            } else if (v10 == ma) {
                ans = max(ans, now);
            }

            k5 *= 5;
        }
        k2 *= 2;
    }

    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;  // 测试用例数量，默认为1
    // cin >> T;  // 如果需要多组测试数据，取消此行注释

    while (T--) {
        solve();
    }
}

U505285 开光灯

题目描述

现在有$n$个灯泡排成一行，分别编号$ 1 $ ~ $ n $，灯泡默认都是关闭的，而小T手速惊人，他每次可以选择一个区间$ [l,r] $，然后改变这区间内的所有灯泡的状态，如果此时灯泡是打开的，则变关闭，否则从关闭变打开。现在你已经知道小T进行了$ m $次操作，但小$ T $想考考你，如果此时小$ T $第$ i $个操作不执行的话，此时多少盏灯泡是打开的。

输入格式

第一行 两个整数$ n ,m $ 表示灯泡的数量和小$ T $操作的次数。

接下来$ m $行，每行两个整数$ l,r $ 表示小$ T $操作的区间。

输出格式

一行$ m $个数字,每个数字之间用空格隔开，表示小$ T $第$ i $个操作不执行的话此时打开着的灯泡数。

样例 #1

样例输入 #1

1
2
3
5 2
1 5
2 4

样例输出 #1

1
3 5

样例 #2

样例输入 #2

1
2
3
4
5
10 4
1 10
2 4
3 8
6 9

样例输出 #2

1
3 6 3 5

提示

第一个样例，当第一个操作不做时，此时只有$2,3,4$打开着，故答案为$3$，当第二个操作不做时，此时灯全部打开着，故答案为$5$。

数据规模与约定

保证所有测试点$ 1\le l \le r \le n $。

对于$ 20%$的数据 , 保证 $1 \le n, m \le 500 $，并且每个操作中$ l $和$ r $都相等，即操作的都是同一段区间，不保证$ l = r $。

对于$ 60%$的数据 , 保证 $ 1 \le n, m \le 5000 $。

对于 $100 %$ 的数据，保证$1 \le n, m \le 10^6 $。

解决这个问题，我们需要采用一种高效的方法来处理大量的查询和更新操作。直接模拟每个操作会超时，因为最坏情况下时间复杂度可能达到𝑂(𝑛×𝑚)O(n×m)，这在给定的数据范围内是不可接受的。因此，我们考虑使用差分数组的思想来优化我们的算法。

解题思路

  1. 初始化差分数组：创建一个长度为𝑛+2n+2的差分数组diff，用来记录每个位置的变化情况。额外的两个位置是为了避免边界条件的特殊处理。
  2. 应用所有操作：遍历每个操作，根据操作的区间[𝑙,𝑟][l,r]对差分数组进行更新。具体来说，增加diff[l]，减少diff[r+1]。这样做的目的是为了标记区间的开始和结束，方便后续计算每个位置的实际状态。
  3. 计算最终状态：通过前缀和的方式计算每个位置的最终状态。这一步需要遍历差分数组，累加值来确定每个灯泡是否开启。
  4. 模拟移除每个操作：再次遍历每个操作，假设当前操作没有发生，重新计算差分数组，并根据更新后的差分数组计算新的灯泡状态。统计开启的灯泡数量，并将结果存储起来。
  5. 输出结果：最后输出存储的结果。

实现细节

  • 使用一个额外的变量来记录当前开启的灯泡总数，以便快速计算移除某个操作后的影响。
  • 在模拟移除每个操作时，只需调整该操作对差分数组的影响，然后基于当前的开启灯泡总数和受影响的区间长度来计算新的开启灯泡数。
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
#include <iostream>
#include <vector>
using namespace std;

// 解决问题的函数
vector<int> solve(int n, int m, const vector<pair<int, int>>& operations) {
    vector<int> diff(n + 2, 0);  // 差分数组，长度为 n+2，以避免边界条件的特殊处理
    
    // 应用所有操作到差分数组
    for (const auto& op : operations) {
        int l = op.first;
        int r = op.second;
        diff[l] += 1;  // 区间开始位置加1
        diff[r + 1] -= 1;  // 区间结束位置的下一个位置减1
    }
    
    // 计算每个灯泡的最终状态
    vector<int> state(n + 1, 0);
    int on_count = 0;  // 记录最终开启的灯泡数量
    for (int i = 1; i <= n; ++i) {
        state[i] = state[i - 1] + diff[i];  // 前缀和计算每个位置的最终状态
        if (state[i] % 2 == 1) {  // 如果灯泡是开启的
            on_count++;
        }
    }
    
    vector<int> results;  // 存储每个操作移除后开启的灯泡数量
    // 模拟移除每个操作并计算开启的灯泡数量
    for (const auto& op : operations) {
        int l = op.first;
        int r = op.second;
        // 计算移除该操作后的影响
        int change = 0;
        if (state[l] % 2 == 1) {  // 如果该操作原本是关闭灯泡的
            change = (r - l + 1);  // 移除后应增加 (r - l + 1) 个开启的灯泡
        } else {  // 如果该操作原本是开启灯泡的
            change = -(r - l + 1);  // 移除后应减少 (r - l + 1) 个开启的灯泡
        }
        
        results.push_back(on_count + change);  // 计算并存储结果
    }
    
    return results;
}

int main() {
    int n, m;
    cin >> n >> m;  // 读取灯泡数量和操作次数
    vector<pair<int, int>> operations(m);  // 存储所有操作
    for (int i = 0; i < m; ++i) {
        cin >> operations[i].first >> operations[i].second;  // 读取每个操作的区间
    }
    
    vector<int> results = solve(n, m, operations);  // 调用 solve 函数计算结果
    for (int res : results) {
        cout << res << " ";  // 输出每个操作移除后开启的灯泡数量
    }
    cout << endl;
    
    return 0;
}