「考试总结」ZROI-21-NOIP冲刺-TEST1 总结

发表于 分类于
ZROI-21-NOIP冲刺-TEST1 总结

#T1 数字变换

#题意简述

对于有序二元组 \((a,b)\) 及质数 \(p\)，有如下两种变化操作：

  • 变为 \((2a \bmod p,(b+p-a)\bmod p)\)；
  • 变为 \(((a+p-b)\bmod p, 2b\bmod p)\)；

现给定 \((a,b),(c,d),p\)，问 \((a,b)\) 经过多少次操作可以得到 \((c,d)\)。

有 \(p\leq10^9+7,0\leq a,b,c,d\leq p-1\)，多组数据，\(q\leq10^5\)。

#大体思路

性质 1. \((a,b)\) 可以变化为 \((c,d)\) 的充分必要条件是 \[ (a+b)\bmod p=(c+d)\bmod p. \] 这一点可以归纳证明。不妨设 \((a+b)\bmod p\) 为 \(sum\)，于是我们只需要将 \(a\) 变为 \(c\) 即可。

不难发现对于任何可以表示成如下结构 \(2^ka-sum\cdot t\) 的数，其中 \(k\in[0,w],t\in[0,2^k)\)，\(w\) 为 \(p\) 在二进制表示下的位数，都一定可以由 \(a\) 通过给定变化得到，于是我们只需要枚举 \(k\)，看 \(\dfrac{2^k-c} {sum}\) 在 \(\bmod p\) 意义下是否是二进制表示下位数小于 \(k\) 即可。

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#define ll long long

const int N = 100010;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

ll p, q, a, b, c, d, w;

ll fpow(ll x, ll y, ll c) {
    ll res = 1;
    while (y) {
        if (y & 1) (res *= x) %= c;
        y >>= 1, (x *= x) %= c;
    }
    return res;
}

int get_digit(ll x) {
    int res = 0; while (x) ++ res, x >>= 1; return res;
}

int main() {
    read(p); read(q); w = get_digit(p);
    while (q --) {
        read(a); read(b); read(c); read(d);
        if ((a + b) % p != (c + d) % p) {puts("-1"); continue;}
        ll sum = (a + b) % p, inv = fpow(sum, p - 2, p);
        for (int i = 0; i <= w; ++ i) {
            ll now = ((1ll << i) * a % p - c + p) % p * inv % p;
            int now_cnt = get_digit(now);
            if (now_cnt <= i) {printf("%lld\n", i); break;}
        }
    }
    return 0;
}

#T2 均分财产

一道挺有意思的乱搞题。

#题意简述

给定 \(n(n\leq2\times10^5)\) 个数 \(a_i\leq W=2\times10^5\)，任意删除不超过 \(k(\min(25,n-2)\leq k\leq n-2)\) 个数，要求将剩下的数分为两个和相等的可重集，给出方案。数据随机。

#大体思路

当 \(n\leq25\) 时，枚举所有子集，找到两个元素和相等的集合 \(A,B\) 即可，最终答案为 \(A'=A-A\cap B,B'=B-A\cap B\)，时间复杂度 \(O(2^n)\).

否则，将前 \(n-25\) 个元素贪心地分类，若当前元素 \(a_i\) 和 \(t<0\) 则分到 \(A\)，\(t\) 加上 \(a_i\)，否则分到 \(B\)，\(t\) 减去 \(b_i\)，这样最后得到的 \(t\in[0,W)\)。对于剩下的 \(25\) 个元素，只需要枚举所有的子集，找到两个差为 \(t\) 的即可。时间复杂度 \(O(n+2^{25})\).

对于 \(25\) 个元素的所有子集，一定有元素和小于等于 \(25W\)，而一共有 \(2^{25}\) 个子集，比 \(26W\) 大许多，由于是随机数据，几乎一定会出现两个集合元素差为 \(x(x\in[0,W))\)。

这里枚举子集的部分直接用的 \(O(3^n)\) 的爆搜+剪枝，也可以过。

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int N = 1000010;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int T, n, k, a[N], ans = -1, s[N], LMT, st[N][3];

void dfs(int t, int tot, int lsum, int rsum) {
    if (~ans) return;
    if (t == LMT + 1) {if (lsum - rsum == T) ans = 1;return;}
    if (tot < k && !(~ans)) s[t] = 0, dfs(t + 1, tot + 1, lsum, rsum);
    if (!(~ans)) s[t] = 1, dfs(t + 1, tot, lsum + a[t], rsum);
    if (!(~ans)) s[t] = 2, dfs(t + 1, tot, lsum, rsum + a[t]);
}

int main() {
    read(n); read(k); LMT = min(n, 25);
    int tot[3]; tot[0] = tot[1] = tot[2] = 0;
    for (int i = 1; i <= n; ++ i) read(a[i]);
    for (int i = 26; i <= n; ++ i){
        if (T > 0) T -= a[i], st[++ st[0][1]][1] = i;
        else T += a[i], st[++ st[0][2]][2] = i;
    }
    dfs(1, 0, 0, 0);
    if (!(~ans)) {puts("-1"); return 0;}
    for (int i = 1; i <= LMT; ++ i) ++ tot[s[i]];
    printf("%d ", tot[1] + st[0][1]);
    for (int i = 1; i <= st[0][1]; ++ i)
      printf("%d ", st[i][1]);
    for (int i = 1; i <= LMT; ++ i)
      if (s[i] == 1) printf("%d ", i);
    printf("\n%d ", tot[2] + st[0][2]);
    for (int i = 1; i <= st[0][2]; ++ i)
      printf("%d ", st[i][2]);
    for (int i = 1; i <= LMT; ++ i)
      if (s[i] == 2) printf("%d ", i);
    printf("\n"); return 0;
}

#T3 查询工资

#题意简述

给定一棵以 \(1\) 为根，有 \(n(n\leq 8\times 10^5)\) 个节点的树，给定参数 \(k(2\leq k\leq10^5)\)，每个点上有一个权值（不给出），有以下两种可行的询问方式：

  • 对于点 \(x\)，如果它的儿子个数不少于 \(k\) 个，那么可以得到它所有儿子的权值和；
  • 对于点 \(x\)，如果它的子树中的点的个数不少于 \(k+1\) 个，那么可以得到它所有的子孙（不包括自己）的权值和；

如果一个点是叶子节点，那么它可以被删去，删除操作可以做任意多次。

问在合适的删除操作后，可以通过给定的询问方式得到权值的点的个数。

多组数据，\(\sum n\leq4\times10^6\).

#大体思路

发现一个点可以被查到，那么它一定没有兄弟，否则这些点一定都一起出现，无法区分。

  1. 如果点 \(x\) 的子树大小大于等于 \(k+1\)，那么它可以用父亲子树-自己子树得到对应权值；

  2. 如果点 \(x\) 的子树大小小于等于 \(k\)，那么它和它子树中的点一定同时出现，当且仅当 \(x\) 是叶子才能被区分；

    这时求它的权值一定是其父亲的父亲的子树和减去他的所有儿子再减去它的其他儿子的子树，于是要求：

    • \(x\) 是叶子；
    • \(x\) 没有兄弟；
    • \(x\) 父亲的父亲至少有 \(k\) 个儿子；
    • \(x\) 父亲的父亲的其他子树要么是叶子，要么子树大小不小于 \(k+1\)；

考虑设计 DP，设 \(f_x\) 表示以 \(x\) 为根的子树（不包括自己）可以得到的最大数量；

对于情况 1.，如果存在一个儿子 \(v\) 的子树大小不小于 \(k+1\)，那么考虑用 \(f_v+1\) 更新；

对于情况 2.，需要有一个子树大小小于等于 \(k\) 的儿子，且 \(x\) 有大于等于 \(k\) 个儿子，可以将它删成子树大小为 \(2\)，那么可以将所有子树大小不足 \(k+1\) 的儿子删为叶子，那么此时可以用所有儿子的 \(f\) 之和加 \(1\) 进行更新。

时间复杂度为 \(O(n)\).

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#define mset(l, x) memset(l, x, sizeof(l))

const int N = 1000010;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

struct Edge{int u, v, nxt;} e[N];

int T, n, k, head[N], ecnt(1), f[N], siz[N], son[N];

inline void add_edge(int u, int v) {
    e[ecnt].u = u, e[ecnt].v = v;
    e[ecnt].nxt = head[u], head[u] = ecnt ++;
}

void get_ans(int x) {
    siz[x] = 1; son[x] = 0, f[x] = 0; int t = 0;
    for (int i = head[x]; i; i = e[i].nxt) {
        get_ans(e[i].v); f[x] += f[e[i].v];
        siz[x] += siz[e[i].v]; ++ son[x];
        if (!f[e[i].v] && siz[e[i].v] > 1) t = 1;
    }
    if (son[x] >= k && t) ++ f[x];
    for (int i = head[x]; i; i = e[i].nxt)
      if (siz[e[i].v] >= k + 1)
        f[x] = max(f[x], f[e[i].v] + 1);
}

int main() {
    read(T);
    while (T --) {
        ecnt = 1; mset(head, 0);
        read(n), read(k); int x = 0;
        for (int i = 2; i <= n; ++ i)
          read(x), add_edge(x, i);
        get_ans(1); printf("%d\n", f[1]);
    }
    return 0;
}

#T4 多项式题

诈骗题，虽然题名叫“多项式题”，但与多项式一点关系也没有。

#题意简述

给定一个长度为 \(n(n\leq2\times10^5)\) 的数串，可以划分为任意段，每一段可以看作一个十进制数，每种划分的价值是所有段上的数之积。问所有划分的积之和。

#大体思路

设 \(f_i\) 表示将前 \(i\) 位划分为若干段的价值和，根据乘法分配律可得 \[ f_i=\sum\limits_{j=0}^{i-1}val_{j+1,i}\cdot f_j, \] 直接计算时间复杂度为 \(O(n^2)\)，考虑优化。 \[ \begin{aligned} f_i=&\sum\limits_{j=0}^{i-1}(Val_i-Val_j\cdot10^{i-j})f_j\\ =&Val_i\sum\limits_{j=0}^{i-1}f_j-10^i\sum\limits_{j=0}^{i-1}10^{-j}\cdot Val_j\cdot f_j\\ =&Val_i\cdot g_{i-1}-10^i\cdot h_{i-1},\\ g_i=&g_{i-1}+f_i,\\ h_i=&h_{i-1}+10^{-i}\cdot Val_i\cdot f_i. \end{aligned} \] 其中 \(f,g,h\) 都可以线性维护，于是时间复杂度为 \(O(n)\).

由于我对逆元的了解不深，所以预处理逆元的时间复杂度为 \(O(n\log n)\)，不过正解好像可以做到整体 \(O(n)\).

群里某位大佬的思路：

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define ll long long

const int N = 1000010;
const ll MOD = 998244353;

char s[N]; int n; ll val[N], b[N], inv[N], f[N], h[N], g[N];

ll fpow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) (res *= x) %= MOD;
        y >>= 1, (x *= x) %= MOD;
    }
    return res;
}

int main() {
    scanf("%d%s", &n, s); b[0] = f[0] = g[0] = 1, val[0] = 0;
    for (int i = 1; i <= n; ++ i)
      val[i] = (val[i - 1] * 10 % MOD + s[i - 1] - '0') % MOD;
    for (int i = 1; i <= n; ++ i) b[i] = b[i - 1] * 10 % MOD;
    for (int i = 0; i <= n; ++ i) inv[i] = fpow(b[i], MOD - 2);
    for (int i = 1; i <= n; ++ i) {
        f[i] = (val[i] * g[i - 1] % MOD - b[i] * h[i - 1] % MOD + MOD) % MOD;
        g[i] = (g[i - 1] + f[i]) % MOD;
        h[i] = (h[i - 1] + val[i] * f[i] % MOD * inv[i] % MOD) % MOD;
    }
    printf("%lld", f[n]); return 0;
}