长脖子鹿省选模拟赛 [LnOI2019SP]快速多项式变换(FPT)

本片题解设计两种解法

果然是签到题...

因为返回值问题T了好久...

第一眼：搜索大水题？

 然后...竟然A了

 1 #include
 2 #include
 3 #include
 4 #include
 5 #define int long long
 6 using namespace std;
 7 inline int read(){
 8     int ans=0,f=1;char chr=getchar();
 9     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
11     return ans*f;
12 }int fm,m,tot,a[105],x,ff,p[105],q[105];
13 void dfs(int x,int now){
14     if(ff) return;
15     if(x==0&&now>=m) return;
16     if(now<m){
17         ff=1;
18         int t=100;
19         while(p[t]==0) t--;
20         cout<1<" ";
21         for(int i=1;i<=t;i++) cout<" ";
22         return;
23     }
24     int t=now/a[x];
25     for(int i=t;i>=0;i--)    p[x]=i,dfs(x-1,now-a[x]*i);
26 }
27 signed main(){
28     m=read(),fm=read();
29     x=1;a[0]=1;
30     while(x101){a[++tot]=x*m;x=x*m;}
31     dfs(tot,fm);
32     return 0;
33 }

 但其实只要分析一下，就发现式子跟进制转换有很大关系啊，我们只要把fm当做m进制数来处理即可

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include 
 7 #include
 8 #define int long long
 9 using namespace std;
10 inline int read(){
11     int ans=0,f=1;char chr=getchar();
12     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
13     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
14     return ans*f;
15 }void write(long long x){
16     if(x < 0) putchar('-'),x = -x;
17     if(x > 9) write(x / 10);
18     putchar(x % 10 + '0');
19 }int n,m,a[505],tot;
20 signed main(){
21     m=read(),n=read();
22     while(n){a[++tot]=n%m;n/=m;}
23     printf("%d\n",tot);
24     for(int i=1;i<=tot;i++)write(a[i]),putchar(' ');
25     return 0;
26 }

转载于:https://www.cnblogs.com/zhenglw/p/10505881.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！