NOIP训练营内部试题-分糖果

NOIP训练营内部试题-分糖果

摘自：清北学堂NOIP训练营试题T2

题目：分糖果

分糖果

(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。

题解：

50分 暴力

#include

#include

#define mod 12345647

using namespace std;

int n,k,ans;

bool check(int x){

while(x){

if(x%10==3)return 0;

x/=10;

}

return 1;

}

int main(){

freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);

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

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

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

int k=n-i-j;

if(check(i)&&check(j)&&check(k))ans++;

if(ans>=mod)ans-=mod;

}

}

cout<

fclose(stdin);fclose(stdout);

return 0;

}

100分 数位dp

/*

    枚举两个数，第三个数是确定，判断一下。

    f[i]表示i这个数字是否有3

    dp[i][j][0/1][0/1][0/1]来表示当前从高到低第i位，并且这一位需要向它的高位进j位   j=[0,2]  这3个数分别是否超过了k

for (i=1; i<=|a|; i++)

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

for (u=0; u<=1; u++)

for (v=0; v<=1; v++)

for (w=0; w<=1; w++)

for (x=0; x<=9; x++)

for (y=0; y<=9; y++)

for (z=0; z<=9; z++)

if (x+y+z>=10*j &&x!=3 && y!=3 && z!=3)

{

int k=x+y+z-10*j;

if (k==a[i]) {dp[i+1][0][][][]+=dp[i][j];}

if (k==a[i]-1){dp[i+1][1][][][]+=dp[i][j];}

if (k==a[i]-2){dp[i+1][2][][][]+=dp[i][j];}

}

n=|a|

cout<

*/

#include

#include

#include

#include

#include

#include

#include

using namespace std;

const int MOD=12345647;

intdp[10005][3][2][2][2],a[10005],b[10005],len1,len2,i,j,k,l,t,I,J,K,L,T,s1,s2,s3,ans;

char n[10005],LL[10005];

void ADD(int &A,int B) {A+=B; if (A>=MOD) A-=MOD;}

int main()

{

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

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

scanf("%s",n);

scanf("%s",LL);

len1=strlen(n);len2=strlen(LL);

for (i=0; i

for (i=0; i

for (i=0; i

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

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

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

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

for (t=0; t<=1; t++) dp[i][j][k][l][t]=0;

dp[0][0][0][0][0]=1;

for (i=0; i

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

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

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

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

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

{

for (s1=0; s1<=9; s1++)

if (s1!=3)

for (s2=0; s2<=9; s2++)

if (s2!=3)

for (s3=0; s3<=9; s3++)

if (s3!=3)

{

I=i+1;

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

if (J>2 || J<0)continue;

if (k==0 &&s1

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

if (l==0 &&s2

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

if (t==0 &&s3

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

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

}

}

for (k=0; k<=1; k++) for(l=0; l<=1; l++) for (t=0; t<=1; t++) ADD(ans,dp[len1][0][k][l][t]);

cout<

return 0;

}