Codeforces Round #193 (Div. 2)

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

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;

}

巴特西

Codeforces Round #193 (Div. 2)

最新文章

热门文章