Educational Codeforces Round 91 (Rated for Div. 2)(ABCD题解)

题目大意：
要你找到$1<=i<j<k<=n$并且$aj>ai,aj>ak$。
思路：
直接暴力就行了。
代码：

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;

const int maxn = 2e3 + 10;
int a[maxn];
void solved(){
    int n;cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    a[0] = a[n + 1] = 0;
    for(int i = 2; i < n; i++){
        int l = i - 1;
        while(a[i] < a[l] && l >= 0)l--;
        if(l == 0)continue;
        int r = i + 1;
        while(a[i] < a[r] && r <= n + 1)r++;
        if(r == n + 1)continue;
        cout<<"YES"<<endl;
        cout<<l<<" "<<i<<" "<<r<<endl;return ;
    }
    cout<<"NO"<<endl;
}
int main(){
    int t;cin>>t;
    while(t--)
    solved();
    return 0;
}

题面大意：
给你一个字符串只包含石头，剪刀，布，要你构造一个字符串使得它的的值最大，字符串的值等于$1/n{\sum }_{i=1}^{n}win(i)$，$win(i)$表示机器人从下标$i$开始，然后一共我赢的数量。
思路：
容易发现，字符串对我们要构造的字符串的每一位贡献都是$|s|$，所以我们直接求出字符串中出现最多的字符，然后出它的克星就行了。
代码：

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
void solved(){
    string str;cin>>str;
    int r = 0,s = 0,p = 0;
    for(int i = 0 ; i < str.size(); i++){
        if(str[i] == 'R')r++;
        if(str[i] == 'S')s++;
        if(str[i] == 'P')p++;
    }
    char ans;
    if(r > s){
        if(p > r)ans = 'S';
        else ans = 'P';
    }else {
        if(p > s)ans = 'S';
        else ans = 'R';
    }
    string res ;
    for(int i = 0; i < str.size(); i++)res += ans;
    cout<<res<<endl;
}
int main(){
    int t;cin>>t;
    while(t--) solved();
    return 0;
}

题目大意：
给你一个长度为$n$的数组，和一个$x$，问你最多能把数组拆成多少个数组，使得每个数组的值不低于$x$，每个数组的值为这个数组的元素个数乘$min(ai)$。
思路：
贪心；
先对数组降序，然后慢慢找就行了。
代码：

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
ll a[maxn];
bool cmp(ll a,ll b){
    return a > b;
}
/*
1 447153477
348243555
*/
void solved(){
    int n;cin>>n;
    ll x;cin>>x;
    for(int i = 1; i <= n; i++)cin>>a[i];
    sort(a + 1,a + 1 + n,cmp);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(a[i] >= x)ans++;
        else {
            int cnt = 2;
            i++;
            while(i <= n && cnt * a[i] < x)i++,cnt++;
            if(i <= n && cnt * a[i] >= x)ans++;
        }
    }
    cout<<ans<<endl;
}
int main(){
    int t;cin>>t;
    while(t--) solved();
    return 0;
}

题面大意：
给你序列$a,b$，现在问你要将序列$a$转化为$b$，最小消费是多少？，你可以使用两个技能,$1:$选择一个长度为$k$的连续子段，将它全部删除，消费$x$，或者选择消费$y$选择相邻两个数，其中小的从序列中删除。
思路：
像这种题，感觉都没什么思路，所以我们一般先从暴力想，对字符串两两匹配，相同就匹配下一个，不相同，就从$a$中找到相同的，然后记录一下长度和最大值(如果最大值小于b[i]，说明可以选择直接全部$len$次$y$)，当长度大于$k$，我们枚举块数，然后选一个最小值就行了，然后加到答案上继续匹配。
核心：

for(ll o = 1; o * k<= len; o++)
      res = min(res,x * o + (len - o * k) * y);

当前选$o$个连续的长度为$k$的自断，剩下的直接用$y$计算，这里是先用$y$魔法，然后剩下$o$块一次性消除。
代码：

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;

const int maxn = 2e5 + 10;
typedef long long int ll;
ll a[maxn],b[maxn];
/*
23 5
10 3 3
2 1 4 11 8 10 5 6 7 9 12 3 14 13 16 18 21 15 17 19 20 23 22 0
4 6 3 18 23 0
*/
void solved(){
    ll n,m;cin>>n>>m;
    ll x,y,k;cin>>x>>k>>y;
    for(int i = 1; i <= n; i++)cin>>a[i];
    for(int i = 1; i <= m; i++)cin>>b[i];
    b[n + 1] = a[n + 1] = 0;
    if(m == n){
        for(int i = 1; i <= n; i++)
            if(a[i]!=b[i]){
                cout<<"-1"<<endl;return;
            }
        cout<<"0"<<endl;
    }else{
        ll ans = 0;
        for(int i = 1,j = 1; i <= m + 1; i++,j++){
            if(a[j] == b[i])continue;
            ll M = a[j];
            ll len = 0;
            while(j <= n && a[j] != b[i]){
                M = max(a[j],M);
                len++;j++;
            }
            if(j == n + 1){
                cout<<"-1"<<endl;return;
            }
            ll res = 1e18;
            for(ll o = 1; o * k<= len; o++){
                res = min(res,x * o + (len - o * k) * y);
            }
            if((M < b[i]) || M < b[i - 1] && i - 1 >= 1){
                res = min(res,len * y);
            }
            if(res ==1e18){
                cout<<"-1"<<endl;return;
            }
            ans += res;
        }
        cout<<ans<<endl;
    }
}
int main(){
    solved();
    return 0;
}

最后

以上就是虚心鸡为你收集整理的Educational Codeforces Round 91 (Rated for Div. 2)(ABCD题解)的全部内容，希望文章能够帮你解决Educational Codeforces Round 91 (Rated for Div. 2)(ABCD题解)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。