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;
} 複制