UOJ Logo tm的博客

博客

标签

JSTSC2016滚粗记

2016-05-16 18:20:51 By tm

其实我本来并不想写的..毕竟人比较sb,而且我也不是js人...

然而好像确实被踩得有点惨了..GG..一脸智障..

day -1

啊切不动题弃疗

day 0

啊切不动题弃疗

day 1

开场30分钟: 啊T1分数规划然而我并不会 啊T2 sb树同构xjb搞搞好像有些细节写不动 啊T3啊不会

啊头昏脑胀睡觉睡了30min.

起来码T2 sb树同构.. 从第一个版本代码开始写到写完花了1.5h,过第一个样例.5h,发现细节狗带了调了.5h,发现我是sb输出方案时会gg写了.5h,发现过不了样例调调调.5h,最后代码长度6k+顺利狗带

智障选手表示不会T3..

出考场心情差极了..啊T3是个绝世sb题..啊T2某爷只写了3k...GG

然后下午FMB听了jb课..感觉有点赛艇..(似乎不是很高深♂)

回来一查成绩果然T2狗带成了0分..意料之中...

所以其实是一篇爆0记

总感觉给day 2立了一个Flag..

我是sb..

<a href="http://dwz.cn/ioi-bd" style="color:#f39;">IOI Rank board</a>

2015-07-28 19:43:02 By tm

我很想写掉未来程序・改

2015-05-22 23:04:51 By tm

可是我一个小时才写出FlowManager,半个小时才写出LexemeParser...

String flow manager

#define __PORALLOC 4096
#define chfy(x) (char*)x
#define sc sizeof(char)
#include "malloc.h"
namespace _strutils{
    struct strbuf{
        char* str;
        int len,alen;
        strbuf(){
            len=0;
            alen=__PORALLOC;
            str=chfy(malloc(alen*sc));
        }
        ~strbuf(){
            free(str);
        }
        inline bool ext(){
            alen<<=1;
            int i=0;
            char* q=chfy(malloc(alen*sc));
            if(!q) return false;
            for(;i<len;++i) q[i]=str[i];
            for(;i<alen;++i) q[i]=0;
            free(str);
            str=q;
            return true;
        }
        inline void read_fstdio(FILE* ff){
            int c;
            while(c=fread(str+len,sc,sc*__PORALLOC,ff)){
                if((len+=c)==alen) if(!ext()) return;
            }
        }
    };
    struct sfilereader{
        strbuf buf;
        int cur;
        void totread(bool autoRead,FILE* from){
            if(autoRead) buf.read_fstdio(from);
        }
        inline char p(){return cur<buf.len?buf.str[cur]:-1;}
        inline int n(){return cur<buf.len?++cur:cur;}
        inline char* pos(){return buf.str+cur;}
        inline bool e(){return cur>=buf.len;}
        inline bool h(){return cur<buf.len;}
    };
}

Lexeme parser

namespace lexemeParser{
    const long long _lexNam=0ll;
    const long long _lexOpr=1ll;
    const long long _lexNum=2ll;
    const long long _lexSep=3ll;
    const long long _lexEOF=4ll;
    struct lexemeString{char* start;int len;inline void print(){for(int i=0;i<len;++i) putchar(start[i]);}};
    struct lexemeElement{
        long long type;lexemeString* data;
        inline void eval(){
            long long q=0;
            for(int i=0;i < data->len;++i) q=q*10+(data->start[i]-'0');
            data=reinterpret_cast<lexemeString*>(q);
        }
    };
    inline long long type(char x){
        if(x==-1) return _lexEOF;
        if('0'<=x&&x<='9') return _lexNum;
        if('a'<=x&&x<='z') return _lexNam;
        if('A'<=x&&x<='Z') return _lexNam;
        if(x=='_') return _lexNam;
        if(x==' '||x=='\n'||x=='\r') return _lexSep;
        return _lexOpr;
    }
    struct lexemeTokenizer{
        _strutils::sfilereader p;
        lexemeElement E[10000];
        lexemeString  S[10000];
        int El,Sl;
        lexemeTokenizer(FILE* ff){
            p.totread(true,ff);
        }
        lexemeElement* nextToken(){
            int l=0;
            long long q;
            while((q=type(p.p()))==_lexSep) p.n();
            if(q==4ll) return NULL;
            lexemeElement* A=E+(El++);
            lexemeString*  B=S+(Sl++);
            fflush(stdout);
            A->data=B;
            A->type=q;
            B->len=0;
            B->start=p.pos();
            switch(q){
                case 2ll:
                while((q=type(p.p()))==_lexNum) ++B->len,p.n();
                A->eval();
                --Sl;
                break;
                case 0ll:
                while((q=type(p.p()))==_lexNum||q==_lexNam) ++B->len,p.n();
                break;
                case 1ll:
                --Sl;
                long long* a=(long long*)&(A->data);
                char c=p.p();
                p.n();
                switch(c){
                    case '{': *a=0ll; break;
                    case '}': *a=1ll; break;
                    case '[': *a=2ll; break;
                    case ']': *a=3ll; break;
                    case '(': *a=4ll; break;
                    case ')': *a=5ll; break;
                    case '!': if(p.p()=='=') *a=6ll,p.n(); else *a=7ll; break;
                    case '-': *a=8ll; break;
                    case '*': *a=9ll; break;
                    case '%': *a=10ll; break;
                    case '<': if(p.p()=='=') *a=11ll,p.n(); else if(p.p()=='<') *a=21ll,p.n(); else *a=12ll; break;
                    case '>': if(p.p()=='=') *a=13ll,p.n(); else if(p.p()=='>') *a=22ll,p.n(); else *a=14ll; break;
                    case '+': *a=15ll; break;
                    case '=': if(p.p()=='=') *a=16ll,p.n(); else *a=17ll; break;
                    case '^': *a=18ll; break;
                    case '&': *a=19ll; p.n(); break;
                    case '|': *a=20ll; p.n(); break;
                    case '#': *a=23ll; break;
                    case ';': *a=24ll; break;
                    case ',': *a=25ll; break;
                }
                break;
            }
            return A;
        }
        inline bool hasTokenLeft(){ return p.h(); }
    };
}

顺便附上问题..

namespace lexemeParser{
    const long long _lexNam=0ll;
    const long long _lexOpr=1ll;
    const long long _lexNum=2ll;
    const long long _lexSep=3ll;
    const long long _lexEOF=4ll;
    struct lexemeString{char* start;int len;inline void print(){for(int i=0;i<len;++i) putchar(start[i]);}};
    struct lexemeElement{
        long long type;lexemeString* data;
        inline void eval(){
            long long q=0;
            for(int i=0;i < data->len;++i) q=q*10+(data->start[i]-'0');
            data=reinterpret_cast<lexemeString*>(q);
        }
    };
    inline long long type(char x){
        if(x==-1) return _lexEOF;
        if('0'<=x&&x<='9') return _lexNum;
        if('a'<=x&&x<='z') return _lexNam;
        if('A'<=x&&x<='Z') return _lexNam;
        if(x=='_') return _lexNam;
        if(x==' '||x=='\n'||x=='\r') return _lexSep;
        return _lexOpr;
    }
    struct lexemeTokenizer{
        _strutils::sfilereader p;
        lexemeElement E[10000];
        lexemeString  S[10000];
        int El,Sl;
        lexemeTokenizer(FILE* ff){
            p.totread(true,ff);
        }
        lexemeElement* nextToken(){
            int l=0;
            long long q;
            while((q=type(p.p()))==_lexSep) p.n();
            if(q==4ll) return NULL;
            lexemeElement* A=E+(El++);
            lexemeString*  B=S+(Sl++);
//            fflush(stdout);
            A->data=B;
            A->type=q;
            B->len=0;
            B->start=p.pos();
            switch(q){
                case 2ll:
                while((q=type(p.p()))==_lexNum) ++B->len,p.n();
                A->eval();
                --Sl;
                break;
                case 0ll:
                while((q=type(p.p()))==_lexNum||q==_lexNam) ++B->len,p.n();
                break;
                case 1ll:
                --Sl;
                long long* a=(long long*)&(A->data);
                char c=p.p();
                p.n();
                switch(c){
                    case '{': *a=0ll; break;
                    case '}': *a=1ll; break;
                    case '[': *a=2ll; break;
                    case ']': *a=3ll; break;
                    case '(': *a=4ll; break;
                    case ')': *a=5ll; break;
                    case '!': if(p.p()=='=') *a=6ll,p.n(); else *a=7ll; break;
                    case '-': *a=8ll; break;
                    case '*': *a=9ll; break;
                    case '%': *a=10ll; break;
                    case '<': if(p.p()=='=') *a=11ll,p.n(); else if(p.p()=='<') *a=21ll,p.n(); else *a=12ll; break;
                    case '>': if(p.p()=='=') *a=13ll,p.n(); else if(p.p()=='>') *a=22ll,p.n(); else *a=14ll; break;
                    case '+': *a=15ll; break;
                    case '=': if(p.p()=='=') *a=16ll,p.n(); else *a=17ll; break;
                    case '^': *a=18ll; break;
                    case '&': *a=19ll; p.n(); break;
                    case '|': *a=20ll; p.n(); break;
                    case '#': *a=23ll; break;
                    case ';': *a=24ll; break;
                    case ',': *a=25ll; break;
                }
                break;
            }
            return A;
        }
        inline bool hasTokenLeft(){ return p.h(); }
    };
}

为什么这个代码会Segmentation fault呀,差别完全就是一个毫无关联的fflush(stdout)

完整的Lexeme parser module程序

#include "cstdio"
#include "cstring"
#define __PORALLOC 4096
#define chfy(x) (char*)x
#define sc sizeof(char)
#include "malloc.h"
namespace _strutils{
    struct strbuf{
        char* str;
        int len,alen;
        strbuf(){
            len=0;
            alen=__PORALLOC;
            str=chfy(malloc(alen*sc));
        }
        ~strbuf(){
            free(str);
        }
        inline bool ext(){
            alen<<=1;
            int i=0;
            char* q=chfy(malloc(alen*sc));
            if(!q) return false;
            for(;i<len;++i) q[i]=str[i];
            for(;i<alen;++i) q[i]=0;
            free(str);
            str=q;
            return true;
        }
        inline void read_fstdio(FILE* ff){
            int c;
            while(c=fread(str+len,sc,sc*__PORALLOC,ff)){
                if((len+=c)==alen) if(!ext()) return;
            }
        }
    };
    struct sfilereader{
        strbuf buf;
        int cur;
        void totread(bool autoRead,FILE* from){
            if(autoRead) buf.read_fstdio(from);
        }
        inline char p(){return cur<buf.len?buf.str[cur]:-1;}
        inline int n(){return cur<buf.len?++cur:cur;}
        inline char* pos(){return buf.str+cur;}
        inline bool e(){return cur>=buf.len;}
        inline bool h(){return cur<buf.len;}
    };
}
namespace lexemeParser{
    const long long _lexNam=0ll;
    const long long _lexOpr=1ll;
    const long long _lexNum=2ll;
    const long long _lexSep=3ll;
    const long long _lexEOF=4ll;
    struct lexemeString{char* start;int len;inline void print(){for(int i=0;i<len;++i) putchar(start[i]);}};
    struct lexemeElement{
        long long type;lexemeString* data;
        inline void eval(){
            long long q=0;
            for(int i=0;i < data->len;++i) q=q*10+(data->start[i]-'0');
            data=reinterpret_cast<lexemeString*>(q);
        }
    };
    inline long long type(char x){
        if(x==-1) return _lexEOF;
        if('0'<=x&&x<='9') return _lexNum;
        if('a'<=x&&x<='z') return _lexNam;
        if('A'<=x&&x<='Z') return _lexNam;
        if(x=='_') return _lexNam;
        if(x==' '||x=='\n'||x=='\r') return _lexSep;
        return _lexOpr;
    }
    struct lexemeTokenizer{
        _strutils::sfilereader p;
        lexemeElement E[10000];
        lexemeString  S[10000];
        int El,Sl;
        lexemeTokenizer(FILE* ff){
            p.totread(true,ff);
        }
        lexemeElement* nextToken(){
            int l=0;
            long long q;
            while((q=type(p.p()))==_lexSep) p.n();
            if(q==4ll) return NULL;
            lexemeElement* A=E+(El++);
            lexemeString*  B=S+(Sl++);
            fflush(stdout);
            A->data=B;
            A->type=q;
            B->len=0;
            B->start=p.pos();
            switch(q){
                case 2ll:
                while((q=type(p.p()))==_lexNum) ++B->len,p.n();
                A->eval();
                --Sl;
                break;
                case 0ll:
                while((q=type(p.p()))==_lexNum||q==_lexNam) ++B->len,p.n();
                break;
                case 1ll:
                --Sl;
                long long* a=(long long*)&(A->data);
                char c=p.p();
                p.n();
                switch(c){
                    case '{': *a=0ll; break;
                    case '}': *a=1ll; break;
                    case '[': *a=2ll; break;
                    case ']': *a=3ll; break;
                    case '(': *a=4ll; break;
                    case ')': *a=5ll; break;
                    case '!': if(p.p()=='=') *a=6ll,p.n(); else *a=7ll; break;
                    case '-': *a=8ll; break;
                    case '*': *a=9ll; break;
                    case '%': *a=10ll; break;
                    case '<': if(p.p()=='=') *a=11ll,p.n(); else if(p.p()=='<') *a=21ll,p.n(); else *a=12ll; break;
                    case '>': if(p.p()=='=') *a=13ll,p.n(); else if(p.p()=='>') *a=22ll,p.n(); else *a=14ll; break;
                    case '+': *a=15ll; break;
                    case '=': if(p.p()=='=') *a=16ll,p.n(); else *a=17ll; break;
                    case '^': *a=18ll; break;
                    case '&': *a=19ll; p.n(); break;
                    case '|': *a=20ll; p.n(); break;
                    case '#': *a=23ll; break;
                    case ';': *a=24ll; break;
                    case ',': *a=25ll; break;
                }
                break;
            }
            return A;
        }
        inline bool hasTokenLeft(){ return p.h(); }
    };
}
FILE* input;
int main(){
    input=fopen("lexemeParserTest.in","r");
    lexemeParser::lexemeTokenizer lt(input);
    lexemeParser::lexemeElement* temp;
    while(lt.hasTokenLeft()){
        temp=lt.nextToken();
        switch(temp->type){
            case 0:
                printf("ident/kwd/path  ");
                temp->data->print();
                break;
            case 1:
                printf("Operator      # %lld",reinterpret_cast<long long>(temp->data));
                break;
            case 2:
                printf("Number          %lld",reinterpret_cast<long long>(temp->data));
        }
        putchar('\n');
    }
    return 0;
}

窝就是很好奇

2014-12-08 20:47:15 By tm

为何swap跑得比赋值快?

共 4 篇博客