1 条题解

  • 0
    @ 2026-11-15 22:43:19

    A 星际通讯 (telecom) 题解

    题目大意

    • 一次按键:选择一个整数 x ≥ 0
      • 立即传输 10^x 字节
      • 花费 2^x 秒
    • 给定一个需传输的字节数 r (1 ≤ r ≤ 10¹⁸),求最少需要多少秒。
    • 共有 T (1 ≤ T ≤ 5 × 10⁴) 次独立查询。

    Solution

    本题考察模拟,同一位的块数绝不会 ≥10\geq 10 ,这就意味着正好就是 rr 的十进制展开。

    进一步分析,如果第 ii 位(10i10^i)有 did_i(0−90 - 9)个块,那么它们所产生的总时间是 di⋅2id_i\cdot2^i。

    整体最少时间 time(r)time(r) 即 ∑i=018di⋅2i\sum_{i = 0}^{18}d_i\cdot2^i,其中 ii 只需要到 1818,原因是 101810^{18} 是给定的上界。

    算法

    1. 读入 r 按字符串处理,方便取得每一位的十进制数字。
    2. 从最低位(个位)开始向高位遍历:
      • 当前位置下标记为 i,数字为 d。
      • 累加 ans += d × (1LL << i)。
    3. 输出 ans。
    • i ≤ 18,因此 1LL << i 不会溢出 64 位。
    • 每个 r 最多 19 位,总运算量 T × 19,约 95 万次,非常快。

    Code

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        int T;
        if (!(cin >> T)) return 0;
        while (T--) {
            string r;
            cin >> r;
            long long ans = 0;
            int len = r.size();
            // 从最低位开始处理:r[len-1] 是个位
            for (int i = 0; i < len; ++i) {
                int digit = r[len - 1 - i] - '0';
                ans += 1LL * digit * (1LL << i);   // digit × 2^i
            }
            cout << ans << '\n';
        }
        return 0;
    }
    

    B 禁忌的联盟 (lol) 题解

    Step 1: 忽略 aia_i 颜色限制,只处理 bib_i 不互质

    定义DP状态

    定义一个DP状态:f[p],表示以质因数 pp 为最后一位因子的最长子序列长度。

    转移方式

    观察到,如果两个数 bi,bjb_i, b_j 有公共质因数 pp,那么它们之间可以相连。

    对于每个 bib_i,我们枚举它所有的质因数 pp,找到所有 f[p]f[p] 中的最大值 max_valmax\_val,然后令当前元素作为结尾的子序列长度为 max_val+1max\_val + 1;然后反向更新所有这些质因数的 f[p]←max⁡(f[p],dpi)f[p] \leftarrow \max(f[p], dp_i)。

    这个部分的复杂度是 O(n⋅log⁡bi)O(n \cdot \log b_i),因为对每个 bib_i 做质因数分解。

    Step 2: 引入 aia_i 不同的限制(颜色限制)

    每个质因数 pp 下,维护两个记录:

    • f[p].max1:最大的子序列长度,以及对应的 aia_i
    • f[p].max2:第二大的子序列长度(必须与 max1 的 aia_i 不同)

    转移逻辑

    对于当前元素 (ai,bi)(a_i, b_i),设 bib_i 的所有质因数集合为 PP,我们尝试从这些质因数对应的最长记录中转移:

    $$dp[i] = \max_{p \in P} \begin{cases} f[p].\text{max1}.\text{value} & \text{if } f[p].\text{max1}.\text{color} \neq a_i \\ f[p].\text{max2}.\text{value} & \text{if } f[p].\text{max1}.\text{color} = a_i \end{cases}$$

    然后将 dp[i]dp[i] 更新回所有 p∈Pp \in P 的 f[p] 中对应的位置。

    总复杂度:O(nlog⁡bmax⁡)O(n \log b_{\max}),其中 bmax⁡=105b_{\max} = 10^5

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <utility>
    #include <cstring>
    #include <cmath>
    #include <set>
    #include <map>
    #include <unordered_map>
    using namespace std;
    #define int long long
    using pii = pair<int, int>;
    using ull = unsigned long long;
    // #define debug(x) cout << #x << ":" << x << endl
    constexpr int M = 5e5 + 2;
    
    int col[M], a[M];
    int pri[M];
    int prime[M];
    int n, cnt, ans;
    
    struct node
    {
        int len, c;
    };
    
    node max1[M], max2[M];
    
    void ols(int n)
    {
        int i, j;
        for (i = 2; i <= n; i++)
        {
            if (!pri[i])
            {
                pri[i] = i;
                prime[cnt++] = i;
            }
            for (j = 0; i * prime[j] <= n; j++)
            {
                pri[i * prime[j]] = prime[j];
                if (i % prime[j] == 0)
                {
                    break;
                }
            }
        }
    }
    
    vector<int> f(int x)
    {
        vector<int> t;
        while (x > 1)
        {
            int p = pri[x];
            t.push_back(p);
            while (x % p == 0)
                x /= p;
        }
        return t;
    }
    
    void solve()
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i] >> col[i];
    
        ols(5e5);
        for (int i = 1; i <= n; i++)
        {
            auto v = f(a[i]);
            int curmax = 0;
    		cerr<<i<<":"<<curmax<<endl; 
            for (auto &ele : v)
            {
            	cerr<<ele<<"ssss"<<endl;
                if (max1[ele].c == col[i])
                    curmax = max(curmax, max2[ele].len);
                else
                    curmax = max(curmax, max1[ele].len);
            }
            curmax++;
            
            ans = max(ans, curmax);
            for (auto &ele : v)
            {
                if (max1[ele].c == col[i])
                    max1[ele].len = max(max1[ele].len, curmax);
                else
                {
                    if (curmax > max1[ele].len)
                    {
                        max2[ele] = max1[ele];
                        max1[ele] = {curmax, col[i]};
                    }
                    else if (curmax > max2[ele].len)
                    {
                        max2[ele] = {curmax, col[i]};
                    }
                }
            }
        }
        cout << ans << endl;
    }
    
    signed main()
    {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
    }
    

    C 神秘合金 (medal)

    首先,定义 dp[sum, u] 表示从节点 1 到节点 uu 的路径中,经过的所有边的 aia_i 总和为 sum 时,路径的 bib_i 总和的最小值。我们的目标是从节点 1 到节点 NN,找到使性能值最小的路径,性能值为:

    (∑i∈Pai)×(∑i∈Pbi)(\sum_{i \in P} a_i) \times (\sum_{i \in P} b_i)

    在这个过程中,状态转移的关键是根据边的属性 (ai,bi)(a_i, b_i) 更新状态。

    具体地,如果当前在节点 uu,通过一条边 (u→v)(u \to v) 转移到节点 vv,并且该边的 aia_i 和 bib_i 分别为 aa 和 bb,那么状态转移方程可以表示为:

    $$dp[\text{sum} + a][v] = \min(dp[\text{sum} + a][v], dp[\text{sum}][u] + b)$$

    说明:

    • 其中 sum\text{sum} 表示当前路径的 aia_i 总和。
    • 通过边 (u→v)(u \to v),新的路径的 aia_i 总和为 sum+a\text{sum} + a,路径的 bib_i 总和为 dp[sum][u]+bdp[\text{sum}][u] + b。

    这个方程的含义是:当我们从节点 uu 转移到节点 vv 时,如果当前路径的 aia_i 总和为 sum,我们就将这个新的路径的 aia_i 总和 sum+a\text{sum} + a 和新的 bib_i 总和 dp[sum][u]+bdp[\text{sum}][u] + b 更新到状态 dp[sum+a][v]dp[\text{sum} + a][v]。

    注意到 ai>0a_i > 0 时,状态相同的情况之间没有转移:

    由于题目中规定 ai>0a_i > 0,即每条边的 aia_i 值都是正整数。因此,当前路径的 ∑ai\sum a_i 总和会随着每一次转移而增加,不能减少。

    • 假设某条路径经过了节点 uu 和节点 vv,且路径的 ∑ai=sum\sum a_i = \text{sum}。
    • 当我们通过边 (u→v)(u \to v) 转移时,新的路径的 ∑ai\sum a_i 会变为 sum+a\text{sum} + a(因为 ai>0a_i > 0),而 ∑ai\sum a_i 一定会增加。
    • 因为 ∑ai\sum a_i 增加,且每个状态的 ∑ai\sum a_i 之间是严格递增的,所以在计算 dpdp 时,如果某个状态的 ∑ai\sum a_i 已经确定了一个值,那么我们就可以直接从小的 ∑ai\sum a_i 值开始枚举,从而避免不必要的重复计算。

    因此,状态之间不可能相同的情况会导致我们不需要转移到相同的 ∑ai\sum a_i 值。换句话说,路径的 ∑ai\sum a_i 总和的变化是单调递增的,因此状态间不会有相同的 ∑ai\sum a_i 值进行转移。

    时间复杂度为 O(N⋅M⋅max(ai))O(N \cdot M \cdot \text{max}(a_i))

    • 1

    信息

    ID
    217
    时间
    1000ms
    内存
    512MiB
    难度
    2
    标签
    递交数
    1
    已通过
    1
    上传者