Acw第 101 场周赛

总结

太菜了,只能做简单题,复杂点的只能过样例 😭 ,加油吧

4972. 解方程

给定一个一元二次方程

$$ ax^2 + bx + c = 0 $$

保证给定方程有解，且恰好有两个不同的实数根。

请你对该方程进行求解。

一元二次方程求根公式为：

$$ x = \frac{-b \pm \sqrt{b^2-4ac}}{2a} $$

输入格式

共一行，包含三个整数 a,b,c。

输出格式

共两行，第一行输出较大的根，第二行输出较小的根。

结果保留六位小数。

数据范围

所有测试点满足 −1000≤a,b,c≤1000，保证给定方程有解，且恰好有两个不同的实数根。

输入样例：

1 30 200

输出样例：

-10.000000
-20.000000

题解:

这个比较简单,一次Ac

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    double triangle = sqrt(pow(b, 2) - (4 * a * c));
    double res1 = (-b + triangle) / (2 * a);
    double res2 = (-b - triangle) / (2 * a);
    if (res1 > res2)
        cout << fixed << setprecision(6) << res1 << endl << res2 << endl;
    else
        cout << fixed << setprecision(6) << res2 << endl << res1 << endl;
    return 0;
}

4973. 栈

给定一个栈，初始时栈为空。

你需要依次进行 n 个操作。

每个操作给定一个由小写字母构成的非空字符串，随后进行判断：

• 如果栈中已经包含该字符串，则将该字符串上升至栈顶，栈中其它元素的相对顺序保持不变。
• 如果栈中还未包含该字符串，则将该字符串直接插入到栈的顶部。

所有操作完成后，请你按照从栈顶到栈底的顺序，依次输出栈内所有元素。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个由小写字母构成的非空字符串。

输出格式

按照从栈顶到栈底的顺序，依次输出栈内所有元素。

每个元素占一行。

数据范围

前 55 个测试点满足 1 ≤ n ≤ 10。
所有测试点满足 1 ≤ n ≤ 2×10^5，每个给定字符串的长度范围 [1,10]。

输入样例1：

4
apple
pear
banana
pear

输出样例1：

pear
banana
apple

输入样例2：

8
pen
book
eraser
desk
desk
eraser
book
pen

输出样例2：

pen
book
eraser
desk

题解:

自己

题目让用stack来操作,但是需求不太好实现,就换成了vector

题目中的输出样例可以过,当数据量大的时候就会Time Limit Exceeded

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> arr;
    string temp;
    
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        vector<string>::iterator it = find(arr.begin(), arr.end(), temp);
        if (it != arr.end()) {
            arr.erase(it);
            arr.push_back(temp);
        } else {
            arr.push_back(temp);
        }
    }

    for (vector<string>::reverse_iterator it = arr.rbegin(); it != arr.rend(); it++) {
        cout << *it << endl;
    }
    return 0;
}

正解-逆向推导

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 200010, M = 11;

int n;
char str[N][M];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%s", str[i]);

    unordered_set<string> hash;
    for (int i = n - 1; i >= 0; i -- )
        if (!hash.count(str[i]))
        {
            puts(str[i]);
            hash.insert(str[i]);
        }

    return 0;
}

正解-正向做

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 200010, M = 11;

int n;
int l[N], r[N], idx;
char str[N][M];
unordered_map<string, int> pos;

int insert(int k, int x)
{
    l[x] = k, r[x] = r[k];
    l[r[x]] = x, r[k] = x;
}

void remove(int k)
{
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main()
{
    l[0] = r[0] = 1;
    l[1] = r[1] = 0;
    idx = 2;

    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        char* s = str[idx];
        scanf("%s", s);
        if (pos.count(s))
        {
            int k = pos[s];
            remove(k);
            insert(0, k);
        }
        else
        {
            pos[s] = idx;
            insert(0, idx);
            idx ++ ;
        }
    }

    for (int i = r[0]; i != 1; i = r[i])
        puts(str[i]);

    return 0;
}

4974. 最长连续子序列

给定一个长度为 n 的整数序列 a1,a2,…,an。

给定序列满足，任意两个相邻元素之差的绝对值不超过 1，即对于每个 1 ≤ i <= n，保证 | ai+1 − ai | ≤ 1。

请你找到给定序列的一个尽可能长的连续子序列，要求该连续子序列应满足其中的最大元素与最小元素之差不超过 1。

输出满足条件的最长连续子序列的长度。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数，表示满足条件的最长连续子序列的长度。

数据范围

前 6 个测试点满足 2 ≤ n ≤ 20。
所有测试点满足 2 ≤ n ≤ 10^5,1 ≤ ai ≤ 10^5。

输入样例1：

5
1 2 3 3 2

输出样例1：

4

输入样例2：

11
5 4 5 5 6 7 8 8 8 7 6

输出样例2：

5

题解:

自己

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 1e5 + 10;
int n;
int arr[N];

int main(int argc,char** argv){
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    int answer = 0;

    for(int i = 0; i < n; i++){
        int startValue = arr[i];
        int maxValue = startValue;
        int minValue = startValue;
        
        for(int start = i + 1;start < n; start++){
            maxValue = arr[start] > maxValue ? arr[start] : maxValue;
             minValue = arr[start] < minValue ? arr[start] : minValue;
             int absValue = abs(maxValue - minValue);
             
            if(absValue <= 1){
                answer = start - i + 1 > answer ? start - i + 1 : answer;
            }else{
                break;
            }
        }
    }
    
    printf("%d",answer);
}

正解

提取性质: 合法的序列中只会存在两个不同的元素,一个为x另一个就会为y，y=x+1 or y = x-1

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int w[N], cnt[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);

    int res = 0;
    for (int i = 0, j = 0, s = 0; i < n; i ++ )
    {
        if (!cnt[w[i]]) s ++ ;
        cnt[w[i]] ++ ;

        while (s > 2)
        {
            cnt[w[j]] -- ;
            if (!cnt[w[j]]) s -- ;
            j ++ ;
        }

        res = max(res, i - j + 1);
    }

    printf("%d\n", res);
    return 0;
}

引用

1.第 101 场周赛 竞赛 - AcWing

2. 弹幕里遇到一个很自信的同学 | AcWing第101场周赛：https://www.bilibili.com/video/BV1to4y1w71n/