0%

Codeforces - Round 852 Div 2

Contestant(alt). Rank 6738. Rating -86 (+414 -500).

A. Yet Another Promotion

题意

定义两天内提供购物服务,每天的货物价格分别为 ,在第一天存在促销活动,购买 个货物后会赠送一个。输出购买 个货物的最少花费。

思路

对于 个所需货物, 分别为第一天和第二天的价格,那么我们只需分类讨论即可:

  1. 前者小,那么我们将能参与促销的货物全都在第一天购买,也就是总共有 个货物是参与了促销。此时,我们得到了 个货物,那么剩余的货物就作为正常购买,我们用 购买即可;
  2. 后者小,直接全都在第二天买即可。

时间复杂度:

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int a, b, n, m;
        cin >> a >> b >> n >> m;
        cout << min(n * b, (n / (m + 1)) * m * a + (n - (n / (m + 1)) * (m + 1)) * min(a, b)) << '\n';
    }
    return 0;
}

一个大铸币没看懂题卡了半天

B. Fedya and Array

题意

给出如下定义:

若一个元素的相邻元素都比它大,那么定义其为 local minimum;若一个元素的相邻元素都比它小,那么定义其为 local maximum

给定一个首尾相连的序列中 local maximum 的总和和 local minimum 的总和 ,构建该序列,满足相邻数相差 ,且长度最短。

思路

显然, 一定是一个符合条件的序列,下面我们来证明一下可行性:

为相邻的 local maximumlocal minimum ,那么对于 ,想要得到 ,就必须得有 个数字,因而我们可以得到下面的式子:

化简即可得到 ,证毕。

时间复杂度:

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N];

signed main() {
    ios::sync_with_stdio(0);
    int t, x, y;
    cin >> t;
    while(t --){
        cin >> x >> y;
        vector<int> ans;
        for(int i=x;i>y;i--) ans.emplace_back(i);
        for(int i=y;i<x;i++) ans.emplace_back(i);
        cout << ans.size() << '\n';
        for(auto &i : ans) cout << i << ' ';
        cout << '\n';
    }
    return 0;
}

好妙的做法

C. Dora and Search

题意

给定一个排列,输出一段连续区间的左右端点的下标,满足两个端点既不是区间内的最大值,也不是区间内的最小值。

思路

我们可以用类似双指针的方法,从两侧开始夹逼,只要去除区间外的点后,最大值和最小值都不在端点,那就直接输出。

时间复杂度:

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10, inf = 0x3f3f3f3f;

int a[N];

signed main() {
    ios::sync_with_stdio(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        for(int i=0;i<n;i++) cin >> a[i];
        int l = 0, r = n - 1, vl = 1, vr = n;
        while(l <= r){
            if(a[l] == vl) l ++, vl ++;
            else if(a[l] == vr) l ++, vr --;
            else if(a[r] == vl) r --, vl ++;
            else if(a[r] == vr) r --, vr --;
            else break;
        }
        if(l <= r) cout << l + 1 << ' ' << r + 1 << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}

不是排列的话就只有找拐点了