HDU Contest 1 解题报告

简单容斥。

选修 $a,b$ 之中恰好一门 $=$ 选修 $a$ $+$ 选修 $b$ $-$ 同时选修 $a,b$

所以记录一下同时选修 $2$ 门的数量就好。

• 注意，记录的时候使用 $m$ 个 unordered_map() ，不要把所有的 pair 放在一起，否则容易 $TLE$。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;

int n, m, cnt[maxn];
unordered_map<int, int> mp[maxn];
int a[3];

int main() {
    scanf("%d%d",&n,&m);
    while (n--) {
        int op;
        scanf("%d",&op);
        if (op == 1) {
            scanf("%d%d%d",&a[0],&a[1],&a[2]);
            sort(a, a+3);
            for (int i = 0; i < 3; i++) {
                cnt[a[i]]++;
                for (int j = i+1; j < 3; j++) {
                    mp[a[i]][a[j]]++;
                }
            }
        } else {
            scanf("%d%d",&a[0],&a[1]);
            sort(a, a+2);
            int ans = cnt[a[0]] + cnt[a[1]] - 2 * mp[a[0]][a[1]];
            printf("%d\n", ans);
        }
    }
}

很明显的质因数分解。但是复杂度看起来不太对：$n \sqrt{(a_i)} = 4 \times 10^9$

这里，我们要用到 $\log a_i$ 复杂度的质因数分解！

主要原理是：在 欧拉筛 过程中，我们可以得到每个数字的 最小质因子，所以我们预处理出 $1$ 到 $10^7$ 的所有数字的最小质因子。在分解 $a_i$ 的时候，不断除掉最小质因子即可。

复杂度：$n \log a_i$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;

bool p[maxn];
int n, primes[maxn], tail = 0, cnt[maxn], small[maxn];
// small[i] 代表数字 i 的最小质因子

void init() {
    fill(p, p+maxn, 1);
    small[1] = 1;
    for (int i = 2; i < maxn; i++) {
        if (p[i]) primes[++tail] = i, small[i] = i;
        for (int j = 1; j <= tail; j++) {
            int cur = i * primes[j];
            if (cur >= maxn) break;
            p[cur] = 0;
            small[cur] = primes[j];  // 最小质因子
            if (i % primes[j] == 0) break;
        }
    }
}

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) (res *= a) %= mod;
        b >>= 1;
        (a *= a) %= mod;
    }
    return res;
}

int main() {
    init();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int a; scanf("%d", &a);
        while (a > 1) {
            int sp = small[a];
            int c = 0;
            while (a % sp == 0) a /= sp, c++;
            cnt[sp] = max(cnt[sp], c);
        }
    }
    ll ans = 1;
    for (int i = 2; i < maxn; i++) {
        ans = (ans * qpow(i, cnt[i])) % mod;
    }
    cout << ans << endl;
}

首先发现权值均为 $1$，我们就可以用 bfs() 求出初始的最短路径了。

对于每次修改，我们需要看一下：本次修改都影响了哪些节点？

但是，我们很难直接看出每次修改影响的节点，如果在整个图上跑最短路复杂度又太高。

注意到，因为原图的最短路来自 BFS，而我们又只关心，$u$ 距离 $1$ 的最短路径 是否比初始状态的大。

所以我们只要看，对于修改的一条边 $(u,v)$，$u$ 和 $v$ 的最短路径是否必须经过 $(u,v)$ 即可。

那么，对于修改 $(u,v)$ 的权值为 $2$，我们可以直接等效替换为：将 $(u,v)$ 从图中删除。

在删除过后，看哪些节点 距离 $1$ 的最短路长度变长了即可（如果不再连通到 $1$，直接令长度为 $inf$）。

证明：删除边 $(u,v)$ $=$ 修改权值？

分两种情况讨论：

1. $u$ 的最短路径长度 没有改变：这说明 $u$ 当前的最短路径并不需要经过 $(u,v)$，所以无论是删除，还是增加权值，都一样。 而对于其他的节点，因为 $u$ 都没受到影响，所以它们也不会受到影响，即答案不变。
   

2. $u$ 的最短路径长度 增加了：说明 $u$ 原先的最短路径必须经过 $(u,v)$，那么删掉 $(u,v)$ 就保证了最短路径一定无法经过 $(u,v)$。而给 $(u,v)$ 增加权值，$u$ 的新最短路径要么不经过 $(u,v)$（和删除一样），要么仍然经过 $(u,v)$（这样的话，在删除操作中，就说明 $u$ 与 $1$ 断开了）。所以删除和增加权值仍然等效。对于其他的节点，同理。

等效为删除以后，我们发现本题仍然不好做！

正难则反，我们不如考虑反过来处理，我们把对应的边删掉，然后从后往前，开始加边。

我们每次加上一条边 $(u,v)$，都会有如下性质：

1. 如果在加上这条边之前， $u$ 已经有 $d_u’ = d_u$ 了，则 $u$ 对其他节点不会产生任何影响。
2. 如果 $d_u'$ 变小了，那说明 $d_u’ = d_v’ + 1$
3. 如果 $d_u'$ 变小了，那么在变小后，只有 $d_u’ = d_u$ 时，$u$ 才会对其他节点产生 有效影响。

证明上述性质：

证明性质 $1$：$u$ 对其他节点产生影响的话，说明 $u$ 的最短路径缩短了（说明 $d_u'$ 变小了），如果在加上这条边之前已经有 $d_u’ = d_u$，则 $d_u'$ 无法变得更小，所以无法产生影响。

证明性质 $2$：$d_u'$ 如果变小，说明新的最短路径通过了 $(u,v)$，所以 $d_u’ = d_v’ + 1$

证明性质 $3$：有效影响 指的是：在增加 $(u,v)$ 以后，其他的某个节点 $x$ 的 $d_x'$ 变小，且 $d_x’ = d_x$。如果 $d_u'$ 变小，但是仍然有 $d_u’ > d_u$，则其他节点 $x$ 不可能通过 $u$ 来获取原先的最短路径 $d_x$，所以 $u$ 无法对其他节点产生有效影响。

由上，我们的算法就有了：

1. 先建好完整的图，跑一次 BFS 得到所有节点距离 $1$ 的最短距离。
2. 清空图，将所有 未修改 的边加到图中。
3. 从后向前的顺序，进行 加边 操作，当加上 $(u,v)$ 时，看一下是否存在 $u$ 使得 $d_u'$ 减小，且 $d_u’ = d_u$，如果有，更新 $u$ 所有 neighbor 的 $d_x'$ 值，再继续判断上述条件（这是一个递归的操作）。

复杂度：因为每个节点 $u$ 最多只需要更新一次 $d_u'$，每次更新会判断它的所有neighbor，所以复杂度为 $O(n+m)$

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

const int maxn = 1e5+5;
const int maxm = 2e5+5;

int n,m,Q, head[maxn], ecnt = 1, ans[maxn], d[maxn];
bool vis_plan[maxm];
struct Edge {
    int to, nxt;
} edges[maxm<<1];

struct Query {
    int u,v;
} query[maxm];
int plan[maxm];  // plan[i] 代表第i年要提升的query编号

void addEdge(int u, int v) {
    Edge e = {v, head[u]};
    edges[ecnt] = e;
    head[u] = ecnt++;
}

void clear() {
    fill(head, head+maxn, 0);
    ecnt = 1;
}

int curans;  //一开始有n-1个村庄不满

// 村庄u满意了，更新它的所有neighbor
void update(int u) {
    d[u] = ans[u];
    curans--;
    for (int e = head[u]; e; e = edges[e].nxt) {
        int to = edges[e].to;
        if (d[to] != ans[to] && d[u] + 1 == ans[to]) {
            update(to);  // 递归更新
        }
    }
}

// 加上第c条边，并且更新d[]
void add(int c) {
    int u = query[c].u, v = query[c].v;
    addEdge(u, v); addEdge(v, u);
    if (d[u] != ans[u] && d[v] + 1 == ans[u]) { // 更新后，u得到了最短路
        update(u);
    }
    if (d[v] != ans[v] && d[u] + 1 == ans[v]) {
        update(v);
    }
}

int q[maxn], hd = 0, tail = -1;
void init() {
    cin >> n >> m >> Q;
    fill(ans, ans+maxn, 1e9);
    fill(d, d+maxn, 1e9);
    ans[1] = 0;
    d[1] = 0;
    curans = n-1;

    for (int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        addEdge(u, v); addEdge(v, u);
        query[i] = {u,v};
    }
    q[++tail] = 1;
    while (hd <= tail) { //bfs
        int cur = q[hd++];
        for (int e = head[cur]; e; e = edges[e].nxt) {
            int to = edges[e].to;
            if (ans[to] == 1e9) {
                ans[to] = ans[cur] + 1;
                q[++tail] = to;
            }
        }
    }

    clear();  // 去掉所有的边
    for (int i = 1; i <= Q; i++) {
        int a; cin >> a;
        plan[i] = a;
        vis_plan[a] = 1;  // 这条边暂时被删去，之后才加上
    }
    for (int i = 1; i <= m; i++) {
        if (!vis_plan[i]) {
            add(i);
        }
    }
}

int ask_ans[maxm];  // 第i个询问的答案
int main() {
    init();
    for (int i = Q; i >= 1; i--) {
        ask_ans[i] = curans;
        add(plan[i]);
    }
    for (int i = 1; i <= Q; i++) {
        cout << ask_ans[i] << "\n";
    }
}

问题转化一下，我们可以维护两个有序数组 $a, b$，初始状态下 $a = [0,m], b = [0,n]$

$line ~ x$ 代表给数组 $a$ 添加一个元素 $x$，而 $row ~ x$ 代表给 $b$ 添加元素 $x$。

每次添加元素后，我们要找到 $a$ 中相邻元素的最大差值 $d_a$，还有 $b$ 中相邻元素的最大差值 $d_b$。

则，本次修改操作后的答案为 $d_a \times d_b$。

所以一个非常简单的思路是 维护 $2$ 个 map<int,int> 来代表有序数组 $a,b$。然后再用 $2$ 个 map<int, int> 来维护 $a,b$ 中的差值。每次添加元素，都更新一下 差值 map。

复杂度：$O(n\log n)$，会 $TLE$。

正难则反 的思想第二次出现了。我们可以把询问反过来做。

相当于我们先把所有的数字放进 $a,b$ 之中，然后从后往前处理询问，相当于每次从数组中拿走一个元素。

$a,b$ 可以用 链表思想 进行维护，这样删除一个元素和计算新差值的时间就是 $O(1)$ 了。

但是 $a,b$ 内是有序的，排序仍然需要 $O(n \log n)$ 的时间。

注意到 $a,b$ 内所有的元素都 $\leq 10^6$，所以直接使用 桶排序（bucket sort) 即可在 $O(n)$ 完成排序。

复杂度：$O(n+m+k)$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+2;

// 桶排序：将所有元素放进一个 cnt[] 数组内，然后从小到大遍历 cnt[] 数组即可
void bucket_sort(int* arr, int len) {
    static int cnt[maxn];
    for (int i = 1; i <= len; i++) cnt[arr[i]]++;
    int ptr = 0;
    for (int i = 0; i <= 1e6; i++) {
        while (cnt[i] > 0) {
            cnt[i]--;
            arr[++ptr] = i;
        }
    }
}

int n,m,k;
char op[5];
int arr[2][maxn], pos[2][maxn], pre[2][maxn], nxt[2][maxn], tail[2];
ll ans[maxn<<1], maxd[2];  // max diff

// pos[id][val]: val 所在 arr[id] 中的位置
// pre[id][j]: index j的前一个数字的index
// nxt[id][j]: index j的后一个数字的index

struct Query {
    int id, val;
} q[maxn<<1];

int main() {
    scanf("%d%d%d",&n,&m,&k);
    arr[0][1] = arr[1][1] = 0;
    arr[0][2] = m, arr[1][2] = n;
    tail[0] = tail[1] = 2;
    for (int i = 1; i <= k; i++) {
        scanf("%s", op);
        int a, id; scanf("%d", &a);
        if (op[0] == 'l') id = 0;
        else id = 1;

        q[i] = {id, a};
        arr[id][++tail[id]] = a;
    }
    for (int id = 0; id <= 1; id++) {
        bucket_sort(arr[id], tail[id]);
        for (int i = 1; i <= tail[id]; i++) {
            pos[id][arr[id][i]] = i;
            pre[id][i] = i-1, nxt[id][i] = i+1;
            maxd[id] = max(maxd[id], arr[id][i+1] - arr[id][i]);
        }
    }

    for (int i = k; i >= 1; i--) {
        ans[i] = maxd[0] * maxd[1];
        int id = q[i].id, val = q[i].val;
        int p = pos[id][val];
        int pr = pre[id][p], ne = nxt[id][p];
        maxd[id] = max(maxd[id], arr[id][ne] - arr[id][pr]);
        nxt[id][pr] = ne, pre[id][ne] = pr;  // 链表删除元素的更新
    }
    for (int i = 1; i <= k; i++) printf("%lld\n", ans[i]);
}

数位dp比较模版的题目。

令 $dp[i][j][k]$ 为：我们当前到了第 $i$ 位，数字 $mod ~ p = j$，数字内含有 $p$ 与否（含有：$k=1$）。

然后，我们离线化处理一下所有的询问，按照 $p$ 的值进行分类，这样可以只 memset() $9$ 次。

注：也可以在 dp[] 数组里面，额外加一个维度，表示 p 的值，这样就不用离线处理询问了。

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

ll dp[20][9][2];  // dp[i][j][k]: 到第i位，mod p = j, 含有p与否 (k = 1/0) 的数量
int arr[20], n, p;

ll dfs(int i, int j, int k, bool limit) {
    if (i <= 0) {
        if (j == 0 && !k) return 1;
        if (j != 0 && k) return 1;
        return 0;
    }
    if (!limit && dp[i][j][k] != -1) return dp[i][j][k];
    int ed = 9;
    if (limit) ed = arr[i];
    ll res = 0;
    for (int c = 0; c <= ed; c++) {
        res += dfs(i-1, (j*10+c)%p, k||(c == p), limit && (c == ed));
    }
    if (!limit) dp[i][j][k] = res;
    return res;
}

ll solve(ll x) {
    n = 0;
    while (x) {
        arr[++n] = x % 10;
        x /= 10;
    }
    return dfs(n, 0, 0, 1);
}

struct Query {
    int id;
    ll L,R;
};
vector<Query> q[10];
ll ans[maxn];

int main() {
    int T; cin >> T;
    for (int i = 1; i <= T; i++) {
        ll L, R; cin >> L >> R >> p;
        q[p].push_back({i, L, R});
    }
    for (p = 1; p <= 9; p++) {
        memset(dp, -1, sizeof(dp));
        for (auto que : q[p]) {
            ll L = que.L, R = que.R;
            ans[que.id] = solve(R) - solve(L-1);
        }
    }
    for (int i = 1; i <= T; i++) cout << ans[i] << "\n";
}

我们发现，这两种操作，分别是二进制 左移 和 右移。

并且我们发现，无论是左移还是右移，一个数字二进制中， $1$ 的数量都只能减少，而不能增加。

我们设最终的答案为 $x$（最后所有元素等于 $x$），那么 $x$ 的二进制中 $1$ 的数量，必须 $\leq \min\limits_i \{ count(a_i) \}$

我们随便选一个 二进制中 $1$ 的数量最少的数，令其为 $a_k$。

因为 $x$ 必然由 $a_k$ 移动而来，所以我们只要移动 $a_k$，就可以枚举答案 $x$。

问题转化为：已知最终答案为 $x$，如何求出操作次数？

我们再次利用了 $1$ 的数量只减不增的特点，对于每一个 $a_i$，我们都观察一下 $a_i$ 中 $1$ 的数量，分两种情况：

1. $count(a_i) > count(x)$：那么我们右移 $a_i$，直到 $count(a_i) = count(x)$。
2. $count(a_i) = count(x)$：看一下是否可以通过移动 $a_i$ 得到 $x$。（即，它们其中一个是否为另外一个的 $2^j$ 次方）。如果不能通过移动得到，就说明这个 $x$ 是非法的。

对于情况 $2$，我们可以预处理出所有 $2^j$ 对应的 $j$。

• 注意，无论什么情况下，都必然有解。因为 $x = 1$ 一定有解！

复杂度：$O(nlog^2n)$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

int n;
struct node {
    int cnt, val;
} arr[maxn];

int count_bit(int x) {
    int res = 0;
    while (x) {
        if (x&1) res++;
        x >>= 1;
    }
    return res;
}

int ans = 2e9;
map<int, int> mp;
void solve(int x, int t) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int v = arr[i].val;
        int c = arr[i].cnt;
        while (c > t) {  // Case1
            if (v & 1) c--;
            v >>= 1;
            res++;
        }

        // Case2
        if (v < x) {
            if (x % v) return;
            if (!mp.count(x/v)) return;
            res += mp[x/v];
        } else {
            if (v % x) return;
            if (!mp.count(v/x)) return;
            res += mp[v/x];
        }
    }
    ans = min(ans, res);
}

int main() {
    scanf("%d", &n);
    int mincnt = 1e9, mini;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i].val);
        arr[i].cnt = count_bit(arr[i].val);
        if (arr[i].cnt < mincnt) {
            mincnt = arr[i].cnt;
            mini = i;
        }
    }
    for (int j = 0; (1<<j) <= 2e6; j++) {
        mp[(1<<j)] = j;
    }

    for (int v = arr[mini].val; v <= 2e6; v <<= 1) {
        solve(v, count_bit(v));
    }
    for (int v = arr[mini].val >> 1; v >= 1; v >>= 1) {
        solve(v, count_bit(v));
    }
    cout << ans << endl;
}