10.6模拟赛 —— Nescafe17

2022秋

Contest_Summary

Expect：

Present：

• T1看错模数，痛失 $70$ 分
• T2本可以滚动数组优化保证不炸空间，最后在调试题目测试方式下惊险过掉。
• T3难度较大，没想到合适的算法。

T1 Magician

Description

给你 $n$ 个点，现在依次加入 $m$ 条边，每加入一条边，你都需要求出当前的图有多少非空子图是欧拉回路森林。

欧拉回路森林指每个点的度数均为非零偶数的图。

$1\leq n\leq 2\times 10^5,1\leq m\leq 3\times 10^5$。

Solution

首先很容易知道答案单调，观察样例，发现要么不变，要么 $Ans << 1 | 1$

考虑变化的条件，不难发现如果新增的边两端点联通，则答案增加。

考虑感性证明一下，可以把这张图分成很多个小环，那么新增一条边，如果两端点联通，则一定生成唯一一个小环。

所以答案会增加 $1$ 倍，并且还要加上新生成的这个环，所以会 $Ans << 1 | 1$

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48),c  = getchar();
    return f ? -x : x;
}
const int maxn = 2 * 1e5 + 5, mod = 1e9 + 9; 
int n, m;
int Father[maxn], Answer = 0;
inline int Find(int x) {
    if(Father[x] != x) return Father[x] = Find(Father[x]);
    return Father[x];
}
inline void Unnion(int u, int v) {
    int f1 = Find(u), f2 = Find(v);
    if(f1 != f2) Father[f2] = f1;
}
signed main() {
//  freopen("magician.in", "r", stdin);
//  freopen("magician.out", "w", stdout);
    n = read(), m = read();
    for(register int i = 1; i <= n; ++i) Father[i] = i;
    for(register int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        if(Find(u) != Find(v)) printf("%lld\n", Answer % mod);
        else Answer = (Answer << 1ll | 1ll) % mod, printf("%lld\n", Answer % mod);
        Unnion(u, v);
    }
    return 0;
}

Summary

无论是猜到结论还是证明都不是很难，但是出现细节性读题失误。

T2 Guard

Description

给你 $n$ 个物品，每个物品有两个属性 $p$ 和 $v$。
你最开始的得分为 $k$，你有 $p_i$ 的概率拿走第 $i$ 个物品，并且你的得分会加上 $v_i$。

求你最终拿到至少 $l$ 个物品，并且得分为非负数的概率，保留六位小数。

$0\leq k\leq 2\times 10^3,0\leq n\leq 200,-1\leq v_i\leq 10^3,0\leq l\leq n,0\leq p_i\leq 100$。

Solution

首先考虑背包，特殊点在于 $v_i$ 为负时最多为 $-1$。

所以容量超过 $n$ 时多余的就没有意义了，所以可以将所有容量与 $n$ 取 $min$

然后在多开一维记录赢了几场即可。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define f(i, j, k) f[i][min(j, n) + 201][k]
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 205;
int n, L, K;
int Val[maxn];
double p[maxn], f[2][maxn << 1][maxn], Answer;
int main() {
//  freopen("guard.in", "r", stdin);
//  freopen("guard.out", "w", stdout);
    n = read(), L = read(), K = read();
    for(register int i = 1; i <= n; ++i) {
        int x = read(); 
        p[i] = (double) x / 100.0; 
    }
    for(register int i = 1; i <= n; ++i) Val[i] = read();
    f(0, K, 0) = 1.0;
    for(register int i = 0; i < n; ++i) {
        for(register int j = -1 * i; j <= n; ++j)
            for(register int k = 0; k <= i; ++k) f((i & 1) ^ 1, j, k) = 0; 
        for(register int j = -1 * i; j <= n; ++j)
            for(register int k = 0; k <= i; ++k) {
                f((i & 1) ^ 1, j + Val[i + 1], k + 1) += p[i + 1] * f(i & 1, j, k);
                f((i & 1) ^ 1, j, k) += (1.0 - p[i + 1]) * f(i & 1, j, k);
            }
        }
    for(register int i = 0; i <= n; ++i)
        for(register int j = L; j <= n; ++j) Answer += f(n & 1, i, j);
    printf("%0.6lf", Answer);
    return 0;
}

Summary

空间差点炸掉，考场上贪了不想滚动，其实无论是滚掉一维还是把数组排序，都能使空间保证不会炸。

T3 Laser

Description

给你 $n$ 个区间，对于数字 $1\sim9$ 中的两个不同的数 $u,v$，若在这 $n$ 个区间中任意选择一个数 $a$，将其低 $k$ 位中的某一位的 $u$ 换成 $v$（或者 $v$ 换成 $u$）均都能落在这 $n$ 个区间内，则称 $u$ 和 $v$ 是 $\text{k-equal}$ 的。

若一个集合 $S$ 内的元素都是互相 $\text{k-equal}$ 的，则称集合 $S$ 是 $\text{k-equivalence class}$。

按照元素的最小值排序所有 $\text{k-equivalence class}$ 后输出。

$1\leq n\leq 10^4,1\leq k\leq 19,1\leq l_1\leq r_1<l_2\leq r_2<\dots<l_n\leq r_n\leq 10^{18}$。

Solution

一道很好的题，类似数位 DP ？

首先要明确一件事，对于某个区间，比较其两端点的每一位，都会对答案造成限制，我们要做的就是如何很好的 check 对于当前位到底哪些数间有限制。

首先可以做一个预处理，把所有形如 $[l, r], [r + 1, k]$ 的区间合并，这样在不同的区间间一定有一些空格。

对于当前的数位 $A[i], B[i]$ 分类讨论。

$1^o$ $A[1,i) = B[1, i)$

$\quad$ 在这中间可以再分两类。

$\quad$ $1)$ $A[i] = B[i]$ :

$\quad\quad$ $p$ 已经确定为 $i$ ，只需要枚举 $q = x$

$\quad\quad$ 此时新区间为 $A[1,i)+x+A(i, n]$ 到 $B[1,i)+x+B(i,n]$

$\quad\quad$ 考虑如何 check 此区间是否合法，只需要二分这两个端点，是否在原图中的同一个区间，如果不在则必定不合法，因为此时一定有一个数会落到空格中。

$\quad\quad$ 到此这种情况解决完毕。

$\quad$ $2)$ $A[i] \neq B[i]$

$\quad\quad$ 此时 $p$ 有三种取值情况，每种情况对应了一种不同的可行区间，如果更改后的区间落在此区间则合法。

$\quad\quad$ $To\in\begin{cases}[A(i, n],99\ldots9] &,p = A[i]\\ [00\ldots0, 99\ldots9] &,p \in (A[i], B[i])\\ [00\ldots0,B(i,n]] &,p = B[i] \end{cases}$

$\quad\quad$ 此种情况考虑完毕。

$2^o$ $A[1,i) \neq B[1, i)$

$\quad$ 考虑前缀取 $A[1,i) + 1$ 至 $B[1,i) - 1$ 的情况，发现第 $i$ 位如何改都没问题，所以不需要考虑这段区间。

$\quad$ 所以只需考虑前缀都等于 $A[1,i)$ 与 $B[1,i)$ 即可，此时前缀相等，递归到第一大类求解。

至此所有情况就考虑完备了。

Code

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 2e4 + 5;
int n, K;
struct node {
    int l, r;
}Line[maxn];
int Vst[15][15], Use[15];
inline int Get_Id(int x) {
    int l = 1, r = n;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(x <= Line[mid].r) r = mid;
        else l = mid + 1;
    }
    return Line[l].l <= x && x <= Line[l].r ? l : 0;
}
inline void Calc(int x, int y, int j, int k) {
    x = Get_Id(x), y = Get_Id(y);
    Vst[j][k] = Vst[k][j] = (x && y && x == y);
}
inline void Work(int Id) {
    int pw = 1;
    for(register int i = 1; i <= K; ++i) {
        int L = Line[Id].l / pw % 10, R = Line[Id].r / pw % 10;
        int Prex = Line[Id].l / (pw * 10) * (pw * 10), Prey = Line[Id].r / (pw * 10) * (pw * 10);
        if(Prex == Prey) {
            for(register int j = L + 1; j < R; ++j)
                for(register int k = 1; k < 10; ++k)
                    if(j != k && Vst[j][k]) {
                        int Cntx = Prex + k * pw;
                        int Cnty = Prey + (k + 1) * pw - 1;
                        Calc(Cntx, Cnty, j, k);
                    }
        }
        else {
            for(register int j = L + 1; j < 10; ++j)
                for(register int k = 1; k < 10; ++k)
                    if(j != k && Vst[j][k]) {
                        int Cntx = Prex + k * pw;
                        int Cnty = Prex + (k + 1) * pw - 1;
                        Calc(Cntx, Cnty, j, k);
                    }
            for(register int j = 1; j < R; ++j)
                for(register int k = 1; k < 10; ++k)
                    if(j != k && Vst[j][k]) {
                        int Cntx = Prey + k * pw;
                        int Cnty = Prey + (k + 1) * pw - 1;
                        Calc(Cntx, Cnty, j, k);
                    }
        }
        int ax = Line[Id].l % pw, ay = pw - 1, bx = 0, by = Line[Id].r % pw;
        if(Prex == Prey && L == R) ay = by, bx = ax;
        for(register int j = 1; j < 10; ++j) {
            if(j != L && Vst[L][j]) {
                int Cntx = Prex + j * pw + ax;
                int Cnty = Prex + j * pw + ay;
                Calc(Cntx, Cnty, L, j);
            }
            if(j != R && Vst[R][j]) {
                int Cntx = Prey + j * pw + bx;
                int Cnty = Prey + j * pw + by;
                Calc(Cntx, Cnty, R, j);
            }
        }
        pw *= 10;
    }
}
signed main() {
//    freopen("laser.in", "r", stdin);
//    freopen("laser.out", "w", stdout);
    n = read(), K = read();
    int tot = 0;
    memset(Vst, 1, sizeof(Vst));
    for(register int i = 1; i <= n; ++i) {
        int l = read(), r = read();
        if(i > 1 && Line[tot].r + 1 == l) Line[tot].r = r;
        else Line[++tot].l = l, Line[tot].r = r;
    }
    n = tot;
    for(register int i = 1; i <= n; ++i) Work(i);
    for(register int i = 1; i < 10; ++i) 
        if(!Use[i]) {
            for(register int j = 1; j < 10; ++j)
                if(!Use[j] && Vst[i][j]) printf("%d", j), Use[j] = 1;
            printf("\n");
        }
    return 0;
}

Summary

很好的分类讨论题，透露出很多思想。

比如对于每一位分开考虑限制，对于一个区间分端点与中间段考虑等等。