206
技術社區[雲棲]
poj 1248 Safecracker
同樣的理解題意很重要，我覺得可能這題作者的本意不是這麼水，沒那麼簡單可以暴力過的，但是我是暴力A了。。。
網上有用回溯的，字典樹的。。。也有5重暴力，反正我是懶得看，暴力我還是有自信自己寫的，說不定寫的還好一些。。哈哈
我這個解法的亮點應該就是轉換以後的sort（），這樣算出來的一定是最大字典序的。。。一次A
題意:給定一個長度為5……12個不同字符組成的字符串,從中選取5個,設為v,w,x,y,z,要滿足等式:v-w^2+x^3-y^4+z^5=target,現在給出字符串和target,求滿足該條件的5個字符(字典序要最大)
AC的代碼：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
char str[15]; //存輸入的字符串
int strNum[15]; //上麵字符串對應的數字
void Trans()
{
int i;
for(i=0;i<strlen(str);i++)
strNum[i]=str[i]-'A'+1;
}
void forceSearch(int len,int target)
{
int i,j,k,l,m; //5重暴力counter
//暴力主體 i是最高位的變量
for(i=len-1;i>=0;i--)
for(j=len-1;j>=0;j--)
{
if(j==i)
continue;
for(k=len-1;k>=0;k--)
{
if(k==i || k==j)
continue;
for(l=len-1;l>=0;l--)
{
if(l==i || l==j || l==k)
continue;
for(m=len-1;m>=0;m--)
{
if(m==i || m==j || m==k || m==l)
continue;
else if(strNum[i] - strNum[j]*strNum[j] + strNum[k]*strNum[k]*strNum[k] - strNum[l]*strNum[l]*strNum[l]*strNum[l] + strNum[m]*strNum[m]*strNum[m]*strNum[m]*strNum[m] == target)
{
printf("%c%c%c%c%c\n",strNum[i]-1+'A',strNum[j]-1+'A',strNum[k]-1+'A',strNum[l]-1+'A',strNum[m]-1+'A');
return;
}
}
}
}
}
printf("no solution\n");
}
int main()
{
int i;
int target;
while(scanf("%d%s",&target,str))
{
if(target==0 && strcmp(str,"END")==0)
return 0;
int len=strlen(str); //存每次字符串的長度
Trans();
sort(strNum,strNum+len);
//test ok
/*for(i=0;i<len;i++)
printf("%d,",strNum[i]);
printf("\n");*/
forceSearch(len,target);
}
return 0;
}
最後更新：2017-04-03 14:53:53