2017北京国庆刷题Day2 afternoon

期望得分：100+100+50=250

实际得分：100+70+50=220

T1 最大值(max)

Time Limit:1000ms Memory Limit:128MB

题目描述

LYK有一本书，上面有很多有趣的OI问题。今天LYK看到了这么一道题目：

这里有一个长度为n的正整数数列ai(下标为1~n)。并且有一个参数k。

你需要找两个正整数x,y，使得x+k<=y，并且y+k-1<=n。并且要求a[x]+a[x+1]+…+a[x+k-1]+a[y]+a[y+1]+…+a[y+k-1]最大。

LYK并不会做，于是它把题扔给了你。

输入格式(max.in)

第一行两个数n，k。

第二行n个数，表示ai。

输出格式(max.out)

两个数表示x,y。若有很多种满足要求的答案，输出x最小的值，若x最小仍然还有很多种满足要求的答案，输出y最小的值。

输入样例

5 2

6 1 1 6 2

输出样例

1 4

对于30%的数据n<=100。

对于60%的数据n<=1000

对于100%的数据1<=n<=100000，1<=k<=n/2，1<=ai<=10^9。

维护连续的k个数的和的后缀最大值

#include<cstdio>

#include<iostream>

#include<algorithm>

#define N 100001

using namespace std;

typedef long long LL;

LL sum[N],p[N],suf[N];

int pos[N];

void read(LL &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

int main()

{

    freopen("max.in","r",stdin);

    freopen("max.out","w",stdout);

    int n,k;

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++) read(sum[i]),sum[i]+=sum[i-];

    for(int i=;i+k-<=n;i++) p[i]=sum[i+k-]-sum[i-];

    for(int i=n-k+;i;i--)

        if(p[i]>=suf[i+]) suf[i]=p[i],pos[i]=i;

        else suf[i]=suf[i+],pos[i]=pos[i+];

    int ansx,ansy;

    LL maxn=;

    for(int i=;i+k+k-<=n;i++)

        if(p[i]+suf[i+k]>maxn) maxn=p[i]+suf[i+k],ansx=i,ansy=pos[i+k];

        else if(p[i]+suf[i+k]==maxn && ansy>pos[i+k]) ansy=pos[i+k];

    printf("%d %d",ansx,ansy);

    return ;

}

T2 吃东西(eat)

Time Limit:2000ms Memory Limit:1024MB

题目描述

一个神秘的村庄里有4家美食店。这四家店分别有A,B,C,D种不同的美食。LYK想在每一家店都吃其中一种美食。每种美食需要吃的时间可能是不一样的。

现在给定第1家店A种不同的美食所需要吃的时间a1,a2,…,aA。

给定第2家店B种不同的美食所需要吃的时间b1,b2,…,bB。

以及c和d。

LYK拥有n个时间，问它有几种吃的方案。

输入格式(eat.in)

第一行5个数分别表示n,A,B,C,D。

第二行A个数分别表示ai。

第三行B个数分别表示bi。

第四行C个数分别表示ci。

第五行D个数分别表示di。

输出格式(eat.out)

一个数表示答案。

输入样例

11 3 1 1 1

4 5 6

输出样例

对于30%的数据A,B,C,D<=50

对于另外30%的数据n<=1000。

对于100%的数据1<=n<=100000000，1<=A,B,C,D<=5000,0<=ai,bi,ci,di<=100000000。

30% 枚举，另外30%分组背包

100%的数据：注意空间1GB

所以可以维护sum[i]表示 C+D 里面时间和为i 的方案数

然后枚举A，B，累计n-A[i]-B[i] 的方案数

#include<map>

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

typedef long long LL;

LL dp[][];

int cost[][],n;

int C[],D[],A[],B[];

int sum[];

inline void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void init()

{

    read(n); read(cost[][]); read(cost[][]); read(cost[][]); read(cost[][]);

    for(int i=;i<=cost[][];i++) read(cost[][i]);

    for(int i=;i<=cost[][];i++) read(cost[][i]);

    for(int i=;i<=cost[][];i++) read(cost[][i]);

    for(int i=;i<=cost[][];i++) read(cost[][i]);

}

void out(LL x)

{

    if(x/) out(x/);

    putchar(x%+'');

}

void work1()

{

    for(int i=;i<=n;i++) dp[][i]=;

    for(int k=;k<=;k++)

        for(int i=;i<=n;i++)

            for(int j=;j<=cost[k][];j++)

                if(i-cost[k][j]>=) dp[k][i]+=dp[k-][i-cost[k][j]];

    out(dp[][n]);

}

void work2()

{

    int ans=;

    for(int i=;i<=cost[][];i++)

        for(int j=;j<=cost[][];j++)

            for(int k=;k<=cost[][];k++)

                for(int l=;l<=cost[][];l++)

                    if(cost[][i]+cost[][j]+cost[][k]+cost[][l]<=n) ans++;

    printf("%d",ans);

}

void work3()

{

    int cnt=,sc=cost[][],sd=cost[][];

    for(int i=;i<=sc;i++) C[i]=cost[][i];

    for(int i=;i<=sd;i++) D[i]=cost[][i];

    int minn=2e8,maxn= ;

    for(int i=;i<=sc;i++)

        for(int j=;j<=sd;j++)

        {

            sum[C[i]+D[j]]++;

            minn=min(minn,C[i]+D[j]);

            maxn=max(maxn,C[i]+D[j]);

        }

    for(int i=minn;i<=maxn;i++) sum[i]+=sum[i-];

    int sa=cost[][],sb=cost[][];

    for(int i=;i<=sa;i++) A[i]=cost[][i];

    for(int i=;i<=sb;i++) B[i]=cost[][i];

    long long ans=;

    for(int i=;i<=sa;i++)

        for(int j=;j<=sb;j++)

            if(n-A[i]-B[j]>=) ans+=sum[min(n-A[i]-B[j],maxn)];

    out(ans);

}

int main()

{

    freopen("eat.in","r",stdin);

    freopen("eat.out","w",stdout);

    init();

    if(cost[][]<= && cost[][]<= && cost[][]<= && cost[][]<=) work2();

    else if(n<=) work1();

    else work3();

    return ;

}

考场上分组背包体积从1开始的，挂了

数据里面有0

T3 分糖果(candy)

Time Limit:1000ms Memory Limit:128MB

题目描述

总共有n颗糖果，有3个小朋友分别叫做L，Y，K。每个小朋友想拿到至少k颗糖果，但这三个小朋友有一个共同的特点：对3反感。也就是说，如果某个小朋友拿到3颗，13颗，31颗，333颗这样数量的糖果，他就会不开心。（也即它拿到的糖果数量不包含有一位是3）

LYK掌管着这n颗糖果，它想问你有多少种合理的分配方案使得将这n颗糖果全部分给小朋友且没有小朋友不开心。

例如当n=3,k=1时只有1种分配方案，当n=4，k=1时有3种分配方案分别是112,121,211。当n=7,k=2时则不存在任何一种合法的方案。

当然这个答案可能会很大，你只需输出答案对12345647取模后的结果就可以了。

输入格式(candy.in)

第一行两个数表示n,k。

输出格式(candy.out)

一个数表示方案总数。

输入样例

99999 1

输出样例

9521331

对于30%的数据n<=100

对于50%的数据n<=1000。

对于另外30%的数据k=1。

对于100%的数据3<=n<=10^10000,1<=k<=n/3，且n,k不包含前导0。

数位DP

dp[i][j][k][l][t] 表示n的前i位，分完后的余数为j，第1/2/3个小朋友的第i位能否随便填的方案数

再枚举3个小朋友分别分多少转移

#include<cstdio>

#include<cstring>

#define N 10003

using namespace std;

const int mod=;

char s[N];

int a[N],b[N],dp[N][][][][];

void ADD(int &i,int j)  {  i+=j; if(i>=mod) i-=mod; }

int main()

{

    freopen("candy.in","r",stdin);

    freopen("candy.out","w",stdout);

    scanf("%s",s+); int len1=strlen(s+);

    for(int i=;i<=len1;++i) a[i]=s[i]-'';

    scanf("%s",s+); int len2=strlen(s+);

    for(int i=;i<=len2;++i) b[i+len1-len2]=s[i]-'';

    dp[][][][][]=;

    int i,j,k,l,t,I,J,K,L,T;

    for(i=;i<len1;i++)

      for(j=;j<;j++)

        for(k=;k<;k++)

          for(l=;l<;l++)

            for(t=;t<;t++)

                if(dp[i][j][k][l][t])

                  for(int s1=;s1<=;s1++)

                    if(s1!=)

                      for(int s2=;s2<=;s2++)

                        if(s2!=)

                          for(int s3=;s3<=;s3++)

                            if(s3!=)

                            {

                                I=i+;

                                J=j*+a[i+]-s1-s2-s3;

                                if(J< || J>) continue;

                                if(!k && s1<b[i+]) continue;

                                K=(k || s1>b[i+]);

                                if(!l && s2<b[i+]) continue;

                                L=(l || s2>b[i+]);

                                if(!t && s3<b[i+]) continue;

                                T=(t || s3>b[i+]);

                                ADD(dp[I][J][K][L][T],dp[i][j][k][l][t]);

                            }

    int ans=;

    for(k=;k<;k++)

        for(l=;l<;l++)

            for(t=;t<;t++)

                ADD(ans,dp[len1][][k][l][t]);

    printf("%d",ans);

}

考场50分做法：枚举第一个，枚举第二个，判断是否合法

#include<cstdio>

using namespace std;

bool check(int k)

{

    while(k)

    {

        if(k%==) return false;

        k/=;

    }

    return true;

}

int main()

{

    freopen("candy.in","r",stdin);

    freopen("candy.out","w",stdout);

    int n,k,ans=;

    scanf("%d%d",&n,&k);

    for(int i=k;i+k+k<=n;i++)

        if(check(i))

            for(int j=k;j+i+k<=n;j++)

                if(check(j)&&check(n-i-j)) ans++;

    printf("%d",ans);

    return ;

}

巴特西

2017北京国庆刷题Day2 afternoon

最新文章

热门文章