2024年期末考试复盘

youhualiuh / 2024-01-17 / 原文

现在开始新的复盘，对喽我这个又导航的直接题题目会有的，开森——>

A.猫猫与广告

思路：

就是矩形能不能把另外一个放进去对应边比对应边那么我们开始吧不过我用的是一个内置函数

总链接：猫猫与广告 (nowcoder.com)

上代码Code

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

int main() {
    int a, b, c, d; cin >> a >> b >> c >> d;
    //长对长 短对短
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);
    return cout << (((a <= c && b <= d) || (a <= d && b <= c)) ? "YES\n" : "NO\n"), 0;
}

B.最大的差

思路：

就是最大减去最小

总链接：最大的差 (nowcoder.com)

直接上Code

#include<bits/stdc++.h>
using namespace std;
//最大值减去最小值
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    int minn = *min_element(a.begin(), a.end());
    int maxn = *max_element(a.begin(), a.end());
    return cout << maxn - minn << '\n', 0;
}

C.吐泡泡

思路：

就是栈的模拟这题就是先执行 o o 因为他会变成 O . O O再执行其次特判 top > 0的时候因为（++top）我的下标索引是从 0 开始的最后输出记得换行就行

总链接：吐泡泡 (nowcoder.com)

补题链接：A-吐泡泡_基础组期末考试补题 (nowcoder.com)

话不多说Code请:

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e2 + 5;

char arr[N];    

int main()
{
    IO;
    string s;
    while (cin >> s) {
        int top = -1;
        for (auto& x : s) {
            arr[++top] = x;
            if (arr[top] == 'o' && arr[top - 1] == 'o' && top > 0) {
                arr[--top] = 'O';
            } 
            if (arr[top] == 'O' && arr[top - 1] == 'O' && top > 0) {
                top -= 2;
            }
        }
        arr[++top] = '\0';
        cout << arr << '\n';
    }
    return 0;
}

D.小红的ABC

思路：

/* 
回文字符串 aa 是一种
          aba 也是一种
          abc 就不是 a or b or c
          是 只有一个 题目说直接-1
举个例子
aabbcc
就这个题目意思是求出最小的回文字符串 你是要遍历全部吗, nonono
low 了吧 我们只要找到两个 两个找不到找三个，那么不久行了
因为abcd aa abbb 等等你会发现 他的最短长度是在1 - 2 - 3里徘徊的
证毕!
*/

首先寻找最小长度的字符串，那么好了只有三种情况-1，2， 3那么好，我们就可以直接开始找了，为什么只有这三种你可以试着推一下

总题：小红的ABC (nowcoder.com)

补题： B-小红的ABC_基础组期末考试补题 (nowcoder.com)

直接上Code:

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int main()
{
    IO;
    string s; cin >> s;
    int n = s.size();
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) return cout << 2 << '\n', 0;
    }
    for (int i = 2; i < n; i++) {
        if (s[i] == s[i - 2]) return cout << 3 << '\n', 0;
    }
    return cout << -1 << '\n', 0;
}

E.主持人的烦恼

思路：

首先是找组，小于m的就加一并且直接进行下下个，前提是排好序，计数就行

/* 
两两同学来组队 颜值差>= m就会背嫌弃,所以说 < m就行
最多能有几组, 需要注意一个人只能出现一个组中就是不能花心(HaHa)

举一下  4 3
        1 3 3 2
首先排序 1 2 3 3
abs(1 - 2) 在 n < m 
abs(3  - 3) 在 n < m
所以有两组
那么我这个方法你可以试试怎么写 加油!
*/

补题：C-主持人的烦恼_基础组期末考试补题 (nowcoder.com)

代码

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
    
int main()
{
    IO;
    int n, m;
    while (cin >> n >> m) {
        int cnt = 0;
        vector<int>a(n);
        for (auto& x : a) cin >> x;
        sort(a.begin(), a.end());
        for (int i = 1; i < n; i++) {
            if (a[i] - a[i - 1] < m) {
                cnt ++;
                i ++;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

F.鹏

思路：

这题题目看仔细上升平飞下降但是平飞可以没那么就好了他的条件就告诉你了，直接跟着他来就行

条件是 a[i] > a[i - 1] and a[i] >= a[i + 1]；

补题：D-鹏_基础组期末考试补题 (nowcoder.com)

代码

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

int main()
{
    IO;
    int n, cnt = 0; cin >> n;
    vector<int>a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i < n; i++) {
        if (a[i] > a[i - 1] && a[i] >= a[i + 1]) {
            cnt ++;
        }
    }
    return cout << cnt << '\n', 0;
}

G.游游的排列统计

思路：

典型的DFS搜索题，判断条件加个if就行

补题：E-游游的排列统计_基础组期末考试补题 (nowcoder.com)

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 2e2 + 10;    
//素小 只有2 3 5 7 11 13 17 19所以用不着
bool st[N], vis[N];    
int n, res;

void dfs(int step, int end) {
    //也可以在if 里判断素相邻的相加是不是素数
    if (step == n + 1) {
        res ++;
        return ;
    }
//相邻
    for (int i = 1; i <= n; i++) {
        if (!vis[i] && !st[i + end]) {
            vis[i] = 1;
            dfs(step + 1, i);
            vis[i] = 0;
        }
    }
}

int main()
{
    IO;
    st[2] = st[3] = st[5] = st[7] = st[11] = st[13] = st[17] = st[19] = 1;
    cin >> n;
    dfs(1, 100);
    return cout << res << '\n', 0;
}

H. 汀博尔

思路：

二分答案法

首先这个check函数是来判断如果这个值大于或等于 L，则累加到 sum 中。如果 sum 大于或等于 S，则返回1，否则返回0。

<^-^>

最差的情况就是一棵树刚刚长到max(S,L)，这样就没别的树什么事了，所以上界r=

max(S, L) / Ma

下面Ma统计为S L 的最差考虑所以 1e18这样写肯定会导致Tle是减少了范围，增大我们成功，哈哈

补题：F-汀博尔_基础组期末考试补题 (nowcoder.com)

#include<bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;

ll A[N], H[N];
ll n, S, L, Ma;
bool check(ll mid)
{
    ll sum = 0;
    for(int i = 0; i < n; i++)
    {
        ll x = H[i] + mid * A[i];
        if(x >= L) sum += x;
        if(sum >= S) return 1;
    }
    return 0;
}
int main()
{
    IO;
    cin >> n >> S >> L;
    for(int i = 0; i < n; i++) cin >> H[i];
    for(int i = 0; i < n; i++)
    {
        cin >> A[i]; Ma = max(Ma, A[i]);
    }
    ll l = 0, r = max(S, L) / Ma;
    while(l <= r)
    {
        ll mid = (l + r) / 2;
        if(check(mid)) r = mid - 1;
        else l = mid + 1;
    }
    return cout << l << '\n', 0;
}