本文主要是介绍【题解】8 月 26 日模拟赛题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言

因为我很困，又不想颓废，所以我来写题解了。

\(\texttt{In memory of will7101}\)。

\(\texttt{T1}\) 偶数个 \(3\)

题目大意

对于给出的 \(n\)，求所有的 \(n\) 位数中含有偶数个 \(3\) 的数的个数。注意：

1. 包含偶数个 \(3\) 可以为包含 \(0\) 个 \(3\)
2. \(0\) 不算在 \(1\) 位数内

答案对 \(12345\) 取模。

\(0 < n \leq 1000\)

解题思路

签到题。看到题目是计数问题，考虑设 \(dp_{i, 0}\) 表示 \(i\) 位数中含有偶数个 \(3\) 的数的个数，\(dp_{i, 1}\) 表示 \(i\) 位数中含有奇数个 \(3\) 的数的个数。显然当最后一位为 \(3\) 时 \(3\) 的个数的奇偶性会发生变化，反之取 \(0\) 到 \(9\) 中除 \(3\) 以外的任意数字 \(3\) 的个数的奇偶性不发生变化，共有 \(9\) 种选择。因此状态转移方程为：

\(dp_{i, 0} = dp_{i - 1, 1} + dp_{i - 1, 0} \times 9\)

\(dp_{i, 1} = dp_{i - 1, 0} + dp_{i - 1, 1} \times 9\)

显然当 \(i = 1\) 时含有偶数个 \(3\) 的数有 \(1, 2, 4, 5, 6, 7, 8, 9\) 共 \(8\) 个（\(0\) 不算在 \(1\) 位数内），含有奇数个 \(3\) 的数有 \(3\)。因此边界条件为 \(dp_{i, 0} = 8, dp_{i, 1} = 1\)。

参考代码

#include <cstdio>
using namespace std;
 
const int maxn = 1e3 + 5;
const int mod = 12345;
 
int n;
int dp[maxn][2];
 
int main()
{
    dp[1][0] = 8, dp[1][1] = 1;
    scanf("%d", &n);
    if (n == 1)
    {
        puts("9");
        return 0;
    }
    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = (dp[i - 1][1] + dp[i - 1][0] * 9) % mod;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 9) % mod;
    }
    printf("%d\n", dp[n][0]);
    return 0;
}

\(\texttt{T2}\) 购物

题目大意

现在给您一个长度为 \(n\) 的数组 \(p\) 和 \(k\) 次操作。每次操作您可以令数组 \(p\) 中任意一个位置 \(i\) 的 \(p_i = q_i\)。您可以重复对一个位置进行操作，换言之在操作不重复的前提下您可以不进行恰好 \(k\) 次操作。现在请求出在至多 \(k\) 次操作后，至多能从数组中选出的元素个数使得选出的元素之和小于等于 \(m\)。

\(1 \leq k \leq n \leq 5 \times 10^4, 1 \leq m \leq 10^14, 1 \leq q_i \leq p_i \leq 10^9\)

解题思路

大家好，因为我非常喜欢贪心乱搞过题，所以我用被自己 hack 的程序草过了这道题

看到题目需要求最优解首先考虑贪心或者 \(dp\)，发现 \(dp\) 并不能找到一个合适的状态来在有限的时空要求内解决问题，因此考虑贪心做法。

我们可以得到一些比较显然的贪心策略：

1. 选出 \(q_i\) 前 \(k\) 小的元素操作，然后统计其余部分
2. 选出 \(p_i - q_i\) 前 \(k\) 小的元素操作，然后排序元素统计
3. 先按 \(q_i\) 选出前 \(k\) 小的元素操作，然后其余元素按照 \(q_i\) 为第一关键字，\(p_i\) 为第二关键字升序排序。每次考虑将当前元素替换到贪心策略中是否更优，求出最优操作策略后排序元素统计

然而这些贪心策略都不完全正确。我们发现这道题的贪心策略很难用 每次都选出当前的局部最优解，最后合并成全局最优解 的套路来确定。反而像是操作 \(3\) 一样的替换构造更加适合确定具体的贪心策略。因此我们在难以直接考虑贪心策略的时候，不妨使用反悔贪心来解决。

这道题中使用反悔贪心的时间复杂度是 \(\mathcal{O}(nlogn)\) 的，并且可以发现每个元素至多被反悔一次。因此在保证正确性的前提下可以使用反悔贪心。考虑从最基础的贪心策略入手：选出 \(q_i\) 前 \(k\) 小的元素操作。如果原本 \(p_i = q_i\) 并且从第 \(k + 1\) 小的 \(q_i\) 开始 \(p_i - q_i\) 的值极大，那么这个贪心策略显然是错的。考虑反悔。

假设现在我们已经操作了 \(q_i\) 前 \(k\) 小的元素，现在在考虑是否需要反悔第 \(i\) 个元素（\(i \geq k + 1\)）。如果我们最终需要选出元素 \(i\)，那么元素 \(i\) 与前 \(k\) 小的元素、已经选中的元素之和必定小于等于 \(m\)。为了令和尽量小，我们把没有被操作的元素按照 \(p_i\) 升序排列。

假如当前元素 \(y\) 可以被操作，设已经被操作的元素中 \(\min\{p_i - q_i\} = x\)，那么必定有 \(p_y - q_y > x\)。也就是在仅考虑前 \(y\) 个元素的情况下，如果我们加入元素 \(i\) 合法并且反悔第 \(y\) 个元素可以使和更小，那么我们可以反悔第 \(y\) 个元素。如果不反悔第 \(y\) 个元素，当其与已经选中的元素之和小于等于 \(m\) 时同样可以被选中。

证明：此时不反悔第 \(y\) 个元素的贡献为 \(p_y + p_z - (p_z - q_z)\)，反悔第 \(y\) 个元素的贡献为 \(p_z + p_y - (p_y - q_y)\)。因为 \(p_y - q_y > x = p_z - q_z\)，所以 \(p_y + p_z - (p_z - q_z) > p_z + p_y - (p_y - q_y)\)，也就是反悔第 \(y\) 个元素可以使得可行解更优。显然取等于时我们操作 \(q_i\) 更小的元素更优。因此贪心策略成立。

故而我们可以用一个小根堆来维护原始贪心策略中未被操作的部分。将剩余部分按 \(p_i\) 升序排序后每次取出小根堆的堆顶模拟即可。

时间复杂度 \(\mathcal{O}(nlogn)\)。

参考代码

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
#define int long long
 
const int maxn = 1e6 + 5;
 
struct node
{
    int p, q;
    bool operator < (const node& rhs) const
    {
        return p - q > rhs.p - rhs.q;
    }
} a[maxn];
 
int n, k, ans;
long long m;
priority_queue<node> pq;
 
bool cmp(node a, node b)
{
    if (a.q != b.q)
        return a.q < b.q;
    return a.p > b.p;
}
 
bool CMP(node a, node b)
{
    return a.p < b.p;
}
 
signed main()
{
    scanf("%lld%lld%lld", &n, &k, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].p, &a[i].q);
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= k; i++)
    {
        m -= a[i].q;
        pq.push(a[i]);
        if (m < 0)
        {
            printf("%lld\n", i - 1);
            return 0;
        }
    }
    ans = k;
    sort(a + k + 1, a + n + 1, CMP);
    for (int i = k + 1; i <= n; i++)
    {
        int tp = pq.top().p, tq = pq.top().q;
        if (a[i].p - a[i].q > tp - tq && a[i].q + tp - tq <= m)
        {
            m -= (a[i].q + tp - tq);
            ans++, pq.pop(), pq.push(a[i]);
        }
        else if (a[i].p <= m)
            ans++, m -= a[i].p;
    }
    printf("%lld\n", ans);
    return 0;
}

\(\texttt{T3}\) 拆网线

题目大意

现在给您一棵包含 \(n\) 个点 \(n - 1\) 条边的树。您需要选出 \(k\) 个结点和若干条边，使得这 \(k\) 个结点中的任意一个结点可以通过被选出的边和至少另外一个被选出的结点连通。试求最少需要选出的边的数量。

输入包含 \(t\) 组数据。

\(2 \leq k \leq n \leq 10^5, t \leq 10\)

解题思路

这道题又需要求最优解。树论题优先考虑树形 \(dp\) 和树上贪心。我们观察题目的最优解性质：每个结点至少需要连出一条边才能使得它和另外一个结点连通，又因为一条边最多连接两个结点，所以连接一条边最多能让 \(2\) 个结点连通，并且这两个结点为父子关系。

我们不妨贪心地考虑，每次都选出一对父子结点来连边，这样情况足够优时至少选出 \(\lceil \frac{k}{2} \rceil\) 条边就可以使所有被选出的点连通了。现在问题转化成：求在一棵树 \(T\) 中至多能选出的不相交父子结点对数，考虑树形 \(dp\)。设 \(dp_i\) 为结点 \(i\) 子树内的最大不相交父子结点对数。

当结点 \(i\) 不与它的子结点连边时，\(\forall j \in son_i, dp_i = \sum\limits dp_j\)。当结点 \(i\) 与它的子结点 \(j\) 连边时，其余子结点都无法与结点 \(i\) 连边，并且结点 \(j\) 的子结点无法和结点 \(j\) 连边。不妨另设 \(\forall j \in son_i, sum_i = \sum\limits dp_j\)，那么此时 \(\forall k \in son_i, k \neq j, dp_i = \sum\limits dp_k + sum_j + 1\)。

因为题目给出的是无根树，因此不妨以结点 \(1\) 为根。如果 \(2 \times f_1 < k\)，说明还有结点无法直接和别的结点配对。此时如果存在一对度为 \(0\) 的父子结点，那么 \(f_1\) 一定不是最优解。换言之，树中不存在一对度都为 \(0\) 的父子结点，此时任意找出一个度为 \(0\) 的结点与其父亲或儿子连边即可。这部分结点每个结点都需要独自贡献一条边，因此多贡献的边数为 \(k - f_1 \times 2\)。

时间复杂度 \(\mathcal{O}(n)\)。

参考代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;
 
struct node
{
    int to, nxt;
} edge[maxm];
 
int t, n, k, cnt;
int head[maxn], f[maxn], sum[maxn];
 
inline int read()
{
    int res = 0, flag = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            flag = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        res = res * 10 + ch - '0';
        ch = getchar();
    }
    return res * flag;
}
 
void add_edge(int u, int v)
{
    cnt++;
    edge[cnt].to = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}
 
void dfs(int u, int fa)
{
    for (int i = head[u]; i; i = edge[i].nxt)
    {
        int v = edge[i].to;
        if (v == fa)
            continue;
        dfs(v, u);
        sum[u] += f[v];
    }
    f[u] = sum[u];
    for (int i = head[u]; i; i = edge[i].nxt)
    {
        int v = edge[i].to;
        if (v == fa)
            continue;
        f[u] = max(f[u], sum[u] - f[v] + sum[v] + 1);
    }
}
 
int main()
{
    int v, flag;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &k);
        cnt = 0, flag = (k & 1), k -= flag;
        memset(head, 0, (n + 1) * sizeof(int));
        memset(f, 0, (n + 1) * sizeof(int));
        memset(sum, 0, (n + 1) * sizeof(int));
        for (int i = 1; i <= n - 1; i++)
        {
            scanf("%d", &v);
            add_edge(i + 1, v);
            add_edge(v, i + 1);
        }
        dfs(1, 0);
        if (f[1] * 2 >= k)
            printf("%d\n", k / 2 + flag);
        else
            printf("%d\n", f[1] + (k - f[1] * 2) + flag);
    }
    return 0;
}

\(\texttt{T4}\) 密室

题目大意

给定您一个 \(n\) 点 \(m\) 边的无向图，已知通过第 \(i\) 条无向边需要若干钥匙，并且每到达一个房间均能获得若干钥匙。已知经过某条无向边后该无向边所需要的钥匙不会消失，且最多有 \(k\) 种不同的钥匙。如果图种的无向边边权均为 \(1\)，试求从结点 \(1\) 到达结点 \(n\) 的最短路长度。如果结点 \(1\) 无法到达结点 \(n\)，输出 No Solution。

\(n \leq 5000, m \leq 5299, 0 \leq k \leq 10\)

解题思路

如果题目给出了一张无向图，并且该无向图的边权均为 \(1\)，那么这道题正解大概率不是最短路。因此我们考虑广搜解决。我们发现如果需要判断能否经过某条有向边，必须记录在当前结点拥有的钥匙情况。一种直观的想法是用一个数组记录下是否拥有第 \(i\) 种钥匙，常数较大。发现题目给出 \(k \leq 10\)，因此可以考虑使用状压 \(\mathcal{O}(1)\) 解决。

不妨用一个二进制数，从右往左数第 \(i\) 位表示是否拥有第 \(i\) 个钥匙，\(1\) 有 \(0\) 无。我们把所有钥匙情况都用这种方法表示，判断拥有钥匙情况为 \(x\) 是否能通过需要钥匙情况为 \(j\) 的无向边即为 x & j == j。

因为状态总数为 \(2^k \times n\)，所以时间复杂度最坏是 \(\mathcal{O}(1024n)\)。

参考代码

#include <cstdio>
#include <queue>
using namespace std;
 
const int maxn = 5e3 + 5;
const int maxm = 6e3 + 5;
const int maxt = (1 << 10);
 
struct node
{
    int to, nxt, w;
} edge[maxm];
 
int n, m, k, cnt;
int head[maxn], w[maxn];
bool vis[maxn][maxt];
queue<int> qnode, qvis, qstep;
 
inline int read()
{
    int res = 0, flag = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            flag = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        res = res * 10 + ch - '0';
        ch = getchar();
    }
    return res * flag;
}
 
void add_edge(int u, int v, int w)
{
    cnt++;
    edge[cnt].to = v;
    edge[cnt].nxt = head[u];
    edge[cnt].w = w;
    head[u] = cnt;
}
 
int main()
{
    int u, v, c, val;
    int fnode, fvis, fstep;
    bool flag = false, eflag;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < k; j++)
        {
            scanf("%d", &val);
            if (val == 1)
                w[i] |= (1 << j);
        }
    }
    for (int i = 1; i <= m; i++)
    {
        c = 0;
        scanf("%d%d", &u, &v);
        for (int j = 0; j < k; j++)
        {
            scanf("%d", &val);
            if (val == 1)
                c |= (1 << j);
        }
        add_edge(u, v, c);
    }
    vis[1][w[1]] = true;
    qnode.push(1);
    qvis.push(w[1]);
    qstep.push(0);
    while (!qnode.empty())
    {
        fnode = qnode.front();
        fvis = qvis.front();
        fstep = qstep.front();
        qnode.pop(), qvis.pop(), qstep.pop();
        if (fnode == n)
        {
            printf("%d\n", fstep);
            flag = true;
            break;
        }
        for (int i = head[fnode]; i; i = edge[i].nxt)
        {
            eflag = true;
            for (int j = 0; j < k; j++)
            {
                if (edge[i].w & (1 << j))
                {
                    if (!(fvis & (1 << j)))
                    {
                        eflag = false;
                        break;
                    }
                }
            }
            if (!eflag)
                continue;
            v = edge[i].to;
            c = fvis | w[v];
            if (!vis[v][c])
            {
                vis[v][c] = true;
                qnode.push(v);
                qvis.push(c);
                qstep.push(fstep + 1);
            }
        }
    }
    if (!flag)
        puts("No Solution");
    return 0;
}

后记

开学前倒数第二场模拟赛，还算可以。另外写题解的时候有只黄色的猴子在骚扰我并宣称自己是 \(\texttt{Ling_Lover}\)。猴子：阿绫是什么东西？

唐门玄天宝录总纲，第三条，确定对手是敌人，只要其有取死之道，就不要手下留情，否则只会给自己增添烦恼

这篇关于【题解】8 月 26 日模拟赛题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！