Educational Codeforces Round 121 (Rated for Div. 2) unr场 A B C

56 阅读 0 评论 37 点赞

我是靠谱客的博主飘逸睫毛膏，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 121 (Rated for Div. 2) unr场 A B C，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Educational Codeforces Round 121 (Rated for Div. 2) A B C

A. Equidistant Letters

思路： 每个字母在里面出现不超过两次且使每一对出现两次的字母之间的距离相同。那么直接 $s o r t$ 结束

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
void solve(){
    string s;
    cin>>s;
    sort(s.begin(),s.end());
    cout<<s<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

B. Minor Reduction

思路： 因为题目要求使得一次合并之后留下来的数尽可能的大，那么容易发现如果有两个数合并能够进位一定大于所有不能进位的情况，而又因为进位的母位为必定是 $1$ ，为了使其对原值损耗最小那么一定是尽可能从低位进位。如果都没有进位，因为两个数相加会跟接近于 $10$ ，所以这个相加尽可能靠近高位，且在都没有进位下一定是最高位。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
void solve(){
    string s;
    cin>>s;
    for(int i=s.size()-1;i>=1;i--){
        if(s[i]-'0'+s[i-1]-'0'>=10){
            for(int j=0;j<i-1;j++){
                cout<<s[j];
            }
            cout<<(s[i]-'0'+s[i-1]-'0');
            for(int j=i+1;j<s.size();j++){
                cout<<s[j];
            }
            cout<<endl;
            return ;
        }
    }
    cout<<s[0]-'0'+s[1]-'0';
    for(int i=2;i<s.size();i++)cout<<s[i];
    cout<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C. Monsters And Spells

思路： 将本题转换为区间和并问题(Acwing算法基础贪心专题)，具体代码加注释看代码。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=110;
int k[N],h[N];
PII a[N];
vector<PII>S;
signed main(){
    int t;
    cin>>t;
    while(t--){
       int st=-2e9,end=-2e9;
       int n;
       cin>>n;
       for(int i=1;i<=n;i++)cin>>k[i];
       for(int i=1;i<=n;i++)cin>>h[i];
       for(int i=1;i<=n;i++){
           a[i]={k[i]-h[i]+1,k[i]};//存入n个区间，每个点的始末位置
       }
       sort(a+1,a+1+n);//排序然后进行区间和并
       int res=0;
       S.clear();//清空
       for(int i=1;i<=n;i++){
           if(end<a[i].first){
               if(end!=-2e9)S.push_back({st,end});//如果end!=-2e9说明前面存在一个区间，那么将他存入。
               st=a[i].first,end=a[i].second;//更新st和end为新一个区间的始末
           }
           else if(a[i].second>end){//表示重叠了，那么将两个区间合并
               end=a[i].second;
           }
       }
       if(st!=-2e9&&end!=-2e9)S.push_back({st,end});//存入最后一个区间
       for(auto x:S){
           res+=(x.second-x.first+1)*(x.second-x.first+2)/2;//套公式1+2+3+4..+100=...
       }
       cout<<res<<endl;
    }
    return 0;
}