IDA*的一道题目

Leave a comment

被搞残了,还把袁源也连累了,主要昨天写的有点厌烦情绪,不愿意静心来分析代码!
这个习惯太差了,不会思考的人就不会写代码,我悔过我认错!
可以用Gprof来分析代码:gprof -a 。。。。https://www.cs.drexel.edu/cgi-bin/manServer.pl/usr/share/man/man1/gprof.1可以导出函数调用次数,唉!要能用VS的工具就好了,可惜MS的工具要交钱,买不起哟!~~~~
提醒自己:
1。消栈的时候,要注意状态如何减去,很重要[可以多次剪枝],尤其是启发函数加最优剪枝是可以并举!这点是付出代价才学会的!
2。有函数增减性来剪枝的时候,千万要好好写,就是这个把正确的子数给砍掉了!
很奇怪福建的那个为什么不能Accept呢,难道还有什么地方不同,我想自己写个测试数据来试验,结果直接把那个“标程”给跑死了,俄!
算了,点到即止,等把下面的问题搞定再回头优化!
时间:370ms
#include <iostream>
#include <fstream>
using namespace std;
const int MAXSH=10;
unsigned long x,y;
typedef struct state{
    unsigned long a,b,i;
    int g;
    unsigned long path[MAXSH];
}state;
typedef state* stateptr;
const int MAXSK=10000000, INC=1;
state stack[MAXSK];
//pre-defined
void IDAstar(unsigned long x, unsigned long y);
unsigned long gcd(unsigned long x, unsigned long y);
//implementation
unsigned long gcd(unsigned long x, unsigned long y){
    //assert(x>0&&y>0);
    if(x==y) return x;//void swap
    if(x>y) x^=y,y^=x,x^=y;
    if(x==0) return y;
    //x<y
    if(x&0x1){//x odd
        if(y&0x1)//y odd
            return gcd(x, (y-x)>>1);
        else return gcd(x, y>>1);
    }
    else{//x is even
        if(y&0x1) return gcd(x>>1, y);
        else return 2*gcd(x>>1, y>>1);
    }
}
unsigned long path[MAXSK];
unsigned long best[MAXSK];
void IDAstar(unsigned long x, unsigned long y){
    assert(y>=x);
    if(x==1){
        cout<<1<<" "<<y<<endl;return;
    }
    if(y%x==0){
        cout<<1<<" "<<y/x<<endl;return;
    }
    int top=0,pathT=0u,bindex; unsigned long min=INC;
    bool success=false;
    do{
        //intial
        top=0,pathT+=INC;
        bindex=pathT;
        min=ULONG_MAX;
        stack[0].a=x,stack[0].b=y,stack[0].g=0,stack[0].i=y/x;
        memset((void*)best, 0xff, sizeof(long)*MAXSK);//sigh!
        top++;//stack top
        do{//pop-up first item
            state cur=stack[–top];
            if(cur.a==1){
                if(cur.g<=bindex&&cur.b>cur.i&&cur.b<best[bindex]){//incremental order
                    best[cur.g]=cur.b,bindex=cur.g;
                    memcpy((void*)best, cur.path, sizeof(long)*cur.g);
                    success=true;
                }
            }
            else{//cur.a!=1
                if(cur.a*(cur.i+1)/cur.b+cur.g<=pathT){//branches cut-off
                    long pre=(cur.b/cur.a>cur.i+1?cur.b/cur.a:cur.i+1),//incremental
                    next=(cur.b*(pathT-cur.g))/cur.a;//low boundary wrong!
                    if(cur.b/cur.a+pathT-cur.g+1>best[bindex]&&next<=cur.i){
                        continue;
                    }
                    if(pre<=next&&pre<=best[bindex]){//f value
                        for(long k=next;k>=pre;k–){//best[num] to cut off branches
                            long a=cur.a*k-cur.b, b=cur.b*k;//overflow
                            if(a<=0||b<=0) continue;//incremental function
                            long h=a*(k+1)/b;
                            //(a/b-1/k)*(k+1)=(k+1)a/b-(1+1/k),k des!
                            if(b/a+pathT-cur.g+1>best[bindex]) break;
                            if(h+cur.g+1>pathT) continue;
                            unsigned long d=gcd(a,b);
                            stack[top].a=a/d,stack[top].b=b/d,stack[top].g=cur.g+1;
                            stack[top].i=k;//previous value
                            stack[top].path[cur.g]=k;//copy into path
                            memcpy(stack[top].path, cur.path, sizeof(long)*cur.g);
                            top++;
                        }
                    }
                }
                else{
                    if(cur.g+cur.b/cur.a<min){
                        min=cur.g+cur.b/cur.a;//cut-off branches’s boundary
                    }
                }
            }
        }while(top>0&top<MAXSK);
    }while(!success&&top<MAXSK&&pathT<MAXSH);//top is valid?
    int i=0;
    while(best[i]!=ULONG_MAX){cout<<best[i]<<" ";i++;}
    cout<<endl;
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif
    int n;
    cin>>n;
    while(n>0){
        cin>>x,cin>>y;
        IDAstar(x,y);
        n–;
    }
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
 
递归版本的标程在CSDN上有,不过有些特殊的测试数据没有我的跑得快!但是福建的居然说我的答案有问题,我自己写了个程序来生成数据验证,都没发现错!
算了吧,没必要较真聊!
 
我的两组稀奇古怪的测试数据:那个递归的标程跑了3分钟多,我的只用了16s,不过牛人的程序应该瞻仰的,写得很飘逸!
袁源说的对,程序就是要思路清晰,我一定要加油,把基本算法的框架都要烂熟于胸[那种一边写一边写的习惯太要不的了!虽然我现在还完全做不到,但我一直会向着对程序框架和关键点都能熟练实现的目标加油的!]
Advertisements

A*的一道题目

Leave a comment

A*是一种带权广度优先的启发算法,很经典的一道题目!
启发函数比较难找,而且,思路比较绕,题目链接!
2472 – Editing a Book
Asia – Kanpur – 2001/2002
 
最后的启发函数:是用后继错误的字符数目[书上的表述有问题,不过牛人写书都是观其大略,能理解]做的,dH<=3,这样,每次的H下降最多为3,为保持f的递增,只有把g函数[每次增加1]强行*3,好了,这样f就是一个递增函数了!
书上说用二叉树作字典,个人认为没有hash的效果好,实验了下,确实如此!当然如果二叉树的节点进行块分配的话,或许要快点,但路径长度的优化,涉及到平衡问题.如果用Treap的实现,递归栈必然会影响其性能.观察下,每个特征字符串长度不大[Color Hash那个长度太大,即使用unsigned __int64也是拼命的冲突],因此hash应该要快点,如果追求性能的话,可以将hash的next节点作块分配,当然这里就不说了[因为CRT和系统的内存分配不一定是连续的,只是C有一次性分配的策略,因此Jon才提出块分配的优化,个人认为看情况了!我这里一个slot的冲突本来就不大,在做块分配逻辑的话,反而在初始时会影响内存分配,所以就没写]
 
T1是待扩展表,T2是判重表[前者用优先队实现,自己用***_heap实现了个,很快15行不到;判重麻烦点,多写了个replace的逻辑],还做了一个对象分配表[这个很重要,程序反复派拨内存对性能影响很大;而且用char代替了int数组,这里要注意cin读入的时候与类型相关,要自己转型!]
 
还有就是这道题目的非常麻烦的地方,如果进行字符串的裁剪,和H函数值计算:
这里用了一个简单的方法:用位图标记连续区域,最优的策略是不会破坏连续区域的,再在做位图的时候,把后继标志记录下来f[value]=i,代表值为value的后继在索引i的位置,其实借用了计数的思路![预处理只需要0(len)].
我花了很长时间研究怎么剪贴,用代码实现:开始是用直观的思路,真的“粘贴复制”,发现很烦,代码写的近似不可读!
其实不用那么复杂,可以用reverse_segment的逻辑,只需要标记边界即可;只是边界也有两种情况,开始写了一种,调试的时候发现老是栈溢出,但看了下分配数远远不到最大值,郁闷了![曾经有冲动想请教高手]仔细一看,原来是忽略了一种情况,sigh!
 
感觉数据量小的时候,c++和c的文件操作时间上差别不大,虽然实际上隐藏的咚咚远远不是时间能衡量的!
 
时间:290MS[gcc]
#include <iostream>
#include <bitset>
#include <fstream>
#include <algorithm>
using namespace std;
//state length
int len=0, index=0;
const int MAX=20;
char input[MAX];//save 3/4
//state type
typedef struct state{
    char* s;
    state* pre;//g,h,f Heuristic;pre
    int g,h,f;
}state;
typedef state* stateptr;
const int MAXHEAP=10000, MAXHASH=10007, MUL=11;
//default strategy for comparsion
int inline cmp(const void* p1, const void* p2){//cast
    return ((stateptr)p1)->f>((stateptr)p2)->f;
}
//simple priority_queue, 18->37lines for priority_queue
class heap{
private:
    int size;
    stateptr _h[MAXHEAP];
public:
    void inti(){//clr heap
        //memset((void*)_h, 0, sizeof(stateptr)*MAXHEAP)
        size=0;
    }
    void push_back(const stateptr p){
        assert(size<MAXHEAP);//heap is less than MAXHEAP threshold
        _h[size++]=p;
        push_heap(_h, _h+size, cmp);
    }
    stateptr pop_front(){
        if(size<=0) return NULL;
        pop_heap(_h, _h+size, cmp),size–;
        return _h[size];//last item
    }
    void replace(const stateptr p){
        for(int i=0;i<size;i++){
            if(memcmp((void*)p->s,(void*)(_h[i]->s),len)==0){
                if(p->f<_h[i]->f) _h[i]->f=p->f;
                return;
            }
        }
    }
    int sz(){return size;}
};
//global heap, for new state
heap h_gT1;
//simple implementation for hash table
typedef struct node{
    unsigned __int64 key;//8bytes
    stateptr s;//4bytes
    node* next;//4bytes
}node;
typedef node* nodeptr;
//simple implemenation for shash, a little too many check for logic for editing book
//70 lines 41->119
class shash{
private:
    nodeptr _bin[MAXHASH];
public:
    void clr(){
        nodeptr nt, pre;
        for(int i=0; i<MAXHASH; i++){
            nt=_bin[i];
            while(nt){pre=nt,nt=nt->next,delete pre;}
        }
    }
    stateptr insert(stateptr ns, int& ret){//must return state pointer!
        if(!ns){ ret=-1; return NULL; }
        unsigned __int64 hKey=0;
        int hEntry=0;
        for(int i=0; i<len; i++) hKey=hKey*MUL+ns->s[i];
        hEntry=hKey%MAXHASH;
        assert(hKey>=0&&hEntry>=0);
        nodeptr nd=_bin[hEntry], newnode, pre=NULL;
        int keycmp=-1;
        for(;nd;pre=nd,nd=nd->next){
            if(hKey<nd->key) continue;
            else if(hKey==nd->key){//hKey==nd->key
                keycmp=memcmp((void*)(nd->s->s), (void*)(ns->s), len);
                if(!keycmp)break;
            }
            else break;
        }
        if(nd&&!keycmp){//replace or not
            if(nd->s->f>ns->f){
                nd->s->f=ns->f; ret=1;return ns;//replace
            }
            ret=-1; return NULL;
        }
        newnode=new node;
        newnode->key=hKey, newnode->s=ns, newnode->next=NULL;
        if(!pre){//pre is NULL
            if(!nd) _bin[hEntry]=newnode;//here severe bugs!
            else _bin[hEntry]=newnode, newnode->next=nd;//here severe bugs!
        }
        else{//pre is null
            if(!nd) pre->next=newnode;
            else pre->next=newnode, newnode->next=nd;
        }
        ret=2;return ns;
    }
    int searchrep(stateptr ns){
        if(!ns) return -1;
        unsigned __int64 hKey=0;
        for(int i=0; i<len; i++) hKey=hKey*MUL+ns->s[i];
        assert(hKey>=0);
        int keycmp=-1;
        nodeptr nd=NULL;//scope checking
        for(nd=_bin[hKey%MAXHASH]; nd; nd=nd->next){
            if(nd->key!=hKey) continue;
            else{
                keycmp=memcmp((void*)(nd->s->s), (void*)(nd->s), len);
                if(!keycmp) break;
            }
        }
        if(nd&&keycmp==0){//equal,replace items in T1 is meanless!so..
            if(nd->s->f>ns->f){
                nd->s->f=ns->f; return 1;//replace
            }
            return 0;//exists
        }
        return -1;//no key
    }
};
//global shash, for existing state
shash h_gT2;
const int MAXSTATE=10000;
class stateBuf{
private:
    state _buf[MAXSTATE];
    char _s[MAXSTATE];
    int top, front;
    int maxtop, maxfront;
public:
    void init(){top=0, front=0,maxtop=0,maxfront=0;}
    stateptr getState(){
        assert(top<MAXSTATE);
        if(top+1>maxtop) maxtop=top+1;
        return _buf + (top++);
    }
    void removeState(){
        top–;
    }
    void removeS(){
        front-=len;
    }
    char* getS(){
        assert(front+len<MAXSTATE);//last index
        if(front+len>maxfront) maxfront=front+len;
        char *tmp=&_s[front]; front+=len;
        return tmp;
    }
    int getMaxTop(){return maxtop;}
    int getMaxFront(){return maxfront;}
};
//global buf for state
stateBuf h_gST;
//backtrack for answer!
void inline print(stateptr cur);
//AStar algorithm
void Astar();
//expand algorithm
void expand(stateptr cur);
//reverse logic
void reverse_l(char* arr, int l, int end);
void inline print(stateptr cur){
    if(!cur) return;
    if(cur->pre) print(cur->pre);
    for(int i=0; i<len; i++) cout<<(int)cur->s[i]<<" ";
    cout<<endl;
}
//A* algorithm : BFS + f fuctions
void Astar(){
    h_gST.init(),h_gT1.inti(), h_gT2.clr();//reset for each case
    int i, ret;
    //intialization
    stateptr ini=h_gST.getState();
    ini->g=0,ini->pre=NULL,ini->s=input;
    for(i=0, ini->h=0; i<len-1; i++)
        if(input[i]!=input[i+1]-1) ini->h++;
    //ini->f function
    ini->f=ini->h;//g is zero starting point!
    h_gT1.push_back(ini),h_gT2.insert(ini, ret);
    assert(ret!=-1);
    bool OK=false; stateptr cur;
    while(!OK&&h_gT1.sz()>0){
        cur=h_gT1.pop_front();
        //check answer
        OK=true;
        for(i=0; i<len-1; i++) OK=OK&&(cur->s[i]==cur->s[i+1]-1);//all true
        if(OK){//print-out all number,backtrack to top
            cout<<index<<" "<<cur->g<<endl;
            print(cur);
            break;
        }
        else expand(cur);
    }
}
//reverse logic
void reverse_l(char* arr, int l, int end){//l,end is boundary index
    for(char *p=arr,*q=arr+end; p<=q; p++,q–)
        if(*p!=*q) *p^=*q,*q^=*p,*p^=*q;
    for(char *p=arr,*q=arr+end-l-1; p<=q; p++,q–)
        if(*p!=*q) *p^=*q,*q^=*p,*p^=*q;
    for(char *p=arr+end-l,*q=arr+end; p<=q; p++,q–)
        if(*p!=*q) *p^=*q,*q^=*p,*p^=*q;
}
//expand algorithm
void expand(stateptr cur){
    char *sp=cur->s;//problem here!how to find next status
    //we shouldn’t cut-off right segment to small pieces
    bitset<64> bt(0x0);//[0…len-1]
    int f[len+1];//f function,continual digital
    int i,start,l;
    for(i=0;i<len;i++){
        f[sp[i]-1]=i;//sp[i]-1 ‘s following item
        assert(sp[i]-1<=len);//keep true
        if(i!=len-1){
            if(sp[i]==sp[i+1]-1) bt.set(i, 1);//right
            else bt.set(i, 0);
        }
    }
    f[len]=len;//last one is invalid
    //status change,copy of status
    for(i=0;i<len;){//find first 0, then next 0
        start=i,l=1;//intial value
        while(bt.test(i)&&i<len) l++,i++;
        if(i==len) break;
        /*logic:generate status*/
        stateptr next=h_gST.getState();
        char* str=h_gST.getS();
        strncpy(str, cur->s, len);//copy to the shadow buffer
        next->g=cur->g+1,next->h=cur->h,next->s=str,next->pre=cur;
        //reverse logic,[i…last-1], the whole length is l-1
        int last=f[(int)str[start+l-1]];//last segment
        /*Heuristic Algorithm for H*/
        if(start>0&&last<len&&str[start-1]==str[last]-1) next->h–;
        if(last>0&&last<len&&str[last-1]==str[start]-1) next->h–;
        if(last<len) next->h–;
        //assert(next->h>=0);//right,keep true
        next->f=next->g*3+next->h;
        /*reverse logic, [start, start+l-1, last-1]*/
        assert(last!=start);//impossible
        if(last>start)//first
            reverse_l(str+start, l-1, last-start-1);//right!
        else
            reverse_l(str+last, start-1-last, start+l-1-last);//based on str+last pointer address
        /*OK checking for last*/
        int sr=h_gT2.searchrep(next);
        if(sr==-1)//new state
            h_gT1.push_back(next);
        else if(sr==1)//existing state, bug may be in T1, replace in T1
            h_gT1.replace(next);
        else //invalid state
            h_gST.removeS(),h_gST.removeState();
        i=start+l;//get next
    }
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in){
        cerr<<"error to open input.txt"<<endl;
        return EXIT_FAILURE;
    }
    cin.rdbuf(in.rdbuf());
    #endif
    int k;
    #ifdef fbase
    while(cin>>index&&index){
        cin>>len;
        for(int i=0;i<len;i++)
            cin>>k,input[i]=k;//int
        Astar();
    }
    #else
    FILE* fp=fopen("input.txt","r");
    if(!fp) return EXIT_FAILURE;
    while(fscanf(fp, "%d", &index)&&index){
        fscanf(fp, "%d", &len);
        for(int i=0;i<len;i++)
            fscanf(fp, "%d\n", &k),input[i]=k;//fscanf is address operation
        Astar();
    }
    #endif
    #ifdef fbase
    in.close();
    #else
    fclose(fp);
    #endif
    return 0;
}
#undef fbase
 

Color_Hash

Leave a comment

始终在800ms左右徘徊,唉!和书上的0.08差了10倍!难道是自己的hash函数有问题,做了个辅助键,还是不行!
怎么呢?细节还是有问题,状态的标示开的数组太大了,对性能影响太大了,失败的很!
等下在书上标注下!
 
还是很迷惑,不过主要问题是没有找到一个比较好的方法来去掉,path指针,为了省掉BFS的队列,又要增加状态的储存栈,实在是两者不可
兼得呀!还是有问题,我要疯了,昨晚写着写着Vista直接蓝屏了,搜索太容易爆栈了!
还是内力不过,加油写代码!
 
要点:
1.hash表的储存,hKey是一个辅助键,可以屏蔽掉一些明显不等的键值;[char的空间储存可以比int小很多,可惜没能找到一个比较好的映射函数,如果能找到一个
单射函数,那就爽了,根本不用memcmp比较了,失败!]
2.反向搜索的路径和正向搜索的路径是对称的,因此一定要在反向搜索时,把搜索路径转化到正向路径上
3.谁能告诉我,如果把hash表里面的路径空间再节省点,估算了下20MB,完全拿不上台面!不管了,下一个课题了!
 
时间:800MS[gcc]
/*
*ACM/ICPC Regional Contest : Spain
*Perimeter search algorithm
*/
#include <iostream>
#include <fstream>
#include <memory>
#define debug
#undef debug
using namespace std;
//Hashtable macro
//Hashtable pre-defined macro
const int NUMOFKEY=24, HSIZE=6007, MUL=5, MAX=17,//take care of hash overflow
    BACKHEIGHT=9,
    MAXBUF=10000000,MAXPATH=10000000,//20000000->20MB
    HALF=NUMOFKEY/2;
char input[NUMOFKEY], cmd[MAX], bestcmd[MAX];
char t[NUMOFKEY]={0,3,4,3,0,5,6,5,0,1,2,1,0,7,8,7,0,9,10,9,0,1,2,1};//final status
char buf[MAXBUF],pat[MAXPATH];
int backcmd[5]={0,3,4,1,2};//ignore the 0
int i_gK=0,i_gP=0,bestlen;
 
typedef struct node{
    __int64 key;//3key->64
    char *value, *path;//64
    int h;node* next;//64
}node;
typedef node* nodeptr;
nodeptr hash[HSIZE];//take care of bugs,6000*6->36K
//insert:bool-true,false;
bool insert(char* value, char* path, int h){//Key must be terminated!
    if(!value||!path) return false;
    //Hash key
    unsigned __int64 hKey=0;
    int hEntry=0, keycmd=-1;
    //char may be terminate
    for(int i=0; i<NUMOFKEY-3; i++) hKey=hKey*MUL+value[i];
    hEntry=hKey%HSIZE;
    #ifdef debug
    assert(hEntry>=0&&hEntry<HSIZE);
    #endif
    nodeptr nd=hash[hEntry], newnode, pre=NULL;//current node and pre
    for(;nd;pre=nd,nd=nd->next){
        if(nd->key!=hKey) continue;
        keycmd=memcmp(nd->value, value, NUMOFKEY-3);
        if(keycmd) continue;
        else break;//memcmp==0
    }
    //node==NULL||node->key>=hKey
    if(nd!=NULL&&!keycmd){
        if(h<nd->h){nd->h=h; nd->path=path; return true;}
        else if(h==nd->h) return true;
        else return false;
    }
    //one time for construction
    newnode=new node;
    newnode->key=hKey,newnode->value=value,newnode->path=path,newnode->h=h, newnode->next=NULL;
    if(!nd){//node==NULL
        if(!pre) hash[hEntry]=newnode;
        else pre->next=newnode;
    }
    else{//node!=NULL,
        if(!pre) hash[hEntry]=newnode;
        else pre->next=newnode;
        newnode->next=nd;
    }
    return true;
}
//nodeptr is required to return, that is needed to decide how to add path!
nodeptr search(char* value){
    if(!value) return NULL;
    unsigned __int64 hKey=0;
    int hEntry=0;
    for(int i=0;i<NUMOFKEY-3;i++) hKey=hKey*MUL+value[i];
    #ifdef debug
    assert(hKey>=0);
    #endif
    hEntry=hKey%HSIZE;
    for(nodeptr nd=hash[hEntry]; nd; nd=nd->next){
        if(nd->key!=hKey) continue;//obvious, not equal
        if(!memcmp(nd->value, value, NUMOFKEY-3)) return nd;//lose of quality, sigh!
    }
    return NULL;
}
//reset all
void biBFS();
//reuse cmd[MAX] to record path, then use pat to record!take care of ending
void backdfs(char* value, int step);
void fordfs(char* value, int step);
void rotate_t(char* arr, int type);
void rotate_t(char* arr, int type){//这个函数看似复杂,实际上运行效率比较高,基本已经不用改了
    int i,j;
    if(type==1){//left wheel turn CLOCK-WISE
        for(i=0,j=HALF-1;i<=j;i++,j–){//[0…HALF-1], reverse
            if(arr[i]!=arr[j]) arr[i]^=arr[j];arr[j]^=arr[i];arr[i]^=arr[j];
        }
        if(arr[0]!=arr[1])
            arr[0]^=arr[1];arr[1]^=arr[0];arr[0]^=arr[1];
        for(i=2, j=HALF-1;i<=j;i++,j–){
            if(arr[i]!=arr[j])
                arr[i]^=arr[j];arr[j]^=arr[i];arr[i]^=arr[j];
        }
        memcpy(arr+NUMOFKEY-3,arr+HALF-3,3);
    }
    else if(type==2){//right wheel turn CLCOK-WISE
        for(i=HALF,j=NUMOFKEY-1;i<=j;i++,j–){//[HALF…NUMOFKEY-1], reverse
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        if(arr[NUMOFKEY-1]!=arr[NUMOFKEY-2])
            arr[NUMOFKEY-1]^=arr[NUMOFKEY-2],arr[NUMOFKEY-2]^=arr[NUMOFKEY-1],arr[NUMOFKEY-1]^=arr[NUMOFKEY-2];
        for(i=HALF,j=NUMOFKEY-3;i<=j;i++,j–){
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        memcpy(arr+HALF-3,arr+NUMOFKEY-3,3);
    }
    else if(type==3){//left wheel turn COUNTER-CLOCK-WISE
        for(i=0,j=HALF-1;i<=j;i++,j–){//[0…HALF-1], reverse
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        if(arr[HALF-1]!=arr[HALF-2])
            arr[HALF-1]^=arr[HALF-2],arr[HALF-2]^=arr[HALF-1],arr[HALF-1]^=arr[HALF-2];
        for(i=0, j=HALF-3;i<=j;i++,j–){
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        memcpy(arr+NUMOFKEY-3,arr+HALF-3,3);
    }
    else if(type==4){//right wheel turn COUNTER-CLOCK-WISE
        for(i=HALF,j=NUMOFKEY-1;i<=j;i++,j–){//[HALF…NUMOFKEY-1], reverse
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        if(arr[HALF]!=arr[HALF+1])
            arr[HALF]^=arr[HALF+1],arr[HALF+1]^=arr[HALF],arr[HALF]^=arr[HALF+1];
        for(i=HALF+2,j=NUMOFKEY-1;i<=j;i++,j–){
            if(arr[i]!=arr[j]) arr[i]^=arr[j],arr[j]^=arr[i],arr[i]^=arr[j];
        }
        memcpy(arr+HALF-3,arr+NUMOFKEY-3,3);
    }
}
void backdfs(char* value, int step){
    if(step>BACKHEIGHT) return;
    int cur,cup;
    for(int i=1;i<5;i++){//cmd for height
        cmd[step]=backcmd[i];//here:command for back-rotated
        cur=i_gK,cup=i_gP,i_gK+=NUMOFKEY,i_gP+=step+1;//buf[i_gK…NUMOFKEY],pat[i_gP…BACKHEIGHT+1]
        #ifdef debug
        assert(i_gK<MAXBUF&&i_gP<MAXPATH);
        #endif
        memcpy(buf+cur,value,NUMOFKEY);
        memcpy(pat+cup,cmd,step+1);//[0…step],step+1 items
        rotate_t(buf+cur, i);
        if(insert(buf+cur, pat+cup, step))
            backdfs(buf+cur, step+1);
        else i_gK-=NUMOFKEY,i_gP-=(step+1);//move back,对于dirty state要毫不留情,只要不放入hash,一概复用!
    }
}
void fordfs(char* value, int step){
    if(step>bestlen-BACKHEIGHT) return;//cut-off half of branch
    nodeptr cur=search(value);
    if(!cur){
        for(int i=1; i<5; i++){
            cmd[step]=i;
            rotate_t(value, i);
            fordfs(value, step+1);
            rotate_t(value, backcmd[i]);//DFS的代码模板,不说什么了!
        }
    }
    else{//cur already exists for backdfs,cur->path[0,cur->h] back_table
        if(cur->h+1+step<bestlen){//back table[0…cur->h], however, fordfs?->0…step-1
            bestlen=cur->h+step+1;
            memcpy(bestcmd, cmd, step);
            for(int i=step,j=cur->h;j>-1;i++,j–) bestcmd[i]=cur->path[j];
        }
    }
}
void biBFS(){
    if(!memcmp(input, t, NUMOFKEY))//same
        cout<<"PUZZLE ALREADY SOLVED"<<endl;
    else{
        bestlen=17;
        fordfs(input, 0);
        if(bestlen>=17)
            cout<<"NO SOLUTION WAS FOUND IN 16 STEPS"<<endl;
        else{//out for best
            for(int i=0; i<bestlen; i++)
                if(bestcmd[i]!=0) cout<<(int)(bestcmd[i])<<" ";
            cout<<endl;
        }
    }
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in){
        cerr<<"error to open input.txt"<<endl;
        return EXIT_FAILURE;
    }
    cin.rdbuf(in.rdbuf());
    #endif
    int n,i=0,k;
    cin>>n;
    backdfs(t, 0);//search back for one time,由于从一个终结状态出发,因此我只需要做一个公共的hash表就可以了,9路长时,速度最快,和书上差不多,估计我的系统高速缓存相关,要比书上大一个级别
    while(n>0){
        for(i=0;i<NUMOFKEY;i++){ cin>>k, input[i]=k;}
        cout<<endl;
        biBFS();
        n–;
    }
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase

Hash+周界,等于头痛

Leave a comment

写了点Win32的咚咚,感觉比较顺手,再回头写算法,头大头大!
Hash+周界,等于我直接崩溃!
Hash的值越界了,还算的多开心的,俄!加上按位比较,速度又慢了很多!
加大反向搜索空间,快了很多,可惜答案一直不对,头痛得很!

关于wcout,wofstream的一些东西

Leave a comment

遇到一个问题,解决了,做个总结:WIN32编程原来没想到把c++和WIN32放在一起做开发,上次被个缓冲区的溢出搞怕了,所以用c++的流来代替!

结果故事就开始了,文章有点长,要读做好心理准备哈![其实,要知道答案不用看前面,直接看case就晓得怎么编码了,不过,如果你懂了运行时的机制,那么你也就懂料,为什么会有这个问题,所以。。。]

  • 总结下在VC[2005]下的CRT调用

[存在模式转换wcout,wiofstream,如果不需要的话,直接调用_fwrite(crt的ASCI运行时)写入到设备即可]:

operator<< -> streambuf::virtual streamsize __CLR_OR_THIS_CALL xsputn(const _Elem *_Ptr,streamsize _Count)
                  -> int __cdecl fputc (int ch,FILE *str) [msvcr80d.dll]  -> int __cdecl _write_nolock (int fh,  const void *buf, unsigned cnt) [write.c]

最关键的步骤在_write_nolock[这个名字说明函数已经成功通过"关键段"的同步验证]的设计步骤: [这个函数内部会判断所谓的字符模式,注意这个模式是流状态(流缓冲区)的模式]

  1. tmode = _textmode(fh);//测试当前字符状态:__IOINFO_TM_ANSI(ASCN C模式),__IOINFO_TM_UTF8,  __IOINFO_TM_UTF16LE
  2. 当前的字符模式匹配,以及console缓冲区的匹配]                                                                                                                                                               if (_isatty(fh) && (_osfile(fh) & FTEXT))//OK,读取当前模式
    {

                DWORD dwMode;
                _ptiddata ptd = _getptd();
                isCLocale = (ptd->ptlocinfo->lc_handle[LC_CTYPE] == _CLOCALEHANDLE);
                toConsole = GetConsoleMode((HANDLE)_osfhnd(fh), &dwMode);
    }
  3. 转化操作:                                                                                                                                                                                                                toConsole && !(isCLocale && (tmode == __IOINFO_TM_ANSI))) //针对Console的,若当前locale和标准C不匹配,或者当前字符模式不是默认的ANSI模式,则进行转化:首先进行double convert,然后用writeFile写到设备;                                                                                                                                           

简单的说,就是当前的wcout,cout会根据两点来进行核心操作:

  • 当前字符类型,就是上面提到的字符状态:char->wchar_t,wchar_t->char,下面是调用平台相关API[windows下的WideXXXtoChar,或者相反的函数]
  • 当前的现场[c++程序设计语言里locale类]

但这里有个陷阱,就是看上面的转化条件[若当前locale是标准c时,会进行转化么?不会的!]

说了这么多,MS的CRT宽字符转化是什么时候进行,事实是:当你的字符类型是宽字符,且locale不是标准c时才进行。[不相信的话,去VS里面F11自己看!]

好了,这就很容易解释下面的一些现象了:

case 1:

我们在默认的locale条件下,完全没有转化,直接打出,当前这是由于运行时的环境是简体中文的,因此是能输出中文的!

cout<<locale().name().c_str()<<endl;
cout<<cout.getloc().name().c_str()<<endl;
cout<<"cout   不支持输出中文? "<<endl;

case 2:

我去控制面板将系统语言更改为EN_US,locale("")会获取系统平台相关的默认语言,这个时候自然就不能输出中文了!

[顺便说一句,JRE的设置也是从系统默认语言环境中读取的,所以如果你要给老大做演示,而所有的默认系统对话框都是中文,你知道怎么做萨!]

locale::global(locale(""));//cout.imbue(std::locale("Chinese"));这句是强制的流locale绑定,呵呵,建议用这个,locale("")与系统相关,出了问题不好找
cout<<locale().name().c_str()<<endl;
cout<<cout.getloc().name().c_str()<<endl;
cout<<"cout   不支持输出中文? "<<endl;

以上的两种情况都不存在转化[double convert]问题,下面来看两个比较容易错的情况:[呵呵,开始吓了我一跳,仔细分析了下,恍然大悟]

case 3: wcout的试验

wchar_t s0[15]=TEXT("丁磊");
char s2[30];
::WideCharToMultiByte(CP_ACP, NULL, s0, _countof(s0), s2, _countof(s2), NULL, NULL);//to ASCI
cout<<s2<<endl;
wcout<<s0<<endl;

第一cout肯定是没问题的,情况和case1,case2一样,下面的wcout呢?不要惊讶,如果你追踪堆栈的话,你会发现在 int __cdecl fputc (int ch,FILE *str)之后,会得到一个错误码,然后直接退出:

看看这个函数

wint_t __cdecl fputwc (
        wchar_t ch,
        FILE *str
        )
{
        REG1 FILE *stream;
        REG2 wint_t retval;

        _VALIDATE_RETURN((str != NULL), EINVAL, WEOF);

        /* Init stream pointer */
        stream = str;

        _lock_str(stream);
        __try {

        retval = _fputwc_nolock(ch,stream);

        }
        __finally {
                _unlock_str(stream);
        }

        return(retval);
}

/***
*_fputwc_nolock() –  putwc() core routine (locked version)
*
*Purpose:
*       Core putwc() routine; assumes stream is already locked.
*
*       [See putwc() above for more info.]
*
*Entry: [See putwc()]
*
*Exit:  [See putwc()]
*
*Exceptions:
*
*******************************************************************************/

wint_t __cdecl _fputwc_nolock (
        wchar_t ch,
        FILE *str
        )
{

        if (!(str->_flag & _IOSTRG))
        {
            if (_textmode_safe(_fileno(str)) == __IOINFO_TM_UTF16LE)
            {
                /* binary (Unicode) mode */
                if ( (str->_cnt -= sizeof(wchar_t)) >= 0 ) {
                    return (wint_t) (0xffff & (*((wchar_t *)(str->_ptr))++ = (wchar_t)ch));
                } else {
                    return (wint_t) _flswbuf(ch, str);
                }
            }
            else if (_textmode_safe(_fileno(str)) == __IOINFO_TM_UTF8)
            {
                /*
                 * This is for files open for unicode writes. We need 2 chars
                 * instead of 1. Note that even if we are writing UTF8, we don’t
                 * really need to worry about it here. _write will take care of
                 * proper conversion.
                 */

                char * p = (char *)&ch;

                if(_putc_nolock(*p, str) == EOF)
                    return WEOF;

                ++p;

                if(_putc_nolock(*p, str) == EOF)
                    return WEOF;

                return (wint_t)(0xffff & ch);

            }
            else if ((_osfile_safe(_fileno(str)) & FTEXT))//对于标准输入在这里,前面两种是文本模式
            {
                int size, i;
                char mbc[MB_LEN_MAX];

                /* text (multi-byte) mode */
                if (wctomb_s(&size, mbc, MB_LEN_MAX, ch) != 0)
                {
                        /*
                         * Conversion failed; errno is set by wctomb_s;
                         * we return WEOF to indicate failure.
                         */
                        return WEOF;
                }
                for ( i = 0; i < size; i++)
                {
                        if (_putc_nolock(mbc[i], str) == EOF)
                                return WEOF;
                }
                return (wint_t)(0xffff & ch);
            }
        }
        /* binary (Unicode) mode */
        if ( (str->_cnt -= sizeof(wchar_t)) >= 0 )
                return (wint_t) (0xffff & (*((wchar_t *)(str->_ptr))++ = (wchar_t)ch));
        else
                return (wint_t) _flswbuf(ch, str);
}

为什么呢?你可能有点抓狂,可是确实如此,自己犯的错,MS CRT当然不会替你买单!

问题在wchar_t s0[15]=TEXT("丁磊");//这个编码是多长,4*sizeof(wchar_t),两个中文字符在转化入wchart_t时,是以0xXX的形式放入的,虽然能看到自己的名字很爽,但是字符数组里面的存储可能让你很不爽。每个汉字的高低字节被分别存入两个wchar_t里面!俄!~~

随后的事情就很容易理解了,在下面的函数里面,CRT为你的每个wchar_t进行分别的高低字节验证,发现不符合安全验证规范[说实话,这里追进去看代码,没看的很懂的]!新的_s函数当然不买你的帐!直接返回异常码了!

/* text (multi-byte) mode */
                if (wctomb_s(&size, mbc, MB_LEN_MAX, ch) != 0)
                {
                        /*
                         * Conversion failed; errno is set by wctomb_s;
                         * we return WEOF to indicate failure.
                         */
                        return WEOF;
                }

因此对于case 3: wcout的正确写法:

wchar_t s0[15]=TEXT("丁磊");
 char s2[30];
 ::WideCharToMultiByte(CP_ACP, NULL, s0, _countof(s0), s2, _countof(s2), NULL, NULL);//to ASCI
 cout<<s2<<endl;
 wcout<<s2<<endl;//有点惊讶吧,不过这是对的!

但这样还是不直观,如果更直观的搞定呢,其实很简单,我们强制的给流一个locale状态让它不是ASCI的标准状态即可![这样它就不会到FTEXT模式,而是转到相应的Unicode编码处理处了!]

case 4: wcout,cout

wchar_t s0[15]=TEXT("丁磊");
 char s2[30];
 ::WideCharToMultiByte(CP_ACP, NULL, s0, _countof(s0), s2, _countof(s2), NULL, NULL);//to ASCI
 wcout.imbue(locale("Chinese"));
 cout<<s2<<endl;
 wcout<<s0<<endl;

case 5: 文件操作类似

wchar_t s0[15]=TEXT("丁磊");

wofstream out("proc.txt");
 if(!out) return EXIT_FAILURE;
 try{
  out.imbue(locale("Chinese"));//如果注释掉这行,那wofstream又会傻拉巴即的去当你的字符是FTEXT处理,自然就是被_s给砍掉了,所以proc.txt就是空
  out<<L"输出0:"<<s0<<endl;//注意L,使得“输出0“也是同上处理,所以自然为空
  out<<L"输出1:"<<s0<<endl;
 }catch(const runtime_error& ex){
  cerr<<ex.what()<<endl;//这个不是用异常处理的,所以ex肯定是永远抓不到,是用返回异常码的方式处理
 }
 out.close(); cout<<endl;

  • GCC呢?赫赫,好的多,为什么好的多呢?GCC是一个纯的编程平台,MS CRT里面还有语言包的转化处理,如果你在GCC里面这样写wchar_t *s0=L"丁磊";,GCC编译都通不过,因此你要辛苦点去处理ASCI码了,去翻汉字国标吧!顺便提一下Code::Block里面其实有wofstream的支持的,只是有点麻烦,不如直接调windows的API方便,见http://www.hardforum.com/archive/index.php/t-973922.html[所以MS方便是方便,就是有的时候,让人费解,如果想GCC那样,什么都开放出来,让你自己去看,反而没人骂了]
  • 至于这个MS的support,呵呵,你可以当不存在,因为与其问别人,不如自己动手去看运行时的程序!http://support.microsoft.com/default.aspx/kb/274012
  • 那天看到有人在CSDN上发贴子,不过没人管,估计是比较冷的地方吧!如果不是想将win32和c++结合起来用一下,也不会搞出这个问题来!做过了,就不难了!

一些关于locale的资料:

  1. BJ的《c++程序设计语言》,附录里面-中文名叫《现场》locale
  2. c++网上的库描述[GCC这块没有MS crt做的好,locale的很多东西都不能用!感觉c++的locale理念和MS的相差很远,所以几乎什么都没有!]

今天的收获

Leave a comment

一句,剪枝很重要!
  • A的代码:北大真是福地呀!随便A,连goto这种垃圾也能过,哈哈哈!
Memory: 256K

Time: 125MS

Language: C++

Result: Accepted

 

 

#include <iostream>

using namespace std;

const int MAXLEN = 10,MAXPTS = 10,MAXVALUE = 30000;

int n,a[MAXPTS],b[MAXPTS],cmd[MAXLEN],bestcmd[MAXLEN];
int caseno=1,bestlen;
char *cmdstr[5] = { "ADD", "DIV", "DUP", "MUL", "SUB" };

void try1(int step, int stack, int *s[])
{
  int i,c,sn[MAXPTS],*tmp;
  if(step >= bestlen) return;//看到"剪刀"的作用了,很强大的地方,快了不少

  for(i=0;i<n;i++)
    if(b[i] != s[stack][i]) break;
  if(i == n)
    {
      bestlen = step;memcpy(bestcmd,cmd,sizeof(int)*step);
      return;
    }
  if(step == MAXLEN) return;

  for(c=0;c<5;c++)
    {
      if(c != 2 && stack < 1) continue;
      //if(c == 2 && stack > MAXLEN-1-step) continue;
      cmd[step] = c;
      if(c==0){for(i=0;i<n;i++) sn[i] = s[stack-1][i] + s[stack][i];}
      else if(c==1){
for(i=0;i<n;i++)
    if(s[stack][i] == 0)  goto skip;
    else  sn[i] = s[stack-1][i] / s[stack][i];
      }else if(c==2){
tmp = s[stack+1]; s[stack+1] = s[stack];
try1(step+1,stack+1,s);
s[stack+1] = tmp;
      }else if(c==3){
  for(i=0;i<n;i++) sn[i] = s[stack-1][i] * s[stack][i];
      }else if(c==4){
  for(i=0;i<n;i++) sn[i] = s[stack-1][i] s[stack][i];
      }
      for(i=0;i<n;i++)
         if(abs(sn[i])>MAXVALUE) goto skip;
      tmp = s[stack-1],s[stack-1] = sn;
      try1(step+1,stack-1,s);//keep stack-1 here!
      s[stack-1] = tmp;
      skip: ;
    }
}

void process_data()
{
  int *s[MAXPTS],i;

  s[0] = a;
  bestlen = MAXLEN + 1;
  try1(0,0,s);

  cout<<"Program "<<(caseno++)<<endl;
  if(bestlen > MAXLEN)
    cout<<"Impossible";
  else
    if(bestlen == 0)
      cout<<"Empty sequence";
    else
      for(i=0;i<bestlen;i++){
         cout<<cmdstr[bestcmd[i]];
         if(i!=bestlen-1)cout<<" ";
      }
  cout<<endl<<endl;
}

int main(){
    int i=0;
    while(cin>>n&&n){
        for(i=0; i<n; i++) cin>>a[i];
        for(i=0; i<n; i++) cin>>b[i];
        process_data();
    }
    return 0;
}

  • 被浙大ACM鄙视的代码:完全看不出问题,呵呵!用个bool来控制循环![换成int,居然过了,俄!!]

#include <fstream>
#include <iostream>
using namespace std;

//backup data
const int MaxSize=30,MAXVALUE=30000,cmdn=5,MAXSK=10,thre=10;
//stack is smaller than before
int a[MaxSize],b[MaxSize],cur=1;
int bestcmd[thre],cmd[thre];
char* cmdstr[cmdn]={"ADD", "DIV", "DUP", "MUL", "SUB"};
//for track and dfs
void track(int n);
void dfs(int sk, int cmdnum, int* stk[], int& bestnum, const int&n);

void dfs(int sk, int cmdnum, int* stk[], int& bestnum, const int&n){
    if(sk<0||cmdnum>=bestnum) return;//cut-off branches
    int k=0;
    for(;k<n;k++) if(stk[sk][k]!=b[k]) break;
    if(k==n){//cut-off branches
        bestnum=cmdnum;
        memcpy(bestcmd,cmd,sizeof(int)*cmdnum);
    }
    int s[MAXSK],c,i,*tmp;
    bool skip=false;
    for(c=0;c<cmdn;c++){
        if(sk==0&&c!=2) continue;
        cmd[cmdnum]=c,skip=false;//avoid to access unnecessary array
        //if(c==2&&cmdnum+sk+1>thre)continue;
        if(c==0){//ADD
            for(i=0;i<n;i++){
                s[i]=stk[sk-1][i]+stk[sk][i];
                if(s[i]>MAXVALUE||s[i]<-1*MAXVALUE){skip=true;break;}
            }
        }
        else if(c==1){
            for(i=0;i<n;i++){
                if(stk[sk][i]==0){skip=true;break;}//server bugs here
                s[i]=stk[sk-1][i]/stk[sk][i];
                if(s[i]>MAXVALUE||s[i]<-1*MAXVALUE){skip=true;break;}
            }
        }
        else if(c==2){
            tmp=stk[sk+1],stk[sk+1]=stk[sk];//here,backup the modified item
            dfs(sk+1,cmdnum+1,stk,bestnum,n);
            stk[sk+1]=tmp;
        }
        else if(c==3){
            for(i=0;i<n;i++){
                s[i]=stk[sk-1][i]*stk[sk][i];
                if(s[i]>MAXVALUE||s[i]<-1*MAXVALUE){skip=true;break;}
            }
        }
        else if(c==4){
            for(i=0;i<n;i++){
                s[i]=stk[sk-1][i]-stk[sk][i];
                if(s[i]>MAXVALUE||s[i]<-1*MAXVALUE){skip=true;break;}
            }
        }
        if(!skip){//skip=false;
            tmp=stk[sk-1],stk[sk-1]=s;
            dfs(sk-1,cmdnum+1,stk,bestnum,n);
            stk[sk-1]=tmp;
        }
    }
}

void track(int n){
    int bestnum=thre+1, *stk[MAXSK], i;
    stk[0]=a;
    dfs(0, 0, stk, bestnum, n);
    cout<<"Program "<<(cur++)<<endl;
    if(bestnum==0) cout<<"Empty Sequence";
    else if(bestnum<=thre){
        for(i=0; i<bestnum; i++){
            cout<<cmdstr[bestcmd[i]];
            if(i!=bestnum-1)cout<<" ";
        }
    }
    else cout<<"Impossible";
    cout<<endl<<endl;
}

#define fbased
int main(){
    #ifdef fbased
    ifstream in("input.txt");
    if(!in){cerr<<"error to open input file"<<endl; return EXIT_FAILURE;}
    cin.rdbuf(in.rdbuf());
    #endif
    int n,i=0;
    while(cin>>n&&n){
        for(i=0; i<n; i++) cin>>a[i];
        for(i=0; i<n; i++) cin>>b[i];
        track(n);
    }
    return 0;
}
#undef fbased

搜索基础[DFS,BFS,IDS,基于查找表的周界搜索]

Leave a comment

一道广搜的题目:很容易做错,当然如果不较真的话,早就搞定了!
  • 要点1:open_close表,注意区别状态空间[pre]辅助栈[sk]的状态[天真了,开始想了半天]
  • 要点2:其实不用两个表也能做,只是判重比较耗时间;可以用编程之美的那种思路,把跑过的状态作为close表,因此close表的区间为[0,bt+1),注意是半开区间;如果要用STL algorithm来判重的话,可以作一个unary_function函数子,在find_if在半开区间搜索,注意STL的搜索算法失败是置在结束位的!
  • C++的收获:如何管理堆内存?“零散”堆内存是必须要回收的,否则bad_alloc在搜索里面是非常容易出现的!顺便提一句,这种代码风格不值得提倡,主要是为了练习算法所以才这样写[先抽自己一下],全局变量在大型开发里,还是少用为妙,在多线程坏境里面问题尤其多;就面向对象而言,这种代码完全达不到c++的大众水平,会带坏小朋友的!
  1. 用一个全局的指针数组来保存,然后统一回收[有问题来回折腾heap,效率不高]
  2. 用一个全局的void* buffer来统一分配对内存[这里犯了个错,placement new的buffer也是有地址指向的,因此转成int来更好操作],统一管理内存!
  • STL的效率比较,开始用vector来作open_close表的容器,程序跑了1.2s还可以;换为数组之后,翻了一倍多400MS就搞定了,只是要估计状态空间的总值,开得有点大!

BFS:

1。open_close表vector实现:GCC,1.2s

#include <iostream>
#include <fstream>
#include <memory>
#include <string>
#include <assert.h>
#include <vector>

//Optimal Program : BFS
using namespace std;
const int MaxSize=200, Threshold=10, CMDT=5, MAXVALUE=30000, MAX=5000000;
int a[MaxSize],b[MaxSize],pairs;
int* buffer;

typedef struct{//in order to re-allocate the pointer
 int* s, l, pre/*pre-state in state space*/, sk,/*pre-stack*/ cmd, cmdnum;
}state;

#define fbased 1
long times=0;

char *cmdStr[CMDT]={"ADD", "DIV", "DUP", "MUL", "SUB"};

//output to calculation
inline int* output(state& pre, int cmd, vector<state>& open_close){
 int *s2=open_close[pre.sk].s, *s1=pre.s, *cal=NULL;
 cal=new(&buffer[times*pairs])int[pairs](); times++;
 if(cmd==0)//ADD
  for(int i=0; i<pairs; i++){
   cal[i]=s1[i]+s2[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
 else if(cmd==1){//DIV
  for(int i=0; i<pairs; i++){
   if(!s1[i]) return NULL;//quit with zero on the top of stack
   cal[i]=s2[i]/s1[i];
  }
 }
 else if(cmd==3)//MUL
  for(int i=0; i<pairs; i++){
   cal[i]=s2[i]*s1[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
 else if(cmd==4)//SUB
  for(int i=0; i<pairs; i++){
   cal[i]=s2[i]-s1[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
  return cal;
}

void BFS(int i){
 //open-close table
 vector<state> open_close;
 int bt=0,et,cl=0;//cl for command length
 //current element for start
 state item, next;
 item.s=a,item.pre=item.sk=-1,item.l=1,item.cmdnum=0;//item.l represents the height of stack
 open_close.push_back(item);
 bool t=false;times=0;
 while(cl<=Threshold&&bt<open_close.size()){
  et=open_close.size();cl++;
  while(bt<et){//for the same level
   item=open_close[bt];
   if(!memcmp((void*)item.s, (void*)b, sizeof(int)*pairs)){
    cl=item.cmdnum,t=true;break;
   }
   //single operand, having only one choice
   if(item.l==1){//if the stack height is 1, so only one "DUP" operation
    next.pre=next.sk=bt;//index
    next.l=item.l+1;//stack height
    next.cmd=2;
    next.cmdnum=cl;
    next.s=item.s;//check domain [0…b),check duplicate logic
    open_close.push_back(next);
   }
   else{//stack current is two element at least
    for(int k=0; k<CMDT; k++){
     next.pre=bt;//?right or not,wrong!2 stack units back!
     if(k!=2) {
      next.l=item.l-1,next.sk=open_close[item.sk].sk;
      next.s=output(item, k, open_close);//output bugs!
     }
     else{
      next.l=item.l+1,next.sk=bt,next.s=item.s;
     }
     if(!next.s) continue;//go to next command
     next.cmd=k;
     next.cmdnum=cl;
     open_close.push_back(next);
    }
   }
   bt++;
  }
  if(t)break;
 }//while testing

 cout<<"Program "<<i<<endl;
 if(cl<=Threshold){
  int p,z; string cd;
  if(cl>0){
   do{
    p=item.cmd,z=item.pre;
    cd=" "+cd;
    cd=cmdStr[p]+cd;
    if(z!=-1) item=open_close[z];//both of vector and array support []
   }while(z!=-1&&item.l!=1);//stack keep only one unit, sorry! it’s wrong!
   cout<<cd.c_str()<<endl;
  }
  else if(cl==0)
   cout<<"Empty sequence"<<endl;
 }
 else cout<<"Impossible"<<endl;
}

int main()
{
#ifdef fbased
 ifstream in("input.txt");
 if(!in){
  cerr<<"error to open file"<<endl;
  return EXIT_FAILURE;
 }
 cin.rdbuf(in.rdbuf());
#endif
 buffer=new int[MAX];
 assert(buffer!=NULL);
 int i=1,j,k;
 while(cin>>pairs&&pairs){
  for(k=0;k<2;k++){
   if(!k)
    for(j=0;j<pairs;j++) cin>>a[j];
   else for(j=0;j<pairs;j++) cin>>b[j];
  }
  BFS(i++);
 }

 delete[] buffer;
 int sum=1;
 for(int i=0; i<10; i++)sum*=5;
 cout<<sum<<endl;

 system("pause");

 return 0;
}
#undef fbased

2。open_close表数组实现:GCC,400ms

#include <iostream>
#include <fstream>
#include <memory>
#include <string>
#include <assert.h>
#include <vector>

//Optimal Program : BFS
using namespace std;
const int MaxSize=200,Threshold=10,CMDT=5,MAXVALUE=30000,MAXBUF=5000000;
int a[MaxSize],b[MaxSize],pairs;
int *buffer;//the sum of buffer
//int *g[MAXBUF];
#define std 2

typedef struct{//in order to re-allocate the pointer
 int* s, l, pre/*pre-state in state space*/, sk,/*pre-stack*/ cmd, cmdnum;
}state;

#define fbased 1
long times=0;
state buf[MAXBUF];//state space buffer

char *cmdStr[CMDT]={"ADD", "DIV", "DUP", "MUL", "SUB"};

//output to calculation
inline int* output(state& pre, int cmd){
 int *s2=buf[pre.sk].s, *s1=pre.s, *cal=NULL;
 //cal=new int[pairs];
 //g[times++]=cal;
 cal=new(&buffer[times*pairs])int[pairs](); times++;
 if(cmd==0)//ADD
  for(int i=0; i<pairs; i++){
   cal[i]=s1[i]+s2[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
 else if(cmd==1){//DIV
  for(int i=0; i<pairs; i++){
   if(!s1[i]) return NULL;//quit with zero on the top of stack
   cal[i]=s2[i]/s1[i];
  }
 }
 else if(cmd==3)//MUL
  for(int i=0; i<pairs; i++){
   cal[i]=s2[i]*s1[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
 else if(cmd==4)//SUB
  for(int i=0; i<pairs; i++){
   cal[i]=s2[i]-s1[i];
   if(cal[i]>MAXVALUE||cal[i]<-1*MAXVALUE) return NULL;
  }
  return cal;
}

void BFS(int i){
 //open-close table
 //vector<state> open_close;
 int bt=0,et,cl=0,top=0;//cl for command length
 //current element for start
 state item, next;
 item.s=a,item.pre=item.sk=-1,item.l=1,item.cmdnum=0;//item.l represents the height of stack
 buf[top++]=item;
 //open_close.push_back(item);
 bool t=false;times=0;
 while(cl<=Threshold&&bt<top){
  et=top;cl++;
  while(bt<et){//for the same level
   item=buf[bt];
   if(!memcmp((void*)item.s, (void*)b, sizeof(int)*pairs)){
    cl=item.cmdnum,t=true;break;
   }
   //single operand, having only one choice
   if(item.l==1){//if the stack height is 1, so only one "DUP" operation
    next.pre=next.sk=bt;//index
    next.l=item.l+1;//stack height
    next.cmd=2;
    next.cmdnum=cl;
    next.s=item.s;//check domain [0…b),check duplicate logic
    buf[top++]=next;
    //open_close.push_back(next);
   }
   else{//stack current is two element at least
    for(int k=0; k<CMDT; k++){
     next.pre=bt;//?right or not,wrong!2 stack units back!
     if(k!=2) {
      next.l=item.l-1,next.sk=buf[item.sk].sk;
      next.s=output(item, k);//output bugs!
     }
     else{
      next.l=item.l+1,next.sk=bt,next.s=item.s;
     }
     if(!next.s) continue;//go to next command
     next.cmd=k;
     next.cmdnum=cl;
     buf[top++]=next;
     //open_close.push_back(next);
    }
   }
   bt++;
  }
  if(t)break;
 }//while testing

 cout<<"Program "<<i<<endl;
 if(cl<=Threshold){
  int p,z; string cd;
  if(cl>0){
   do{
    p=item.cmd,z=item.pre;
    cd=" "+cd;
    cd=cmdStr[p]+cd;
    if(z!=-1) item=buf[z];//both of vector and array support []
   }while(z!=-1&&item.l!=1);//stack keep only one unit, sorry! it’s wrong!
   cout<<cd.c_str()<<endl;
  }
  else if(cl==0)
   cout<<"Empty sequence"<<endl;
 }
 else cout<<"Impossible"<<endl;
 //strategy 1: im-efficient!
 //for(int k=0; k<times; k++) delete[] g[k];
}

int main()
{
#ifdef fbased
 ifstream in("input.txt");
 if(!in){
  cerr<<"error to open file"<<endl;
  return EXIT_FAILURE;
 }
 cin.rdbuf(in.rdbuf());
#endif
 buffer=new int[MAXBUF];
 assert(buffer!=NULL);
 int i=1,j,k;
 while(cin>>pairs&&pairs){
  for(k=0;k<2;k++){
   if(!k)
    for(j=0;j<pairs;j++) cin>>a[j];
   else for(j=0;j<pairs;j++) cin>>b[j];
  }
  BFS(i++);
 }

 delete[] buffer;
 return 0;
}
#undef fbased

马上把双向广搜模型和DFS版本写了,搜索是比较有意思,模型比较难,但写出来一种,以后就可以复用了,比较经济的一种算法!

Older Entries