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（待更新）

原文：http://blog.csdn.net/coraline_m/article/details/18881829