2022年6月周赛习题笔记

目录

• 6月4日：ACwing第54场周赛
• • AcWing 4428. 字符串
  • AcWing 4429. 无线网络
  • AcWing 4430. 括号序列
• 6月5日：LeetCode 第 296 场周赛
• • 6090. 极大极小游戏
  • 6091. 划分数组使最大差为 K
  • 6092. 替换数组中的元素
  • 6093. 设计一个文本编辑器

6月4日：ACwing第54场周赛 AcWing 4428. 字符串

题目链接

#include 
#include 
#include 

using namespace std;

int main()
{
    int n;
    string s;
    cin >> n >> s;
    unordered_set<char> S;
    for (auto c : s)
        S.insert(tolower(c));
    if (S.size() == 26) puts("YES");
    else puts("NO");
    return 0;
}

AcWing 4429. 无线网络

题目链接

选择其中一个基站，每次从大到小枚举该基站的半径，每一次抛出去一个点，用于更新另一个基站的半径。当一个基站的半径固定的时候，另外一个基站的半径也一定是固定的。

并且可以知道，最后的结果一定是一个整数，题目中给出"答案四舍五入到个位"是无用的。因为最终圆的边一定在某一个点上，这个点到圆心的半径一定是一个整数。如果半径大于这个点到圆心的距离，那么这个圆是可以缩小的。

排序 O ( l o g n ) O(logn) O(logn)，枚举一个圆的半径 O ( n ) O(n) O(n)，求另一个圆的半径 O ( 1 ) O(1) O(1)，总的时间复杂度 O ( l o g n ) O(logn) O(logn)。

#include 
#include 
#include 

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2010;

int n;
PII s1, s2;
PII q[N];

LL dist(PII a, PII b) {
    LL dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

bool cmp(PII a, PII b) {
    return dist(s1, a) < dist(s1, b);
}

int main() {
    cin >> n >> s1.x >> s1.y >> s2.x >> s2.y;
    for (int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
    sort(q, q + n, cmp);
    LL res = 1e18, r = 0;
    for (int i = n - 1; i >= 0; i--) {
        res = min(res, dist(q[i], s1) + r);
        r = max(r, dist(q[i], s2));
    }
    res = min(res, r);
    printf("%lld\n", res);
    return 0;
}

AcWing 4430. 括号序列

题目链接

题目给出，只有两种变换方法，要么左括号变成右括号，要么右括号变成左括号，变换之后左右括号数量相同。

首先字符串长度必须为偶数，否则返回0；

然后统计字符串中所有左括号和右括号的数量，分别记为 l 、 r l、r l、r。如果它们差的绝对值不为2 ，则一定没有合法方案，输出0。即它们应该满足

• 如果 l > r l > r l>r，那么应该有 l = r + 2 l = r + 2 l=r+2；
• 如果 l < r l < r l<r，那么应该有 r = l + 2 r = l + 2 r=l+2；

当左括号的数量多于右括号的时候，令左括号的值为1，右括号的值为-1，为了满足题目条件对于 s 的任意前缀字符串，其中包含的 ( 的数量均不少于 ) 的数量，可以得出任意前缀字符串的前缀和不能<= 0。从左往右扫描，扫描到第一次出现前缀和< 0，即左括号的数量小于右括号数量少的时候，就需要要修改一个右括号为左括号，这时候可以修改的方案数为前面右括号的数量。对于每一种方案，修改完之后还需要观察后面所有的前缀和是否满足，如果满足，即为答案。

当右括号的数量多于左括号的时候，先将其镜像，然后左右括号互换，将此问题转换为为当左括号的数量多于右括号的情况，用上面的方法求解。

#include 
#include 
#include 

using namespace std;

const int N = 1e6 + 10;

int n;
char s[N];

int work() {
    int cnt = 0, r = 0; // 前缀和cnt，右括号数量r
    for (int i = 0; i < n; i++)
        if (s[i] == '(') cnt++;
        else {
            cnt--; r++;
            if (cnt < 0) {
                cnt += 2;
                for (int j = i + 1; j < n; j++)
                    if (s[j] == '(') cnt++;
                    else {
                        cnt--;
                        if (cnt < 0) return 0;
                    }
                return r; // 前面右括号的数量即为方案数
            }
        }
    return 0;
}

int main() {
    scanf("%d%s", &n, s);
    int l = 0, r = 0;
    for (int i = 0; i < n; i++)
        if (s[i] == '(') l++;
        else r++;
    if (r == l + 2) printf("%d\n", work());
    else if (l == r + 2) {
        reverse(s, s + n);
        for (int i = 0; i < n; i++)
            if (s[i] == '(') s[i] = ')';
            else s[i] = '(';
        printf("%d\n", work());
    } else puts("0");
    return 0;
}

6月5日：LeetCode 第 296 场周赛 6090. 极大极小游戏

题目链接

class Solution {
public:
    vector<int> add(vector<int> q) {
        vector<int> res(q.size() / 2);
        for (int i = 0; i < q.size() / 2; i++) {
            if (i % 2)
                res[i] = max(q[i * 2 + 1], q[2 * i]);
            else res[i] = min(q[i * 2 + 1], q[2 * i]);
        }
        return res;
    }

    int minMaxGame(vector<int> &nums) {
        if (nums.size() == 1) return nums[0];
        vector<int> ans = add(nums);
        while (ans.size() != 1)
            ans = add(ans);
        return ans[0];
    }
};

6091. 划分数组使最大差为 K

题目链接

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

6092. 替换数组中的元素

题目链接

class Solution {
public:
    vector<int> arrayChange(vector<int> &nums, vector <vector<int>> &operations) {
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); i++)
            mp[nums[i]] = i;
        for (auto c: operations) {
            int index = mp[c[0]];
            mp.erase(c[0]);
            mp[c[1]] = index;
            nums[index] = c[1];
        }
        return nums;
    }
};

6093. 设计一个文本编辑器

题目链接

class TextEditor {
public:
    stack<char> a, b;

    TextEditor() {
        a = stack<char>();
        b = stack<char>();
    }

    void addText(string text) {
        for (auto c: text)
            a.push(c);
    }

    int deleteText(int k) {
        int target = k;
        while (k > 0 && !a.empty())
            a.pop(), k--;
        return target - k;
    }

    string cursorLeft(int k) {
        while (!a.empty() && k > 0) {
            b.push(a.top());
            a.pop();
            k--;
        }
        return readLeftChar();
    }

    string cursorRight(int k) {
        while (!b.empty() && k > 0) {
            a.push(b.top());
            b.pop();
            k--;
        }
        return readLeftChar();
    }

    string readLeftChar() {
        if (a.empty()) return "";
        string res = "";
        while (res.size() < 10 && !a.empty()) {
            res += a.top();
            a.pop();
        }
        reverse(res.begin(), res.end());
        // 恢复栈
        for (auto c: res)
            a.push(c);

        return res;
    }
};