学步园

P1  签到题不多说..

#include <iostream>
#include <cstdio>
using namespace std;
int n,m,p,q;
int a[300];
int ans;
int main()
{
    cin>>n>>m;
    for (int i=1; i<=n; i++)
    cin>>a[i];
    ans=0;
    for (int i=1; i<n; i++)
    if (a[i]-a[i+1]-m>ans)
    ans=a[i]-a[i+1]-m;
    cout<<ans<<endl;
    return 0;
}

P2，给一个字符串，问有多少个二元组l,r符合substring(l,r)至少含有一个"bear"。暴力匹配bear,每次统计出当前匹配头到上一次匹配头之间的字母数x，当前匹配尾到字符串尾的字母数y，ans+=x*y,匹配完所有情况ans就是要的答案。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
int n,m,p,q;
int ans;
char s[7000];

int main()
{
//    freopen("in.txt","r",stdin);
    gets(s);
    int len=strlen(s);
    int last=0;
    for (int i=0; i+3<len; i++)
    {
        if (s[i]=='b' && s[i+1]=='e' && s[i+2]=='a' && s[i+3]=='r')
        {
            ans+=(i-last+1)*(len-i-3);
            last=i+1;
        }
    }

    cout<<ans<<endl;
    return 0;
}

P3，给n个数，m组查询，每次查询一个区间l,r，对l,r之间的每个素数，统计n个数中有多少个数是其倍数，并求和..这题我是把n个数全部做了一次分解质因数，每分解出一个素数k就把对应cot[k]++表示其出现的次数+1，查询的时候统计一下l,r之间的素数的cot[i]的和即可..具体实现看代码吧...不过这应该不是正解...cf上跑了1965ms,还是很悬的.....结束后看到一种做法，直接记录每个数出现的次数，然后质数加倍去统计就好..这么做三四百毫秒好像就可以过......

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1e7+11;
bool ok[maxn];
int prime[700000+100];
ll cot[700000+100];
int n,m,k;
int cnt;
int dv[700000];
void ss()
{
    memset(ok,true,sizeof ok);
    ok[2]=true;
    ok[1]=false;
    ok[0]=false;
    for (int i=2; i<maxn; i++)
    {
        if (ok[i])
        {
            for (int j=i+i; j<maxn; j+=i)
            if (ok[j]) ok[j]=false;
        }
    }
    cnt=0;
    for (int i=2; i<maxn; i++)
    if (ok[i])
    {
        prime[cnt++]=i;
    }

//    for (int i=0; i<cnt; i++)
//    cout<<prime[i]<<"\n";
//    cout<<endl;
}

int search(int v)
{
    int m;
    int l=0;
    int r=cnt;
    while (l<r)
    {
        m=(l+r)>>1;
        if (prime[m]<v) l=m+1;
        else r=m;
    }
    return l;
}

void dvd(int num)
{
    dv[0]=0;
    int xx=num;
    if (!ok[num])
    {
        int y=0,kk=0,tt=1;
        while(xx)
        {
            if (xx%prime[y]==0)
            {
//                dv[++dv[0]]=prime[y];
                cot[y]++;
                while (xx%prime[y]==0) xx=xx/prime[y];
            }
            else
            {
                y++;
            }
           if (xx==1) break;
           if (ok[xx])
           {
//               dv[++dv[0]]=xx;
               int ps=search(xx);
               cot[ps]++;
               break;
           }
        }
    }
    else
    {
        int ps=search(num);
        cot[ps]++;
    }
//    for (int i=1; i<dv[0]; i++)
//    cout<<dv[i]<<"*";
//    cout<<dv[dv[0]]<<endl;
}


struct node
{
    int l,r,id;
    ll ans;
    bool operator<(const node& b)const
    {
        if (l==b.l) return r<b.r;
        return l<b.l;
    }
}qy[50550];
int main()
{
//    freopen("in.txt","r",stdin);
    ss();
    memset(cot,0,sizeof cot);
    scanf("%d",&n);
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&k);
        dvd(k);
    }
    for (int i=0; i<cnt; i++)
    cot[i]+=cot[i-1];
    int x,y;
    ll ans=0;
    ll ss1,ss2;
    scanf("%d",&m);
    for (int i=1; i<=m; i++)
    {
        ans=0;
        scanf("%d%d",&x,&y);
        int s1=search(x);
        int s2=search(y);
        bool c1=false;
        if (prime[s1]!=x) s1--,c1=true;
        if (prime[s2]!=y) s2--;
        if (s1>0)
        {
            if (!c1) ans+=cot[s2]-cot[s1-1];
            else ans+=cot[s2]-cot[s1];
        }
        else ans+=cot[s2];
        printf("%I64d\n",ans);
    }


    return 0;
}