四糸智乃

02-14 21:01 深信服_算法工程师

发布于江苏

关注

【题解】牛客小白月赛110

A 智乃办赛

题解

如代码所示，类似500进制数取十位和个位

时间复杂度 $O(1)$

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    printf("%c%03d\n",(n-1)/500+'A',(n-1)%500+1);
    return 0;

}

B 智乃的Wordle

题解

如代码所示，初始化成r，先一重循环判断是不是g，否则双重循环判断是不是y

字符串长度固定，时间复杂度为常数 $O(1)$

#include <bits/stdc++.h>
using namespace std;

int main() {
    string secret, guess;
    cin >> secret >> guess;

    string result(8, 'r'); // 初始化结果为红色

    // 第一次遍历，处理绿色
    for (int i = 0; i < 8; ++i) {
        if (secret[i] == guess[i]) {
            result[i] = 'g';
        }
    }

    // 第二次遍历，处理黄色
    for (int i = 0; i < 8; ++i) {
        if (result[i] == 'r') { // 如果当前是红色
            for (int j = 0; j < 8; ++j) {
                if (secret[j] == guess[i]) {
                    result[i] = 'y';
                    break;
                }
            }
        }
    }

    // 输出结果
    cout << result << endl;

    // 判断是否全部猜对
    if (result == "gggggggg") {
        cout << "congratulations" << endl;
    } else {
        cout << "defeat" << endl;
    }

    return 0;
}

C 智乃的数字

题解

方法一

注意力惊人，注意到循环节是 $30$ ，每 $30$ 个数循环出现 $7$ 个智数，则有 $a[7]=\{3,5,9,15,21,25,27\}+30k, k \in N$ ，直接输出 $a[(n-1)\%7]+(n-1)/7\times30$

注意力不怎么惊人可以看方法二，使用很少的注意力发现容斥的时候全集是 $30$ ，推测出循环节也是 $30$ ，然后就不需要容斥直接打表了

时间复杂度 $O(1)$

#include <bits/stdc++.h>

using namespace std;
int T;
long long n, a[] = {3, 5, 9, 15, 21, 25, 27};

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%lld", &n);
        printf("%lld\n", a[(n - 1) % 7] + (n - 1) / 7 * 30);
    }
    return 0;
}

方法二

二分+容斥，比较麻烦并不推荐，小学数学题之求阴影部分面积，如图所示

alt

#include <bits/stdc++.h>

using namespace std;

long long calc(long long x)
{
    return x / 5 + x / 3 - x / 15 - x / 6 - x / 10 + x / 30;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        long long k;
        scanf("%lld", &k);
        long long l = 1, r = 1e10, ans;
        while (l <= r)
        {
            long long mid = (l + r) >> 1;
            if (calc(mid) >= k)
            {
                ans = mid;
                r = mid - 1;
            } else
            {
                l = mid + 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

D 智乃与长短期主义者博弈

题解

区间dp，比较套路和板子，写法比较多怎么写都能过，但是处理不好容易写的非常不优雅，重点说一下如何利用一些性质把代码写的优雅。

要点一

由于只有两名玩家进行游戏，假设玩家1的得分为 $a$ ，则游戏结束时令一名玩家的得分一定为 $sum-a$ 。dp过程中不必储存两名玩家的得分，保留一名玩家的得分或者差值，与保留一个pair数比较大小等价（即dp数组存一个数就是存俩数，效果相同）

要点二

将两个玩家先后手操作合并成一个回合内的操作，这样最终剩下 $1$ 个或者 $2$ 个时作为dp的起点，剩下的情况都归为一类，更好考虑

方程

以 $dp[l][r]$ 表示区间以 $[l,r]$ 开始游戏，短期主义者先手时，最优操作下两名玩家的得分之差为例

$dp[l][r] = \begin{cases} -a[l] & \text{if } l = r \\ \min(a[l], a[r]) - \max(a[l], a[r]) & \text{if } l + 1 = r \\ \max(a[l+1] - a[l] + dp[l+2][r], a[r] - a[l] + dp[l+1][r-1]) & \text{else if } a[l] \geq a[r] \\ \max(a[r-1] - a[r] + dp[l][r-2], a[l] - a[r] + dp[l+1][r-1]) & \text{else if } a[l] < a[r] \end{cases}$

最后输出 $\frac{sum-dp}{2}$ , $\frac{sum+dp}{2}$

时间复杂度 $O(n^2)$

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1005;
const int INF=1<<30;
int a[MAXN],dp[MAXN][MAXN];
int dfs(int l,int r)
{
    if(dp[l][r]!=-INF)return dp[l][r];
    if(l==r)
    {
        return dp[l][r]=-a[l];
    }
    if(l+1==r)
    {
        return dp[l][r]=min(a[l],a[r])-max(a[l],a[r]);
    }
    if(a[l]>=a[r])
    {
        return dp[l][r]=max(a[l+1]-a[l]+dfs(l+2,r),a[r]-a[l]+dfs(l+1,r-1));
    }else
    {
        return dp[l][r]=max(a[r-1]-a[r]+dfs(l,r-2),a[l]-a[r]+dfs(l+1,r-1));
    }
}
int main()
{
    int n,sum=0;
    scanf("%d",&n);
    for(int i=0;i<n;++i)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    for(int i=0;i<n;++i)
    {
        for(int j=i;j<n;++j)
        {
            dp[i][j]=-INF;
        }
    }
    int ans=dfs(0,n-1);
    printf("%d %d",(sum-ans)/2,(sum+ans)/2);
}

E 智乃的跳跃排序

题解

首先注意到样例4

3 2
3 1 2

如果没给这个样例就不知道要死多少人了

因为有一个明显的错解，甚至是第一想法是：猜测本题结论与交换操作的过程无关，只考虑结果，使用一个并查集，将所有 $|i-j|=k$ 和 $|a_i-a_j|=k$ 的元素并到一起，然后每个集合内排下序，如果合起来是排好序的就是yes，否则no

思考的过程为：

1、猜想与操作的过程无关，只讨论结果，考虑分组排序合并看整体是否有序的思路肯定没问题，如果这个大前提被推翻了，则本题显然是一个np问题，只能dfs暴力

2、问题肯定出在 $|i-j|=k$ 和 $|a_i-a_j|=k$ 这一步不能合并在一起考虑

3、考虑添加一个轻微的限制条件：先只进行若干次 $|i-j|=k$ ，然后再只进行若干次 $|a_i-a_j|=k$ 操作（稍后会有证明）

以样例1

6 5
3 2 8 4 5 1

为例，我们先在满足 $|i-j|=k$ 条件时，尝试排序

我们做这么一个操作，将数组排序前后“竖”起来按照%k分组，如图所示

alt

如上图，我们得到了 $k=5,3,2$ 时的分组情况

注意到组内是可以任意交换的，所以我们对原数组分组后，组内也做一个排序，尽可能的和排序后的数组对齐，将两个图形叠放找不同

alt

红色部分表示结果不一致部分，即只通过 $|i-j|=k$ 排序后，仍然不能满足条件的部分，所以需要 $|a_i-a_j|=k$ 的交换，对于这个样例只需要检查 $3$ 和 $8$ 是不是能交换就做完了。

对于更复杂的情况，不可能也是暴力的判断不满足条件的位置如何进行交换的，但我们注意到 $|a_i-a_j|=k$ 的交换条件，仍然是一个满足条件的集合内可以互相交换，不妨在一开始就把属于相同集合的数字分成另一个维度的“组”，为了避免人类不能理解高纬度下的分组，我们一般使用颜色的方式染色来理解

alt

只需要略微修改刚才的过程，我们先按照 $|a_i-a_j|=k$ 的条件染色，将满足条件的数字染成同色，接下来的排序和对比，都和值无关，而是用"颜色"来代替值

时间复杂度 $O(nlogn)$

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100005;
int fa[MAXN], n, k, a[MAXN], b[MAXN];
struct ID {
    map<int, int>mp;
    int tot;
    int operator ()(int x) {
        auto it = mp.find(x);
        if (it == mp.end())return -1;
        return it->second;
    }
    void insert(int x) {
        if (mp.find(x) == mp.end()) {
            mp[x] = ++tot;
        }
    }
} id;
vector<int>v1[MAXN], v2[MAXN];

int findf(int x) {
    return x == fa[x] ? x : fa[x] = findf(fa[x]);
}

void unions(int x, int y) {
    if (findf(x) == findf(y)) {
        return;
    }
    fa[findf(x)] = findf(y);
}

int main() {
    bool f = true;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; ++i) {
        id.insert(a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        int x = id(a[i]);
        int y = id(a[i] + k);
        int z = id(a[i] - k);
        if (y != -1) {
            unions(x, y);
        }
        if (z != -1) {
            unions(x, z);
        }
    }
    for (int i = 1; i <= n; ++i) {
        //这里放的是颜色，用并查集的根节点代替了
        v1[(i - 1) % k].push_back(findf(id(a[i])));
        v2[(i - 1) % k].push_back(findf(id(b[i])));
    }
    for (int i = 0; i < min(k, n); ++i) {
        sort(v1[i].begin(), v1[i].end());
        sort(v2[i].begin(), v2[i].end());
        if (v1[i] != v2[i]) {
            f = false;
        }
    }

    printf(f ? "Yes\n" : "No\n");
    return 0;
}

/*
6 5
3 2 8 4 5 1

6 5
3 2 11 4 5 1
 * */

猜想的证明

本题中需要证明的几个关键猜想

1、操作的过程无关，可以只讨论结果

2、添加轻微限制条件后，新问题与原命题等价

因为本人表达能力不是很好，所以采用数形结合的方法给出一个比较形象但是不怎么严谨的证明

首先解密游戏里面有这样一种常见pazzle：二维矩阵置换

alt

说在 $n\times n$ 二维矩阵里面有 $n$ 个宝石，并且每一行每一列里有且仅有一颗宝石，现在进行若干次操作，每次可以交换两行或者两列，问能不能让所有宝石放到第 $i$ 行第 $i$ 列这条对角线上。

在二维矩阵交换行和列的过程中，行和列互不影响，可以各自独立的维护一个置换，所以二维矩阵可以通过这种方式 $O(1)$ 的维护交换行和列，

并且先置换行或者先置换列还是操作交叉进行，都不影响最后矩阵的结果

这个模型天然就满足我们需要证明的两个猜想，那么如何将本题等价转化成二维矩阵置换模型呢

首先将数组离散化成排列，然后直接标记到点 $p(i,a[i])$ ，这个排序的操作也就是放到第 $i$ 行第 $i$ 列这条对角线上

以样例4为例

3 2
3 1 2

alt

这个问题好像变得非常直观了，一眼就能发现中间这个永远都换不到

当然顺着这个数形结合的证明思路，也可以写出相应的AC代码，但是感觉做的更烦了，像个大模拟，感兴趣可以自行尝试

F

题解

因为懒得证明贪心，所以搞了一个稍微繁琐点但是不需要证明的写法

首先分情况讨论，如果 $x$ 是0，那么把所有的 $0$ 改成 $1$ 就行了

考虑 $x$ 不是 $0$ ，由于 $0$ 乘任何数都是 $0$ ，所以改啥都不如改 $0$

考虑把哪些位置改成 $0$ ，还是由于 $0$ 乘任何数都是 $0$ ，所以每一个乘积为 $x$ 的区间都至少要包含 $1$ 个 $0$ 就能满足题目要求

暴力的想，我们能不能枚举所有乘积为 $x$ 的区间，显然能枚举，这里和枚举/统计区间和为 $x$ 的方法相同，即考虑前缀乘积用 $pre_j$ 表示，维护到set或者map等查询数据结构中，假设当前的前缀乘积为 $pre_i$ ，则需要查询 $pre_i * inv(pre_j)\equiv x$ ，移项得 $pre_i * inv(x)\equiv pre_j$ ，这里有个小技巧是把 $inv$ 项给到 $x$ 可以预处理减少常数，大家平时写代码可以注意这种同余等式，虽然在本题中由于还有查询结构所以 $log$ 压不掉，但换一个题可能就是多一个 $log$ 少一个 $log$ 的区别，然后从左到右扫描，这样就得到了所有右端点为 $r$ 的全部区间，虽然能暴力，但是不能太暴力，不然这些区间总共可能是 $n^2$ 级别的，好在在枚举的过程中，因为固定了一个右端点 $r$ ，对于左端点，显然如果 $[l,r]$ 满足题目要求，则 $[l-1,r]$ 必定也满足题目要求，所以在这里进行一步去重，仅保留右端点不同，左端点最大的区间，这样区间的数目仅剩下 $n$ 个，允许我们进一步暴力

注意每当碰到 $0$ 的时候需要清理全部区间

接下来暴力从右往左扫描一次，在每个 $i=r$ 区间右端点的位置激活该区间，然后继续向左扫描，当发现有激活的区间要从左侧离开时，放置一个 $0$ ，然后清理当前全部的激活区间

这个解法就不需要证明贪心了，因为相当于我们实际上枚举了全部的区间，只不过将互相包含的区间做了去重

正常做的话一个循环一波大贪心过去就行了，过程中碰到乘积为 $x$ 就放个 $0$ ，没必要学题解先暴力求出所有乘积为 $x$ 的区间，再合并，然后再放 $0$

时间复杂度 $O(nlogn)$

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100005;
int n;
long long p, x;
long long a[MAXN];
int pos[MAXN];
bool inset[MAXN];
vector<int> G[MAXN];

long long qpow(long long x, long long y, long long p)
{
    long long result = 1;
    x = x % p;
    while (y)
    {
        if (y & 1)
        {
            result = (result * x) % p;
        }
        y >>= 1;
        x = (x * x) % p;
    }
    return result;
}

long long inv(long long a, long long p)
{
    return qpow(a, p - 2, p);
}


int main()
{
    scanf("%d %lld %lld", &n, &p, &x);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld", &a[i]);
    }
    if (x == 0)
    {
        for (int i = 1; i <= n; ++i)
        {
            a[i] = a[i] == 0 ? 1 : a[i];
        }
    } else
    {
        for (int i = 1; i <= n; ++i)
        {
            a[i] = a[i] == x ? 0 : a[i];
        }
        long long pre;
        long long ix = inv(x, p);
        map<long long, int> mp;
        for (int i = 0; i <= n; ++i)
        {
            if (a[i] == 0)
            {
                pre = 1;
                mp.clear();
                mp[1] = i;
                continue;
            }
            pre = pre * a[i] % p;
            auto it = mp.find(pre * ix % p);
            if (it != mp.end())
            {
                pos[i] = it->second + 1;
                G[it->second + 1].push_back(i);
            }
            mp[pre] = i;
        }
        stack<int> s;
        for (int i = n; i; --i)
        {
            if (pos[i])
            {
                inset[i] = true;
                s.push(i);
            }
            for (auto &j: G[i])
            {
                if (inset[j])
                {
                    a[i] = 0;
                    while (!s.empty())
                    {
                        inset[s.top()] = false;
                        s.pop();
                    }
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        printf("%lld%c", a[i], " \n"[i == n]);
    }

    return 0;
}