A

概率 模拟

八个一样的显示器，都是七段数码管，每个灯管都有一个通电后亮不亮的概率。一次尝试点亮每一个灯管。上下各四个，问上下形成的数字和为给定数字的概率。

七个灯管之间是独立的，用每个灯管亮灭的概率能组合出显示0-9的数字的概率，进一步可以算出四个灯管组成不同数字的概率。然后枚举上面的灯管，上下和一定，可以确定下面的灯管的值和概率，相乘就是上下加起来等于c的一种情况的概率，累加就是答案

计算0-9的数字的概率这块写起来有点难受，可能有状压的写法更快，以及可以用自动取模的modint类来省去取模

复杂度，瓶颈在预处理四位数的概率，可以压到

void solve() {
    int c;
    cin >> c;
    vi p(8), q(8);
    rep(i, 1, 7) {
        cin >> p[i];
        q[i] = 100 - p[i];
 
        p[i] = p[i] * inv(100, M2) % M2;
        q[i] = q[i] * inv(100, M2) % M2;
//      cout<<p[i]<<' '<<q[i]<<'\n';
    }
 
    vi P(10);
    P[0] = p[1] * p[2] % M2 * p[3] % M2 * q[4] % M2 * p[5] % M2 * p[6] % M2 * p[7] % M2;
    P[1] = q[1] * q[2] % M2 * p[3] % M2 * q[4] % M2 * q[5] % M2 * p[6] % M2 * q[7] % M2;
    P[2] = p[1] * q[2] % M2 * p[3] % M2 * p[4] % M2 * p[5] % M2 * q[6] % M2 * p[7] % M2;
    P[3] = p[1] * q[2] % M2 * p[3] % M2 * p[4] % M2 * q[5] % M2 * p[6] % M2 * p[7] % M2;
    P[4] = q[1] * p[2] % M2 * p[3] % M2 * p[4] % M2 * q[5] % M2 * p[6] % M2 * q[7] % M2;
    P[5] = p[1] * p[2] % M2 * q[3] % M2 * p[4] % M2 * q[5] % M2 * p[6] % M2 * p[7] % M2;
    P[6] = p[1] * p[2] % M2 * q[3] % M2 * p[4] % M2 * p[5] % M2 * p[6] % M2 * p[7] % M2;
    P[7] = p[1] * q[2] % M2 * p[3] % M2 * q[4] % M2 * q[5] % M2 * p[6] % M2 * q[7] % M2;
    P[8] = p[1] * p[2] % M2 * p[3] % M2 * p[4] % M2 * p[5] % M2 * p[6] % M2 * p[7] % M2;
    P[9] = p[1] * p[2] % M2 * p[3] % M2 * p[4] % M2 * q[5] % M2 * p[6] % M2 * p[7] % M2;
     
//  rep(i,0,9){
//      cout<<P[i]<<' ';
//  }
 
    vi num(3000);
    rep(i, 0, 2) {
        rep(j, 0, 9) {
            rep(x, 0, 9) {
                rep(y, 0, 9) {
                    int v = i * 1000 + j * 100 + x * 10 + y;
                    int pp = P[i] * P[j] % M2 * P[x] % M2 * P[y] % M2;
                    num[v] = (num[v] + pp) % M2;
                }
            }
        }
    }
 
    int ans = 0;
    rep(i, 0, c) {
        ans += num[i] * num[c - i] % M2;
        ans %= M2;
    }
    cout << ans << '\n';
}

B

思维 概率

两个人都有一个序列，每一轮大的走并得分。可以随意排列，问一方得到最大得分的方案数？

对手手里最小的牌是的，那我如果有一个比小的牌，它后面的都打不出去，即使后面有更大的，因为必须按顺序出，卡在就不动了。所以我们应该把能得分的牌都在前面都打出来，哪些牌能得分？就是所有比大的，这些牌遇到对手的都能得分，剩下的牌都是打不出去的，放在后面

能打出的，和打不出的牌，两堆的顺序是无所谓的，能打出去的话无论怎么拍都能打出去，只是时间问题，打不出去的怎么拍也不可能打出去。

所以这两堆分别全排列，乘起来的方案数就是答案

int p[N];
void solve() {
    int n;
    cin >> n;
    vi a(n + 1), b(n + 1);
 
    rep(i, 1, n) {
        cin >> a[i];
    }
    rep(i, 1, n) {
        cin >> b[i];
    }
 
    int mn = inf;
    rep(i, 1, n) {
        mn = min(mn, b[i]);
    }
 
    int cnt = 0;
    rep(i, 1, n) {
        if (a[i] > mn) {
            cnt++;
        }
    }
 
    int ans = p[cnt] * p[n - cnt] % M2;
    cout << ans << '\n';
}

C

思维 诈骗

令为最大值的位置，实际上可以给所有位置变成最大值，除了由于这是开区间，开头结尾不能改。

void solve() {
    int n;
    cin >> n;
    vi a(n + 1);
    int ans = 0, mx = 0;
    rep(i, 1, n) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
 
    ans += a[1];
    if (n != 1) {
        ans += a[n];
    }
    ans += max(0ll, n - 2) * mx;
     
    cout<<ans<<'\n';
}

D

二分 贪心

显然有单调性，考虑二分。

接下来就是最多进行步，把所有都染红，所需的初始染色点是否超过个？由于只能往右染色，考虑从左往右染色，每一次可以设置一个初始染色点，让他走个时间步，看他能延伸到最远多少，然后从下一个未染色的点开始，再放一个初始染色点，这样继续下去，看把所有染色，，需要的初始染色点是否超过个

具体实现上，一个点染色了，每一步会把右侧个点都染色，所以染色后每一个时间步的拓展，考虑的是上一个时间步所有染红的点，同时往右染色一次，最远能到多远。这可以预处理前缀最大值得到，含义是假设当前把前缀都染红了，下一秒，最远能拓展到多少，我们贪心模拟的时候，经过一秒，可以直接从跳到

模拟时，如果一个初始染色点，经过了步，则停止，在右侧第一个白色位置再开一个初始染色点。或者，如果右侧有一堆障碍，把这次初始染色点的传播阻断了，这表现为，则需要走过这段障碍，到下一个白色位置放一个种子，重新开始。

void solve() {
    int n, k;
    cin >> n >> k;
 
    vi a(n + 1), nxt(n + 1);
    int cnt = 0;
    rep(i, 1, n) {
        cin >> a[i];
        nxt[i] = max(nxt[i - 1], a[i] + i);
        if (a[i]) {
            cnt++;
        }
    }
 
    if (cnt <= k) {
        cout << 0 << '\n';
        return;
    }
    int l = 1, r = n;
    auto check = [&](int x)->bool{
        int use = 1;
        int i = 1;
 
        while (i <= n && a[i] == 0) {
            i++;
        }
        int time = 0;
        while (i <= n) {
            time++;
            i = nxt[i];
            if (i >= n) {
                break;
            }
            if (nxt[i] == i) {
                while (i <= n && nxt[i] == i) {
                    i++;
                }
                if (i <= n) {
                    use++;
                    time = 0;
                }
            } else if (time == x) {
                i++;
                while (i <= n && a[i] == 0) {
                    i++;
                }
                if (i <= n) {
                    time = 0;
                    use++;
                }
            }
        }
        return use <= k;
    };
    while (l <= r) {
        int m = (l + r) / 2;
        if (check(m))r = m - 1;
        else l = m + 1;
    }
    if (l <= n) {
        cout << l << '\n';
    } else {
        cout << -1 << '\n';
    }
 
}

E

模拟 思维

这实际上就是一个环形数组上一个长度为的滑窗，求窗口内元素和最大值，枚举即可

void solve() {
    int n, k;
    cin >> n >> k;
    vi a(n + 1);
    rep(i, 1, n) {
        cin >> a[i];
    }
 
    int ans = max(k + a[1], k + a[n]);
    rep(i, 1, n - 1) {
        ans = max(ans, a[i] + a[i + 1]);
    }
    cout << ans << '\n';
}

G

数位贪心

操作是把一个数对称反转，去掉前导零。问一个区间内执行这个操作后的最大值？

数位最大值问题，首先是长度更长的（不含前导零）肯定更大，优先考虑长度更长的，尽可能要去取到右边界的长度。如果不是的形式，一定能取到。如果是，则答案是这样。

因此可以分类讨论，但是有点麻烦。考虑一个不需要分类讨论的做法：直接枚举答案的长度，然后对于每个长度计算最优答案，这样可以规避分类讨论。对于一个特定长度，我们从高位开始贪心，那肯定高位优先选大的数，问题是，选了大的，可能对后面的选择范围有影响，比如，对于长度的，最优肯定是，但为了选这个，我们不得不把十位范围从缩到

具体来说，就是当前可选的范围是的话，想让当前数位是，则需要在这个范围内找模同余的最小和最大数，作为新的区间范围，如果不存在非空区间，说明这个是无法满足的，尝试更小，否则这一位就确定了，以去看下一位

int p[20];
void solve() {
    int l, r;
    cin >> l >> r;
 
    string s = to_string(l);
    string t = to_string(r);
 
    int ans = 0;
    rep(i, s.size(), t.size()) {
        int L = max(l, p[i - 1]), R = min(r, p[i - 1] * 10 - 1);
        int cur = 0;
        rep(j, 1, i) {
            for (int d = 9; d >= 0; d--) {
                int nL = (L - d + 9) / 10;
                int nR = R - d >= 0 ? (R - d) / 10 : -1;
                if (nL <= nR) {
                    L = nL;
                    R = nR;
                    cur = cur * 10 + d;
                    break;
                }
            }
        }
        ans = max(ans, cur);
    }
    cout << ans << '\n';
}

H

位运算 dp 滑窗 前缀和

一个加法表达式，可以把一些换成按位或，规定按位或的优先级更高，问有多少种换法，换之后表达式的值和换之前相等？

如果我们把一个后缀都换成按位或，那么只要这个后缀的值和原来相同，那这两种表达式的值都是相同的，前面的无影响，这就是无后效性，考虑，表示前缀相等的替换方案数。

我们可以枚举后缀，如果一个后缀换成按位或，值和换之前相等，则可以有转移。注意这里我们只考虑把后缀全都换成按位或，只换一部分的可以等价于换多次全部换成按位或，比如可以看成两次

但这样转移的，还是太慢。注意到一个性质，如果某一个后缀，使用不相等了，那更长的后缀肯定也都不相等，不用考虑了，也就是说每次可以转移的，组成了的一个后缀。并且有单调性，越长，参与运算的元素越多，越可能出现不相等的情况。于是考虑滑窗/二分维护每个的最长后缀，然后前缀和查询这个后缀内的，直接转移。

这里我采用滑窗，过程中需要快速查询区间按位或，使用表

void solve() {
    int n;
    cin >> n;
 
    vi a(n + 1), s(n + 1);
    rep(i, 1, n) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
 
    SparseTable st(a);
 
    vi f(n + 1);
    f[0] = 1;
    int cur = f[0];
    for (int l = 1, r = 1; r <= n; r++) {
        while (s[r] - s[l - 1] != st.query(l, r)) {
            cur = (cur - f[l - 1] + M2) % M2;
            l++;
        }
        f[r] = cur;
        cur = (cur + f[r]) % M2;
//      cout << f[r] << ' ';
    }
 
    cout << f[n] << '\n';
}

J

解1：线段树优化prim

这是个完全图，不能，考虑。的关键是，每次扩充生成树集合时，需要快速找到一个连接生成树集合，和其余点的最短边，直接找是，需要用数据结构优化这一过程。

这里选择线段树，每次查询实际上就是在上，找到一个，其中是生成树点集内的点。这是个区间查询，所以可以线段树，每个点保存对应区间内最小，以及取到这个边的对应，因为我们需要把这个加入生成树集合。

一个点加入生成树后，需要把这个点的出边也纳入考虑，这等价于一个线段树区间更新，我们让这个点作为，去更新。删除一些边的影响是，如果不删，我们直接更新全部区间，现在删了一些点，相当于在上挖掉一些点，形成几个区间，我们分别对这些区间做更新即可。

区间更新则需要懒标记和下传，懒标记记录待生效的最小，下传时，需要利用这个，计算出这个区间的，于是我们还需要知道这个区间内的最小，以及最小值的下标，组合起来就是这个区间的最小边。

一个点加入生成树后，后续不能对产生贡献，所以把这个点的点权，和这个点的置为

需要注意这个图可能不连通，如果中途出现查询出的最小边是就说明没有边可加了，无解，直接结束。如果运行满轮说明联通，有解

每次更新是一个线段树查询，加上和这个点有关的删除边，每个会创造一次更新，总复杂度

int a[N];
struct Tree {
#define ls u<<1
#define rs u<<1|1
    struct Node {
        int l, r;
        pii mnv, mne;
        int todo;
    } tr[N << 2];
 
    void pushup(int u) {
        tr[u].mnv = min(tr[ls].mnv, tr[rs].mnv);
        tr[u].mne = min(tr[ls].mne, tr[rs].mne);
    }
 
    void pushdown(int u) {
        tr[ls].todo = min(tr[ls].todo, tr[u].todo);
        tr[rs].todo = min(tr[rs].todo, tr[u].todo);
        tr[ls].mne = min(tr[ls].mne, {tr[u].todo + tr[ls].mnv.fi, tr[ls].mnv.se});
        tr[rs].mne = min(tr[rs].mne, {tr[u].todo + tr[rs].mnv.fi, tr[rs].mnv.se});
    }
 
    void build(int u, int l, int r) {
        tr[u] = {l, r, {a[l], l}, {a[l] + inf, l}, inf};
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(u);
    }
 
    void modify(int u, int l, int r, int val) {
        if (tr[u].l >= l && tr[u].r <= r) {
            tr[u].todo = min(tr[u].todo, val);
            tr[u].mne = min(tr[u].mne, {tr[u].mnv.fi + val, tr[u].mnv.se});
            return ;
        } else {
            int mid = (tr[u].l + tr[u].r) >> 1;
            pushdown(u);
            if (mid >= l)   modify(ls, l, r, val);
            if (r > mid) modify(rs, l, r, val);
            pushup(u);
        }
    }
 
//  ll query(int u, int l, int r) {
//      if (l <= tr[u].l && tr[u].r <= r)    return  tr[u].mx;
//      pushdown(u);
//      int mid = (tr[u].l + tr[u].r) >> 1;
//      if (r <= mid)return query(ls, l, r);
//      if (l > mid)return query(rs, l, r);
//      return query(ls, l, r) + query(rs, l, r);
//  }
    void del(int u, int idx) {
        if (tr[u].l == tr[u].r) {
            tr[u].mnv = {inf, idx};
            tr[u].mne = {inf + a[idx], idx};
            return ;
        } else {
            int mid = (tr[u].l + tr[u].r) >> 1;
            pushdown(u);
            if (idx <= mid) del(ls, idx);
            else del(rs, idx);
            pushup(u);
        }
    }
} t;
void solve() {
    int n, m;
    cin >> n >> m;
    rep(i, 1, n) {
        cin >> a[i];
    }
 
    vector<set<int>>s(n + 1);
    vvi g(n + 1);
 
 
    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        s[u].insert(v);
        s[v].insert(u);
    }
 
    rep(i, 1, n) {
        for (int x : s[i]) {
            g[i].push_back(x);
        }
    }
 
    t.build(1, 1, n);
 
    int idx = 1;
    int ans = 0;
    rep(i, 1, n - 1) {
        t.del(1, idx);
        int l = 0;
        for (int r : g[idx]) {
            if (l + 1 <= r - 1) {
                t.modify(1, l + 1, r - 1, a[idx]);
            }
            l = r;
        }
        if (l + 1 <= n) {
            t.modify(1, l + 1, n, a[idx]);
        }
 
        ans += t.tr[1].mne.fi;
        idx = t.tr[1].mne.se;
//      cout<<t.tr[1].mne.fi<<' '<<t.tr[1].mne.se<<'\n';
        if (ans >= inf)break;
    }
 
    if (ans >= inf) {
        ans = -1;
    }
    cout << ans << '\n';
}

解2：boruvka

prim和kruskal的结合，维护多个连通块，初始每个点自己是一个连通块，每一轮，对每个联通快，找到连接这个连通块和其他连通块的最小边，连接这条边，合并连通块，连接的边加入最小生成树。这样每轮最坏也是连通块两两合并，连通块个数折半，只会进行轮。

每一轮，对于每个联通快寻找最小边的过程。维护一个包含所有点权的，枚举连通块，把当前块内点从删掉，再枚举连通块内点，把每个点有关的删除边的端点，也删掉（如果不再当前连通块内才删除，在当前块内在上一步的删除就已经删了），此时剩下的点，就是可以和当前枚举的点组成边的所有点，我们想让边权z最小，取最小点即可。这样每个点都有一个最小边，块内每个点的最小边，再取，就是这个连通块这一轮的最小边，如果这条边存在，且两个端点在不同连通块内（可能会出现两个端点都在一个连通块内，此时什么都不做），连接这条边。我们刚才删除的点，是为了查询临时删除，查询后还要恢复。

执行轮数和查询都是，插入和删除是复杂度，由于线段树的很大，这个做法没有比做法一慢多少

int f[N], sz[N];
pii mn[N];
int find(int x) {
    if (f[x] == x)return x;
    return f[x] = find(f[x]);
}
void merge(int x, int y, vvi &s) {
    x = find(x), y = find(y);
    if (sz[x] > sz[y])swap(x, y);
    for (int v : s[x]) {
        s[y].push_back(v);
    }
    f[x] = y;
    sz[y] += sz[x];
}
void solve() {
    int n, m;
    cin >> n >> m;
    vi a(n + 1);
    rep(i, 1, n) {
        cin >> a[i];
    }
 
    vvi g(n + 1);
    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    int ans = 0;
    set<pii>all;
    vvi s(n + 1);
    rep(i, 1, n) {
        f[i] = i;
        sz[i] = 1;
        s[i].push_back(i);
        all.insert({a[i], i});
    }
 
 
 
    while (1) {
        rep(i, 1, n) {
            mn[i] = {inf, 0};
        }
         
        int cnt=0;
        rep(i, 1, n) {
            if (find(i) == i) {
                for (int x : s[i]) {
                    all.erase({a[x], x});
                }
                for (int x : s[i]) {
                    for (int y : g[x]) {
                        if(find(y)==find(x))continue;
                        all.erase({a[y], y});
                    }
                    if (all.size()) {
                        auto [v, id] = *all.begin();
                        mn[i] = min(mn[i], {a[x] + v, id});
                    }
                    for (int y : g[x]) {
                        if(find(y)==find(x))continue;
                        all.insert({a[y], y});
                    }
                }
                for (int x : s[i]) {
                    all.insert({a[x], x});
                }
            }
        }
        int t=0;
        rep(u, 1, n) {
            int v = mn[u].se;
            if (v && find(u) == u && find(u) != find(v)) {
                cnt++;
                merge(u, v, s);
                ans += mn[u].fi;
            }
        }
        if(!cnt)break;
    }
    for(int i=1;i<=n;i++){
        if(find(i)!=find(1)){
            cout<<-1<<'\n';
            return;
        }
    }
    cout << ans << '\n';
}

K

诈骗 数学

构造一个长度，元素各不相同，都是正整数，元素和等于元素乘积的序列。

注意到元素都不同的话，元素乘积的增长远远快于元素和，所以对于较大的肯定无解，只有较小，和，乘积是同阶的，才可能有解。

手玩发现只有有解，时，和，乘积差距最小的是，也是，不相等。

void solve() {
    int x;
    cin >> x;
    if (x == 1) {
        cout << "YES\n";
        cout << 1 << '\n';
    } else if (x == 3) {
        cout << "YES\n" << 1 << ' ' << 2 << ' ' << 3 << '\n';
    } else {
        cout << "NO\n";
    }
}

L

数论

执行一次的乘法，乘上尽可能小的数，让一个数的最低位变成。最低位是就是的倍数，就是至少含一组因子，想变成这样的话，就看缺哪个，用乘法补上，都不缺乘，缺一个就补那个，缺两个直接乘

void solve() {
    int n;
    cin>>n;
    if(n%10==0){
        cout<<1<<'\n';
    }
    else if(n%2==0){
        cout<<5<<'\n';
    }
    else if(n%5==0){
        cout<<2<<'\n';
    }
    else{
        cout<<10<<'\n';
    }
}