POJ 1248HDU 1015 Safecracker

    技术2025-12-07  20

     

    从给出的字符串中选取5个,设为v,w,x,y,z,要满足等式:v-w^2+x^3-y^4+z^5=target;(要求字典序最大)

    因为可能有多组解,而题目要求输出字典序最大的那个,所以先将字符串按升序排序然后再搜索,这样得到的第一组解即为答案

    const int N=20+5; int n,m,t; int i,j,k; char s[N]; int ans[5]; bool vis[N],flag; void DFS(int step,const int len) { if(flag) return ; if(step==5){ int sum=ans[0]-pow(ans[1],2)+pow(ans[2],3)-pow(ans[3],4)+pow(ans[4],5); if(sum==k){ flag=1; for(int i=0;i<5;i++) cout<<char(ans[i]+'A'-1); } return ; } //debug(step); for(int i=0;i<len;i++){ if(vis[i]) continue; vis[i]=1; ans[step]=s[i]-'A'+1; DFS(step+1,len); if(!flag) vis[i]=0; } return ; } int main() { //IOS; while(~sd(k)){ ss(s); if(k==0 && s[0]=='E') break; int len=strlen(s); sort( s,s+len,greater<char>() ); ms(vis,0); flag=0; //cout<<s<<endl; DFS(0,len); //debug(k); if(flag){ puts(""); } else puts("no solution"); } //PAUSE; return 0; }

     

    Processed: 0.020, SQL: 9