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<iostream>
#include<cstdio>
#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<<ans;
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<<dp[n][0];
*/
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int MOD=12345647;
int dp[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<len1; i++) a[i+1]=n[i]-'0';
for (i=0; i<len1; i++) b[i+1]=0;
for (i=0; i<len2; i++) b[1+i+len1-len2]=LL[i]-'0';
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<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++)
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<b[i+1]) continue;
K=(k || s1>b[i+1]);
if (l==0 && s2<b[i+1]) continue;
L=(l || s2>b[i+1]);
if (t==0 && s3<b[i+1]) continue;
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<<ans<<endl; ans=0;
return 0;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。