acwing 第63场周赛【2022.08.06】

桃扇骨 2023-09-28 18:54 71阅读 0赞

#### acwing第63场周赛【2022.08.06】 ####

*  一、4503. 数对数量
 *   *  1. 题目描述
     *  2. 思路分析
     *  3. 代码实现
 *  二、4504. 字符串消除
 *   *  1. 题目描述
     *  2. 思路分析
     *  3. 代码实现
 *  三、4505. 最大子集
 *   *  1. 题目描述
     *  2. 思路分析
     *  3. 代码实现
 *  四、周赛总结

## 一、4503. 数对数量 ##

### 1. 题目描述 ###

![在这里插入图片描述][7c926afbbfdf45fb915ff52f631071ed.png]

### 2. 思路分析 ###

签到题，只需暴力枚举出三个条件的整数对`(x, y)`的个数即可。

### 3. 代码实现 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int a, b, n;
        int res = 0;
        cin >> a >> b >> n；
        
        for (int i = 0; i <= a; i ++ ) 
        {
            for (int j = 0; j <= b; j ++ )
            if (i + j == n) res ++;
        }
        cout << res << endl;
        
        return 0;
    }

## 二、4504. 字符串消除 ##

### 1. 题目描述 ###

![在这里插入图片描述][2ebbb8290cf54a7fb9fa8a184961f6a7.png]

### 2. 思路分析 ###

1.  使用栈进行维护，首先将第一个字符压入栈中，依次枚举每个字符
    
     *  如果栈不为空且该字符于栈顶元素相同，则栈顶元素出栈，并且`ans++`；
     *  否则将该字符压入栈中；
2.  如果`ans`为奇数，则先手必赢；如果`ans`为偶数，则先手必输。

### 3. 代码实现 ###

#include <bits/stdc++.h>
    #include <cstring>
    
    using namespace std;
    
    const int N = 1e5 + 10;
    
    char a[N];
    stack<char> stk;
    
    int main()
    {
        int res = 0;
        scanf("%s", a);
    
        stk.push(a[0]);
        for (int i = 1; i < strlen(a); i ++ )
        {
            if (stk.size() > 0 && a[i] == stk.top())
            {
                stk.pop();
                res ++;
            }
            else
            {
                stk.push(a[i]);
            }
        }
        if (res % 2 == 0) cout << "No" << endl;
        else cout << "Yes" << endl;
    
        return 0;
    }

## 三、4505. 最大子集 ##

### 1. 题目描述 ###

![在这里插入图片描述][65c5843477b24d0fa876c0523182f110.png]

### 2. 思路分析 ###

提示：集合最大可能的大小是3，最小的大小不会小于1，三个数的情况是等差数列。

1.  首先把所有数放入哈希集合；
2.  枚举最小值，以及公差（最多30种公差），找到长度3以内的最长序列；
3.  剪枝：找到长度为3的序列就直接结束算法。

### 3. 代码实现 ###

#include <bits/stdc++.h>
    
    using namespace std;
    
    const int N = 200010, M = 1999997, INF = 0x3f3f3f3f;
    
    int n;
    int q[N], h[M];
    
    int find(int x)
    {
        int t = (x % M + M) % M;
        while (h[t] != INF && h[t] != x)
            if ( ++ t == M)
                t = 0;
        return t;
    }
    
    int main()
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
        sort(q, q + n);
    
        memset(h, 0x3f, sizeof h);
    
        int res[3], s[3];
        int rt = 0, st = 0;
        for (int i = 0; i < n; i ++ )
        {
            for (int j = 0; j <= 30; j ++ )
            {
                int d = 1 << j;
                s[0] = q[i], st = 1;
                for (int k = 1; k <= 2; k ++ )
                {
                    int x = q[i] - d * k;
                    if (h[find(x)] == INF) break;
                    s[st ++ ] = x;
                }
                if (rt < st)
                {
                    rt = st;
                    memcpy(res, s, sizeof s);
                    if (rt == 3) break;
                }
            }
            if (rt == 3) break;
            h[find(q[i])] = q[i];
        }
    
        printf("%d\n", rt);
        for (int i = 0; i < rt; i ++ )
            printf("%d ", res[i]);
    
        return 0;
    }

## 四、周赛总结 ##

本次周赛只ac了前两道，第三题想复杂了就没有ac出来，争取下一次周赛ak。

**关注博主不迷路，内容持续更新中。**

[7c926afbbfdf45fb915ff52f631071ed.png]: https://img-blog.csdnimg.cn/7c926afbbfdf45fb915ff52f631071ed.png
[2ebbb8290cf54a7fb9fa8a184961f6a7.png]: https://img-blog.csdnimg.cn/2ebbb8290cf54a7fb9fa8a184961f6a7.png
[65c5843477b24d0fa876c0523182f110.png]: https://img-blog.csdnimg.cn/65c5843477b24d0fa876c0523182f110.png