BITACM2018第二轮积分赛（一）题解

A - 一道可持久化并查集好题

出题人： $zhber$

通过/提交： $17/37$

题解： 此题数据极小，直接模拟即可。撤销操作就是不执行前面 $k$ 次操作，把撤销操作视为返回 $k$ 次之前的历史版本。用state[i][j][k] 表示第 $i$ 次操作后第 $j$ 个点和第 $k$ 个点是否联通，对于 $1$ 操作，复制上一次操作之后的状态，然后考虑新增的经过 $a-b$ 边而可到达的点对。这些新点对（记为x^y）一定是 $x$ 在一侧， $y$ 在另一侧，由于新加了 $a-b$ 而联通。那么分别找 $a,b$ 能到达的点放到两集合内，取两个集合各一点配对都设为联通即可 $O(n^2)$ 。或者直接floyd传递闭包 $O(n^3)$ 。对于第 $2$ 种操作，复制上一次的状态，暴力找和它联通的点数。对于第三种操作，复制的不是上一次的状态，而是第 $x-k-1$ 次的状态。时间复杂度 $O(n^2m)$ ，空间复杂度 $O(n^2m)$ 。

#include<bits/stdc++.h>
#define maxn 100 + 10
using namespace std;
int state[maxn][maxn][maxn];
int n,m;
int main()
{
    scanf(\"%d%d\",&n,&m);
    for (int i=1;i<=n;i++) state[0][i][i]=1;
    for (int i=1;i<=m;i++)
    {
        int op;scanf(\"%d\",&op);
        if (op==1)
        {
            for (int j=1;j<=n;j++)
                for (int k=1;k<=n;k++)
                    state[i][j][k]=state[i-1][j][k];
            int a,b;scanf(\"%d%d\",&a,&b);
            vector<int>A,B;A.clear();B.clear();
            for (int j=1;j<=n;j++)
            {
                if (state[i][a][j])A.push_back(j);
                if (state[i][b][j])B.push_back(j);
            }
            for (int j=0;j<A.size();j++)
                for (int k=0;k<B.size();k++)
                {
                    state[i][A[j]][B[k]]=1;
                    state[i][B[k]][A[j]]=1;
                }
        }else if (op==2)
        {
            for (int j=1;j<=n;j++)
                for (int k=1;k<=n;k++)
                    state[i][j][k]=state[i-1][j][k];
            int a,sum=0;scanf(\"%d\",&a);
            for (int j=1;j<=n;j++)if (state[i][j][a])sum++;
            printf(\"%d\\n\",sum);
        }else if (op==3)
        {
            int k;scanf(\"%d\",&k);
            for (int j=1;j<=n;j++)
                for (int l=1;l<=n;l++)
                    state[i][j][l]=state[i-k-1][j][l];
        }
    }
}

B - zhb love math

出题人： $strawberry$

通过/提交： $1/2$

题解： 考虑每个元素 $b_i$ 对答案的贡献，一定是一些包含 $b_i$ 的区间，且区间除了它以外，没有 $b_j$ 是 $b_i$ 的因数。容易想到的是，对每个 $b_i$ 找到包含它可行区间的最左边 $l_i$ 和包含它可行区间的最右边 $r_i$ 那么任何区间 $[l,r]\\ l,r∈[l_i,r_i]$ 都是答案，这样的区间有 $(i-l_i+1)×(r_i-i+1)$ 个，朴素的 $O(n^2)$ 想法是从 $i$ 开始往左往右扫，找到第一个 $b_j\\%b_i=0$ 的 $j$ 就是边界，因为 $n\\leq 10^5$ ，是不能通过这题的。考虑怎么优化，当枚举到 $i$ 的时候，对于 $i$ 左侧的 $b_j$ 如果 $b_j\\%b_i=0$ 那么对于位置 $j$ 的 $r_j$ 最右只能到 $(i-1)$ 的位置！，因为 $b_i\\leq 10^4$ ，所以可以直接枚举 $b_i$ 的倍数 $j$ 去更新答案，从左往右扫以 pre[i] 表示 $i$ 最后出现的位置，对于 $b_i$ 如果出现过其倍数 $j$ ，就有 r[pre[j]]=i-1 。同理扫着扫一遍对 $l$ 维护一个 last[i] 数组就能得到答案。时间复杂度 $O(nlogm)$ ，空间复杂度 $O(n+m)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
/* head */
int a[maxn], l[maxn], r[maxn], pre[maxn], last[maxn];
void solve() {
    int n;
    scanf(\"%d\", &n);
    for (int i = 1; i <= n; i++) {
        scanf(\"%d\", &a[i]);
        l[i] = 1, r[i] = n;
    }
    memset(pre, 0, sizeof pre);
    memset(last, 0, sizeof last);
    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= 10000; j += a[i]) {
            if (pre[j] != 0 && r[pre[j]] == n) r[pre[j]] = i - 1;
        }
        pre[a[i]] = i;
    }
    for (int i = n; i >= 1; i--) {
        for (int j = a[i]; j <= 10000; j += a[i]) {
            if (last[j] != 0 && l[last[j]] == 1) l[last[j]] = i + 1;
        }
        last[a[i]] = i;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans = (ans + 1LL * (i - l[i] + 1) * (r[i] - i + 1) % mod) % mod;
    printf(\"%lld\\n\", ans);
}
int main() {
    int t;
    scanf(\"%d\", &t);
    while (t--) solve();
    return 0;
}

C - 旅かえる

出题人： $FSMM$

通过/提交： $28/130$

题解： 将问题反过来看就是问第 $n$ 片荷叶到第 $i$ 片荷叶所需要花的最短时间。就是一个简单的最短路模型，我们读入时候倒着建边，从 $n$ 点开始跑一遍单源最短路就是答案！时间复杂度 $O(n^3)$ ，空间复杂度 $O(n+m)$ 。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 100005
#define INF 0x3f3f3f3f
typedef long long ll;

using namespace std;

struct Edge
{
    int to, next;
}edge[maxn*2];
int head[maxn], tot, dis[maxn];
bool vis[maxn];
void Init()
{
    memset(head, -1, sizeof(head));
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    tot = 0;
}
void add(int u, int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void spfa(int s)
{
    queue<int> que;
    while(!que.empty()) que.pop();
    que.push(s); vis[s] = true;
    dis[s] = 0;
    while(!que.empty()){
        int tmp = que.front();
        que.pop(); vis[tmp] = false;
        for (int i = head[tmp]; ~i; i = edge[i].next){
            int to = edge[i].to;
            if (dis[to] > dis[tmp] + 1){
                dis[to] = dis[tmp] + 1;
                if (!vis[to]){
                    que.push(to); vis[to] = true;
                }
            }
        }
    }
}
int main()
{
    int T, n, x;

    scanf(\"%d\", &T);
    while(T--){
        scanf(\"%d\", &n);
        Init();
        for (int i = 1; i <= n; i++){
            scanf(\"%d\", &x);
            if (i - x >= 1) add(i - x, i);
            if (i + x <= n) add(i + x, i);
        }
        spfa(n);
        for (int i = 1; i < n; i++){
            if (dis[i] == INF) printf(\"-1 \");
            else printf(\"%d \", dis[i]);
        }
        printf(\"0\\n\");
    }
    return 0;
}