题意
一个 IP 地址是一个 32 位的 2 进制整数，分成四组 8 位的 2 进制整数（没有前导 0）。
比如说，0.255.1.123 是一个正确的 IP 地址，而0.256.1.123 和 0.255.1.01 不是正确的。
定义一个合法的回文 IP 地址为 Beautiful IP Address （回文地址就是去掉“.”后是个回文字符串的地址）， 给出 n 个数字，求出所有可用这些数字组成的Beautiful Addresses（数字可以重复使用，但不能有一个数字不被使用）。
思路1
先枚举一个用所给的n个数字构成字符串（长度2-6），用它构造一个回文串。然后枚举切割点，即“.”放置的位置，并同时判断每一组数字是否是0-255之间的整数并且没有前导0。将每一个合法的答案记录下来，最后输出。
#include<bits/stdc++.h>
using namespace std;
int n,x[15],rec[5],cnta,ans[1000000][5];
int val(string s,int a,int b){//将字符串s中[a,b)这一段的值算出来
int res=0;
bool flag=0;
for(int i=a;i<b;++i){
if(s[i]!='0') flag=1;
if(s[i]=='0'&&flag==0&&i!=b-1) return 256;//前导0不合法
res=res*10+s[i]-'0';
}
return res;
}
void cutIP(string s){//枚举三个'.'放在哪里
int si=s.size();
for(int i=1;i<si-2;i++){
if(val(s,0,i)>255) continue;
for(int j=i+1;j<si-1;j++){
if(val(s,i,j)>255) continue;
for(int k=j+1;k<si;k++){
if(val(s,j,k)>255||val(s,k,si)>255) continue;
cnta++;
ans[cnta][0]=val(s,0,i);
ans[cnta][1]=val(s,i,j);
ans[cnta][2]=val(s,j,k);
ans[cnta][3]=val(s,k,si);
}
}
}
}
void buildIP(int cnt,string s){//将一个字符串对称，成为一个回文串
string res=s;
reverse(s.begin(),s.end());
if(cnt%2) s.erase(0,1);
res=res+s;
cutIP(res);
}
bool checku(string s){//检查是否有数字没有用到
bool flag[15]={0};
int si=s.size(),cnt=0;
for(int i=0;i<si;i++)
if(!flag[s[i]-'0']){
flag[s[i]-'0']=1;
cnt++;
}
if(cnt<n) return 0;
else return 1;
}
void IP(int cnt,int ps,string s){
if(ps>(cnt+1)/2){
if(checku(s))
buildIP(cnt,s);
return;
}
for(int i=1;i<=n;i++) IP(cnt,ps+1,s+char(x[i]+'0'));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
for(int i=4;i<=12;i++)//枚举IP地址的长度
IP(i,1,"");
printf("%d\n",cnta);
for(int i=1;i<=cnta;i++){
printf("%d",ans[i][0]);
for(int j=1;j<4;j++) printf(".%d",ans[i][j]);
printf("\n");
}
return 0;
} 思路2
预处理出0-255中所有数的位数（cnum），每一位（num），包含的数字（h，通过位运算，类似于状压dp，将bool数组转成一个整数），能不能用（flag，保证用到的数里没有未给出的数字）。应当包含哪些数（即给出的数，have，与h原理相同），ex[i] 是i是否被包含。
再枚举每一段的数（0-255），判断是否包含所有给出的数且不包含其他数，是否是回文串。
最后ans记录答案并输出。具体见代码。
主要细节：0的处理。由于t=i=0，无法进入while循环，要将预处理中的每个数组的第0个进行特殊判断处理。
代码优势：预处理后常数很小，代码结构清晰不易写错，好调试。
#include<bits/stdc++.h>
using namespace std;
int n,x[15],have,h[256],num[256][4],cnum[256],cntans;
bool flag[256],ex[10];
struct answer{
int p,q,s,t;
} ans[1000005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x[i]);
have|=(1<<x[i]);
ex[x[i]]=1;
}
h[0]=1;
num[0][++cnum[0]]=0;
for(int i=0;i<256;i++){
int t=i;
flag[i]=1;
while(t){
h[i]|=(1<<(t%10));
num[i][++cnum[i]]=t%10;
if(!ex[t%10]) flag[i]=0;
t/=10;
}
if(i==0&&!ex[0]) flag[i]=0;
}
for(int a=0;a<256;a++){
if(!flag[a]) continue;
for(int b=0;b<256;b++){
if(!flag[b]) continue;
for(int c=0;c<256;c++){
if(!flag[c]) continue;
if((h[a]|h[b]|h[c])!=have) continue;
//这个剪枝很关键，前三个数确定，IP地址已经过半，可以判断是否包含了所有数
for(int d=0;d<256;d++){
if(!flag[d]) continue;
int res[20],cntr=0;
for(int i=cnum[a];i>=1;i--) res[++cntr]=num[a][i];
//while x%10 处理出来的数位是倒着的，将它们合并时也得倒着
for(int i=cnum[b];i>=1;i--) res[++cntr]=num[b][i];
for(int i=cnum[c];i>=1;i--) res[++cntr]=num[c][i];
for(int i=cnum[d];i>=1;i--) res[++cntr]=num[d][i];
bool f=1;
for(int i=1;i<cntr-i+1;i++)
if(res[i]!=res[cntr-i+1]){
f=0;
break;
}
if(f) ans[++cntans].p=a,ans[cntans].q=b,ans[cntans].s=c,ans[cntans].t=d;
}
}
}
}
printf("%d\n",cntans);
for(int i=1;i<=cntans;i++) printf("%d.%d.%d.%d\n",ans[i].p,ans[i].q,ans[i].s,ans[i].t);
return 0;
}