藍雪的Online Judge日誌

2015年4月14日星期二

TIOJ 1020 . F.Number Insertion

這竟然只是暴搜OAO

#include <cstdio>

#include <cstdlib>

int ans[100] = {0};

int dfs(int* arr, int k, int klim, int len){

    if(k > klim){

        bool bigger = false;

        for(int lx = 0;lx < len;lx++){

            if(arr[lx] == ans[lx]) continue;

            if(arr[lx] > ans[lx]) bigger = true;

            if(arr[lx] < ans[lx]) bigger = false;

            break;

}

        if(bigger){

            for(int lx = 0;lx < len;lx++)

                ans[lx] = arr[lx];

}

        return 1;

}

    int cnt = 0;

    for(int lx = 0;lx+1 < len;lx++){

        if(k%(arr[lx] + arr[lx+1]) == 0){

            for(int ly = len;ly >= lx+2;ly--)

                arr[ly] = arr[ly-1];

            arr[lx+1] = k;

            cnt += dfs(arr, k+1, klim, len+1);

            for(int ly = lx+1;ly < len;ly++)

                arr[ly] = arr[ly+1];

}

}

    return cnt;

}

int main(){

    int k; scanf("%d", &k);

    int arr[100] = {0, 1};

    int cc = dfs(arr, 2, k, 2);

    printf("%d\n", cc);

    for(int lx = 0;lx <= k;lx++)

        printf("%d ", ans[lx]);

    puts("");

    return 0;

}

TIOJ 1018 D.A Logical Problem

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <vector>

using namespace std;

int whword(vector<char*>& lst, int a, int b, const char* pat){

    for(int lx = a;lx <= b;lx++)

        if(strcmp(lst[lx], pat) == 0)

            return lx;

    return -1;

}

int whword(vector<char*>& lst, const char* pat){

    return whword(lst, 0, ((int)lst.size()) - 1, pat); 

}

struct sing{

    bool pnot;

    char pc;

};

sing operator not(sing a){

    a.pnot = not a.pnot;

    return a;

}

void printsing(sing a){

    if(a.pnot)

        printf("not ");

    printf("%c", a.pc);

    return;

}

sing transsing(vector<char*>& lst, int a, int b){

    sing ret;

    int wrd_cnt = b-a+1;

    ret.pnot = wrd_cnt == 2;

    ret.pc =  lst[b][0];

    return ret;

}

struct cond{

    int cnt;

    sing sg1;

    int con;

    sing sg2;

};

cond operator not(cond a){

    a.con = 1-a.con;

    a.sg1 = not a.sg1;

    a.sg2 = not a.sg2;

    return a;

}

void printcond(cond a){

    if(a.cnt == 1)

        printsing(a.sg1);

    else{

        printsing(a.sg1);

        printf(" %s " , a.con == 1 ? "and" : "or");

        printsing(a.sg2);

}

    return;

}

cond transcond(vector<char*>& lst, int a, int b){

    int wh_and = whword(lst, a, b, "and");

    int wh_or = whword(lst, a, b, "or");

    int pos = max(wh_or, wh_and);

    cond ret;

    if(pos == -1){

        ret.cnt = 1;

        ret.sg1 = transsing(lst, a, b);

        return ret;

}

    ret.cnt = 2;

    ret.con = pos == wh_and;

    ret.sg1 = transsing(lst, a, pos-1);

    ret.sg2 = transsing(lst, pos+1, b);

    return ret;

}

int main(){

    int T; scanf("%d\n", &T); while(T--){

        char buf[50];

        fgets(buf, 50, stdin);

        if(feof(stdin)) break;

        char* ptr = strtok(buf, " ");

        vector<char*> lst;

        while(ptr != NULL){

            lst.push_back(ptr);

            //printf("[%s]\n", ptr);

            ptr = strtok(NULL, " ");

}

        if(lst[(int)lst.size() - 1][0] == '\n')

            lst.pop_back();

        if(lst.size() < 4){

            T++;

            continue;

}

        int wh_IF = whword(lst, "IF"), wh_THEN = whword(lst, "THEN");

        //printf("IF = %d, THEN = %d\n", wh_IF, wh_THEN);

        cond cc1 = not transcond(lst, wh_IF+1, wh_THEN-1),

             cc2 = not transcond(lst, wh_THEN+1, (int)lst.size()-1);

        printf("IF "); printcond(cc2); printf(" THEN ") ; printcond(cc1);       

        puts("");

}

    return 0;

}

2015年4月10日星期五

POJ 1279 Art Gallery

半平面交

＊記得注意^算子優先順序

// note ^ operator 
// * operator 

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <algorithm>
#include <functional>

using namespace std;

template<class T>
void pvec(vector<T> val){
    for(int lx = 0;lx < val.size();lx++){
        val[lx].print();
        printf(" ");
    }
    puts("");
    return;
}

const double eps = 1e-7;

struct Point{
    double x, y;
    Point(double _x = 0, double _y = 0):x(_x), y(_y){}
    int id() const {
        if(x > 0 and y >= 0) return 0;
        if(y > 0 and x <= 0) return 1;
        if(x < 0 and y <= 0) return 2;
        if(y < 0 and x >= 0) return 3;
        return -1;
    }
    void print(){ printf("(%.2f,%.2f)", x, y); return; }
};

Point operator+(const Point& a, const Point& b){return Point(a.x + b.x, a.y + b.y);}
Point operator-(const Point& a, const Point& b){return Point(a.x - b.x, a.y - b.y);}
Point operator*(const Point& a, double k){return Point(a.x*k, a.y*k);}
Point operator*(double k, const Point& a){return Point(a.x*k, a.y*k);}
double operator*(const Point& a, const Point& b){return a.x*b.x + a.y*b.y;}
double operator^(const Point& a, const Point& b){return a.x*b.y - a.y*b.x;}

struct Line{
    Point p1, p2, dt;
    Line(Point a = Point(), Point b = Point()):p1(a), p2(b){dt = p2-p1;return;}
    void print(){ p1.print(); printf("->"); p2.print();}
};

bool IsParallel(const Line& a, const Line& b) { return fabs(a.dt^b.dt) < eps; }
bool IsInPlane(const Line& a, const Point& p){ return (a.dt^(p-a.p1)) >= eps; }

bool operator<(const Point& a, const Point& b){
    int ida = a.id(), idb = b.id();
    return (ida != idb) ? ida < idb : 0 < (a^b);
}

typedef vector<Point> Polygon;

Point GetLineInterX(const Line& l1, const Line& l2){
    const Point &a1 = l1.p1, &a2 = l1.p2;
    const Point &b1 = l2.p1, &b2 = l2.p2;
    Point a = a2-a1, b = b2-b1, s = b1-a1;
    return a1 + a*((b^s)/(b^a));
}

bool lcmp(const Line& a, const Line& b){
    return (a.p2-a.p1) < (b.p2-b.p1);
};

Polygon GetPlaneInterX(vector<Line>& _inp){
    if(_inp.size() <= 2) return Polygon();
    sort(_inp.begin(), _inp.end(), lcmp);
    // deal with parellel part
    vector<Line> inp(1, _inp[0]);
    for(int lx = 1;lx < _inp.size();lx++){
        Line& prc_line = inp[(int)inp.size() - 1];
        if(IsParallel(prc_line, _inp[lx])){
            if(IsInPlane(prc_line, _inp[lx].p2))
                prc_line = _inp[lx];
        }else
            inp.push_back(_inp[lx]);
    }
    int sz = inp.size();
    if(sz <= 2) return Polygon();
    
    int qs = 0, qe = 2;
    vector<Line> que(sz+1);
    que[0] = inp[0], que[1] = inp[1];
    for(int lx = 2;lx < sz;lx++){
        while(qe-qs >= 2 and not IsInPlane(inp[lx], GetLineInterX(que[qe-1], que[qe-2]))) qe--;
        while(qe-qs >= 2 and not IsInPlane(inp[lx], GetLineInterX(que[qs]  , que[qs+1]))) qs++;
        que[qe++] = inp[lx];
    }

    while(qe-qs >= 2 and not IsInPlane(que[qs]  , GetLineInterX(que[qe-1], que[qe-2]))) qe--;
    while(qe-qs >= 2 and not IsInPlane(que[qe-1], GetLineInterX(que[qs]  , que[qs+1]))) qs++;
    if(qe-qs <= 2) return Polygon();

    que[qe++] = que[qs];
    Polygon ret;
    for(int lx = qs;lx < qe-1;lx++)
        ret.push_back(GetLineInterX(que[lx], que[lx+1]));
 
    return ret;
}

double GetArea(Polygon a){
    if(a.size() == 0) return 0;
    double ret = 0;
    a.push_back(a[0]);
    for(int lx = 0;lx+1 < a.size();lx++)
        ret += a[lx]^a[lx+1];
    return ret/2;
}

int main(){
    int T; scanf("%d", &T);
    while(T--){
        Polygon hls;
        int n; scanf("%d", &n);
        for(int lx = 0;lx < n;lx++){
            Point inp;
            scanf("%lf %lf", &inp.x, &inp.y);
            hls.push_back(inp);
        }
        if(GetArea(hls) < 0) reverse(hls.begin(), hls.end());
        hls.push_back(hls[0]);
        vector<Line> par;
        for(int lx = 0;lx < n;lx++)
            par.push_back(Line(hls[lx], hls[lx+1]));
         
        Polygon getres = GetPlaneInterX(par);

        printf("%.2f\n", GetArea(getres));

    }
    return 0;
}

ZeptoLab Code Rush 2015 E. Transmitting Levels

pop_back那裏特判一堆也不太知道怎寫好._.

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long int  int64;

int64 an[2000000];
int rtpos[2000000];
int que[2000000];

int main(){
    int n, q; scanf("%d %d", &n, &q);
    for(int lx = 0;lx < n;lx++){
        scanf("%I64d", an + lx);
        an[lx + n] = an[lx];
    }

    while(q--){
        int64 b; scanf("%I64d", &b);
        int ptrs = 0;
        int64 cnt = 0;
        for(int lx = 0;lx < 2*n;lx++){
            cnt += an[lx];
            while(cnt > b){
                cnt -= an[ptrs];
                ptrs++;
            }
            rtpos[lx] = ptrs;
        }
        //for(int lx = 0;lx < 2*n;lx++)
        //    printf("%d%c", rtpos[lx], lx==2*n-1 ? ('\n'):(' '));
        int ed = 0;
        int ans = 2*n;
        int qs = 0, qe = 0;
        for(int lx = 0;lx < 2*n;lx++){
            while(qe-qs >= 1 and rtpos[lx] == rtpos[que[qe-1]])
                qe--;
            while(qe-qs >= 2 and rtpos[lx] <= que[qe-2])
                qe--;
            if(qe-qs >= 2 and que[qe-2] == rtpos[lx]-1)
                qe--;
            que[qe++] = lx;
            while(qs < qe and lx - rtpos[que[qs]] + 1 >= n){
                ans = min(qe-qs, ans);
                /*printf("get ans:");
                for(int lx = qs;lx < qe;lx++)
                    printf("[%d %d] ", rtpos[que[lx]], que[lx]);
                printf("\n");*/
                qs++;
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

2015年4月9日星期四

TIOJ 1306 . 字串中的字串

http://tioj.ck.tp.edu.tw/problems/1306

重點:
* %在把P放到暫存區時有點慢 ==> const + if

#include <cstdio>

#include <cstdlib>

#include <cstring>

using namespace std;

typedef long long int int64;

const int64 P = 1000000007, X = 31;

int64 Xn[10010];

void init(){

    Xn[0] = 1;

    for(int lx = 1;lx <= 10001;lx++){

        Xn[lx] = Xn[lx-1]*X;

        Xn[lx] %= P;

}

    return;

}

struct hasher{

    int64 val[10010];

    int len;

    hasher(char* _str){

        val[0] = 0;

        len = strlen(_str);

        for(int lx = 0; _str[lx] != 0;lx++){

            val[lx+1] = val[lx]*X + (int64)(_str[lx] - 'a');

            val[lx+1] %= P;

}

        return;

}

    int64 getval(int a, int b){

        int64 ret = val[b] - val[a-1]*Xn[b-a+1];

        ret %= P; if(ret < 0) ret += P;

        return ret;

}

};

int64 hash(char* _str){

    int64 ret = 0;

    for(int lx = 0;_str[lx] != 0;lx++){

        ret = ret*X + (int64)(_str[lx] - 'a');

        ret %= P;

}

    return ret;

}

int main(){

    init();

    char mstr[10010], istr[10010];

    int T ; scanf("%d", &T);

    while(T--){

        scanf("%s", mstr);

        hasher hash_mstr(mstr);

        int Q; scanf("%d", &Q);

        while(Q--){

            scanf("%s", istr);

            int len = strlen(istr);

            int c = 0;

            int cpval = hash(istr);

            for(int lx = 1;lx + len-1 <= hash_mstr.len;lx++){

                c += hash_mstr.getval(lx, len + lx-1) == cpval;

}

            printf("%d\n", c);

}

}

    return 0;

}

2015年4月14日 星期二

TIOJ 1020 . F.Number Insertion

TIOJ 1018 D.A Logical Problem

2015年4月10日 星期五

POJ 1279 Art Gallery

ZeptoLab Code Rush 2015 E. Transmitting Levels

2015年4月9日 星期四

TIOJ 1306 . 字串中的字串

2015年4月14日星期二

2015年4月10日星期五

2015年4月9日星期四