Codeforces 637(Div.2)

A题

题意：给你n包零食，每包零食的重量为c-d~c+d之间，每包零食里面的每片的重量在a-b~a+b之间。现在给你一些数据，问你质量从a-b到a+b的n片能不能构成总质量从c-d到c+d的零食。

思路：这道题的话，我们分别把最小最大求出，比较一下即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n, a, b, c, d;
    cin >> t;
    while (t--)
    {
        cin >> n >> a >> b >> c >> d;
        int minn1 = a - b;
        int minn2 = c - d;
        int maxx1 = a + b;
        int maxx2 = c + d;
        if (maxx1 * n < minn2 || minn1 * n > maxx2)
            cout << "NO" << endl;
        else
            cout << "YES" << endl;
    }
    return 0;
}

B题

题意：定义“顶”：对于任意一个i，若满足a[i] > a[i - 1] 与 a[i] > a[i + 1]，则称i为“顶点”。给定区间长度为k，要求滑动窗口，统计[L，L + k - 1]中“顶点”个数（不含区间端点），“顶点”个数最多且左端点下标最小的的区间，输出该区间的L和共有的“顶点”个数。

思路：这道题的话，预处理一下前面有多少个山峰，sum[i]就是前i个数的山峰数量（包括第i个数），这样区间内的山峰数量就可以计算了。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
using namespace std;
int a[maxn], sum[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n, m;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        memset(sum, 0, sizeof(sum));
        int k = 0, l = 1;
        for (int i = 2; i <= n; i++)
        {
            if (a[i] > a[i - 1] && a[i] > a[i + 1] && i < n)
                sum[i] = sum[i - 2] + 1;
            else
                sum[i] = sum[i - 1];
            if (i >= m && sum[i - 1] - sum[i - m + 1] + 1 > k)
            {
                l = i - m + 1;
                k = sum[i - 1] - sum[i - m + 1] + 1;
            }
        }
        cout << k << " " << l << endl;
    }
    return 0;
}

C题

题意：一个序列生成器按照规则生成序列：依次考虑1~n，对于每个数i，我们为其选择在生成序列中位置，有生成的规则：生成一个数组r，第j个数的值记作r[j]，满足：j <= r[j] <= n，且当前生成序列当中（没有完全生成好，也就是有的位置没有生成的数），第r[j]个位置必须保证没有数生成（换句话说，若在先前操作中该位置已经填上了数了，那么r[j]不可以是该位置的下标），同时r[j]须越小越好（如果3、4和5均可，则选择3，因为值最小）。再生成count数组，记录r数组中每一个值的个数。譬如：r[3] = {2, 2, 3}，则count[4] = {0, 2, 1}（统计出现次数）。言归正传，在生成环节结束后（r和count数组生成完毕了），对于i生成的位置，该位置为count数组中数最大的位置的下标（如果count[4]最大，该数应填在生成序列中的第四个），若有多个位置下的值满足，则在其中选择任意一个位置。给定一个序列p，求是否可以按上述规律生成p。

思路：这道题的话，从1-n填数，在i位置填数，下一个要么在 i+1 的位置填，要么在[1，i-1]之间填。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int a[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int ans = 1, flag = 1;
        for (int i = n; i; i--)
        {
            if (ans == a[i])
                ans++;
            else if (ans < a[i])
                ans = a[i];
            else if (a[i + 1] - a[i] != 1)
            {
                flag = 0;
                break;
            }
        }
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦