牛客春招刷题训练营-2025.03.27题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 杨辉三角的变形

可以打表算出答案为 。
则答案

n = int(input())
if n <= 2:
    print(-1)
elif n % 2 == 1:
    print(2)
elif n % 4 == 0:
    print(3)
else:
    print(4)

中等题 计算日期到天数转换

根据题意计算即可。

days = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
a, b, c = list(map(int, input().split()))
if (a % 4 == 0 and a % 100 != 0) or a % 400 == 0:
    days[2] += 1
print(sum(days[1:b]) + c)

困难题 而后单调

原题链接

首先数组不能有重复元素，否则无解。
将 数组离散化成值域为 的数组 。
离散化后本问题简化为：寻找一段长度为 的区间，使得区间内元素单调递增或单调递减且相邻两个数的差值均为 。
可设前缀和数组 ，。
先寻找单调递增的区间：从 至 枚举 ，设 ，如果 且 则有解。
寻找单调递减的区间，将 数组反转即可。
若均为寻找到，即为无解。

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    vector<int> b(a);
    sort(b.begin(), b.end());
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        if (mp[b[i]]) {
            cout << "NO\n";
            return;
        }
        mp[b[i]] = i + 1;
    }
    vector<int> c(n);
    for (int i = 0; i < n; i++)c[i] = mp[a[i]];
    vector<int> pre(n);
    for (int i = 1; i < n; i++)
        pre[i] = pre[i - 1] + (c[i] > c[i - 1]);
    int l = 0, r = m - 1;
    while (r < n) {
        if (pre[r] - pre[l] == r - l && c[r] - c[l] == r - l) {
            cout << "YES\n";
            return;
        }
        l++;
        r++;
    }
    reverse(c.begin(), c.end());
    fill(pre.begin(), pre.end(), 0);
    for (int i = 1; i < n; i++)
        pre[i] = pre[i - 1] + (c[i] > c[i - 1]);
    l = 0, r = m - 1;
    while (r < n) {
        if (pre[r] - pre[l] == r - l && c[r] - c[l] == r - l) {
            cout << "YES\n";
            return;
        }
        l++;
        r++;
    }
    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}