首页 > 其他 > 详细

Codeforces Round #535 (Div. 3)

时间:2020-03-22 23:49:48      阅读:65      评论:0      收藏:0      [点我收藏+]

Codeforces Round #535 (Div. 3)

A. Two distinct points

题意:从两个关系任意的区间取两个不同的数。(q≤500,1≤l,r≤109

思路:取两个不同的端点即可。

技术分享图片
#include <bits/stdc++.h>
using namespace std;
void solve(){
    int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
    for(int i:{l1,r1})
        for(int j:{l2,r2})
            if(i!=j){
                cout<<i<< <<j<<"\n";
                return;
            }
}
int main()
{
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}
View Code

B. Divisors of Two Integers

题意:给出含有两个数因子(包含1和该数本身)的数组,找出这两个数。(2≤n≤128,1≤di≤104

思路:记录每个因子出现的次数,最大因子即为第一个数,消去该数因子,余下最大因子即为第二个数。

技术分享图片
#include <bits/stdc++.h>
using namespace std;
const int M=11000;
int cnt[M];
int main()
{
    int n;cin>>n;
    int mx=0;
    for(int i=0;i<n;i++){
        int t;cin>>t;
        ++cnt[t];
        mx=max(mx,t);
    }
    for(int i=1;i<=mx;i++)
        if(mx%i==0) --cnt[i];
    for(int i=mx;i>=1;i--)
        if(cnt[i]){
            cout<<i<< <<mx<<"\n";
            break;
        }
    return 0;
}
View Code

C. Nice Garland

题意:一条长为n的灯带,可能有Red,Green,Blue三种颜色,找出使相同颜色间距可被3整除的最小替换次数。(1≤n≤2x105

思路:枚举哪种排列替换次数最小即可。

技术分享图片
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;string s;cin>>n>>s;
    char p[3]={R,G,B};sort(p,p+3);
    int mi=INT_MAX;string ans;
    do{
        int cnt=0;string t=s;
        for(int i=0;i<n;i++)
            if(t[i]!=p[i%3])
                t[i]=p[i%3],++cnt;
        if(cnt<mi) mi=cnt,ans=t;
    }while(next_permutation(p,p+3));
    cout<<mi<<"\n"<<ans<<"\n";
    return 0;
}
View Code

D. Diverse Garland

题意:找出使相邻两个颜色不同的最小替换次数。

思路:贪心,如果si和si+1颜色相同,根据si和si+2的颜色改变si+1的颜色即可,因为改变后者带来的收益不会低于改变前者

技术分享图片
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;cin>>n;
    string s;cin>>s;s+=" ";
    int ans=0;
    for(int i=0;i<n;i++)
        if(s[i]==s[i+1])
            for(char c:{R,G,B})
                if(s[i]!=c&&s[i+2]!=c){
                    ++ans,s[i+1]=c;
                    break;
                }
    cout<<ans<<"\n"<<s<<"\n";
    return 0;
}
View Code

 

Codeforces Round #535 (Div. 3)

原文:https://www.cnblogs.com/Kanoon/p/12548478.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!