索思乐学

P12124 [蓝桥杯 2024 省 B 第二场] 前缀总分

发表于 2025-08-13

题意简述

给定 $n$ 个字符串 $s_{1 \sim n}$ ，修改某字符串的某个字符，使 $\sum_{i<j} \operatorname{LCP}(s_i,s_j)$ 最大。$\operatorname{LCP}(p, q)$ 为字符串 $p, q$ 的最长公共前缀长度。

思路

考虑 dp。定义 $f_{i, j, k}$ 表示 $s_i$ 和 $s_j$ 从第 $k$ 位开始到结尾的子串的最长公共前缀长度。

状态转移： \[ f_{i, j, k} = \begin{cases} 0, & s_{i, k} \neq s_{j, k}\\ f_{i, j, k+1} + 1, & s_{i, k} = s_{j, k} \end{cases} \] 统计答案时，我们枚举要修改的字符串编号 $i$，修改字符的下标 $k$ 和修改后的字符 $c$。记这次修改可以使答案增加 $d$。对于所有 $j \neq i$，有以下两种情况使答案变动：

如果 $f_{i, j, 1} = k-1$ 且 $c = s_{j,k}$，这说明原本 $s_i$ 和 $s_j$ 相等的部分在第 $k$ 位这里断开了，修改之后可以给它接上。$d \gets d + f_{i,j,k+1}+1$。
如果 $f_{i,j,1} \ge k$ 且 $c \neq s_{j,k}$，这说明原本 $s_i$ 和 $s_j$ 有一个较长的最长公共前缀，我们这次修改给它破坏了。$d \gets d - (f_{i,j,1}-k+1)$。

记原本不加修改的答案为 $ans$。则 $ans + \max\{d\}$ 即为最终答案。时间复杂度 $\mathcal O(n^2|s_i||\sum|)$，其中 $|\sum| = 26$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 205;
string s[N];
int f[N][N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = min(s[i].size(), s[j].size())-1; k >= 1; k--)
                if (s[i][k] == s[j][k])
                    f[i][j][k] = f[i][j][k+1] + 1;
    int ans0 = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i+1; j <= n; j++)
            ans0 += f[i][j][1];
    int ans = ans0;
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k < s[i].size(); k++) {
            for (char c = 'a'; c <= 'z'; c++) {
                int add = 0;
                for (int j = 1; j <= n; j++) {
                    if (j == i || k >= s[j].size()) continue;
                    if (f[i][j][1] == k-1 && c == s[j][k])
                        add += f[i][j][k+1]+1;
                    if (f[i][j][1] >= k && c != s[j][k])
                        add -= f[i][j][1]-k+1;
                }
                ans = max(ans, ans0+add);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

The End

P12289 [蓝桥杯 2024 国 Java A] 修改数位

发表于 2025-08-13

题意简述

把一个数字 $a$ 改成 $b$ 要花费 $|b-a|$，你要修改一个数 $m$，让修改后的数存在连续的 $10$ 位，包含了从 $0$ 到 $9$ 的所有数字。求最小花费。

思路

令 $a_i$ 为 $m$ 从左到右第 $i$ 位，可以用滑动窗口维护 $a_i, a_{i+1}, \dots, a_{i+9}$ 这 $10$ 位中数字 $j (0 \le j < 10)$ 的个数，记为 $cnt_{i, j}$。开两个动态数组 v1, v2。如果 $cnt_{i, j}=1$，无需操作；如果 $cnt_{i, j} = 0$，说明需要新增一个数字 $j$，则在 v1 中添加 $j$；如果 $cnt_{i, j} > 1$，说明数字 $j$ 过多了，则在 v2 中添加 $cnt_{i, j}-1$ 个数字 $j$。容易发现 v1 和 v2 的大小一定相等。由于顺序枚举，v1 和 v2 也都是有序的。我们让 v2[k] 变为 v1[k]，统计花费即为答案。

时间复杂度 $\mathcal O(nk)$，其中 $k = 10$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int cnt[10];
string a;
vector<int> v1, v2;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> a;
    a = " " + a;
    int n = a.size()-1;
    for (int i = 1; i <= 10; i++)
        cnt[a[i]-'0']++;
    for (int i = 0; i <= 9; i++) {
        if (cnt[i] == 0) v1.push_back(i);
        else if (cnt[i] > 1) fill_n(back_inserter(v2), cnt[i]-1, i); // 在v2末尾插入cnt[i]-1个i
    }
    int sum = 0;
    for (int i = 0; i < v1.size(); i++)
        sum += abs(v1[i]-v2[i]);
    int ans = sum;
    for (int i = 11; i <= n; i++) {
        v1.clear(); v2.clear();
        cnt[a[i-10]-'0']--, cnt[a[i]-'0']++;
        for (int j = 0; j <= 9; j++) {
            if (cnt[j] == 0) v1.push_back(j);
            else if (cnt[j] > 1) fill_n(back_inserter(v2), cnt[j]-1, j); // 在v2末尾插入cnt[j]-1个j
        }
        sum = 0;
        for (int j = 0; j < v1.size(); j++)
            sum += abs(v1[j]-v2[j]);
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

The End

P12880 [蓝桥杯 2025 国 C] 数字配对

发表于 2025-08-11

题意简述

给定 $n$ 个正整数 $a_1,\dots,a_n$，满足 $1 \le n, a_i \le 10^6$。求满足 $i < j$ 且 $a_i+1=a_j$ 的 $(i, j)$ 个数，且不能重复使用。

思路

拿到题第一时间可能会想到枚举每个数，只要前面有对应的数就直接匹配。比如：

for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (cnt[a[i]-1])
        cnt[a[i]-1]--, ans++;
    else
        cnt[a[i]]++;
}

但这样是错误的。当输入为 4 2 3 4 3 时，$a_1$ 与 $a_4$ 配对，$a_2$ 与 $a_3$ 配对，答案为 $2$，而程序输出为 $1$。我们发现，按原序列枚举的弊端是在我们处理一个数时，不知道后面还有没有相同的数。同时，$a_i$ 与 $n$ 同阶启发我们改变贪心策略，枚举每一个具体数值。

对每个数 $a_i$，开一个 vector 记录它在原序列中出现的每个位置。对于相邻的两个 vector，使用双指针统计答案，每个位置都尽量和最靠后的位置匹配。这样这道题就做完了。

感性证明：假设 $a_i=x, a_j=a_k=x+1$，$i<j<k$。如果我们将 $a_i$ 与 $a_j$ 匹配，若存在 $l$ 满足 $j<l<k, a_l = x+2$，我们就损失了一组匹配。所以找位置靠后的匹配一定不劣。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e6+5;
vector<int> cnt[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, mx = 0, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cnt[x].push_back(i);
        mx = max(mx, x);
    }
    n = mx;
    for (int i = 2; i <= n; i++) {
        int j = cnt[i-1].size()-1, k = cnt[i].size()-1;
        while (j >= 0 && k >= 0) {
            while (j > 0 && cnt[i-1][j] > cnt[i][k])
                j--;
            if (cnt[i-1][j] > cnt[i][k]) break; // 此时cnt[i-1]枚举完了
            while (k > 0 && j > 0 && cnt[i-1][j] < cnt[i][k])
                ans++, k--, j--, cnt[i].pop_back(); // 删除对应位置，避免下次循环重复计算
            if (cnt[i-1][j] < cnt[i][k]) { // 此时cnt[i]枚举完了
                ans++, cnt[i].pop_back();
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

The End

LibreOJ #6439. Popcount Xor

发表于 2025-08-10

1. 题目描述

给定正整数 $n$，用二进制整数表示，求 $\bigoplus_{i=0}^{n-1} \operatorname{popcount}(i)$。保证 $1 \le n \le 2^{3\times10^5}$。

2. 思路

令 $s$ 为输入的字符串，下标从 $0$ 开始。枚举每个 $s_i = 1$ 的 $i$，考虑第 $0 \sim i-1$ 位已确定，第 $i$ 位为 $0$ 时对答案的贡献 $c$。则： \[ c = \bigoplus_{j=0}^{|s|-i+1} (cnt_{i-1}+j)\binom{|s|-i+1}{j} \bmod 2 \] 其中 $cnt_i$ 表示从 $s_0$ 到 $s_i$ 中 $1$ 的数量。$\binom{|s|-i+1}{j}$ 是从后面的 $|s|-i+1$ 位中选 $j$ 位的方案数。模 $2$ 是因为同一个数异或自己偶数次结果为 $0$。

由Lucas定理，$\binom{n}{m} \bmod 2 = \binom{n\bmod2}{m\bmod2} \binom{\lfloor\frac{n}{2}\rfloor}{\lfloor\frac{m}{2}\rfloor} \bmod 2$，不断将 $n, m$ 一起右移一位，可得 $\binom{n}{m} \bmod 2 = \prod_i \binom{n>>i \& 1}{m >> i \& 1}$。

又由于 $\binom{1}{1}=\binom{1}{0}=\binom{0}{0} = 1,\binom{0}{1} = 0$，我们发现： \[ \binom n m \bmod 2 = [n \& m = m] \] 所以： \[ c = \bigoplus_{j=0}^{|s|-i+1} (cnt_{i-1}+j)[(|s|-i+1) \& j = j] \] 算这个式子的复杂度可以接受。

3. 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size(), cnt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') continue;
        for (int j = n-i-1; ; j = (j-1)&(n-i-1)) {
            ans ^= (cnt+j);
            if (!j) break;
        }
        cnt++;
    }
    cout << ans << endl;
    return 0;
}

The End

一个网络流模版（支持最大流和费用流）

发表于 2025-03-07

代码：

template<int N, typename T = int>
struct Graph {
    struct Edge {
        int v, rev;
        T c, w;
    };
    array<vector<Edge>, N> gh;
    array<int, N> d, cur;
    array<T, N> dis;
    bitset<N> vis;
    T inf = numeric_limits<T>().max(), Ans = 0;

    void add(int u, int v, T c, T w = 0) {
        gh[u].push_back({v, (int)gh[v].size(), c, w});
        gh[v].push_back({u, (int)gh[u].size()-1, 0, -w});
    }
    bool bfs(int s, int t) {
        d.fill(0);
        for (T& i : dis) i = inf;
        d[s] = 1, dis[s] = 0;
        queue<int> q;
        q.push(s);
        vis = 0;
        vis[s] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            vis[u] = false;
            for (auto e : gh[u]) {
                if (dis[u] + e.w < dis[e.v] && e.c) {
                    d[e.v] = d[u] + 1, dis[e.v] = dis[u] + e.w;
                    if (!vis[e.v]) q.push(e.v), vis[e.v] = true;
                }
            }
        }
        return dis[t] != inf;
    }
    T dfs(int u, int t, T fl) {
        if (u == t || !fl) return fl;
        T ret = 0;
        for (int& i = cur[u]; i < gh[u].size(); i++) {
            Edge& e = gh[u][i];
            if (d[e.v] == d[u] + 1 && e.c > 0 && dis[e.v] == dis[u] + e.w) {
                T f = dfs(e.v, t, min(fl, e.c));
                if (f > 0) {
                    e.c -= f;
                    gh[e.v][e.rev].c += f;
                    ret += f;
                    fl -= f;
                    Ans += f * e.w;
                    if (!fl) break;
                }
            }
        }
        return ret;
    }
    pair<T, T> max_flow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.fill(0);
            T x;
            while ((x = dfs(s, t, inf)))
                ans += x;
        }
        return {ans, Ans};
    }
};

P5814 [CTSC2001] 终极情报网

发表于 2025-03-02

1.题目描述

有 $N$ 名间谍，分别用数字 $1,2,\cdots,N$ 编号。间谍可以双向联系。$[0,1]$ 的实数 $S_{i,j}$ 表示第 $i$ 和第 $j$ 名间谍联系的安全程度，正整数 $M_{i,j}$ 表示他们这次联系时能够互相传递的消息的最大数目。$[0,1]$ 的实数 $AS_j$ 表示总部与间谍 $j$ 之间进行联系的安全程度，正整数 $AM_j $ 表示总部和间谍 $j$ 之间传递的消息的最大数目。消息从间谍手中交到敌军的过程是绝对安全的。

现在总部有 $K$ 条假消息，求传递所有消息的最大安全程度。

2.思路

本题可以用费用流模型解决。每条边 $(i, j)$ 的流量上限为 $M_{i, j}$，费用为 $S_{i, j}$。建图时要加入三个点 $S, s, t$，其中 $S$ 向 $s$ 连一条费用是 $1$，流量上限是 $K$ 的边，保证最大流不超过 $K$。$s$ 和 $t$ 分别表示总部和敌军总部，$s$ 向所有点 $i$ 连流量上限为 $AM_i$，费用为 $AS_i$ 的边，所有点向 $t$ 连流量上限为 $\infty$，费用为 $1$ 的边。其余连双向边建图即可。

对与本题，费用流的bfs过程需要处理 $s$ 到每个点路径的最大安全度乘积。即 $dis_i = \max_{(j, i) \in E} \{dis_j * S_{j, i}\}, dis_s=1$。每次产生新的流 $f$ 时，将答案加上 $dis_t ^ f$。注意在各种比大小时加一个 $eps$。

3.注意事项

与常规费用流不同，本题的费用累计方式是乘而不是加。建图时一组反向边的费用应该互为倒数。
特别注意本题的输出，由于需要保留 $5$ 位有效数字，所以向 $0.01$ 这种答案要补足到 $0.010000$，不能直接使用cout.precision(5)，手写一个输出函数即可解决问题。

4.代码

#include <bits/stdc++.h>
using namespace std;

using ld = long double;
const int N = 310;
const ld eps = 1e-12;
struct Edge {
    int v, rev, c;
    ld w;
};
vector<Edge> gh[N];
int cur[N], M[N];
ld dis[N], Ans = 1, S[N], dep[N];
bitset<N> vis;
ld qpow(ld a, int b) {
    ld ans = 1;
    for (; b; b >>= 1) {
        if (b&1) ans *= a;
        a *= a;
    }
    return ans;
}
void add(int u, int v, int c, ld w) {
    // vector存图记录反向边编号。
    gh[u].push_back({v, (int)gh[v].size(), c, w});
    gh[v].push_back({u, (int)gh[u].size()-1, 0, 1.0/w});
}
ld bfs(int s, int t) {
    memset(dis, 0, sizeof(dis));
    memset(dep, 0, sizeof(dep));
    vis = 0;
    dis[s] = 1, dep[s] = 1;
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (auto e : gh[u]) {
            if (e.c > 0 && dis[u] * e.w - dis[e.v] > eps) {
                dis[e.v] = dis[u] * e.w, dep[e.v] = dep[u] + 1;
                if (!vis[e.v]) q.push(e.v);
            }
        }
    }
    return dis[t];
}
int dfs(int u, int t, int fl) {
    if (u == t || !fl) return fl;
    int ret = 0;
    for (int& i = cur[u]; i < gh[u].size(); i++) {
        auto& e = gh[u][i];
        if (e.c > 0 && abs(dis[e.v] - dis[u] * e.w) <= eps && dep[e.v] == dep[u] + 1) {
            int f = dfs(e.v, t, min(fl, e.c));
            if (f > 0) {
                ret += f;
                fl -= f;
                e.c -= f;
                gh[e.v][e.rev].c += f;
                if (fl == 0) break;
            }
        }
    }
    return ret;
}
int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t) > eps) {
        memset(cur, 0, sizeof(cur));
        int x;
        while ((x = dfs(s, t, INT_MAX)))
            ans += x, Ans *= qpow(dis[t], x);
    }
    return ans;
}
void deal() {
    char ch[40];
    double ans = Ans;
    sprintf(ch,"%.15lf\n",ans);
    int sum = 0,i;
    for (i = 0; sum < 5; i++)
        if ((ch[i]!='0' && ch[i]!='.') | (sum>0))
            sum++;
    if (ch[i] >= '5')
        ch[i-1]++;
    ch[i] = 0;
    for(; i >= 0; i--) {
        if (ch[i] == '.') break;
        else if (ch[i] > '9')
            ch[i-1]++, ch[i] = '0';
    }
    printf("%s\n",ch);
}

int main() {
    // freopen("agent.in", "r", stdin);
    // freopen("agent.out", "w", stdout);
    int n, k;
    cin >> n >> k;
    int s = n+1, t = n+2, s1 = n+3;
    for (int i = 1; i <= n; i++)
        cin >> S[i];
    for (int i = 1; i <= n; i++)
        cin >> M[i];
    for (int i = 1; i <= n; i++)
        add(s, i, M[i], S[i]);
    for (int i = 1; i <= n; i++) {
        int ok;
        cin >> ok;
        if (ok)
            add(i, t, INT_MAX, 1);
    }
    add(s1, s, k, 1);
    while (true) {
        int u, v, c;
        ld w;
        cin >> u >> v;
        if (u == -1 && v == -1) break;
        cin >> w >> c;
        add(u, v, c, w);
        add(v, u, c, w);
    }
    int fl = dinic(s1, t);
    if (fl != k) cout << "0.0000" << endl;
    else deal();
    return 0;
}

The End

P11577 [CCC2020] Epidemiology

发表于 2025-01-18

1.题目描述

有 $N$ 个人在第 $0$ 天患病。当一个人患病时，他会在明天感染 $R$ 个人，随后便不再感染他人。没有一个人会被感染超过一次。我们想要确定造成 $P+1$ 个人患病的最早时间。

2.思路

简单模拟即可。我们用变量 $d_i$ 记录第 $i$ 新增的患病人数，由于每人能感染 $r$ 人，所以 $d_i = d_{i-1} \times R$。不断让 $N$ 加上 $d_i$，直到 $N > P$。此时的天数 $i$ 就是答案。

3.注意事项

退出循环时，$i$ 的值是感染 $P$ 个人后的第二天。所以答案是 $i-1$。

4.代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int p, n, r;
    cin >> p >> n >> r;
    int d = n, i;
    for (i = 1; n <= p; i++) {
        d *= r;
        n += d;
    }
    cout << i-1 << endl;
    return 0;
}

5.时间复杂度

循环变量 $d$ 在每次循环中都会乘上 $R$，所以时间复杂度是 $\mathcal O(\log_R P)$。

The End

【模版】一些字符串函数（仅代码）

发表于 2025-01-16

KMP（前缀函数）

定义：

$bd_i$：对于字符串 $s$，使 $s_{0 \dots bd_{i}-1} = s_{i-bd_{i}+1 \dots i}$ 成立的最大值。

代码：

for (int i = 1; i < n; i++) {
	int j = bd[i-1];
	while (j && s[i] != s[j]) j = bd[j-1];
	if (s[i] == s[j]) j++;
	bd[i] = j;
}

字符串下标从 $0$ 开始。

exKMP（Z函数）

定义：

$z_i$：字符串 $s$ 与 $s$ 以 $i$ 为起始的后缀的最长公共前缀。

代码：

void getZ(const string& s, int z[]) {
    int n = s.size(), l = 0, r = -1;
    for (int i = 1; i < n; i++) {
        int k = (i > r) ? 0 : min(z[i-l], r-i+1);
        while (i+k < n && s[i+k] == s[k]) k++;
        z[i] = k;
        if (i+k-1 > r)
            l = i, r = i+k-1;
    }
    z[0] = n;
}

字符串下标从 $0$ 开始。

Manacher

定义：

$d_{1i}$：以 $i$ 为中心的奇回文串的最大半径。

$d_{2i}$：以 $i-1$ 和 $i$ 为中心的偶回文串的最大半径。

$len$：所求的答案之一，$s$ 中最长回文串的长度。

代码：

int n = s.size();
int len = 0, nl = 0, nr = 0;
for (int i = 0, l = 0, r = -1; i < n; i++) {
	int k = (i>r) ? 1 : min(d1[l+r-i], r-i+1);
	while (0<=i-k && i+k<n && s[i-k]==s[i+k]) k++;
	d1[i] = k--;
	if (i+k>r)
		l = i-k, r = i+k;
	if (r-l+1 > len)
		len = r-l+1, nl = l, nr = r;
}
for (int i = 0, l = 0, r = -1; i < n; i++) {
  	int k = (i>r) ? 0 : min(d2[l+r-i+1], r-i+1);
  	while (0<=i-k-1 && i+k<n && s[i-k-1]==s[i+k])k++;
  	d2[i] = k--;
  	if (i+k>r)
   		l = i-k-1, r = i+k;
   	if (r-l+1 > len)
   		len = r-l+1, nl = l, nr = r;
}

字符串下标从 $0$ 开始。

【模板】后缀数组（仅代码）

发表于 2025-01-16

1.定义

$sa_i$：字典序排名为 $i$ 的后缀，其首字符下标为 $sa_i$。

$rk_i$：首字符下标为 $i$ 的后缀，其字典序排名为 $rk_i$。（显然 $sa_{rk_i} = i$）

$h_i$：$sa_i$ 与 $sa_{i-1}$ 所表示的后缀的最长公共前缀的长度。（满足 $h_{rk_i} \ge h_{rk_{i-1}}-1$）

2.代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5, M = 200;
int n;
char a[N];
int sa[N*2], rk[N*2], rk0[N*2], cnt[M], id[N*2], h[N*2];
int pos = 0, ans = 0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin.getline(a+1, N);
    n = strlen(a+1);

    int m = 128, i;
    for (i = 1; i <= n; i++)
        cnt[rk[i] = a[i]]++;
    for (i = 1; i <= m; i++)
        cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; i--)
        sa[cnt[rk[i]]--] = i;
    int p = 1;
    for (int len = 1; p < n; len *= 2, m = p) {
        p = 1;
        for (i = n - len + 1; i <= n; i++)
            id[p++] = i;
        for (i = 1; i <= n; i++)
            if (sa[i] > len)
                id[p++] = sa[i] - len;
        for (i = 0; i <= m; i++)
            cnt[i] = 0;
        for (i = 1; i <= n; i++)
            cnt[rk[i]]++;
        for (i = 1; i <= m; i++)
            cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; i--)
            sa[cnt[rk[id[i]]]--] = id[i];
        for (i = 0; i <= n; i++)
            rk0[i] = rk[i];
        p = 0;
        for (i = 1; i <= n; i++) {
            if (rk0[sa[i]] == rk0[sa[i - 1]] && rk0[sa[i] + len] == rk0[sa[i - 1] + len])
                rk[sa[i]] = p;
            else
                rk[sa[i]] = ++p;
        }
    }

    for (int i = 1, k = 0; i <= n; i++) {
        if (k) k--;
        while (a[i+k] == a[sa[rk[i]-1]+k]) k++;
        h[rk[i]] = k;
    }

    for (int i = 1; i <= n; i++)
        cout << sa[i] << ' ';
    cout << endl;
    for (int i = 1; i <= n; i++)
        cout << h[i] << ' ';
    return 0;
}

字符串下标从 $1$ 开始。

P8712 [蓝桥杯 2020 省 B1] 整数拼接

发表于 2025-01-13 更新于 2025-01-16

1.题目描述

给定一个长度为 $n$ 的数组 $A_1,A_2,\cdots,A_n$。你可以从中选出两个数 $A_i$ 和 $A_j$（$i\neq j$），然后将 $A_i$ 和 $A_j$ 一前一后拼成一个新的整数。例如 12 和 345 可以拼成 12345 或 34512。注意交换 $A_i$ 和 $A_j$ 的顺序总是被视为 $2$ 种拼法，即便是 $A_i=A_j$ 时。

请你计算有多少种拼法满足拼出的整数是 $K$ 的倍数。

原题链接：https://www.luogu.com.cn/problem/P8712

2.思路

由于 $1 \le n \le 10^5$，使用时间复杂度为 $\mathcal O(n^2)$ 的算法枚举每种拼接显然不可行。面对这个问题，我们需要一种储存数组 $A$ 中信息的方法，可以让我们在每次遍历 $A_i$ 时以较少的时间复杂度得知能与 $A_i$ 拼接的整数个数。

设数组中两个元素 $A_j$ 和 $A_i$ 的数字位数分别为 $v$ 和 $u$，因为拼接后的数是 $K$ 的倍数，所以有 $A_j \cdot 10^u + A_i \equiv 0 \pmod K$，即 $A_j \cdot 10^u \equiv -A_i \pmod K$。由于 $A_i \le 10^9$，即 $A_i$ 最多有十位，我们可以开 $10$ 个哈希表，对于第 $p$ 个哈希表，存储 $A_i \cdot 10^u \mod K$ 的每个值出现的次数。这样我们在遍历时就能用哈希表里的值进行快速相加了。

3.注意事项

由于 $K \le 10^5$，我们把两个模 $K$ 的余数相乘时会超出int的范围。此外拼接方法的总数在极限情况下也会超出int的范围。所以记得开long long。
按以上方法计算会多算到自己与自己拼接的情况。所以当 $A_i \cdot 10^u + A_i \equiv 0 \pmod K$ 时，要把答案减 $1$。
可以用log10(x) + 1快速计算 $x$ 的数字位数。

4.代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5;
int n, k, a[N];
long long pw[11]; // 10^u % k
unordered_map<int, int> mp[11];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    pw[0] = 1;
    for (int i = 1; i <= 10; i++)
        pw[i] = (pw[i-1] * 10) % k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 1; j <= 10; j++)
            mp[j][a[i] * pw[j] % k]++;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int len = log10(a[i]) + 1, mod = (k - a[i] % k) % k; // mod等价于数学上的-a[i] mod k
        ans += mp[len][mod];
        if (a[i] * pw[len] % k == mod)
            ans--;
    }
    cout << ans << endl;
    return 0;
}

5.复杂度分析

时间复杂度：$\mathcal O(n \log_{10} \max A_i)$

The End