Codeforces Round #472 A-D

A题：

题意：就是给你一个长度为n的字符串，有三种颜色，其中有一些‘？’的字符代表未着色，你需要找到至少有两种方法染色，同时满足相邻两个字符间不能相同；

思路：有两种染色方法的前提:首先给定的字符串中不能出现相邻相同的字符；只要满足这三种条件都可以：‘？’出现在首或尾，‘？’出现在相同字符之间，'?'连续出现两次以上；

#include<iostream>

#include<cstring>

using namespace std;

int main()

{

    int n;

    string s;

    cin>>n>>s;int cnt=,flag=;

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

    {

        if(s[i]=='?')

        {

            if(i==||i==n-)cnt+=;

            else if(s[i-]==s[i+])cnt+=;

            else if(s[i-]=='?'||s[i+]=='?')cnt+=;

        }

        else if(i<n-&s[i]==s[i+])flag=;

    }

    if(flag||cnt<)cout<<"No"<<endl;

    else cout<<"Yes"<<endl;

    return ;

}

B题

题意：给定一种操作，即对于某非空的正整数集合的集合R，C，对于R_i和C_i，填充网格中R_i行与C_i列相交点为黑色，且R和C中任意两集合互斥。对于某网格，如能从空白网格经这样的操作变成该网格则输出“Yes”，否则输出“No”。

思路：暴力就ok了。。

#include<iostream>

#include<cstring>

using namespace std;

int n,m;

string s[];

bool check(int x,int y)

{

    for(int i=;i<m;i++)

    {

        if(s[x][i]!=s[y][i])return ;

    }

    return ;

}

int main()

{

    cin>>n>>m;

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

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

    {

        for(int j=;j<m;j++)

        {

            for(int c=i+;c<n;c++)

            {

                if(s[i][j]==s[c][j]&&s[i][j]=='#')

                {

                    if(!check(i,c))

                    {

                        cout<<"No"<<endl;

                        return ;

                    }

                }

            }

        }

    }

    cout<<"Yes"<<endl;

    return ;

}

C题

题意：给定一个n长的数组，找到3个数，其下标分别为i，j，k，其中i<j<k，满足(a[k]-a[j])/(a[k]-a[i])最大，同时a[k]与a[i]的差值不能超过给定的U；

思路：排序后枚举i，二分查找a[k]的最大值，要满足a[k]-a[j]最大，即j最小，即j=i+1；不断更新ans即可，但要注意精度问题（因为这个wa了几次orz

#include<iostream>

#include<algorithm>

#include<cstdio>

#define inf 0x3f3f3f3f

using namespace std;

double a[];

int main()

{

    int n,d;

    cin>>n>>d;

    double ans=-;

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

    sort(a,a+n);

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

    {

        int t=lower_bound(a,a+n,a[i]+d)-a;

        if(t>=n)t=n-;

        while(a[t]>a[i]+d&&t>i+)t--;

        if(a[t]-a[i]<=d&&t>i+&&t<n)ans=max(ans,1.0*(a[t]-a[i+])/(a[t]-a[i]));

    }

    printf("%.11llf\n",ans);

    return ;

}

D题

题意：一个人每天对河流水位进行标记，给定n天严格大于河流水位的标记数，求每天在当天河流水位下的标记数的总和；

思路：由于每天的水位下的标记数=总标记数-a[i]-1，要使得每天的标记数最小，我们就需要使得到当天的总标记数最小；只要a[i]+1<=前一天的总标记数，那么当天的总标记数就可以不用增加；否则，当天的标记数就要增加，因为每天的标记数最多+1，所以如果a[i]+1>前一天的总标记数+1，当天的总标记数=a[i]+1,但是前一天的标记数也需要更新，所以弄一个循环就可以解决；

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long LL;

const int maxn=1e5+;

LL a[maxn],cnt[maxn];

int main()

{

    int n;

    cin>>n;

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

    cnt[]=;

    LL ans=;

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

    {

        if(a[i]+>cnt[i-])

        {

            if(a[i]>cnt[i-])cnt[i]=a[i]+;

            else cnt[i]=cnt[i-]+;

        }

        else cnt[i]=cnt[i-];

    }

    for(int i=n-;i>=;i--)if(cnt[i+]-cnt[i]>)cnt[i]=cnt[i+]-;

    for(int i=;i<n;i++)ans+=cnt[i]-a[i]-;

    cout<<ans<<endl;

    return ;

}

巴特西

Codeforces Round #472 A-D

最新文章

热门文章