好想不好写，好写不好想，周赛压轴题到底难度几何？一起来盘一盘！

ACM算法日常

发布于 2021-06-16 16:25:13

4810

文章被收录于专栏：ACM算法日常ACM算法日常

双周赛 53

长度为三且各字符不同的子字符串

给定一个长为

的字符串

用一个长度为

的滑动窗口滑

，可以得到

n - 2

个子串

对于每一个子串，如果每一个字符都只出现了一次，那么称之为好字符串

计算

中所有长为

的好字符串的个数

题解

遍历计算

class Solution {
public:
    bool check(string s)
    {
        return s[1] != s[0] && s[2] != s[1] && s[2] != s[0];
    }
    int countGoodSubstrings(string s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i + 3 <= n && check(s.substr(i, 3))) ans++;
        }
        return ans;
    }
};

数组中最大数对和的最小值

给定长为

的数组

，其中

为偶数

现在把

中元素两两分组，一共分成

\frac{n}{2}

组，每一组的值

a_{i}

为组内两元素的和

现在要求分组，使得

a_{i}

的最大值最小

数据规定

2\leq n\leq 10^5

题解

把数组排序，最大值和最小值配对即可

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < n / 2; ++i) ans = max(ans, nums[i] + nums[n - 1 - i]);
        return ans;
    }
};

后记

本以为是个二分答案，但是看到过题的人实在太多了，发觉应该是个简单的贪心

矩阵中最大的三个菱形和

给定一个

m\times n

的矩阵，降序返回所有正菱形（正方形旋转

45°

）中三个最大的互不相同的菱形和，如果不同的和少于三个，则将它们全部返回。

菱形和表示边所经过的格子的权值和，如果菱形边长为

，那么菱形和就是其所在格子的权值

数据规定

1\leq m,\ n\leq 100

题解

枚举每一个中心点，计算菱形四个顶点所在的位置，然后暴力计算和

时间复杂度

O(m^2n^2\cdot min(m,\ n))

，不过到不了这个极限，因此可以暴力跑

#define pb push_back
const int DX[] = {-1, 0, 1, 0};
const int DY[] = {0, 1, 0, -1};
class Solution {
public:
    bool check(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
    vector<int> getBiggestThree(vector<vector<int>>& grid) {
        set<int> ans;
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int f = 0, l = 1;
                ans.insert(grid[i][j]);
                while (1) {
                    int X[4] = {0}, Y[4] = {0};
                    for (int k = 0; k < 4; ++k) {
                        if (check(i + DX[k] * l, j + DY[k] * l, m, n)) {
                            X[k] = i + DX[k] * l;
                            Y[k] = j + DY[k] * l;
                        }
                        else {f = 1; break;}
                    }
                    if (f) break;
                    else {
                        int temp = 0, x1, x2, y1, y2;

                        x1 = X[0], x2 = X[1];
                        y1 = Y[0], y2 = Y[1];
                        while (x1 <= x2) temp += grid[x1++][y1++];

                        x1 = X[1], x2 = X[2];
                        y1 = Y[1], y2 = Y[2];
                        while (x1 <= x2) temp += grid[x1++][y1--];

                        x1 = X[2], x2 = X[3];
                        y1 = Y[2], y2 = Y[3];
                        while (x1 >= x2) temp += grid[x1--][y1--];

                        x1 = X[3], x2 = X[0];
                        y1 = Y[3], y2 = Y[0];
                        while (x1 >= x2) temp += grid[x1--][y1++];
                        for (int k = 0; k < 4; ++k) temp -= grid[X[k]][Y[k]];
                        l++, ans.insert(temp);
                    }
                }
            }
        }
        while (ans.size() > 3) ans.erase(ans.begin());
        return vector<int>(ans.rbegin(), ans.rend());
    }
};

后记

可以用斜着的前缀和优化到

O(mn\cdot min(m,\ n))

两个数组最小的异或值之和

给定两个长为

的数组

A,\ B

，现在可以重排列

，使得

A,\ B

对应元素异或和最小，返回这个最小值

A,\ B

的异或和指的是

\sum\limits_{i = 1}^{n}A_{i}\oplus B_{i}

数据规定

1\leq n\leq 14

题解

状态压缩

定义

dp\left[j\right]

表示前

count(j)

个位置，

中元素选择情况为

时的异或和最小值，其中

为二进制数，

count(j)

表示

中

的个数

例如

(10101)_{2}

表示前

个位置放置

B_{1},\ B_{3},\ B_{5}

的某一个排列

再例如

(00110)_{2}

表示前

个位置放置

B_{3},\ B_{4}

的某一个排列

考虑计算到位置

，对应

中选择了

个元素，这

个元素有

种排列方式，但如果以第

位置的值划分状态，可以得到

种可能的情况

举例来讲，考虑计算到第

个位置，状态

(10101)_{2}

表示从

中选择了

B_1,\ B_3,\ B_5

的某一个排列放置在前三个位置，那么一共有

3! = 6

种排列情况，但是考虑第三个位置元素的值，最终就只有三种情况，即第三个位置分别放置

B_1,\ B_3,\ B_5

因此，我们完成了状态划分，实际上是一个等价类划分，我们可以依此进行状态转移

举例来理解转移过程，考虑当前选择情况为

(10101)_{2}

，于是

c = 3

，这意味着从

中选择了

B_1,\ B_3,\ B_5

的某一个排列放置在前三个位置

B_{1}

放在位置

，转移为

dp\left[(10101)_{2}\right] \leftarrow dp\left[(00101)_{2}\right] + A_{3}\oplus B_{1}

B_{3}

放在位置

，转移为

dp\left[(10101)_{2}\right] \leftarrow dp\left[(10001)_{2}\right] + A_{3}\oplus B_{3}

B_{5}

放在位置

，转移为

dp\left[(10101)_{2}\right] \leftarrow dp\left[(10100)_{2}\right] + A_{3}\oplus B_{5}

所以状态转移方程如下

dp[i] = min(dp[i - (1 << j)] | i & (1 << j) == 1)

初始情况为 dp[0] = 0，时间复杂度

O(n\cdot 2^n)

class Solution {
public:
    #define INF 0x3f3f3f3f
    int minimumXORSum(vector<int>& A, vector<int>& B) {
        int n = A.size();
        int N = 1 << n;
        vector<int> dp(N, INF);
        dp[0] = 0;
        for (int i = 1; i < N; ++i) {
            int c = 0;
            for (int j = 0; j < n; ++j) {
                if (i & (1 << j)) c++;
            }
            for (int j = 0; j < n; ++j) {
                if (i & (1 << j)) {
                    dp[i] = min(dp[i], dp[i - (1 << j)] + (A[c - 1] ^ B[j]));
                }
            }
        }
        return dp[N - 1];
    }
};

后记

状压

的做法类似于哈密顿回路问题

似乎还能转化为二分图带权匹配，有兴趣的同学可以研究一下，时间复杂度

O(n^3)

单周赛 243

检查某单词是否等于两单词之和

将字符串转为数字，例如 abc = 012 = 12, aaa = 000 = 0, dcac = 3202

给定三个字符串

A,\ B,\ C

，设转化后的数字为

a,\ b,\ c

，判断

a + b

是否等于

题解

封装一个计算函数，直接判断即可

class Solution {
public:
    int trans(string s)
    {
        int ans = 0;
        for (int i = 0; i < s.length(); ++i) {
            int x = s[i] - 'a';
            ans *= 10, ans += x;
        }
        return ans;
    }
    bool isSumEqual(string firstWord, string secondWord, string targetWord) {
        return trans(firstWord) + trans(secondWord) == trans(targetWord);
    }
};

插入后的最大值

给定一个大整数

和一个一位正整数

，你可以把

插在

的任意一位

例如

n = 123,\ x = 4

，你可以得到

4123,\ 1423,\ 1243,\ 1234

再例如

x = -123,\ x = 4

，你可以得到

-4123,\ -1423,\ -1243,\ -1234

现在希望得到插入结果中的最大值，请返回这个值

数据规定

1 <= n.length <= 100000
1 <= n[i] <= 9
1 <= x <= 9

题解

考虑贪心

对于

为正整数的情况，我们只要找到

中第一个比

小的位置，把

插在其前面即可

对于

为负整数的情况，我们只要找到

中第一个比

大的位置，把

插在其前面即可

时间复杂度为线性

class Solution {
public:
    string maxValue(string s, int x) {
        int n = s.length();
        int flag = (s[0] == '-' ? 1 : 0);
        int pos = n;
        if (!flag) {
            for (int i = 0; i < n; ++i) {
                if (s[i] - '0' < x) {pos = i; break;}
            }
        }
        else {
            for (int i = 1; i < n; ++i) {
                if (s[i] - '0' > x) {pos = i; break;}
            }
        }
        string ans = s.substr(0, pos) + string(1, x + '0') + s.substr(pos, n - pos);
        return ans;
    }
};

使用服务器处理任务

给定

个处理器，每个处理器的权值为

s_{i}

给定

个任务，每个任务耗时

t_{i}

第

秒开始处理第

个任务，选择一个 空闲的权值最小下标最小 的处理器来处理这个任务

如果一个处理器被使用，他的下一次空闲时间要在当前的基础上加上任务执行的时间

返回处理每个任务的处理器下标所构成的数组

数据规定

1\leq n,\ m\leq 2\cdot 10^5

题解

使用两个优先队列

pq_{1},\ pq_{2}

维护忙碌服务器和闲置服务器

我们期望在所有的空闲服务器中找到 权值最小下标最小 的服务器

定义好结构体的比较规则后，有两个好处

忙碌服务器的队首元素一定是 最早结束且满足期望 的服务器
闲置服务器的队首元素一定是 满足期望 的服务器

任务

在第

秒可以开始处理，设当前任务处理时间为

先将忙碌服务器队列中空闲的服务器加入闲置服务器队列，接下来

如果存在闲置服务器，取队首元素，将其空闲时间置为

x + i

，扔到忙碌服务器

否则，取忙碌服务器队首元素

，将其空闲时间加上

，扔到忙碌服务器

时间复杂度

O((n + m)logn)

#define pb push_back
struct node1
{
    int cap, idx, time;
    node1() {}
    node1(int _cap, int _idx, int _time):
        cap(_cap), idx(_idx), time(_time) {}
    bool operator < (const node1 &A) const {
        if (time != A.time) return time > A.time;
        if (cap != A.cap) return cap > A.cap;
        return idx > A.idx;
    }
};
struct node2
{
    int cap, idx, time;
    node2() {}
    node2(int _cap, int _idx, int _time):
        cap(_cap), idx(_idx), time(_time) {}
    bool operator < (const node2 &A) const {
        if (cap == A.cap) return idx > A.idx;
        return cap > A.cap;
    }
};
class Solution {
public:
    vector<int> assignTasks(vector<int>& s, vector<int>& t) {
        priority_queue<node1> pq1; // busy CPU
        priority_queue<node2> pq2; // free CPU
        int n = s.size(), m = t.size();
        for (int i = 0; i < n; ++i) pq2.push(node2(s[i], i, 0));
        vector<int> ans;
        for (int i = 0; i < m; ++i) {
            int x = t[i];
            while (!pq1.empty() && pq1.top().time <= i) { // find the free CPU
                node1 temp = pq1.top(); pq1.pop();
                pq2.push(node2(temp.cap, temp.idx, temp.time)); // put free CPU into pq2
            }
            if (!pq2.empty()) { // if pq2 not empty, the top is the ans
                node2 temp = pq2.top(); pq2.pop();
                ans.pb(temp.idx);
                pq1.push(node1(temp.cap, temp.idx, i + x));
            }
            else {
                node1 temp = pq1.top(); pq1.pop();
                ans.pb(temp.idx);
                pq1.push(node1(temp.cap, temp.idx, temp.time + x));
            }
        }
        return ans;
    }
};

准时抵达会议现场的最小跳过休息次数

给定

段路程，每一个路程长度为

d_{i}

，给定一个速度

speed

和一个最小时间

走完一个路程需要休息，需要等待到最近的整数时间才可以再次出发，即消耗时间

\left \lceil \frac{d_{i}}{speed}\right \rceil

也允许跳过休息，可以直接出发，即消耗时间为

\frac{d_{i}}{speed}

计算在规定时间

内走完的情况下，最小的跳过休息次数

数据规定

1\leq n\leq 1000

题解

定义

dp\left[i\right]\left[j\right]

表示走到第

个路段，跳了

次的最小时间

为了避免浮点数运算，我们将所有的路程和时间都乘以

speed

同时，题设所说的 等待到整数时间 等价于 等待到最近的速度的倍数，即 向最近的速度的倍数舍入

例如，路程为

\left[1,\ 3,\ 2\right]

，速度和时间分别为

4,\ 2

，乘以速度后路程和时间变为

\left[4,\ 12,\ 8\right]

和

走完第

条路休息，应当把

\frac{4}{4} = 1

向

舍入，设路程为

，则实际消耗的时间为

(\left \lfloor \frac{x - 1}{speed}\right \rfloor + 1)\cdot speed

对于状态转移，考虑第

条路是否跳过休息，于是有

dp\left[i\right]\left[j\right] = min\left\{dp\left[i - 1\right]\left[j - 1\right] + \frac{d\left[i\right]}{speed},\ \left \lceil dp\left[i - 1\right]\left[j\right] + \frac{d\left[i\right]}{speed}\right \rceil\right\}

一开始将所有

dp\left[i\right]\left[j\right]

设为

\infty

，以及

dp\left[0\right]\left[0\right] = 0

，然后开始状态转移，时间复杂度

O(n^2)

，注意开 long long

#define INF 0x3f3f3f3f
typedef long long LL;
class Solution {
public:
    LL trans(LL x, LL s)
    {
        return ((x - 1) / s + 1) * s;
    }
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        vector<LL> a(dist.begin(), dist.end());
        LL s = speed;
        LL h = hoursBefore * s;
        for (int i = 0; i < a.size(); ++i) a[i] *= s;
        vector<vector<LL>> dp(n + 1, vector<LL>(n + 1, INF));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= n; ++j) {
                if (j != 0) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + a[i - 1] / s);
                }
                if (j != n) {
                    dp[i][j] = min(dp[i][j], trans(dp[i - 1][j] + a[i - 1] / s, s));
                }
            }
        }
        int ans = -1;
        for (int i = 0; i <= n; ++i) if (dp[n][i] <= h) {ans = i; break;}
        return ans;
    }
};

后记

本质上是个

背包，考虑第

个物品选或不选来进行状态转移

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-05-31，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度