Codeforces Round 253 (Div. 2)

layout: post

title: Codeforces Round 253 (Div. 2)

author: "luowentaoaa"

catalog: true

tags:

mathjax: true

- codeforces

- 模拟栈

- 贪心

传送门

A.Anton and Letters (签到)

题意

判断字符串里面有多少个不同字符

思路

直接set一下

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

const int maxn=2e5+50;

const ll inf=0x3f3f3f3f3f3f3f3fLL;

set<char>st;

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    string s;

    getline(cin,s);

    int len=s.size();

    for(int i=0;i<len;i++){

        if(s[i]>='a'&&s[i]<='z')st.insert(s[i]);

    }

    cout<<st.size();

    return 0;

}

B.Kolya and Tandem Repeat (暴力模拟)

题意

给你一个字符串,你可以在末尾添加K个任意字符 ,让你找出一个最长的重复两次的字串

思路

直接暴力模拟

对于每个字串长度,字串起点,开始判断，复杂度n^3

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

const int maxn=2e5+50;

const ll inf=0x3f3f3f3f3f3f3f3fLL;

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    string ss;

    cin>>ss;

    string s="";s+='*';s+=ss;

    int k;

    cin>>k;

    for(int i=0;i<k;i++){

        s+='*';

    }

    int ans=0;

    int len=s.size()-1;

    for(int i=1;i<len;i++){

        for(int j=1;j<len;j++){

            if(i+2*j-1>len)continue;

            int head=i,tail=i+j,flag=0;

            for(int k=1;k<=j;k++){

                if(s[head+k-1]=='*'||s[tail+k-1]=='*'||s[head+k-1]==s[tail+k-1])continue;

                flag=1;

            }

            if(!flag)ans=max(ans,j*2);

        }

    }

    cout<<ans;

    return 0;

}

C.Borya and Hanabi (大模拟,二进制模拟)

题意

现在有五种花色五种数字组成的二十五张牌，你手里有诺干张牌，每次你可以询问一种颜色和一种数字，你会得到所有这个花色/数字牌的位置，问你最少多少次可以把所有的牌分类

思路

把题目抽象成一个二维坐标，花色为横坐标，数字为纵坐标，每次可以连接一条线，把一条线上的牌找到,对于一张牌有两种找到方法，

1.这张牌被两条线连接，也就是花色和数字都固定了，

2.这张牌的其他花色或其他数字都被找到了，那么剩下的就只有他了

可以发现我们最多只要连接十条线，所以我们可以直接子集模拟一下十条线的搭配

然后暴力判断能否在这种情况分出任意两张牌

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

const int maxn=2e5+50;

const ll inf=0x3f3f3f3f3f3f3f3fLL;

int x[maxn];

int y[maxn];

void who(string s,int i){

    char top=s[0];

    if(top=='B')x[i]=0;

    else if(top=='Y')x[i]=1;

    else if(top=='W')x[i]=2;

    else if(top=='G')x[i]=3;

    else x[i]=4;

    y[i]=s[1]-'1';

}

int n;

int bit(int i){return 1<<i;}

bool check (int sta) {

    for(int i=0;i<n;i++){

        for(int j=0;j<n;j++){

            if(x[i]==x[j]){

                if( y[i]!=y[j] && (sta&bit(y[i]+5))==0&& (sta&bit(y[j]+5))==0  )return false;

            }

            else{

                if( (sta&bit(x[i])) || (sta&bit(x[j])) )continue;

                if(y[i]!=y[j] && ((sta&bit(y[i]+5)) || (sta&bit(y[j]+5)) ))continue;

                return false;

            }

        }

    }

    return true;

}

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    cin>>n;

    string s;

    for(int i=0;i<n;i++){

        cin>>s;

        who(s,i);

    }

    int ans=inf;

    for(int sta=0;sta<(1<<10);sta++){

        //cout<<bitset<11>(sta)<<endl;

        int num=0;

        for(int i=0;i<5;i++){

            if(sta&(1<<i)){

                num++;

            }

            if(sta&(1<<(i+5))){

                num++;

            }

        }

        if(check(sta))ans=min(ans,num);

    }

    cout<<ans<<endl;

    return 0;

}

D.Andrey and Problem（贪心）

题意

你有N个朋友，每个朋友都有百分之a[i]的几率给你出题，你现在只想要一道题，

想知道你选择哪些朋友给只出一题的几率最大，输出最大几率

例如 n=2

a1=0.1 a2=0.2

答案是 0.1×0.8 + 0.9×0.2=0.26

思路

一开始我是直接DP背包的然后发现错了，结果答案直接排序一下，暴力枚举就行了，我也不知道怎么证明...感觉很奇怪

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

const int maxn=5e4+50;

const ll inf=0x3f3f3f3f3f3f3f3fLL;

double dp[maxn];

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int n;

    cin>>n;

    double yes,no;

    for(int i=1;i<=n;i++)cin>>dp[i];

    sort(dp+1,dp+1+n,[](double a,double b){

         return a>b;});

    yes=dp[1],no=1.0-dp[1];

    for(int i=2;i<=n;i++){

        double nowyes,nowno;

        nowyes=dp[i]*(no)+(1-dp[i])*(yes);

        if(nowyes>yes){

            yes=nowyes;

            no=no*(1-dp[i]);

        }

    }

    cout<<fixed<<setprecision(10);

    cout<<yes;

    return 0;

}

E.Artem and Array (模拟栈，贪心)

题意

给你N个数,这N个数相邻，你每次可以删除一个数，然后得到这个数周围两个数的最小值，（如果有一边没有数字只能获得零值）让你求把这N个数全部删除的值

思路

在纸上模拟一下，如果要最优那就是一开始把小的都删除(等于的也要删除)，最后留下的都是比较大的，会发现留下的数组是一个先递增再递减的数组，并且最大和第二大的值是相邻的无法取到，所以答案就是前面删除获取的值和后面剩下的数组的前n-2小的值

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

const int maxn=2e6+50;

const ll inf=0x3f3f3f3f3f3f3f3fLL;

int n;

ll a[maxn];

ll ans;

ll st[maxn];

int top=0;

int main()

{

    std::ios::sync_with_stdio(false);

    std::cin.tie(0);

    std::cout.tie(0);

    int n;

    cin>>n;

    for(int i=1;i<=n;i++){

        ll x;

        cin>>x;

        while(top>=2&&st[top-1]>=st[top]&&x>=st[top]){

            ans+=min(st[top-1],x);

            top--;

        }

        st[++top]=x;

    }

    sort(st+1,st+top+1);

    for(int i=1;i<=top-2;i++){

        ans+=st[i];

    }

    cout<<ans<<endl;

    return 0;

}

巴特西