2013
12-23

# Consecutive sum

Every body knew that 15 = 1+2+3+4+5 = 4+5+6 = 7+8. Now give you a number N, tell me how many ways to represent N as a sum of consecutive positive integers. For example, 15 have 3 ways to be found.

Each line will contain an signed 32-bits integer N. Process to end of file.

For each case, output the answer in one line.

15
1050

3
11

hash时，把它转化成一个9位的整数，质数取余，拉链法判重。

hash表开成两维的，分别储存两个队列的搜索结果，同时还保存搜到每一个状态所用的step。

1.如果初状态和末状态的逆序数的奇偶性不同，则无解，直接输出-1。证明方法网上有。

2.如果初状态与末状态一样，直接输出0。不要再用双广，双广的话输出结果会是2(显然)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define PRIME 455809
using namespace std;

struct node
{
node(unsigned int t)
{
s=t;
next=NULL;
}
unsigned int s;
int step;
node *next;
};
node *hashtable[460000][2];
struct State
{
int map[10];
int pos;
int step;
} states,statee;

void hinsert(State s,bool ty)
{
unsigned int i,st=0;
for(i=1; i<=9; i++)
st=st*10+s.map[i];
node *f=new node(st);
f->step=s.step;
f->next=hashtable[st%PRIME][ty];
hashtable[st%PRIME][ty]=f;
}
bool exist(State s,bool ty,int &res)
{
unsigned int i,st=0;
for(i=1; i<=9; i++)
st=st*10+s.map[i];
node *f=hashtable[st%PRIME][ty];
while(f)
{
if(f->s==st)
{
res=f->step;
return true;
}
f=f->next;
}
return false;
}
int transfer(State t,queue <State>&Q,bool ty)
{
State s;
int res;
s=t;
if((s.pos-3)>0)
{
swap(s.map[s.pos],s.map[s.pos-3]);
s.step++;
s.pos-=3;
if(exist(s,!ty,res))
{
return (s.step+res);
}
if(!exist(s,ty,res))
{
Q.push(s);
hinsert(s,ty);
}
}
s=t;
if(s.pos+3<10)
{
swap(s.map[s.pos],s.map[s.pos+3]);
s.step++;
s.pos+=3;
if(exist(s,!ty,res))
{
return (s.step+res);
}
if(!exist(s,ty,res))
{
Q.push(s);
hinsert(s,ty);
}
}
s=t;
if((s.pos+1)%3!=1)
{
swap(s.map[s.pos],s.map[s.pos+1]);
s.step++;
s.pos+=1;
if(exist(s,!ty,res))
{
return (s.step+res);
}
if(!exist(s,ty,res))
{
Q.push(s);
hinsert(s,ty);
}
}
s=t;
if((s.pos-1)%3!=0)
{
swap(s.map[s.pos],s.map[s.pos-1]);
s.step++;
s.pos-=1;
if(exist(s,!ty,res))
{
return (s.step+res);
}
if(!exist(s,ty,res))
{
Q.push(s);
hinsert(s,ty);
}
}
return 0;
}

queue<State>Qs;
queue<State>Qe;
int reversenum(State a)
{
int res=0;
for(int i=1; i<=9; i++)
{
if(a.map[i]==0)continue;
for(int j=i-1; j>=1; j--)
{
if(a.map[j]>a.map[i])res++;
}
}
return res;
}
bool prejudge(State a,State b)
{
int t1=reversenum(states);
int t2=reversenum(statee);
if((t1+t2)%2!=0)
{
printf("-1\n");
return true;
}
bool tflag=0;
for(int i=1; i<=9; i++)
{
if(a.map[i]!=b.map[i])
{
tflag=1;
break;
}
}
if(!tflag)
{
printf("0\n");
return true;
}
else return false;
}
int main()
{
int tcases;
scanf("%d",&tcases);
while(tcases--)
{
memset(hashtable,0,sizeof(hashtable));
for(int i=1; i<=9; i++)
{
scanf("%d",&states.map[i]);
if(states.map[i]==0)states.pos=i;
}
statee.step=0;
for(int i=1; i<=9; i++)
{
scanf("%d",&statee.map[i]);
if(statee.map[i]==0)statee.pos=i;
}
states.step=0;

hinsert(states,0);
hinsert(statee,1);
if(prejudge(states,statee))continue;

bool endflag=0;
while(!Qs.empty())Qs.pop();
while(!Qe.empty())Qe.pop();
Qs.push(states);
Qe.push(statee);
while(!Qs.empty()||!Qe.empty())
{
int ns=Qs.size(); //这个是处于同一层的状态的数量
int ne=Qe.size();
if(ns<ne||ne==0) //选择元素个数较少的队列进行扩展
{
for(int i=0; i<ns; i++)//扩展s队列。一次扩展一层，这是双广正确性(得到最优解)的重要保证
{
State cur;
cur=Qs.front();
Qs.pop();
int res=transfer(cur,Qs,0);
if(res)
{
printf("%d\n",res);
endflag=1;
break;
}
}
}
else
{
for(int i=0; i<ne; i++)
{
State cur;
cur=Qe.front();
Qe.pop();
int res=transfer(cur,Qe,1);
if(res)
{
printf("%d\n",res);
endflag=1;
break;
}
}
}
if(endflag)break;
}
}
return 0;
}

1. This write-up presents the gentle in which we can notice the fact. this is extremely wonderful one and gives in depth info.

2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。