• 一点题外话:昨晚和小件哥通了个电话,两个人都有些感概!人嘛经历一些事情总会有些触动的,我还是希望,无论时间如何流逝,或者说境遇如何的转变[或好或坏],能始终保持一颗进取心和平常心。朋友的经历其实也就是自己的经历,在学习中学会成长,学会淡定的分析,学会用自己的目标来衡量自己,而不是用自己来点亮别人所谓的光环。有的时候,我觉得自己还是比较笨,不会用一些聪明的方式来解决问题,但笨总有笨的价值。还是那句话“驽马十驾,功在不舍”!朋友们都好好加油吧,让自己真正的变强大[尤其是内心],不要为一时的失意或者成绩蒙蔽了眼睛,我们仍然在沿着自己的梦想义无反顾地走下去,全身心且全速的!
  • 搜索树形态的选择:http://acm.pku.edu.cn/JudgeOnline/problem?id=1167

伪代码框架:有的时候伪代码比代码更重要,所以Jon喜欢用AWK来描述框架,可以避免进入实现的细节而不可自拔![参考资料:搜索树形态的选择]
void bus(int cur, int start_x){
if(cur==n){
    若[0…start_x-1]均不为-1,则
        if(start_x<best) best=start_x;
return;
}
orig<-bitset<300> bus;
//置位bitset<300>.set(cur);有问题,还是移到内部为好

1.Insert into end_point
foreach i in [0…start_x-1]{
    if(end[i]==-1&&possible(i)){
 end[i]=cur, 更新所有的bitset<300>bus位段
 //寻找下一个cur’在bus中
 bus(cur’,start_x);
 end[i]=-1,bitset<300>bus<-orig
    }
}
2.Insert into start_point
if(start_x+1<best){
    start[start_x]=cur,//寻找下一个cur’在bus中
    bus(cur’,start_x+1);
    start[start_x]=-1;
}
//恢复bitset<300>.reset(cur);//移动到内部为好
}//bus

  • 剪刀分析:当然除了最优剪刀之外,我们还应该注意可行性剪刀,当partial-table的表项都要大于剩余的bus数目时,我们可以直接剪刀了!这道题目我参照了别人的一个论文,但论文中的数据在下不敢苟同,效率应该可以更好的!
  • 所以辅助结果分析:1。可以先做一个bitset[为什么不用系统的那个呢,我们的题目这里是300个!而系统只是用默认机器字长做的一个,如果用的话,一定报错!]好了,自己的BITSET如何实现呢?查照JON牛的实现,BOP第12章,也是常识性的代码,5分钟之内写不完,只能说明基本功不到家;2。DFS里面肯定要设置和恢复bit位段,两个思路,第一保存下本步设计的置位段,恢复时依次恢复[有多少索引呢?300个bus,起码要用char300来保存];第二,导出当前的bitset,OK,我们自己写的bitset当然可以自定义功能罗,这里把指针传进去,然后把当前的bitset保存下来,由于这里是用memcpy,高速缓存效率是比较明显的!加上运行栈的申请连续内存要快一些,所以很快题目的速度就被提高了很多!
  • 黑书上的速度,如果是针对官方文件的,那作者真的应该好好修正下了,PKU上好多牛人的程序0MS哟[就连本菜的程序对于6的测试,最慢都是0.8s,我估计也是直接抄论文的,呵呵,牛人嘛,懒得写这种垃圾程序罗]
  • 最重要的东西提醒自己:在编写循环的时候,要注意变量边界,对于incre==0,>0,<0的情况一定要通盘考虑,建议以后用assert()来设置,不然出现死循环就很难看料,今天就遇到了!唉!内功还要加强呀!

Source Code

Problem: 1167

User: orlando22

Memory: 280K

Time: 110MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    
    using namespace std;
    const int MAXBIT=10, MAXEL=17, MAXBUS=300;
    //Time list
    int busT[MAXBUS], start[MAXEL], end[MAXEL], n, best;
    
    enum{SHIFT=5,ALL=10,MASK=0x1ff,NONZERO=1};
    class IntVecBit{
    private:
        int vec[10];//10*32 is enough
    public:
        IntVecBit(int zero=NONZERO){
            if(zero==NONZERO) setAll();
            else resetAll();
        }
        void setAll(){
            memset((void*)vec, 0xff, sizeof(int)*ALL);
        }
        void resetAll(){
            memset((void*)vec, 0, sizeof(int)*ALL);
        }
        void set(int bit){
            vec[bit>>SHIFT] |= (1<<(bit&MASK));
        }
        void reset(int bit){
            vec[bit>>SHIFT] &= ~(1<<(bit&MASK));
        }
        bool test(int bit){
            return vec[bit>>SHIFT] & (1<<(bit&MASK));
        }
        void backup(int* bvec){//funny implementation
            memcpy((void*)bvec, (void*)vec, sizeof(int)*ALL);
        }
        void recover(int* bvec){//funny implementation
            memcpy((void*)vec, (void*)bvec, sizeof(int)*ALL);
        }
        int fir(){//for all n test!max is n
            int i=0;
            for(;i<n;i++) if(test(i)) break;//testing error here!
            return i;
        }
        int avail(){
            int i=0;
            for(int j=0; j<n; j++) if(test(j))i++;
            return i;
        }
    };
    //bitset<MAXBUS> bs; only applied for 32 bits
    IntVecBit bs;
    
    //declaration: cur-next bus, start_x-next slot
    //so ending search is from [0...start_x-1]
    void bus(int cur, int start_x, int );
    inline bool possi(int i, int cur);//check if start[i] and end[i] could be pairs
    inline void set(int i);
    
    //implementation
    void bus(int cur, int start_x, int lpartial){//cur....?
        if(cur==n){
            int i=0;
            for(;i<start_x; i++) if(end[i]==-1) break;
            if(i==start_x)//all are not -1
                if(start_x<best) best=start_x;
            return;
        }
        //for common logic
        for(int i=0; i<start_x; i++){
            if(end[i]==-1&&possi(i, cur)){
                int vecb[MAXBIT];
                end[i]=cur,bs.backup(vecb);
                set(i);
                if(lpartial-1<=bs.avail())//这个剪刀要迅速想到的,不难,但可以把速度至少提高一倍
                      bus(bs.fir(), start_x, lpartial-1);
                end[i]=-1,bs.recover(vecb);
            }
        }
        if(start_x+1<best){
            start[start_x]=cur,bs.reset(cur);
            if(lpartial+1<=bs.avail())//这个剪刀要迅速想到的,不难,但可以把速度至少提高一倍
                bus(bs.fir(), start_x+1, lpartial+1);
            start[start_x]=-1,bs.set(cur);
        }
    }
    
    //dummy implementation
    inline bool possi(int i, int cur){
        int incre=busT[cur]-busT[start[i]];
        int next=busT[cur]+incre;//incre may be zero,so...
        //in the domain or not
        if(next>busT[n-1]) return true;
        bool flag=true;
        int start=cur+1, j;
        while(next<=busT[n-1]){//lose solution<=
            for(j=start; j<n; j++){//from start->n-1
                if(busT[j]>next){flag=false;break;}//bigger than next, no-found, jump out of circle
                if(busT[j]==next&&!bs.test(j)&&busT[j+1]!=next){flag=false;break;}
                if(busT[j]==next&&bs.test(j)){flag=true;start=j+1;break;}//next oppo
            }
            if(!flag) break;
            if(j==n) break;//j==n&&incre==0
            next+=incre;//incre==0?
        }
        return flag;
    }
    
    inline void set(int i){//function parameter can't conflict with your local parameter:ISO, under MS, cover scope
        int incre=busT[end[i]]-busT[start[i]];
        bs.reset(end[i]);
        //busT[end[i]]+incre
        int next=busT[end[i]]+incre, j;
        for(j=0; j<n&&next<=busT[n-1]; j++)//here<=
            if(busT[j]==next&&bs.test(j))
                bs.reset(j),next+=incre;
    }
    
    int main()
    {
        //implementation
        cin>>n;
        for(int i=0; i<n; i++) cin>>busT[i];
    
        memset((void*)start, 0xff, sizeof(int)*MAXEL);
        memset((void*)end, 0xff, sizeof(int)*MAXEL);
        start[0]=0,bs.reset(0);
        best=(n/2+1>17?17:n/2+1);//这里最好是n/2+1,17的小者,要考虑测试用例的各种情况!
        bus(1, 1, 1);//next slot is 1 for start_x, cur also for bus<1>
        cout<<best<<endl;
    
        return 0;
    }
    
    
Advertisements