CF 292C Beautiful IP Addresses - c++编程基础

题目思路：

Croc 2013年第一轮，晚上做实在没精神啊。。。

简单的分析一下题意可以发现如果n>=7,肯定是无解的,因为每个值各不相同，且必须都用到一次，还要满足回文，假设n=7，那么最小长度=6+1+6=13 > 12 ，所以n>=7肯定无解。

所以深搜暴力求解出所有回文串，个数不会超过2*6^6(n<=6),在枚举每个回文串，对每个回文串添加‘.’，形成IP，所以最大运算次数为27*2*6^6=2519424（肯定远小于这个数的）,而且必须保证形成的ip去掉.后仍为原始的回文串，否则会出现重复与错误。

代码：

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define ll __int64
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define eps (1e-8)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#pragma comment(linker, "/STACK:102400000,102400000")
template T _max(T x,T y){return x>y x:y;}
template T _min(T x,T y){return x template T _abs(T x){return (x < 0) -x:x;}
template T _mod(T x,T y){return (x > 0) x%y:((x%y)+y)%y;}
template void _swap(T &x,T &y){T t=x;x=y;y=t;}
template void getmax(T& x,T y){x=(y > x) y:x;}
template void getmin(T& x,T y){x=(x<0 || y int TS,cas=1;
const int M=100000+5;
int n,a[11];
int vis[11],cnt,tot;
struct ip{
int a,b,c,d;
ip(int _a=0,int _b=0,int _c=0,int _d=0){a=_a,b=_b,c=_c,d=_d;}
void show(){printf("%d.%d.%d.%d\n",a,b,c,d);}
};
struct node{
int a[22],len;
void show(){for(int i=1;i<=len;i++) printf("%d ",a[i]);puts("");}
}tmp;
vectorret;
vectorpal;

bool check(int& num,int len,int cur,int p){
num=0;
for(int i=1;i<=len;i++) num*=10,num+=pal[p].a[cur++];
if(num>255 || (num!=0 && pal[p].a[cur-len]==0) || (num==0 && len!=1))
return false;
return true;
}

void addToRet(int p){
int i,j,k,l,cur;
ip t;
for(i=1;i<=3;i++) if(pal[p].len-i<=9){
if(pal[p].len-i<3 || pal[p].len if(!check(t.a,i,1,p)) continue;
for(j=1;j<=3;j++) if(pal[p].len-i-j<=6){
if(pal[p].len-i-j<2 || pal[p].len if(!check(t.b,j,i+1,p)) continue;
for(k=1;k<=3;k++) if(pal[p].len-i-j-k<=3){
if(pal[p].len-i-j-k<1 || pal[p].len if(!check(t.c,k,i+j+1,p)) continue;
l=pal[p].len-i-j-k;
if(!check(t.d,l,i+j+k+1,p)) continue;
ret.push_back(t);
}
}
}
}

void dfs(int p){
int i;
if(p>tot){
if(cnt==n){
tmp.len=(tot<<1);
for(i=tot+1;i<=tmp.len;i++)
tmp.a[i]=tmp.a[tmp.len-i+1];
pal.push_back(tmp);
if(tot+tot-1>=4){
tmp.len-=1;
for(i=tot+1;i<=tmp.len;i++)
tmp.a[i]=tmp.a[tmp.len-i+1];
pal.push_back(tmp);
}
}
return;
}
for(i=1;i<=n;i++){
if(!vis[i]) cnt++;
vis[i]++;
tmp.a[p]=a[i],dfs(p+1);
vis[i]--;
if(!vis[i]) cnt--;
}
}

void run(){
int i,j;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
clr_all(vis,0),cnt=0;
ret.clear(),pal.clear();
for(tot=2;tot<=6;tot++) if(tot>=n) dfs(1);
for(i=0;i printf("%d\n",ret.size());
for(i=0;i }

void preSof(){
}

int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while((~scanf("%d",&n))) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define ll __int64
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define clr_all(x,c) me

CF 292C Beautiful IP Addresses (一)