Codeforces Round #226 div2(待更新)

A题

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

int a[105];

int main()
{
    int n,m,i;
    while(cin>>n>>m)
    {
        for(i=1;i<=n;i++)
            cin>>a[i];
        int ma=0;
        for(i=1;i<=n-1;i++)
            if(a[i]-a[i+1]>ma)
                ma=a[i]-a[i+1];
        ma-=m;
        if(ma>0) cout<<ma<<endl;
        else cout<<"0"<<endl;
    }
    return 0;
}


B题:

找一个串有多少个子串是包含bear的。

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

char a[5005];
char b[5];

int main()
{
    int i;
    while(cin>>a)
    {
        int len=strlen(a);
        if(len<4)
        {
            puts("0");
            continue;
        }

        long long l,r;
        long long res=0;

        int q=1;
        for(i=0;i<len-3;i++)
        {
            b[0]=a[i];
            b[1]=a[i+1];
            b[2]=a[i+2];
            b[3]=a[i+3];
            b[4]=‘\0‘;

            l=q;
            q++;
            r=len-i-3;
            if(strcmp(b,"bear")==0)
            {
                //cout<<l<<" "<<r<<endl;
                res+=l*r;
                q=1;
            }
        }

        cout<<res<<endl;
    }
    return 0;
}



C题:

题目大意:很明显的需要素数分解,范围是O(10^7),光筛选素数的复杂度就是O(10^7*log(10^7)),然后后面还需要输入哪些数字,然后查询,查询当然是O(1)的,很显然需要预处理,当时想不开,实际上在筛选的时候就可以预处理,详见代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;

bool mark[10000005];
int num[10000005];
long long dp[10000005];

void sxprime()
{
    int i;
    for(i=0;i<=1e7;i++)
    {
        mark[i]=true;
        dp[i]=0;
    }

    for(i=2;i<=1e7;i++)
    {
        if(mark[i])
        {
            dp[i]+=num[i];
            for(int j=i*2;j<=1e7;j+=i)
            {
                mark[j]=false;
                dp[i]+=num[j];
            }
        }
    }
}

int main()
{
    int i;
    int n,m,x;
    while(~scanf("%d",&n))
    {
        for(i=0;i<=1e7;i++)
            num[i]=0;
        while(n--)
        {
            scanf("%d",&x);
            num[x]++;
        }

        sxprime();
        for(i=1;i<=1e7;i++)
            dp[i]=dp[i-1]+dp[i];

        int l,r;
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d",&l,&r);
            l=min(l,10000001);
            r=min(r,10000000);
            printf("%I64d\n",dp[r]-dp[l-1]);
        }
    }
    return 0;
}

/*
6
5 5 7 10 14 15
3
2 11
3 12
4 4
7
2 3 5 7 11 4 8
2
8 10
2 123
*/


D题是一个状压dp的,

然后E是一个矩阵的快速幂。

暂时没什么想法。

这几天什么也没做。。


就把这个作为除夕的博客了。

Codeforces Round #226 div2(待更新)

上一篇:MFC学习-第2,3课


下一篇:八皇后及N皇后的回溯与递归算法