HDUOJ 4720 Naive and Silly Muggles

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

using namespace std;

const double eps = 1e-7;
const double inf = 1e7;

bool db_eq(const double& a, const double& b){return fabs(a-b)<=eps;}
bool db_bt(const double& a, const double& b){return a>b+eps;}
bool db_st(const double& a, const double& b){return a+eps<b;}
bool db_be(const double& a, const double& b){return a>=b-eps;}
bool db_se(const double& a, const double& b){return a<=b+eps;}

struct pt{
    double x, y;
    pt(double _x = 0, double _y = 0): x(_x), y(_y){} 
    double len()const{return sqrt(x*x+y*y);}
};

pt operator+(const pt& a, const pt& b){return pt(a.x+b.x, a.y+b.y);}
pt operator-(const pt& a, const pt& b){return pt(a.x-b.x, a.y-b.y);}
pt operator/(const pt& a, const double& r){return pt(a.x/r, a.y/r);}
double operator^(const pt& a, const pt& b){return a.x*b.y-a.y*b.x;}
pt operator~(const pt& a){return pt(a.y, -a.x);}

struct line{
    // ax + by + c = 0;
    double a, b, c;
    line(){
        a = 0, b = 0, c = 0;
    }
    line(const pt& m, const pt& s){
        a = m.y, b = -m.x;
        c = -(a*s.x+b*s.y);
    }
    pt m()const{
        return pt(-b, a);
    }
};

pt operator*(const line& l1, const line& l2){
    double det = l1.m()^l2.m();
    if(db_eq(det, 0)) return pt(inf, inf);
    double detx = -l1.c*l2.b+l2.c*l1.b;
    double dety =  l1.c*l2.a-l2.c*l1.a;
    return pt(detx/det, dety/det);
}

struct cir{
    pt o;
    double r;
    cir(const pt& _o = pt(), const double& _r = 0): o(_o), r(_r){}
    cir(const pt& pt1, const pt& pt2){o = (pt1+pt2)/2; r = (pt1-o).len();}
    
    cir(const pt& pt1, const pt& pt2, const pt& pt3){
        line l1 = line(~(pt2-pt1), (pt1+pt2)/2);
        line l2 = line(~(pt3-pt1), (pt1+pt3)/2);
        o = l1*l2;
        if(db_eq(o.x, inf)){
            double l12 = (pt1-pt2).len(),
                   l23 = (pt2-pt3).len(),
                   l13 = (pt3-pt1).len();
            if(db_eq(l12+l23,l13)) cir(pt1,pt3);
            else if(db_eq(l13+l23,l12)) cir(pt1,pt2);
            else if(db_eq(l12+l13,l23)) cir(pt2,pt3);
            else assert(0);
        }else{
            r = (o-pt1).len();
        }
    }
    bool has(const pt& p){ return db_bt((p-o).len(),r) == false;}
};

int main(){
    int T; scanf("%d", &T);
    for(int lt = 1;lt <= T;lt++){
        pt p[4],tt;
        for(int lx = 0;lx<4;lx++)
            scanf("%lf %lf", &p[lx].x, &p[lx].y);
        cir cc(p[0],p[1],p[2]);
        cir c01(p[0], p[1]);
        cir c12(p[1], p[2]);
        cir c02(p[0], p[2]);
        if(c01.has(p[2]) and db_st(c01.r, cc.r)) cc = c01;
        if(c02.has(p[1]) and db_st(c02.r, cc.r)) cc = c02;
        if(c12.has(p[0]) and db_st(c12.r, cc.r)) cc = c12;
        
        printf("Case #%d: %s\n", lt, cc.has(p[3])==false ? "Safe":"Danger");
    }
    return 0;
}

HDUOJ 1693 Eat the Trees

卡輸出格式卡一陣子＝＝

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

long long dp[12][12][1<<13];
int n, m;
int tab[12][12];

int main(){
    int c = 1;
    int T; scanf("%d", &T);
    while(T--){
        memset(tab, 0, sizeof(tab));
        scanf("%d %d", &n, &m);
        for(int lx = 0;lx < n;lx++)
            for(int ly = 0;ly < m;ly++)
                scanf("%d", &tab[lx][ly]);
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for(int lx = 0;lx <= n;lx++){
            if(lx){
                for(int sts = 0;sts < 1<<(m);sts++)
                    dp[lx][0][sts] = dp[lx-1][m][sts];
            }
            for(int ly = 0;ly < m;ly++){
                //printf("(%d, %d):\n", lx, ly);
                for(int sts = 0;sts < 1<<(m+1);sts++){
                    //printf("\t sts %d = %lld\n", sts, dp[lx][ly][sts]);
                    int lf = sts&(1<<m);
                    int up = sts&(1<<ly);
                    long long val = dp[lx][ly][sts];
                    if(tab[lx][ly] == 0){
                        if(lf == 0 and up == 0)
                            dp[lx][ly+1][sts] += val;
                        continue;
                    }
                    if(lf&&up) dp[lx][ly+1][sts^lf^up] += val;
                    else if(lf||up) dp[lx][ly+1][sts] += val, 
                        dp[lx][ly+1][sts^(1<<m)^(1<<ly)] += val;
                    else dp[lx][ly+1][sts^(1<<m)^(1<<ly)] += val;
                }
            }
        }
        printf("Case %d: There are %lld ways to eat the trees.\n", c, dp[n][m][0]);
        c++;
    }
    return 0;
}

HDU 2167 Pebbles

16*16*2^16

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int box[20][20];
char tmp[1000];
int sts[2][1<<17];
int main()
{
    for(;;){
        int n;
        if(gets(tmp)==0) break;
        n = (strlen(tmp)+1)/3;
        if(n == 0) continue;
        //printf("n = %d\n", n);
        for(int lx = 0;lx < n;lx++)
            box[0][lx] = 10*(tmp[lx*3]-'0')+tmp[lx*3+1]-'0';
        for(int lx = 1;lx < n;lx++)
            for(int ly = 0;ly < n;ly++)
                scanf("%d", &box[lx][ly]);
        for(int lx = 0;lx < n;lx++)
            box[n][lx] = 0;
        //if(gets(tmp)==0) break;
        memset(sts, 0, sizeof(sts));
        int now = 0;
        for(int lx = 0;lx < n;lx++){
        for(int ly = 0;ly < n;ly++){
            for(int s = 0;s < (1<<(n+1));s++){
                if(((s&1) == 0 or ly == 0) and ((s&2) == 0) and
                   ((s&4) == 0 or ly == n-1) and ((s&(1<<n)) == 0 or ly == 0)){
                    sts[1-now][(s>>1)|(1<<n)] = max(sts[1-now][(s>>1)|(1<<n)],
                                                    sts[now][s]+box[lx][ly]);
                    
                }
                sts[1-now][s>>1] = max(sts[1-now][s>>1], sts[now][s]);
                
            }
            memset(sts[now], 0,sizeof(sts[now]));
            now = 1-now;
        }}
        int mm = 0;
        for(int lx = 0;lx < (1<<n+1);lx++)
            mm = max(mm, sts[now][lx]);
        printf("%d\n", mm);
    }
    return 0;
}

HDU 4963 Dividing a String

http://acm.hdu.edu.cn/showproblem.php?pid=4963

BiBFS
卡了一些怪bug
所以會有一些多餘的codeXD

附上testdata

8
aabbabaabbabaaaa
1 3 7 2
4 2 9 1
5 8 0 6
9 3 8 4

==> 0

8
aabbaabbaabbaabb
203 47 81 99
38 73 97 67
23 11 101 103
91 5 3 1

==>1

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<utility>
using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, pii> pp;
typedef struct _status{ int sts; int pos; int val;}status;
status new_status(int sts, int pos, int val){
    status ret;
    ret.sts = sts;
    if(sts == 1) pos = -1;
    ret.pos = pos;
    ret.val = val;
    return ret;
}
int pushch(int sts, int pos, int ch){
    sts -= 1<<(pos+1);
    sts += ch<<(pos+1);
    sts += 1<<(pos+2);
    return sts;
}
int popch(int sts, int pos, int ch){
    if (sts%2 == ch) return sts>>1;
    return -1;
}
void psts(int a, int n){
    for(int lx = n;lx >= 0;lx--)
        printf("%d", (a&(1<<lx))>>lx);
    return;
}
int rev(int sts){
    int ans = 1;
    while(sts > 1){
        ans <<= 1;
        ans |= sts&1;
        sts >>= 1;
    }
    return ans;
}
int _abs(int a){return max(a, -a);}
int trisearch(vector<int>& t, int val){
    if(t[t.size()-1] <= val) return _abs(t[t.size()-1] - val);
    if(t[0] >= val) return _abs(t[0] - val);
    int tt, tt1, tt2;
    int tts[15], cnt = 0;
    tt = lower_bound(t.begin(), t.end(), val) - t.begin();
    tts[cnt++] = tt-1, tts[cnt++] = tt, tts[cnt++] = tt+1;
    tts[cnt++] = tt-2, tts[cnt++] = tt+2;
    tt = upper_bound(t.begin(), t.end(), val) - t.begin();
    tts[cnt++] = tt-1, tts[cnt++] = tt, tts[cnt++] = tt+1;
    tts[cnt++] = tt+2, tts[cnt++] = tt-2;
    int mm = -1;
    for(int lx = 0;lx < cnt;lx++){
        //if(val == -115)
        //    printf("index = %d\n", tts[lx]);
        if(tts[lx] < 0 or tts[lx] >= t.size()) continue;
        if(mm == -1 or mm >= _abs(t[tts[lx]] - val))
            mm = _abs(t[tts[lx]] - val);
    }
    return mm;
}
status stk[2][2000000];
int main(){
int n;for(;;){
    scanf("%d", &n);
    if(n == 0) break;
    int an[100];
    char str[100];
    int sn[100];
    scanf("%s", str);
    for(int lx = 0;lx < 2*n;lx++){
        scanf("%d", an+lx);
        sn[lx] = str[lx]=='b';
    }
    int left = n + (n%2 == 0);
    int right = 2*n - left;
    int cnt[2]; int lprc = 0;
    stk[lprc][0] = new_status(1, -1, 0);
    cnt[0] = 1; cnt[1] = 0;
    for(int lx = 0;lx < left;lx++){
        int val = an[lx], ch  = sn[lx];
        //printf("to add %d\n", val);
        for(int lx = 0;lx < cnt[lprc];lx++){
            status& gg = stk[lprc][lx];
            //printf("get sts "); psts(gg.sts, gg.pos+1); printf(" = %d\n", gg.val);
            if(gg.pos == -1)
                stk[1-lprc][cnt[1-lprc]++] = new_status(2+ch, 0, gg.val + val);
            else{
                int& pos = gg.pos;
                //printf("%d\n", gg.val + val);
                stk[1-lprc][cnt[1-lprc]++] = new_status(pushch(gg.sts, pos, ch), pos+1, gg.val+val);
                int gp = popch(gg.sts, pos, ch);
                if(gp != -1){
                    if(pos > 0)
                        stk[1-lprc][cnt[1-lprc]++] = new_status(gp, pos-1, gg.val-val);
                    else{
                        stk[1-lprc][cnt[1-lprc]++] = new_status(gp, pos-1, gg.val-val);
                        stk[1-lprc][cnt[1-lprc]++] = new_status(gp, pos-1, val-gg.val);
                    }
                }
            }
        }
        cnt[lprc] = 0;
        lprc = 1-lprc;
        //printf("--\n");
    }
    // assert cnt[lprc] < 4e5
    map<int, vector<int> >mleft;
    for(int lx =0;lx < cnt[lprc];lx++){
        mleft[stk[lprc][lx].sts].push_back(stk[lprc][lx].val);
    }
    for(map<int, vector<int> >::iterator it = mleft.begin(); it != mleft.end() ;it++){
        sort(it->second.begin(), it->second.end());
        /*psts(it->first, 10);
        printf("->");
        for(int lx=  0;lx < it->second.size();lx++)
            printf("%d, ", it->second[lx]);
        printf("\n");*/
    }
    lprc = 0; stk[lprc][0] = new_status(1, -1, 0);
    cnt[0] = 1; cnt[1] = 0;
    for(int lx = 0;lx < right;lx++){
        int val = an[2*n - lx-1], ch  = sn[2*n - lx-1];
        for(int lx = 0;lx < cnt[lprc];lx++){
            status& gg = stk[lprc][lx];
            //printf("get sts "); psts(gg.sts, gg.pos+1); printf(" = %d\n", gg.val);
            if(gg.pos == -1)
                stk[1-lprc][cnt[1-lprc]++] = new_status(2+ch, 0, gg.val + val);
            else{
                int& pos = gg.pos;
                //printf("%d\n", gg.val + val);
                stk[1-lprc][cnt[1-lprc]++] = new_status(pushch(gg.sts, pos, ch), pos+1, gg.val+val);
                int gp = popch(gg.sts, pos, ch);
                if(gp != -1){
                    if(pos > 0)
                        stk[1-lprc][cnt[1-lprc]++] = new_status(gp, pos-1, gg.val-val);
                    else{
                        stk[1-lprc][cnt[1-lprc]++] = new_status(1, -1, gg.val-val);
                        stk[1-lprc][cnt[1-lprc]++] = new_status(1, -1, val-gg.val);
                    }
                }
            }
        }
        cnt[lprc] = 0;
        lprc = 1-lprc;
    }
    const int INF_ans = 800000000;
    int ans = INF_ans;
    for(int lx = 0;lx < cnt[lprc];lx++){
        int sts = rev(stk[lprc][lx].sts);
        int val = stk[lprc][lx].val;
        //printf("right sts = "); psts(sts, 10); printf(" val = %d \n", val);

        if(mleft.count(sts) == 0) continue;
        ans = min(trisearch(mleft[sts], val), ans);
        //printf("%d\n", ans);
        //if(ans == -1) printf("%d\n", 1/0);
    }
    if(ans == INF_ans)
        puts("-1");
    else
        printf("%d\n", ans);
}return 0;}

HDU 4966 GGS-DDU

直接膜拜DJWS的最小樹形圖@@

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef struct _link{int a, b, w;}link;
link links[10000]; int E;
void add_link(int a, int b, int w = 0){
    link nl;
    nl.a = a, nl.b = b, nl.w = w;
    links[E] = nl;
    E++;
    return;
}
int _cnt = 0; int new_vertex(){ _cnt++; return _cnt-1; }
int cal_mst(int root){
    int wei[600], src[600], vis[600], tenta[600], cons[600];
    int w1 = 0, w2 = 0;
    const int INF_weight = 10000;
    memset(cons, 0, sizeof(cons));
    /*for(int lx = 0;lx < E;lx++){
        printf("%d -> %d w=%d\n", links[lx].a, links[lx].b, links[lx].w);
    }*/
    int V = _cnt;
    for(;;){
        //printf("E = %d\n", E);
        memset(wei, 1, sizeof(wei));
        memset(src, -1, sizeof(src));

        for(int lx = 0;lx < E;lx++){
            int& a = links[lx].a;
            int& b = links[lx].b;
            int& w = links[lx].w;
            if(a != b and b != root and w < wei[b])
                wei[b] = w, src[b] = a;
        }
        /*for(int  lx = 0;lx < _cnt;lx++){
            printf("get %d <- %d w=%d\n", lx, src[lx], wei[lx]);
        }*/
        // Jellyfish
        memset(vis, -1, sizeof(vis));
        memset(tenta, -1, sizeof(tenta));

        w1 = 0;
        bool jizzy = false;
        for(int lx =  0;lx < V;lx++){
            if(cons[lx]) continue;
            if(src[lx] == -1 and lx != root) return -1;
            if(src[lx] >= 0) w1 += wei[lx];
            //printf("do at %d\n", lx);
            int s = lx;
            for(;s != -1 and vis[s] == -1;s = src[s]){
                //printf("vis at %d\n", s);
                vis[s] = lx;
            }

            if(s != -1 and vis[s] == lx){
                jizzy = true;
                int j = s;//printf("found s = %d\n", s);
                do{
                    tenta[j] = s; cons[j] = 1;
                    w2 += wei[j]; j = src[j];
                    //printf("j = %d\n", j);
                }while(j != s);
                cons[s] = 0;
            }
        }
        if(jizzy == false) break;
        for(int ly = 0;ly < E;ly++){
            int& a = links[ly].a;
            int& b = links[ly].b;
            int& w = links[ly].w;
            if(tenta[b] >= 0) w -= wei[b];
            if(tenta[a] >= 0) a = tenta[a];
            if(tenta[b] >= 0) b = tenta[b];
            if(a == b) links[ly--] = links[--E];
        }
    }
    return w1+w2;
}
int main()
{
    int an[55];
    int anode[55][551];
    int n, m;while(1){

        scanf("%d %d", &n, &m);
        if(n == 0  and m == 0 ) break;

        _cnt = 0;
        E = 0;

        for(int lx = 0;lx < n;lx++)
            scanf("%d", an+lx);

        int root = new_vertex();
        for(int lx = 0;lx < n;lx++)
            for(int ly = 0;ly <= an[lx];ly++)
                anode[lx][ly] = (new_vertex());

        for(int lx = 0;lx < n;lx++){
            add_link(root, anode[lx][0]);
            for(int ly = 1;ly <= an[lx];ly++)
                add_link(anode[lx][ly], anode[lx][ly-1]);
        }

        while(m--){
            int c1, l1, c2, l2, money;
            scanf("%d %d %d %d %d", &c1, &l1, &c2, &l2, &money);
            add_link(anode[c1-1][l1], anode[c2-1][l2], money);
        }
        //------build graph ok
        printf("%d\n", cal_mst(root));
    }
    return 0;
}