学步园

题目地址： http://codeforces.com/contest/332

第一题：题目又臭又长，读了好长时间才读懂。

n个人，你是0号，从0开始到n-1循环做动作，只要你前面三个人动作一样，你就喝一杯橙汁，问你能喝多少杯，

模拟

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef __int64 LL;
const int N=20005;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

char s[N];

int main()
{
    int i,j,n;
    while(cin>>n)
    {
        scanf("%s",s);
        int len=strlen(s),sum=0;
        for(i=0;i<len;)
        {
            if((i+n)<len)
            {
                i=i+n;
                if(s[i-1]==s[i-2]&&s[i-2]==s[i-3])
                {
                    sum++;
                }
            }
            else
                break;
        }
        cout<<sum<<endl;
    }
    return 0;
}

第二题：给你n个数，要你求一个k使得[a; a + k - 1] 与[b; b + k - 1]的和最大，保证这两个集合不想交。

1、相当于两个dp吧

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef __int64 LL;
const int N=200005;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

LL x[N];
LL dp[N];

int main()
{
    LL i,j,n,k;
    while(scanf("%I64d%I64d",&n,&k)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%I64d",&x[i]);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=k;i++)
            dp[1]+=x[i];
        for(i=2;i<=n-k+1;i++)
            dp[i]=dp[i-1]-x[i-1]+x[i+k-1];
        LL max1=dp[1],Max=0;
        int t1,t2,te=1;
        for(i=1+k;i<=n-k+1;i++)
        {
            if((dp[i]+max1)>Max)
            {
                Max=dp[i]+max1;
                t1=te; t2=i;
            }
            if(max1<dp[i-k+1])
            {
                max1=dp[i-k+1];
                te=i-k+1;
            }
        }
        printf("%d %d\n",t1,t2);
    }
    return 0;
}

2、RMQ算法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef __int64 LL;
const int N=200005;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

LL x[N];
LL dp[N];
LL d[N][20];

LL RMQ(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=(r-l+1))
        k++;
    return max(d[l][k],d[r-(1<<k)+1][k]);
}

int main()
{
    int i,j,n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%I64d",&x[i]);
        memset(dp,0,sizeof(dp));
        for(i=0;i<k;i++)
            dp[0]+=x[i];
        int p=n-k+1;
        for(i=1;i<p;i++)
            dp[i]=dp[i-1]-x[i-1]+x[i+k-1];
        for(i=0;i<p;i++)
            d[i][0]=dp[i];
        for(j=1;(1<<j)<=p;j++)
            for(i=0;i+(1<<j)-1<p;i++)
                d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
        LL Max=0,tmp,kk;
        int t1,t2;
        for(i=0;i<p;i++)
        {
            if((i+k)<p)
            {
                LL s=dp[i]+(tmp=RMQ(i+k,p-1));
                if(Max<s)
                {
                    Max=s;  kk=tmp;
                    t1=i;   t2=i+k;
                }

            }
        }
        for(j=t2;j<p;j++)
            if(dp[j]==kk)
            {
                t2=j;break;
            }
        printf("%d %d\n",t1+1,t2+1);
    }
    return 0;
}