第十四届蓝桥杯大赛软件赛省赛（C/C++ 大学A组）_十四届蓝桥杯幸运数字

---

试题 A: 幸运数

本题总分：$5$ 分

---

【问题描述】

  小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如 $2314$ 是一个幸运数字，因为它有 $4$ 个数位，并且 $2+3=1+4$。现在请你帮他计算从 $1$ 至 $100000000$ 之间共有多少个不同的幸运数字。

【答案提交】

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

---

4430091

---

根据插板法我们可知整数$n$拆分成$k$个非负部分的方案数为$C_{n+k-1}^{k-1}$，有下界，$j$个部分下界为$x$时方案数为$C_{n+k-1-jx}^{k-1}$，那么根据容斥原理可知存在一个部分大于$x$的拆分方案数为${\sum }_{i=1}^k(-1{)}^{i-1}{C}_{n+i-1-i(x+1)}^{i-1}$，记$p(n,k)$为不存在部分大于$x$的拆分方案数，有$$p(n,k)=C_{n+k-1}^{k-1}-\sum _{i=1}^k(-1{)}^{i-1}{C}_k^i{C}_{n+i-1-i(x+1)}^{i-1}=\sum _{i=0}^k(-1{)}^i{C}_k^i{C}_{n+i-1-i(x+1)}^{i-1}.$$考虑到幸运数字数位个数为偶，即不能有前缀$0$，于是考虑将$p(n-1,k)$看作最高位数字大于$1$的方案数，但这样方案数里就包含了高位数字为$10$的方案，显然不合法，所以减去不合法部分$p(n-10,k-1)$，最终答案为$$\sum _{k=1}^4\sum _{n=1}^{9k}(p(n-1,k)-p(n-10,k-1))\cdot p(n,k).$$

#include <stdio.h>

long long C(int n, int m) {
    if (m > n || n < 0) return 0;
    long long C = 1;
    for (int i = 0; i < m; ++i)
        C = C * (n - i) / (i + 1);
    return C;
}

long long p(int n, int k) {
    long long p = 0;
    for (int i = 0, sign = 1; i <= k; ++i, sign = -sign)
        p += sign * C(k, i) * C(n + k - 1 - i * 10, k - 1);
    return p;
}

int main() {
    long long ans = 0;
    for (int k = 1; k <= 4; ++k)
        for (int n = 1; n <= 9 * k; ++n)
            ans += (p(n - 1, k) - p(n - 10, k - 1)) * p(n, k);
    printf("%lld", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

优雅，永不过时

但我也数次强调过，在比赛过程中，编写这种程序的性价比是极低的，不如写个暴力程序开个线程让它自己去跑出答案。

#include <stdio.h>

int ans, buffer[9];

int main() {
    for (int k = 1; k <= 100000000; ++k) {
        int g = 0, n = 0, m = k;
        for (; m; m /= 10) buffer[n++] = m % 10;
        if (n & 1) continue;
        for (int i = 0; i < n >> 1; ++i) g += buffer[i];
        for (int i = n >> 1; i < n; ++i) g -= buffer[i];
        if (!g) ++ans;
    }
    printf("%d", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

试题 B: 有奖问答

本题总分：$5$ 分

---

【问题描述】

  小蓝正在参与一个现场问答的节目。活动中一共有 $30$ 道题目，每题只有答对和答错两种情况，每答对一题得 $10$ 分，答错一题分数归零。
  小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要 $100$ 分，所以到达 $100$ 分时小蓝会直接停止答题。
  已知小蓝最终实际获得了 $70$ 分对应的奖项，请问小蓝所有可能的答题情况有多少种?

【答案提交】

  这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

---

8335366

---

记$d{p}_{i,j}$为第$i$个问题小蓝获得$10j$分的方案数，显然$d{p}_{0,0}=1$，对于问题$i$，如何小蓝回答错误，那么$d{p}_{i,0}={\sum }_{j=0}^{9}d{p}_{i-1,j}$，因为当小明有$10\cdot 10$分时问答结束故不可转移，当小明回答对时则$d{p}_{i,j}=d{p}_{i-1,j-1}$，最终，答案为${\sum }_{i=1}^{30}d{p}_{i,7}$。

#include <stdio.h>

int ans = 0, dp[11] = { 1 };

int main() {
    for (int i = 1; i <= 30; ++i) {
        int loss = 0;
        for (int j = 10; j; --j) {
            loss += dp[j - 1];
            dp[j] = dp[j - 1];
        }
        dp[0] = loss;
        ans += dp[7];
    }
    printf("%d", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

做了个滚动数组，当然也可以暴搜。

#include <stdio.h>

int n = 30, ans = 0, target = 70;

void dfs(int depth, int score) {
    if (depth > n) return;
    if (score == 100) return;
    if (score == target) ++ans;
    dfs(depth + 1, score + 10);
    dfs(depth + 1, 0);
}

int main() {
    printf("%d", (dfs(0, 0), ans));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

试题 C: 平方差

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$10$ 分

---

【问题描述】

  给定 $L,R$，问 $L\le x\le R$ 中有多少个数 $x$ 满足存在整数 $y,z$ 使得 $x=y^2-z^2$。

【输入格式】

  输入一行包含两个整数 L, R，用一个空格分隔。

【输出格式】

  输出一行包含一个整数满足题目给定条件的 $x$ 的数量。

【样例输入】

1 5
1

【样例输出】

4
1

【样例说明】

  $1=1^2-0^2；$
  $3=2^2-1^2；$
  $4=2^2-0^2；$
  $5=3^2-2^2。$

【评测用例规模与约定】

  对于 $40\%$ 的评测用例，$LR\le 5000$；
  对于所有评测用例，$1\le L\le R\le 10^9$。

---

基本数论

---

不知道基不基本，反正我老民科没见过，顺手推推。
对偶数 $a$ ，平方数都可以表示成 $2^2(\frac{a}{2}{)}^2$，即 $a^2\equiv 0(\mathrm{mod}4)$；对奇数 $b$ ，平方数都可以表示成 $(b-1{)}^2+2b-1$，即 $b^2\equiv 1(\mathrm{mod}4)$；
那么就奇偶性而言 $a-a、b-a、a-b$ 的结果为 $0、1、3(\mathrm{mod}4)$，容易得知 $x$ 不可能被分解成 $4c+2$ 的形式。那么 4 c + k , 0 ≤ 4 c + k ≤ R , k ∈ { 0 , 1 , 3 } 4c+k,0\leq 4c+k\leq R,k\in\{0,1,3\} 4c+k,0≤4c+k≤R,k∈{0,1,3} 一定可以被 $y,z,0\le z<y\le R$ 表示吗？
首先将 $4c+k$ 划分为 $2d-1$ 和 $4c$。对于正奇数集 $2d-1$，容易构造 $y=d,z=d-1,x=(y-z)(y+z)=2d-1$，$y^2-z^2$ 可表不大于 $2R-1$ 的正奇数。对于 $4c$，我们令 $y=c,z=c-2$ 则 $x=(y-z)(y+z)=4c-4$，$y^2-z^2$ 可表不大于 $4R-4$ 的 $4$ 的倍数。综上 $x\ne 4c+2$ 时一定可用被 $y^2-z^2$ 表示。

#include <stdio.h>

int L, R;

int main() {
    scanf("%d %d", &L, &R);
    printf("%d",
            R - (R + 2) / 4
            - (L - 1 - (L - 1 + 2) / 4));
}
1
2
3
4
5
6
7
8
9
10

---

试题 D: 更小的数

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$10$ 分

---

【问题描述】

  小蓝有一个长度均为 $n$ 且仅由数字字符 $0\sim 9$ 组成的字符串，下标从 $0$ 到 $n-1$，你可以将其视作是一个具有 $n$ 位的十进制数字 $num$，小蓝可以从 $num$ 中选出一段连续的子串并将子串进行反转，最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 $nu{m}_{new}$ 满足条件 $nu{m}_{new}<num$，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 $num$ 中的位置不完全相同我们就视作是不同的方案。
  注意，我们允许前导零的存在，即数字的最高位可以是 $0$，这是合法的。

【输入格式】

  输入一行包含一个长度为 $n$ 的字符串表示 $num$（仅包含数字字符 $0\sim 9$），从左至右下标依次为 $0\sim n-1$。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

210102
1

【样例输出】

8
1

【样例说明】

  一共有 $8$ 种不同的方案：
  $1）$所选择的子串下标为 $0\sim 1$，反转后的 $nu{m}_{new}=120102<210102$；
  $2）$所选择的子串下标为 $0\sim 2$，反转后的 $nu{m}_{new}=012102<210102$；
  $3）$所选择的子串下标为 $0\sim 3$，反转后的 $nu{m}_{new}=101202<210102$；
  $4）$所选择的子串下标为 $0\sim 4$，反转后的 $nu{m}_{new}=010122<210102$；
  $5）$所选择的子串下标为 $0\sim 5$，反转后的 $nu{m}_{new}=201012<210102$；
  $6）$所选择的子串下标为 $1\sim 2$，反转后的 $nu{m}_{new}=201102<210102$；
  $7）$所选择的子串下标为 $1\sim 4$，反转后的 $nu{m}_{new}=201012<210102$；
  $8）$所选择的子串下标为 $3\sim 4$，反转后的 $nu{m}_{new}=210012<210102$；

【评测用例规模与约定】

  对于 $20\%$ 的评测用例，$1\le n\le 100$；
  对于 $40\%$ 的评测用例，$1\le n\le 1000$；
  对于所有评测用例，$1\le n\le 5000$。

---

$[l,r]$ 的翻转可以由 $(l,r)$ 在常数复杂度意义下转移过来，具体地说：
记 $num[l,r]$ 为下标 $l\sim r$ 构成的子串的数值，$inv[l,r]$ 为下标 $l\sim r$ 构成的子串翻转后的数值，则 $inv[l,r]=num[r]\times 10^{r-l}+inv(l,r)+num[l]$，容易发现 $[l,r]$ 的翻转与原串的大小关系也可以由 $(l,r)$ 在常数复杂度意义下转移过来：
当 $num[r]>num[l]$ 时，$num[r]\ne 0$ 则有 $num[r]\times 10^{r-l}>num[l,r]$ 即 $inv[l,r]>num[l,r]$；
当 $num[r]=num[l]$ 时，则有 $|inv[l,r]>num[l,r]|=|inv(l,r)>num(l,r)|$，当 $E$ 成立时，$|E|=1$，否则等于 $0$；
当 $num[r]<num[l]$ 时，依 $num[r]>num[l]$ 的判别过程，有 $inv[l,r]<num[l,r]$；
于是我们可以枚举每个元素，累加依该元素为中位元素的子序列对答案的贡献。

#include <stdio.h>
#include <string.h>

char num[5010]{1};

int main() {
    gets(num + 1);
    int n = strlen(num), ans = 0;
    for (int k = 2; k < n; ++k)
        for (int i = k, j = k, e1 = 0, e2 = 0; i > 0 && j < n; --i, ++j) {
            if (num[j] != num[i - 1]) e1 = num[j] < num[i - 1];
            if (num[j] != num[i]) e2 = num[j] < num[i];
            ans += e1 + e2;
        }
    printf("%d", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

试题 E: 颜色平衡树

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$15$ 分

---

【问题描述】

  给定一棵树，结点由 $1$ 至 $n$ 编号，其中结点 $1$ 是树根。树的每个点有一个颜色 $C_i$。
  如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。
  求出这棵树中有多少个子树是颜色平衡树。

【输入格式】

  输入的第一行包含一个整数 $n$，表示树的结点数。
  接下来 $n$ 行，每行包含两个整数 $C_i,F_i$，用一个空格分隔，表示第 $i$ 个结点的颜色和父亲结点编号。
  特别地，输入数据保证 $F_1$ 为 $0$ ，也即 $1$ 号点没有父亲结点。保证输入数据是一棵树。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

6
2 0
2 1
1 2
3 3
3 4
1 4
1
2
3
4
5
6
7

【样例输出】

4
1

【样例说明】

  编号为 $1,3,5,6$ 的 $4$ 个结点对应的子树为颜色平衡树。

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$n\le 200，C_i\le 200$；
  对于 $60\%$ 的评测用例，$n\le 5000，C_i\le 5000$；
  对于所有评测用例，$1\le n\le 200000，1\le C_i\le 200000，0\le F_i<i$。

---

启发式合并模板题

#include <stdio.h>
#include <set>

const int N = 200005;

int n, f, ans, cs[N], col[N], head[N], next[N];

int dfn = 0, ld[N], rd[N], dtv[N], siz[N], son[N];

std::multiset<int> sc;

inline void add(int i) {
    if (cs[col[i]]) sc.erase(sc.find(cs[col[i]]));
    sc.insert(++cs[col[i]]);
}

inline void add(int l, int r) { for (; l <= r; ++l) add(dtv[l]); }

inline void del(int l, int r) {
    for (; l <= r; ++l) {
        sc.erase(sc.find(cs[col[dtv[l]]]));
        if (--cs[col[dtv[l]]]) sc.insert(cs[col[dtv[l]]]);
    }
}

void dfs0(int u) {
    ld[u] = ++dfn;
    dtv[dfn] = u;
    siz[u] = 1;
    for (int v = head[u]; v; v = next[v]) {
        dfs0(v);
        siz[u] += siz[v];
        if (!son[u] || siz[son[u]] < siz[v]) son[u] = v;
    }
    rd[u] = dfn;
}

void dfs1(int u, bool keep) {
    for (int v = head[u]; v; v = next[v])
        if (v != son[u]) dfs1(v, 0);
    if (son[u]) dfs1(son[u], 1);
    for (int v = head[u]; v; v = next[v])
        if (v != son[u]) add(ld[v], rd[v]);
    add(u);
    if (*sc.begin() == *sc.rbegin()) ++ans;
    if (!keep) del(ld[u], rd[u]);
}

int main() {
    scanf("%d %d %d", &n, &col[1], &f);
    for (int i = 2; i <= n; ++i)
        scanf("%d %d", &col[i], &f), next[i] = head[f], head[f] = i;
    dfs0(1);
    dfs1(1, 0);
    printf("%d", ans);
}
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
45
46
47
48
49
50
51
52
53
54
55
56

不过观察到树根一定为 $1$ 且 $F_i<i$，于是可用链式前向星构建有向图来表示数，减小程序的运行常数，毕竟 $n$ 在 $2\times 10^5$ 常数大了很有可能会爆栈或者超一点点时。

---

试题 F: 买瓜

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$15$ 分

---

【问题描述】

  小蓝正在一个瓜摊上买瓜。瓜摊上共有 $n$ 个瓜，每个瓜的重量为 $A_i$。
  小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。
  小蓝希望买到的瓜的重量的和恰好为 $m$。
  请问小蓝至少要劈多少个瓜才能买到重量恰好为 $m$ 的瓜。如果无论怎样小蓝都无法得到总重恰好为 $m$ 的瓜，请输出 $-1$。

【输入格式】

  输入的第一行包含两个整数 $n,m$，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。
  第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

3 10
1 3 13
1
2

【样例输出】

2
1

【评测用例规模与约定】

  对于 $20\%$ 的评测用例，$\sum n\le 10$；
  对于 $60\%$ 的评测用例，$\sum n\le 20$；
  对于所有评测用例，$1\le n\le 30，1\le A_i\le 10^9，1\le m\le 10^9$。

---

折半枚举，内存和时间都挺紧张的，就不开map转用 二分+布隆过滤器，交了发到 dotcpp 上去，效果好像还行。
复杂度的话一半的枚举是 $O(3^{\frac{n}{2}})$，另一半要二分查找所以是 $O(\frac{n}{2}{3}^{\frac{n}{2}}\log 3)$。

#include <stdio.h>
#include <algorithm>
#include <bitset>

const int HALF = 14348907;

int n, m, h, H, ans, a[30];

std::bitset<400000009> bloom;

std::pair<int, int> half[HALF];

void make(int i, int w, int k) {
    if (i < 0) half[H++] = {w, k}, bloom[w % 400000009] = 1;
    else {
        make(i - 1, w, k);
        if (w <= m - a[i])
            make(i - 1, w + a[i], k + 1);
        if (w <= m - (a[i] << 1))
            make(i - 1, w + (a[i] << 1), k);
    }
}

void dfs(int i, int w, int k) {
    if (i == n) {
        if (bloom[w % 400000009]) {
            int l = 0, r = h;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (half[mid].first < w) l = mid + 1;
                else r = mid;
            }
            if (half[l].first == w)
                ans = std::min(ans, half[l].second + k);
        }
    } else {
        dfs(i + 1, w, k);
        if (w >= a[i])
            dfs(i + 1, w - a[i], k + 1);
        if (w >= (a[i] << 1))
            dfs(i + 1, w - (a[i] << 1), k);
    }
}

int main() {
    scanf("%d %d", &n, &m), m <<= 1, ans = n << 1;
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    std::random_shuffle(a, a + n);
    make(n / 2, 0, 0);
    std::sort(half, half + H);
    for (int i = 1; i < H; ++i)
        if (half[i].first != half[h].first) half[++h] = half[i];
    dfs(n / 2 + 1, m, 0);
    printf("%d", ans > n ? -1 : ans);
}
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
45
46
47
48
49
50
51
52
53
54
55

---

试题 G: 网络稳定性

时间限制: $1.5\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$20$ 分

---

【问题描述】

  有一个局域网，由 $n$ 个设备和 $m$ 条物理连接组成，第 $i$ 条连接的稳定性为 $w_i$。
  对于从设备 $A$ 到设备 $B$ 的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个。
  我们记设备 $A$ 到设备 $B$ 之间通信的稳定性为 $A$ 至 $B$ 的所有可行路径的稳定性中最高的那一条。
  给定局域网中的设备的物理连接情况，求出若干组设备 $x_i$ 和 $y_i$ 之间的通信稳定性。如果两台设备之间不存在任何路径，请输出 $-1$。

【输入格式】

  输入的第一行包含三个整数 $n,m,q$，分别表示设备数、物理连接数和询问数。
  接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$，分别表示 $u_i$ 和 $v_i$ 之间有一条稳定性为 $w_i$ 的物理连接。
  接下来 $q$ 行，每行包含两个整数 $x_i,y_i$，表示查询 $x_i$ 和 $y_i$ 之间的通信稳定性。

【输出格式】

  输出 $q$ 行，每行包含一个整数依次表示每个询问的答案。

【样例输入】

5 4 3
1 2 5
2 3 6
3 4 1
1 4 3
1 5
2 4
1 3
1
2
3
4
5
6
7
8

【样例输出】

-1
3
5
1
2
3

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$n,q\le 500，m\le 1000$；
  对于 $60\%$ 的评测用例，$n,q\le 5000，m\le 10000$；
  对于所有评测用例，$2\le n,q\le 10^5，1\le m\le 3\times 10^5，1\le u_i,v_i,x_i,y_i\le n，1\le w_i\le 10^6，u_i\ne v_i，x_i,\ne y_i$。

---

最大生成树模板，通过 $\mathrm{Kruskal}$ 算法易知最新应加入生成树的边 $u\stackrel{w}{\leftrightarrow }v$ 是权重最小的边，考虑新建一个节点 $x$，将 $x\stackrel{w}{\leftrightarrow }u、x\stackrel{w}{\leftrightarrow }v$ 加入生成树，容易原先森林里连通的量的通信稳定性显然不变，最近连通的量根据最小生成树的最优性它们的稳定性一定为 $w$，于是我们令 $x$ 为树根，并将 $w$ 上浮到入点，重复这个过程，最终可用看到所有节点对它们的通信稳定度为它们的最近公共祖先的权重。

#include <stdio.h>
#include <algorithm>

const int N = 100005;

struct edge {
    int u, v, w;
    inline bool operator<(edge e) { return w > e.w; };
} edges[3 * N];

int head[N << 1], query[N], next[N << 2], ver[N << 2], wei[N << 1];

int n, m, p, q, cur, ans[N], linked[N << 1], w[N << 1], buffer[N << 1];

int find(int x) { return x == linked[x] ? x : (linked[x] = find(linked[x])); }

bool vis[N << 1];

void dfs(int u) {
    linked[u] = u;
    buffer[p++] = u;
    vis[u] = 1;
    for (int i = head[u]; i; i = next[i])
        dfs(ver[i]), linked[ver[i]] = u;
    for (int i = query[u]; i; i = next[i])
        if (vis[ver[i]]) ans[wei[i]] = w[find(ver[i])];
}

int main() {
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 0; i < m; ++i)
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    for (int i = 0, x, y; i < q; ++i) {
        scanf("%d %d", &x, &y);
        next[++cur] = query[x], query[x] = cur, ver[cur] = y, wei[cur] = i;
        next[++cur] = query[y], query[y] = cur, ver[cur] = x, wei[cur] = i;
    }
    std::sort(edges, edges + m);
    for (int i = (n << 1) - 1; i; --i) linked[i] = i;
    for (int i = 0, x = n; i < m; ++i) {
        int u = find(edges[i].u), v = find(edges[i].v);
        if (u == v) continue;
        w[++x] = edges[i].w;
        linked[u] = linked[v] = x;
        next[++cur] = head[x], head[x] = cur, ver[cur] = u;
        next[++cur] = head[x], head[x] = cur, ver[cur] = v;
    }
    for (int i = (n << 1) - 1; i; --i, p = 0) {
        if (linked[i] == i) dfs(i);
        while (p--) vis[buffer[p]] = 0;
    }
    for (int i = 0; i < q; ++i)
        printf("%d\n", ans[i] ? ans[i] : -1);
}
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
45
46
47
48
49
50
51
52
53
54

$\mathrm{tarjan}$！永远滴神

---

试题 H: 异或和之和

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$20$ 分

---

【问题描述】

  给定一个数组 $A_i$，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 $1\le L\le R\le n$ 的 $L,R$，求出数组中第 $L$ 至第 $R$ 个元素的异或和。然后输出每组 $L,R$ 得到的结果加起来的值。

【输入格式】

  输入的第一行包含一个整数 $n$。
  第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔。

【输出格式】

  输出一行包含一个整数表示答案。

【样例输入】

5
1 2 3 4 5
1
2

【样例输出】

39
1

【评测用例规模与约定】

  对于 $30\%$ 的评测用例，$n\le 300$；
  对于 $60\%$ 的评测用例，$n\le 5000$；
  对于所有评测用例，$1\le n\le 10^5，0\le A_i\le 2^{20}$。

---

令 A i = ∑ k = 0 20 a i , k 2 k , a k ∈ { 0 , 1 } A_i = \sum_{k=0}^{20}a_{i,k}2^k,a_k\in\{0,1\} Ai​=∑k=020​ai,k​2k,ak​∈{0,1}，由于按位运算不进位的特性，则 ${\sum }_{\begin{array}{c}1\le L\le R\le n\end{array}}{⨁}_{i=L}^R{A}_i={\sum }_{k=0}^{20}{\sum }_{\begin{array}{c}1\le L\le R\le n\end{array}}{⨁}_{i=L}^R{a}_{i,k}$，而 $a_{L,k}\oplus a_{L+1,k}\oplus \cdots \oplus a_{R,k}$ 当 $a_{i,k}$ 奇数个非零时为 $2^k$，否则为零，于是枚举每一个 $a_{i,k}$ 将其非零值出现次序的奇偶划分累加，并根据之前累加结果计算出以当前元素为结尾的子序列对答案的贡献。
可以说老模板了。

#include <stdio.h>

int n, a[100000];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    long long ans = 0;
    for (int k = 0; k <= 20; ++k) {
        int cnt[]{ 1, 0 }, j = 0;
        long long sum = 0;
        for (int i = 0; i < n; ++i) {
            j ^= (a[i] >> k) & 1;
            sum += cnt[j ^ 1];
            cnt[j]++;
        }
        ans += sum << k;
    }
    printf("%lld", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

试题  I: 像素放置

时间限制: $1.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$25$ 分

---

【问题描述】

  小蓝最近迷上了一款名为《像素放置》的游戏，游戏在一个 n × m 的网格棋盘上进行，棋盘含有 n 行，每行包含 m 个方格。玩家的任务就是需要对这 n × m 个方格进行像素填充，填充颜色只有黑色或白色两种。有些方格中会出现一个整数数字 x(0 ≤ x ≤ 9)，这表示当前方格加上周围八个方向上相邻的方格（分别是上方、下方、左方、右方、左上方、右上方、左下方、右下方）共九个方格内有且仅有 x 个方格需要用黑色填充。
  玩家需要在满足所有数字约束下对网格进行像素填充，请你帮助小蓝来完成。题目保证所有数据都有解并且解是唯一的。

【输入格式】

  输入的第一行包含两个整数 n, m，用一个空格分隔，表示棋盘大小。
  接下来 n 行，每行包含 m 个字符，表示棋盘布局。字符可能是数字 0 ∼ 9，这表示网格上的数字；字符还有可能是下划线（ASCII 码为 95 ），表示一个不带有数字的普通网格。

【输出格式】

  输出 n 行，每行包含 m 个字符，表示答案。如果网格填充白色则用字符 0 表示，如果网格填充黑色则用字符 1 表示。

【样例输入】

6 8
_1__5_1_
1_4__42_
3__6__5_
___56___
_688___4
_____6__
1
2
3
4
5
6
7

【样例输出】

00011000
00111100
01000010
11111111
01011110
01111110
1
2
3
4
5
6

【样例说明】

     上图左是样例数据对应的棋盘布局，上图右是此局游戏的解。例如第 3 行第 1 列处的方格中有一个数字 3 ，它周围有且仅有 3 个格子被黑色填充，分别是第 3 行第 2 列、第 4 行第 1 列和第 4 行第 2 列的方格。

【评测用例规模与约定】

  对于 $50\%$ 的评测用例，$1\le n,m\le 5$；
  对于所有评测用例，$1\le n,m\le 10$。

---

状压DP

---

轮廓线$\mathrm{DP}$，定义 $d{p}_{i,j,s}$ 为 $(i,j)$ 格前 $2(m+1)$ 格排列方案为 $s$ 时是否存在 $(i-1,j-1)$ 绝对合法的方案。

可以看到，若是用 $01$ 来表示 $s$，则 $s$ 的 $0,1,m-1,m,m+1,2m-1,2m,2m+1$ 数位之和，加上目前 $(i,j)$ 放置与否与原方格中 $(i-1,j-1)$ 的数值相比较，就能判断 $(i-1,j-1)$ 的合法性，事实上还可以加一步对 $(i-1,j-1)$ 后面的方格的违法校验，但这样常数变大时间复杂度上界不变，没必要。
不过这样一共存在 j ∈ { 1 , 2 , m } j\in\{1,2,m\} j∈{1,2,m} 三种特殊情况。

     

对于第一种情况我们直接转移状态，对于第二种情况我们特殊计算左上角方格是否合法，对于最后一种情况我们在一行处理完毕后做一次矫正，复杂度在$O(nm{2}^{2m+2})$，感觉有的够呛，这场题目的时间都开的很极限。

#include <stdio.h>
#include <bitset>

char grid[11][12], *mp, mp8[1 << 22], mp5[1 << 22], last[11];

std::bitset<1 << 22> dp[101]{1};

bool ans[11][11];

int n, m;

inline int get(int n, int i) { return (n >> i) & 1; }

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", grid[i] + 1);
        for (int j = 1; j <= m; ++j)
            if (grid[i][j] != '_') grid[i][j] -= '0';
            else grid[i][j] = 0;
    }
    int pm2 = 1 << (2 * m + 2), mod = pm2 - 1;
    for (int i = 0; i < pm2; ++i) {
        mp5[i] = get(i, m - 1) + get(i, 2 * m - 1);
        if (m > 1) mp5[i] += get(i, 0) + get(i, m) + get(i, 2 * m);
        mp8[i] = mp5[i] + get(i, 1) + get(i, m + 1) + get(i, 2 * m + 1);
    }
    int now = 0, old;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            old = now, ++now;
            mp = j != 2 ? mp8 : mp5;
            for (int s = 0; s < pm2; ++s) dp[now][s] = 0;
            if (grid[i - 1][j - 1]) {
                char temp = grid[i - 1][j - 1], temp1 = temp - 1;
                for (int s = 0; s < pm2; ++s)
                    if (dp[old][s]) {
                        if (temp == mp[s]) dp[now][(s << 1) & mod] = 1;
                        else if (temp1 == mp[s]) dp[now][((s << 1) | 1) & mod] = 1;
                    }
            } else {
                for (int s = 0; s < pm2; ++s)
                    if (dp[old][s]) dp[now][(s << 1) & mod] = dp[now][((s << 1) | 1) & mod] = 1;
            }
        }
        for (int s = 0; s < pm2; ++s)
            if (dp[now][s] && grid[i - 1][m]) dp[now][s] = grid[i - 1][m] == mp5[s >> 1] + (s & 1);
    }
    int s = 0;
    for (; s < pm2;++s)
        if (dp[now][s]) {
            bool flag = 1;
            for (int i = 1; i <= m; ++i) last[i] = get(s, m - i) + get(s, 2 * m - i);
            for (int i = 1; i <= m; ++i)
                if (grid[n][i] && last[i - 1] + last[i] + last[i + 1] != grid[n][i]) {
                    flag = 0;
                    break;
                }
            if (flag) break;
        }
    for (int i = n; i; --i)
        for (int j = m; j; --j) {
            mp = j != 2 ? mp8 : mp5;
            ans[i][j] = s & 1;
            --now, s = s >> 1;
            if ((grid[i - 1][j - 1] && mp[s] + ans[i][j] != grid[i - 1][j - 1]) || !dp[now][s]) s |= pm2 >> 1;
        }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) putchar('0' ^ ans[i][j]);
        putchar('\n');
    }
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

改成对应的记忆化搜索可以通过民间数据，推测原因在于唯一解的数据很难捏，总之是道很粪的题。

#include <stdio.h>
#include <bitset>

char grid[11][12], mp8[1 << 22], mp5[1 << 22], last[11];

std::bitset<1 << 22> mark[11][11];

int n, m, mod, ans[11];

inline int get(int n, int i) { return (n >> i) & 1; }

bool dfs(int i, int j, int s) {
    if (i == n + 1) {
        for (int i = 1; i <= m; ++i) last[i] = get(s, m - i) + get(s, 2 * m - i);
        for (int i = 1; i <= m; ++i)
            if (grid[n][i] && last[i - 1] + last[i] + last[i + 1] != grid[n][i]) return 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) putchar('0' ^ get(ans[i], m - j));
            putchar('\n');
        }
        return 1;
    }
    if (mark[i][j][s]) return 0;
    mark[i][j][s] = 1;
    for (int b : {0, 1}) {
        if (grid[i - 1][j - 1] && grid[i - 1][j - 1] != (j != 2 ? mp8 : mp5)[s] + b) continue;
        if (j < m) {
            if (dfs(i, j + 1, ((s << 1) | b) & mod)) return 1;
        } else {
            if (grid[i - 1][m] && grid[i - 1][m] != mp5[s] + b) continue;
            if (dfs(i + 1, 1, ans[i] = ((s << 1) | b) & mod)) return 1;
        }
    }
    return 0;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", grid[i] + 1);
        for (int j = 1; j <= m; ++j) {
            if (grid[i][j] != '_') grid[i][j] -= '0';
            else grid[i][j] = 0;
        }
    }
    mod = (1 << (2 * m + 2)) - 1;
    for (int i = 0; i <= mod; ++i) {
        mp5[i] = get(i, m - 1) + get(i, 2 * m - 1);
        if (m > 1) mp5[i] += get(i, 0) + get(i, m) + get(i, 2 * m);
        mp8[i] = mp5[i] + get(i, 1) + get(i, m + 1) + get(i, 2 * m + 1);
    }
    dfs(1, 1, 0);
}
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
45
46
47
48
49
50
51
52
53

---

试题 J: 翻转硬币

时间限制: $3.0\mathrm{s}$ 内存限制: $256.0\mathrm{MB}$ 本题总分：$25$ 分

---

【问题描述】

  给定 n 个按顺序摆好的硬币，一开始只有第 1 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 i 并将所有满足 j mod i = 0 的位置 j 的硬币翻转。
  求最少需要多少次操作可以让所有硬币都朝上。

【输入格式】

  输入一行包含一个整数 n 。

【输出格式】

  输出一行包含一个整数表示最少需要的操作次数。

【样例输入 1】

7
1

【样例输出 1】

6
1

【样例输入 2】

1131796
1

【样例输出 2】

688042
1

【评测用例规模与约定】

  对于 30% 的评测用例，$n\le 5\times 10^6$；
  对于 70% 的评测用例，$n\le 10^9$；
  对于所有评测用例，$1\le n\le 10^{18}$。

---

因为无法再取到 $1$ 以外令 $1\mathrm{mod}i=0$ 的值，所有我们一开始翻转 $i=1$ 及所有硬币，同样的无法取到 $2$ 以外令 $2\mathrm{mod}i=0$ 的值，第二步我们翻转 $i=2$ 即所有 $2$ 的倍数，重复这个过程，容易发现仅当 $\mu (i)\ne 0$ 时需要翻转。
稍微解释一下算了，假设 $i$ 不存在平方因子，即不存在整数 $a\ge 2$，满足 $a^2|i$，则 $i$ 在算数基本定理拆解下指数全为 $1$，$i={\prod }_{j=1}^s{p}_j$。当 $s=1$ 时 $i$ 显然需要翻转，因为第 $i$ 个硬币是朝下的；当 $s=2$ 时 $i$ 同样也需要翻转，因为 $i=p_1、p_2$ 翻转后，$p_1{p}_2$ 依然朝下；当 $s=3$ 时 $i=p_1、p_2、p_3、p_1{p}_2、p_1{p}_3、p_2{p}_3$ 翻转，翻转 $6$ 次 $p_1{p}_2{p}_3$ 朝下，需要翻转；也就是当 $i$ 不存在平方因子在遍历到它前它会被翻转 ${\sum }_{i=1}^s{C}_s^i=2^s-2$ 次为偶数次，所以它一定要被翻转，而当 $i$ 存在平凡因子时，它会在前述基础上再翻上 ${\prod }_{j=1}^s{p}_j$ 即 $2^s-1$ 次为奇数次，故无需翻转。
于是我们可以进一步解读题意：
给定正整数 $n$，求 $\sum _{i=0}^n{\mu }^2(i)$。
不过 $n$ 很大，直接通过杜教筛求解无法通过全部评测用例，于是记 $S(n)$ 为 $4\sim n$ 中包含平方因子的数的个数，则答案为 $n-S(n)$，考虑容斥有：$$S(n)=\sum _{k=2}^{\lfloor \sqrt{n}\rfloor }(-1{)}^k\sum _{2\le d_1<d2<\cdots <d_{k-1}\le \lfloor \sqrt{n}\rfloor }\lfloor \frac{n}{\prod d_i^2}\rfloor$$整理得：$$S(n)=\sum _{d=2}^{\lfloor \sqrt{n}\rfloor }-\mu (d)\lfloor \frac{n}{d^2}\rfloor$$答案可变式为：$$n-S(n)=1\lfloor \frac{n}{1^2}\rfloor -S(n)=\sum _{d=1}^{\lfloor \sqrt{n}\rfloor }\mu (d)\lfloor \frac{n}{d^2}\rfloor$$预处理 $\mu$ 长 $(\sqrt{n}{)}^{2/3}$ 的前缀和，剩下的部分通过数论分块+杜教筛求解，$n/d^2,d>(\sqrt{n}{)}^{2/3}$ 一共有 $n^{1/3}$ 种不同的取值，在缓存了杜教筛的结果的情况下复杂度亚于 $O(\sqrt{n})$，但亚多少这个均摊就很难算了。

#include <stdio.h>
#include <unordered_map>
#include <math.h>

const int N = 1.5e7 + 10;

int p[N], mu[N + 1]{0, 1};

bool mark[N + 1];

std::unordered_map<int, long long> S;

long long djs(int n) {
    if (n <= N) return mu[n];
    if (S[n]) return S[n];
    long long sum = 1;
    for (long long l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        sum -= djs(n / l) * (r - l + 1);
    }
    return S[n] = sum;
}

int main() {
    for (int k = 2, m = 0; k <= N; ++k) {
        if (!mark[k])
            p[m++] = k, mu[k] = -1;
        for (int i = 0; i < m; ++i) {
            long long kp = (long long) k * p[i];
            if (kp >= N) break;
            mark[kp] = 1;
            if (k % p[i]) mu[kp] = -mu[k];
            else break;
        }
    }
    long long n, ans = 0;
    scanf("%lld", &n);
    long long l = 1, sn = sqrt(n + 0.5);
    for (long long high = sn > N ? N : sn; l <= high; ++l) {
        ans += mu[l] * (n / l / l);
        mu[l] += mu[l - 1];
    }
    for (long long r; l <= sn; l = r + 1) {
        long long ndd = n / l / l;
        r = sqrt(n / ndd + 0.5);
        ans += (djs(r) - djs(l - 1)) * ndd;
    }
    printf("%lld", ans);
}
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
45
46
47
48
49

不过初始化取 $1e6、1e7$ 都有些测试点会超时，取到 $1.5e7$ 才能通过全部用例。

图像上我也没看太懂，好像均摊下来复杂度能亚 $O(n^{\frac{1}{3}})$，想不明白，内存往题目限制上开就完事了。