【题解】7月11到7月17典例复习

Mon Jul 17 2023

24 分钟

技术 OI学习笔记题解比赛题解复习数论快速幂最大生成树并查集

4043 字

前言#

因为网盘还没有搭建好，题面 PDF 无法上传，所以暂时没有题面

7 月 17 日#

1. maruyu#

是一道让我非常头疼的数论题面，刚刚好让我好好复习一下。

回顾一下题面，要用 $n + 1$ 艘船运送 $k$ 种物质，而且要满足一下两个条件：

没有任何一种物质同时被 $0 \sim n - 1$ 艘船运输；
第 $1\sim n$ 艘船没有运输全部 $k$ 种物资；

现在问你：一共有多少种运输方案？（对 1e9 + 7 取模）

题解#

那么看起来很难（确实很难），我们用一个矩阵来理解。

假设每一行从左往右从 0 开始，到 $n$ 结束；每一列由上而下从 1 开始，从 $k$ 结束。

我们规定 0 代表第 $i$ 艘船选择了第 $j$ 种物质；1 就代表选择。那么我们可以用(i, j)来表示一个状态，从这里开始分析；

首先明确题面，我们不需要运输完所有的 $k$ 种物资，那么我们从 1 到 $k$ 枚举一个实数 $i$ ，代表有 $i$ 种物质没有被取走；
那么我们很简单可以知道这样一共有 ${C}_{k}^{i}\times2^i$ 种情况
接下来我们开始考虑其他的取走的物品的情况
1. 因为头尾的两艘船十分特殊，我们先不考虑它们，先考虑 $1\sim n - 1$ ；
2. 每一条船可以取也可以不取，一共是 $2 ^ {n - 1}$ 种情况
3. 因为我们现在不知道头尾的情况，我们先去掉都是 1 和都是 0 的情况，也就是-2
4. 我们再考虑前后两个特殊的值，把刚才的式子再乘以 $2^2$ ；
5. 最后我们要把刚刚去掉的全部都是 1 和 0 的情况补回来，有下面四种合法情况
  1. 0 111111111111…111
  2. 0 111111111111…110
  3. 1 000000000000…001
  4. 1 000000000000…000
6. 那么此时我们单个物资的情况就是 $\left(2^{n-1}-2\right)\times4+4$ ；
7. 最后此时我们有 $k - i$ 种物质被取走了，那么最后的结果是 ${\left(\left(2^{n-1}-2\right)\times4+4\right)}^{k - i}$
现在我们可以得到一个式子 $\sum_{i=\:1}^k{C}_{k}^{i}\times2^i\times{\left(\left(2^{n-1}-2\right)\times4+4\right)}^{k - i}$ ；
但是这样我们处理非常麻烦，需要化简（使用二项式定理）：
1. 二项式定理： $(a+b)^k=\sum_{i=\:0}^k{C}_{k}^{i}\times a^i\times b^{k-i}$
2. 我们把 $\left(2^{n-1}-2\right)\times4+4$ 用一个变量 $R$ 代替，重写得到 $\sum_{i=\:1}^k{C}_{k}^{i}\times2^i\times{r}^{k - i}$ ；
3. 容易发现 $\sum_{i=\:0}^k{C}_{k}^{i}\times2^i\times{r}^{k-i}=\left(r+2\right)^k$ ，但是这里的 $i$ 是从 0 开始的，我们还需要减去；
4. 最终化简结果为 $\sum_{i=\:1}^k{C}_{k}^{i}\times2^i\times{\left(\left(2^{n-1}-2\right)\times4+4\right)}^{k-i}=\sum_{i=\:1}^k{C}_{k}^{i}\times2^i\times{r}^{k-i}=\left(2^{}+r\right)^k-r^k$
最后使用快速幂计算输出。

注意最后有减法，不要忘记加上 mod 之后再减避免出现负数

FIX 代码#

CPP

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define fastio                   \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define ll long long
#define mod 1000000007

using namespace std;

ll pow(ll a, ll b)
{
	a %= mod;
    ll ans = 1;
	for(; b; b >>= 1)
	{
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

int main()
{
    fastio;
    freopen("maruyu.in", "r", stdin);
    freopen("maruyu.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while (t--)
    {
        ll n, k;
        scanf("%lld%lld", &n, &k);
// 首先明确题目，我们不需要取完所有的K种物品
// 那么我们枚举i(1~k)假设有i种物品没有被取
// 一共就是C(i, k) * 2 ^ i种情况
// 开始考虑其他取走的物品
// 因为题目有两个条件，我们先考虑不受影响的1~n - 1
// 每一条船可以取也可以不取，一共是2 ^ (n - 1)种情况
// 那么如果都是1或者都是0是会影响的，我们暂时去掉-2
// 考虑前后两个，都有01两种情况，一共四种使用乘法公式
// 最后我们要把之前去掉的情况补回来，有下面四种情况
// - 0 111111111111...111
// - 0 111111111111...110
// - 1 000000000000...001
// - 1 000000000000...000
// 那么最后我们还要计算所有剩下的情况，一共是^(k - i)
// 此时结果是：i : [1~K] C(i, k) * (2 ^ i) * ((2 ^ (n - 1)) * 4 + 4) ^ (k - i)
// 我们可以用二项式定理化简：
// - 二项式定理：(a + b) ^ k = i : [0~k] C(i, k) * a ^ i * b ^ (k - i)
// 我们把(2 ^ (n - 1)) * 4 + 4)当做r
// 此时式子为                         i : [1~K] C(i, k) * 2 ^ i * r ^ (k - i)
// 显然我们发现这个式子和 (2 + r) ^ k = i : [0~k] C(i, k) * 2 ^ i * r ^ (k - i)很像
// 但是我们的i是从1开始的，二项式定理的i是从0开始
// 所以我们最后要剪去多余的0
// 最后化简的式子为: (2 + r) ^ k - r ^ k
// 整理得 ans = 2 ^ k * ((2 ^ n - 1) ^ k - (2 ^ n - 2) ^ k)
        printf("%d\n", pow(2LL, k) * (pow(pow(2ll, n) - 1, k) - pow(pow(2LL, n) - 2, k) + mod) % mod);
    }
    return 0;
}

2. truck#

我本来的想法是二分答案验证联通，但是发现复杂度为 $O(Q * \log N(N + M))$ ，得分 60Pt。

题解#

思路来自 HYX 大佬，而非 std

主要思想：最大生成树&并查集

首先我们使用pair离线存贮所有的提问，因为是无向图，我们要双向存储。其中 first 代表的是目标节点，second 代表的是提问编号。

我们把所有的边放在一个vector中，然后定义以边权从大到小排序，用来做最大生成树；

为什么这样做？#

翻译一下题面，就是我们要找两点之间简单路径上面最大的最小值！可能有点拗口，就是在保证联通的情况下，我们这一条路径上面的最小值尽可能大那么我们就可以用最大生成树，把边从大到小依次添加，直到 uv 在同一个连通块里面那么此时添加的这一条边就是 uv 两点之间简单路径上面最大的最小值，也就是答案那么就很简单了，我们从大到小添加边，然后合并，直到 uv 合并，记录 ans 那么我们只需要遍历提问，然后操作并查集，通过路径压缩和启发式合并完全可以通过题目

算法实现#

联系我们之前强连通分量的内容，其实我们这里并查集做的事情差不多，就是把几个点合并成一个点。那么我们先定义一个数组fa代表这个点从属于哪个大点。刚开始fa是他们自己，每次把小的合并到大的，更新fa。

这里我们写一个函数来获得他从属于哪一个大点。

CPP

int get_fa(int a)
{
    return a == fa[a] ? a : fa[a] = get_fa(fa[a]);
}

这里我们fa[a] = get_fa(fa[a])是路径压缩，把父亲直接指向根，节省时间。

最后我们写合并函数。前面我们说了用pair来存储询问，那么其实每一次合并时也合并了询问，我们也要把询问放入并查集->我说过这就和合并几个点相同，其实刚开始每一个点都是一个大点，只不过他们只包含自己而已。

分析查询询问的过程，如果我们查询到的询问的目标在同一个大点中，说明只要连接这一条边，他们就联通了，此时我们把这一次询问的答案记录为此时的边权；如果不再一个大点中，我们就把它合并到一起，进入下一次合并的过程。

最后我们把这个大点归属到需要合并的点中，那么下一次get_fa时，里面所有小点的fa都会更新。

CPP

void merge(int sm, int la, int val)
{
    for (auto temp : que[sm])
    {
        int v = temp.first;
        int id = temp.second;
        if (get_fa(v) == la) ans[id] = val;
        else que[la].push_back(temp);
    }
    fa[sm] = la; // 合并
}

代码#

注意我们要保证时间复杂度在 log 内，需要严格把小的合并到大的，也就是所谓的启发式合并。

CPP

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define fastio                   \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define N 100005
#define T_u 1
#define T_v 2

using namespace std;

struct truck
{
    int u, v;
    int val;
    truck(int a, int b, int c)
    {
        u = a;
        v = b;
        val = c;
    }
    truck()
    {
        u = 0;
        v = 0;
        val = 0;
    }
};

vector<truck> edge;            // 直接存储无向边
vector<pair<int, int>> que[N]; // 保存从N到<first>的第<second>次询问
int fa[N];                     // 并查集的父亲代表元素
int ans[300005];

bool cmp(truck a, truck b)
{
    return a.val > b.val;
}

int get_fa(int a)
{
    return a == fa[a] ? a : fa[a] = get_fa(fa[a]);
}

void merge(int sm, int la, int val)
{
    for (auto temp : que[sm])
    {
        int v = temp.first;
        int id = temp.second;
        if (get_fa(v) == la)
            ans[id] = val;
        else
            que[la].push_back(temp);
    }
    fa[sm] = la;
}

int main()
{
    fastio;
    freopen("truck.in", "r", stdin);
    freopen("truck.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edge.push_back(truck(u, v, w));
    }
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= q; i++)
    {
        int u, v;
        ans[i] = -1;
        scanf("%d%d", &u, &v);
        que[u].push_back({v, i});
        que[v].push_back({u, i});
    }
    sort(edge.begin(), edge.end(), cmp);
    for (truck temp : edge) // 从大开始合并
    {
        int sm = get_fa(temp.u);
        int la = get_fa(temp.v);
        if (sm == la)
            continue;
        if (que[sm].size() > que[la].size())
            swap(sm, la); // 启发式合并
        merge(sm, la, temp.val);
    }
    for (int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
    return 0;
}

7 月 16 日#

1. xor#

题解#

因为题面中 b 是严格递增的，那么我们可以不走回头路，在 $O(N^2)$ 解决问题。

总的来说就是先存储前面两个元素 xor 的值有几个，然后在后面匹配。

代码实现#

首先定义 $cnt_{k}[x]$ 的含义是当第三个元素在k位置时前两个元素 xor 的值为 x 的匹配个数。

我们先定一个指针 $k$ 来指代第三个元素的位置。那么每次移动指针 $k$ 时可以通过遍历a[i] xor a[k]，就可以直接处理好我们需要的 $cnt_{k + 1}$ ，这段操作不计时间复杂度。

然后我们从k + 1开始遍历第四个元素l的位置，每次ans += cnt[a[k] ^ a[l]]，也就是加上当前能够匹配上的元素。

遍历 k 和 l，时间复杂度为 $O(N^2)$ ，可以解决问题。

代码#

CPP

#include <iostream>
#include <cstring>
#include <cstdio>
#define N 1048576 // 注意 2^20
#define ll long long

using namespace std;

ll n, ans;
ll cnt[N];
int a[N];

int main()
{
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    for (int k = 1; k <= n; k++)
    {
        for (int l = k + 1; l <= n; l++)
        {
            ans += cnt[a[k] ^ a[l]];
        }
        for (int i = 1; i < k; i++)
            cnt[a[i] ^ a[k]]++;
    }
    printf("%lld", ans);
    return 0;
}

2. multiplication#

题解#

反正我们不知道谁是谁，我们直接假设元素从小到大排列整齐，方便分析。

那么排好之后是一个 $[0, p-1] \times [0, p-1]$ 的一个 $p \times p$ 矩阵，很像我们的 99 乘法表。

那么用我们聪明的小脑袋想一想，如果是 $n \times p (n < p)$ ，那么很显然十位就是 $n$ 。但是我们最大为 $(p-1) \times (p-1)$ ，简单拆开就是 $p^2-2p+1$ ，刚刚好得到的数字为 $[p-2][1]$ ；

根据这个规律我们可以写出这样一个对应表：

|我们从 0 到 p-1 的数字| p-1 | | :title: 【题解】7 月 11 到 7 月 17 典例复习 tags:

比赛
题解
复习
数论
快速幂
最大生成树
并查集 categories:
OI 学习笔记
题解 abbrlink: 427ba869 pubDate: 2023-07-17 00:00:00 image: https://saroprock.oss-cn-hangzhou.aliyuncs.com/img/7%E6%9C%8817%E6%97%A5.jpgbadge: old

-----: | :-----------: | | 0 | [0][0] | | 1 | [0][p-1] | | 2 | [1][p-2] | | 3 | [2][p-3] | | … | … | | p-1 | [p-2][1] |

容易发现，一个正整数数在 p 进制下乘以 p-1，它的十位刚刚好就是它自己减一。

但是回过来，我们这个矩阵既不是有规律的，甚至于我们都不知道数字是几，但是我们可以通过其他方法记录这个值。

我们知道一个数最大时的十位是它自己减一，这说明什么？说明在之前的十位它都曾出现过。假设有一个数字三，乘以 p-1 得到一个数字十位为 2，这说明它在这个矩阵中一定有十位为 0，1，2 的数字。因为即使 p 最小最小为 3 时，每一次相乘也就是在之前的基础上加三，十位同时进一位，不可能有进两位的情况。

那么就简单了，我们只需要统计一个数在这个矩阵的一行中的数字的十位所出现的种类数，就是它。

0 需要特判，因为 0 乘以任何数都是 0

代码#

CPP

#include <unordered_map>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define ll long long

using namespace std;

const int N = 2000 + 5;
int num[N];
int p;

int main()
{
    freopen("multiplication.in", "r", stdin);
    freopen("multiplication.out", "w", stdout);
    scanf("%d", &p);
    for (int i = 1; i <= p; i++)
    {
        int tot = 0;
        bool zero = true;
        unordered_map<int, int> hash;
        for (int j = 1; j <= p; j++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            if (a != b) zero = false;
            if (hash.count(a)) continue;
            else { tot++; hash[a] = a; }
        }
        if (!zero) num[i] = tot;
    }
    for (int i = 1; i <= p; i++) printf("%d ", num[i]);
    return 0;
}

3. four#

题解#

这个题目很复杂，很烦躁，要静……

但是理解了之后，也非常的简单……

首先方案达到了 $2^{40}$ 级别，基本上属于摆烂的节奏，我们把它先分成两半再匹配，分开来是为了防止暴力爆炸，分成两份是保证脑子不爆炸。

我们先把分开来的 20 个元素变成 $2^{20}$ 个元素，可以直接这样写：

CPP

for (int i = l; i < r; i++)
{
    vector<int> t = temp; // instead dfs
    for (int x : temp)
        t.push_back(x + a[i]);
    temp = t;
}

然后容我来讲解一下判断方法：

我们先在前后各 $2^{20}$ 中选出两个元素
通过pw取模拿出这两个元素的一段
然后相加这两项，那么我们可以简单判断是否在pw + 1位存在 4
如果相加的值在[4 * 10^pw, 4.999… * 10^pw]或者[14 * 10^pw, 14.999… * 10^pw]
就说明在这种情况之下的pw + 1为 4

就这么简单……我也想不到还有什么好说的了，自行阅读代码理解吧。

代码#

CPP

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <array>
#define ll long long

using namespace std;

int a[44];
vector<array<int, 2>> le; // left
vector<array<int, 2>> ri; // right
ll ans;
int n;

vector<array<int, 2>> init(int l, int r)
{
    vector<int> temp{0}; // init 0
    for (int i = l; i < r; i++)
    {
        vector<int> t = temp; // instead dfs
        for (int x : temp)
            t.push_back(x + a[i]);
        temp = t;
    }
    // 第一位是我们取出来的，第二位则是我们保存的这个数原有的值
    vector<array<int, 2>> ret; // first save now. second save old
    for (int x : temp)
        ret.push_back({0, x});
    return ret;
}

void reorder(vector<array<int, 2>> &str, int pw)
{
    vector<array<int, 2>> v[10];
    for (auto [_, x] : str)
    {
	    // 这里我们重新取出pw + 1位并用第一个数字排序
        int head = (x / pw) % 10; // str_head -> |*^****...|
        int val = x % (pw * 10);  // str_val -> (int)|*****...|
        v[head].push_back({val, x});
    }
    str.clear(); // remove
    for (int i = 0; i <= 9; i++)
        for (auto temp : v[i])
            str.push_back(temp);
}

ll calc(int d)
{
	// 假设都符合
    int r = ri.size(); // if all
    ll temp = 0;
    for (int l = 0; l < le.size(); l++)
    {
        // cmp now > d ? check->NO : check->YES
        // 我们相加判断一下这个是否符合要求
        while (r > 0 && ri[r - 1][0] + le[l][0] > d)
            r--; // cmp fail -> r-- -> find other
        temp += r;
    }
    return temp;
}

int main()
{
    freopen("four.in", "r", stdin);
    freopen("four.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    le = init(0, n / 2); // 20 -> 2^20
    ri = init(n / 2, n); // 20 -> 2^20

    for (int i = 0, pw = 1; i <= 8; i++, pw *= 10)
    {
        reorder(le, pw); // -> reorder -> cmp now -> check
        reorder(ri, pw); // -> reorder -> cmp now -> check
        // now -> [4 * 10^pw, 5 * 10^pw - 1]
        // or: -> [14 * 10^pw, 15 * 10^pw - 1]
        ans += calc(5 * pw - 1) - calc(4 * pw - 1) + calc(15 * pw - 1) - calc(14 * pw - 1);
    }
    printf("%lld", ans);
    return 0;
}

7 月 15 日#

【题解】7月11到7月17典例复习

https://frosti.saroprock.com/blog/7月11日到7月17日典例复习/