디지털 학습 노트
디지털 dp에서 windy만 나오고 아무것도 안 되고 띄어쓰기만 하고 기억화 검색만 하고...
요약:
대개 숫자에 대한 요구가 있고 상하한선이 특별히 크다...보통 두 가지 실현 방법이 있는데 점차적으로 추측(dp, 비교적 이해하기 쉽다. 일반적으로 이런 것을 먼저 배운다)/기억화 검색(폭력, 편리, 쓰기 쉽고 sb방법)
판자:
https://www.luogu.org/blog/mak2333/shuwei
loj#10163. Amount of Degrees
https://loj.ac/problem/10163
몇 차멱을 더하면 b진법으로 넘어갈 때 그 한 명이 1이다.답이 담긴 나무마다 여러 갈래로 돌려서 마구잡이로 굴다.대응하는 차멱 분석 & 논문에 주의하십시오:https://wenku.baidu.com/view/d2414ffe04a1b0717fd5dda8.html
#include
#include
#include
using namespace std;
int f[32][32],a[32];//f: i （ i ） j 1 （ b 1）
int k,b;
int solve(int x)
{
int len=0,kk=k;
while (x!=0)
{
a[len++]=x%b; //
x/=b;
}
int ans=0; len--;
for (int i=len;i>=0;i--)
{
if (a[i]==1)
{
ans+=f[i][kk];
kk--;
}
else if (a[i]>1)
{
ans+=f[i+1][kk];
break;
}
if (kk<0) return ans;
}
if (kk==0) ans++; //x k 1
return ans;
}
int main()
{
for (int i=0;i<31;i++)
{
f[i][0]=1;
for (int j=1;j<=i;j++) f[i][j]=f[i-1][j]+f[i-1][j-1];
}
int x,y;
scanf("%d%d%d%d",&x,&y,&k,&b);
printf("%d
",solve(y)-solve(x-1));
return 0;
}
loj#10164. 디지털 게임
https://loj.ac/problem/10164
점진적 접근 방식:
//
#include
#include
#include
using namespace std;
int a[32],f[32][32];//f[i ][ ]（ ？）
int solve(int x)
{
int len=0; memset(a,0,sizeof(a));
while (x)
{
a[++len]=x%10;
x/=10;
}
int ans=0;
for (int i=len;i;i--)
{
if (a[i+1]>a[i]) break;
for (int j=a[i+1];j 기억 검색:
//
#include
#include
#include
using namespace std;
int f[32][32],a[32];//f[ i ][ ]
int dfs(int len,int st,int lim)
{
if (len==0) return 1;
if (lim==0&&f[len][st]!=-1) return f[len][st];
int ans=0,ed; if (lim==1) ed=a[len]; else ed=9;
for (int i=st;i<=ed;i++)
{
if (lim==1&&i==ed) ans+=dfs(len-1,i,1);
else ans+=dfs(len-1,i,0);
}
return ans;
}
int solve(int x)
{
memset(f,-1,sizeof(f));
int len=0;
while (x)
{
a[++len]=x%10;
x/=10;
}
return dfs(len,0,1);
}
int main()
{
int x,y;
while (scanf("%d%d",&x,&y)!=EOF)
{
printf("%d
",solve(y)-solve(x-1));
}
return 0;
}
loj#10165. Windy 수
https://loj.ac/problem/10165
점진적 접근 방식:
//
#include
#include
#include
#include
using namespace std;
int f[32][32],a[32]; //f[ i][ i ( ) ]
void init()
{
for (int i=0;i<=9;i++) f[1][i]=1;
for (int i=2;i<=31;i++)
for (int j=0;j<=9;j++)
for (int k=0;k<=9;k++)
if (abs(j-k)>=2) f[i][j]+=f[i-1][k];
}
int solve(int x)
{
memset(a,0,sizeof(a));
int len=0;
while (x)
{
a[++len]=x%10;
x/=10;
}
int ans=0;
for (int i=1;i=2) ans+=f[i][j]; //
if (abs(a[i+1]-a[i])<2) break;
if (i==1) ans++;
}
return ans;
}
int main()
{
init();
int a,b;
scanf("%d%d",&a,&b);
printf("%d
",solve(b)-solve(a-1));
return 0;
}
기억 검색 방법:
//
#include
#include
#include
using namespace std;
int f[10][10],a[10];//f[ i ][ ]
int dfs(int len,int st,int ze,int lim)//ze lim:
{
if (len==0) return 1;
if (lim==0&&f[len][st]!=-1) return f[len][st];
int ans=0,ed;
if (lim==1) ed=a[len]; else ed=9;
for (int i=0;i<=ed;i++)
{
if (ze==1)
{
int zz=0;
if (i==0) zz=1;
if (lim==1&&i==ed) ans+=dfs(len-1,i,zz,1);
else ans+=dfs(len-1,i,zz,0);
}
else if (abs(st-i)>=2)
{
if (lim==1&&i==ed) ans+=dfs(len-1,i,0,1);
else ans+=dfs(len-1,i,0,0);
}
}
if (lim==0&&st!=0) f[len][st]=ans;
return ans;
}
int solve(int x)
{
memset(a,0,sizeof(a));
int len=0;
while (x)
{
a[++len]=x%10;
x/=10;
}
return dfs(len,0,1,1);
}
int main()
{
memset(f,-1,sizeof(f));
int a,b;
scanf("%d%d",&a,&b);
printf("%d
",solve(b)-solve(a-1));
return 0;
}
loj#10166. '한 권 통5.3 연습1'숫자 게임
https://loj.ac/problem/10166너무 많이 생각하지 말고 바로 수색하면 된다
#include
#include
#include
using namespace std;
int f[32][110],a[32],n;//f[ ][ ]
int dfs(int len,int mod,int lim)
{
if (len==0)
{
if (mod==0) return 1; else return 0;
}
if (f[len][mod]!=-1&&lim==0) return f[len][mod];
int ans=0,ed;
if (lim==1) ed=a[len]; else ed=9;
for (int i=0;i<=ed;i++)
{
if (lim==1&&i==ed) ans+=dfs(len-1,(mod+i)%n,1);
else ans+=dfs(len-1,(mod+i)%n,0);
}
if (lim==0) f[len][mod]=ans;
return ans;
}
int solve(int x)
{
memset(f,-1,sizeof(f));
memset(a,0,sizeof(a));
int len=0;
while (x)
{
a[++len]=x%10;
x/=10;
}
return dfs(len,0,1);
}
int main()
{
int a,b;
while (scanf("%d%d%d",&a,&b,&n)!=EOF)
printf("%d
",solve(b)-solve(a-1));
return 0;
}
loj#10167. '한 권 통5.3 연습2'싫어요. 62.
https://loj.ac/problem/10167
#include
#include
#include
using namespace std;
int f[7][10],a[7];//f[ i][ i ]
int dfs(int len,int last,int lim)
{
if (len==0) return 1;
if (lim==0&&f[len][last]!=-1) return f[len][last];
int ans=0,ed;
if (lim==1) ed=a[len]; else ed=9;
for (int i=0;i<=ed;i++)
{
if (i==4) continue;
if (last==6&&i==2) continue;
if (lim==1&&i==ed) ans+=dfs(len-1,i,1);
else ans+=dfs(len-1,i,0);
}
if (lim==0) f[len][last]=ans;
return ans;
}
int solve(int x)
{
memset(f,-1,sizeof(f));
memset(a,0,sizeof(a));
int len=0;
while (x)
{
a[++len]=x%10;
x/=10;
}
return dfs(len,0,1);
}
int main()
{
int a,b;
while (scanf("%d%d",&a,&b)!=EOF&&a&&b)
{
printf("%d
",solve(b)-solve(a-1));
}
return 0;
}
loj#10168. '한 권 통5.3 연습3'미움 7
https://loj.ac/problem/10168완전 제곱 공식 2333(바보인 척.jpg) 문제풀이 & 분석:https://blog.csdn.net/ten_three/article/details/19698055 &https://www.cnblogs.com/kuangbin/archive/2013/05/01/3053233.html
#include
#include
#include
using namespace std;
#define LL long long
#define mod 1000000007
struct node
{
LL s,sum,sqrsum;// N
node()
{
s=sum=sqrsum=-1;
}
}f[20][10][10];//f[ ][ mod7][ mod7]
int a[20];
LL pi[20];
node dfs(int len,int s,int qs,int lim)// mod7 mod7
{
if (len==0)
{
node tt;
tt.s=tt.sum=tt.sqrsum=0;
if (s!=0&&qs!=0) tt.s=1;
return tt;
}
if (lim==0&&f[len][s][qs].sqrsum!=-1) return f[len][s][qs];
node ans; ans.s=ans.sum=ans.sqrsum=0;
int ed=0;
if (lim==1) ed=a[len]; else ed=9;
for (int i=0;i<=ed;i++)
{
if (i==7) continue;
/*
len i f1,f2,f2...fN len
： (f1+ i*10^(len-1) )^2+(f2+ i*10^(len-1) )^2+...+(fN+ i*10^(len-1) )^2
:
N*(i*10^(len-1))^2+ f1^2+f2^2+...+fN^2+ 2*(i*10^(len-1))*(f1+f2+...fN)
N s 2*(i*10^(len-1))*(f1+f2+...fN) sum sqrsum
*/
node tt;
if (lim==1&&i==ed) tt=dfs(len-1,(s+i)%7,(qs*10+i)%7,1);
else tt=dfs(len-1,(s+i)%7,(qs*10+i)%7,0);
LL si=(i*pi[len-1])%mod;
ans.s=(ans.s+tt.s)%mod;
ans.sum=(ans.sum+(tt.sum+ (si*tt.s)%mod ) %mod )%mod;
ans.sqrsum=(ans.sqrsum+tt.sqrsum+( ((si*si)%mod*tt.s)%mod+ ((2*si)%mod *tt.sum) %mod )%mod )%mod;
}
if (lim==0) f[len][s][qs]=ans;
return ans;
}
LL solve(LL x)
{
memset(a,0,sizeof(a));
int len=0;
while (x)
{
a[++len]=x%10;
x/=10;
}
node ans=dfs(len,0,0,1);
return ans.sqrsum%mod;
}
int main()
{
pi[0]=1;
for (int i=1;i<=18;i++) pi[i]=pi[i-1]*10;
int t;
scanf("%d",&t);
while (t--)
{
LL x,y;
scanf("%lld%lld",&x,&y);
if (x>y) swap(x,y);
printf("%lld
",(solve(y)-solve(x-1)+mod)%mod);
}
return 0;
}
loj#10169. '한 권 통5.3 연습4'숫자 계수
https://loj.ac/problem/10169다른 사람들은 모두 3차원 f[수위][전도제로]+10번, 매번 한 수를 찾을 때마다 나만 f[수위][기입한 숫자] 도깨비 구조체는 한 번에 모든 숫자를 찾고 전도제로를 가지지 않는다...그러니까 전도제로에 주의!!!코드에서 설명한 거 구체적으로 봐!전도 0을 넣지 않으면 그 1차원은 미리 처리하는 것을 기억해야 한다
#include
#include
#include
using namespace std;
struct node
{
bool bk;
long long a[10];
node()
{
bk=0; memset(a,-1,sizeof(a));
}
}f[15][10];
int a[15];
long long pi[15],c[15];
node jia(node x,node y)
{
for (int i=0;i<=9;i++) x.a[i]+=y.a[i];
return x;
}
node dfs(int len,int x,int ze,int lim) //ze：zero
{
if (len==0) {node tt;tt.bk=1;memset(tt.a,0,sizeof(tt.a));tt.a[x]=1;return tt;}
if (ze==0&&lim==0&&f[len][x].bk==1) return f[len][x];
node ans; ans.bk=1; memset(ans.a,0,sizeof(ans.a));
int ed;
if (lim==1) ed=a[len]; else ed=9;
for (int i=0;i<=ed;i++)
{
node tt;
tt=dfs(len-1,i,i==0&&ze==1,i==ed&&lim==1);
/*if (ze==1&&i==0) ;
else if (len>1) tt.a[i]+=tt.t;*/
if (ze==1&&i==0) ;
else
{
if (len>1)
{
if (lim==1&&i==ed) tt.a[i]+=c[len-1]+1;
else tt.a[i]+=pi[len-1];
}
}
ans=jia(ans,tt);
}
if (ze==0&&lim==0) f[len][x]=ans;
// / 1010 len=3, len=2 f[2][ ].a[0]=9 (10,20,30,...,90) 18 (10,20,...,90; 01,02,...,09)
return ans;
}
node solve(long long x)
{
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
/*for (int i=0;i<15;i++)
for (int j=0;j<10;j++) memset(f[i][j].a,-1,sizeof(f[i][j].a)),f[i][j].bk=0;*/
int len=0;
while (x)
{
a[++len]=x%10;
x/=10;
c[len]=a[len]*pi[len-1]+c[len-1]; // （ ）
}
return dfs(len,0,1,1);
}
int main()
{
pi[0]=1;
for (int i=1;i<15;i++) pi[i]=pi[i-1]*10;
long long x,y;
scanf("%lld%lld",&x,&y);
node r=solve(y),l=solve(x-1);
for (int i=0;i<=9;i++)
{
printf("%lld ",r.a[i]-l.a[i]);
}
printf("
");
return 0;
}
끝. 꽃 뿌려!(sd 기억화 검색이 참 좋다)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
단조로운 대기열 최적화 dp 학습 노트제목은 일반적으로 앞의 한 상태에서 현재의 가장 좋은 상태를 얻어 dp를 만족시켜야 하지만 폭력으로 앞의 결정을 찾으면 복잡도는 받아들일 수 없다.이때 양쪽에서 삭제할 수 있지만 한 단락만 추가할 수 있는 단조로운 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
