A Coding E. Coli

2010年4月5日星期一

TIOJ 1249 帳號查詢 [Brute Force]

poao899   1249   Accepted   784K   182MS   G++   1.47K   2010-04-06 01:41:49                              .

糟糕co好長

猥是猥瑣了些但不難

//**********************

#include<algorithm>
struct str{
    char s[70];
    bool operator<(const str &b)const{
        for(int i=0; i<70; i++){
            if(s[i]> b.s[i])return 0;
            else if(s[i]< b.s[i])return 1;
        }
        return 0;
    }
    void get(){
        gets(s);
        int i=0;
        for(; s[i]&&s[i]!=32; ++i);
        for(; i<70; ++i)
            s[i]= 0;
    }
};
struct name{
    str pre, now;
    void get(){
        pre.get(); now=pre;
        std::sort(now.s, now.s+strlen(now.s));
    }
    bool operator<(const name &b)const{
        return now<b.now || !(now<b.now)&&!(b.now<now)&&pre<b.pre;
    }
}na[7000], t;
struct out{
    str ord;
    int st, ed;
    bool operator<(const out &b)const{
        return ord< b.ord;
    }
}o[7000];
int n, oCnt;
bool can;
char buf[70];
void push(str ord, int st, int ed){
    o[oCnt].ord= ord;
    o[oCnt].st= st;
    o[oCnt].ed= ed;
    ++oCnt;
}
int main(){
    while(gets(buf)){
        sscanf(buf, "%d", &n);
        if(n==0)break;
        oCnt= 0;
        for(int i=0; i<n; ++i)
            na[i].get();
        std::sort(na, na+n);;
        for(int i=0, j; i<n; ++i){
            t= na[i];
            for(j=i; j<n; ++j){
                if(t.now< na[j].now)break;
            }
            if(j>i+1){
                push(na[i].pre, i, j);
                i= j-1;
            }
        }
        if(!oCnt)puts("No Answer");
        else{
            std::sort(o, o+oCnt);
            for(int i=0; i<oCnt; i++){
                for(int j=o[i].st; j<o[i].ed; ++j){
                    if(j!=o[i].st)printf(",");
                    printf("%s", na[j].pre.s);
                }
                puts("");
            }
        }
    }
}

TIOJ 1482 孔明棋 [狀態壓縮]

poao899   1482   Accepted   27640K   227MS   G++   0.79K   2010-04-05 19:42:47                 .

對吼忘了只要記走訪過所以不需要DP= =

//****************************************

#include<stdio.h>
int stat[1<<23][24], n, ss;
char in[20];
inline bool getbit(int q, int st){
    return st& (1<<q);
}
void dp(int st, int n){
    if(stat[st][n])return;
    int cnt=0, t1, t2, t3;
    for(int i=0; i<n; ++i){
        cnt+= getbit(i, st);
    }
    stat[st][n]= cnt;
    for(int i=0; i+2<n; ++i){
        if(getbit(i+1, st)){
            t1= getbit(i, st);
            t2= getbit(i+2, st);
            if(t1^t2){
                t3= st^(1<<(i))^(1<<(i+1))^(1<<(i+2));
                dp(t3, n);
                if(stat[t3][n]< stat[st][n])
                    stat[st][n]= stat[t3][n];
            }
        }
    }
}
int main(){
    while(~scanf("%d\n", &n)){
        gets(in);
        ss= 0;
        for(int i=0; in[i]; ++i)
            ss=(ss<<1)+(in[i]=='o');
        dp(ss, n);
        printf("%d\n", stat[ss][n]);
    }
}

TIOJ 1253 砲打皮皮 [Graph]

poao899 1253 Accepted 392K 166MS G++ 0.67K 2010-04-05 19:03:02 .

二分圖匹配

交錯路徑算法，O(V^3)

耶總算會co匹配了>//<

//**************************************

#include<stdio.h>
int n, k, match[1010], cCnt, mCnt, a, b;
bool con[1010][1010], vst[1010];
bool aug(int now){
	for(int i=1; i<=n; i++)
		if(!vst[i]&& con[now][i]){
			vst[i]= 1;
			if(match[i]==-1|| aug(match[i])){
				match[i]= now;
				return 1;
			}
		}
	return 0;
}
int main(){
	while(~scanf("%d%d", &n, &k)){
		if(!n&& !k) break;
		mCnt= 0;
		for(int i=1; i<=n; ++i){
			for(int j=1; j<=n; j++)
				con[i][j]= 0;
			match[i]= -1;
		}
		for(int i=0; i<k; ++i){
			scanf("%d%d", &a, &b);
			con[a][b]= 1;
		}
		for(int i=1; i<=n; ++i){
			for(int j=1; j<=n; ++j) vst[j]= 0;
			if(aug(i)) ++mCnt;
		}
		printf("Case #%d:%d\n", ++cCnt, mCnt);
	}
}

2010年4月4日星期日

POI - PA 2008 Studies [A] [Graph]

02-04-10 08:12 Studies [A] OK 10 .

題目是說

給你一張有向有權圖 V<=300 E<=90000

如果點A能經過一條路徑(可經過重複邊重複點)回到自己那他就是好的點

請輸出所有好的點

SCC，因為非SCC以外的點絕對沒有影響

全部cost反過來，鈴鐺人只要有負圈就表示這個SCC都可以

(原圖存在正圈)

//*********************************

#include<stdio.h>
#include<algorithm>
#define INF 10000000000LL
int color[400], n, m, cCnt, stamp[400], a, b, tt, conv[400], bfCnt, cnt, out[400];
long long c, dist[400];
struct edge{
	int i, j;
	long long co;
	edge *next;
}e[200000], *v[400], *vr[400], e_bf[200000];
bool vis[400], visr[400], canScc[400];
void set(edge **vv, edge *ee, int i, int j, long long c){
	edge *p=vv[i];
	vv[i]=ee; ee->i=i; ee->j=j; ee->co=c; ee->next=p;
}
void dfs(int n){
	vis[n]= 1;
	for(edge *p=v[n]; p; p=p->next)
		if(!vis[p->j]){
			dfs(p->j);
		}
	stamp[++tt]= n;
}
void dfsr(int n){
	visr[n]= 1;
	for(edge *p=vr[n]; p; p=p->next){
		if(!visr[p->j]){
			color[p->j]= color[n];
			dfsr(p->j);
		}
	}
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i=0; i<m; i++){
		scanf("%d%d%lld", &a, &b, &c);
		set(v, e+i, a, b, -c);
		set(vr, e+i+m, b, a, -c);
	}
	for(int i=1; i<=n; i++){
		dist[i]= INF;
		if(!vis[i])
			dfs(i);
	}
	for(int z=tt; z>0; z--){
		int i= stamp[z];
		if(!visr[i]){
			color[i]= ++cCnt;
			conv[cCnt]= i;
			dist[i]= 0;
			dfsr(i);
		}
	}
	for(int i=0; i<m; i++)
		if(color[e[i].i]== color[e[i].j])
			e_bf[bfCnt++]= e[i];
	for(int z=1; z<n; z++)
		for(int i=0; i<bfCnt; i++)
			if(dist[e_bf[i].j]> dist[e_bf[i].i]+e_bf[i].co)
				dist[e_bf[i].j]= dist[e_bf[i].i]+e_bf[i].co;
	for(int i=0; i<bfCnt; i++)
		if(dist[e_bf[i].j]> dist[e_bf[i].i]+e_bf[i].co)
			canScc[color[e_bf[i].i]]= 1;
	for(int i=1; i<=n; i++)
		if(canScc[color[i]])
			out[cnt++]= i;
	printf("%d\n", cnt);
	for(int i=0; i<cnt; i++, putchar(i==cnt?'\n':' '))
		printf("%d", out[i]);
}

TIOJ 1484 仙人掌 [Graph]

poao899 1484 Accepted 824K 947MS G++ 1.89K 2010-04-03 20:44:58 .

可愛題。

給你一張圖問你是不是符合以下條件

1. 整張圖都在同一個SCC
2. 每條邊只能而且必須屬於一個而且只有一個簡單圈

先做一次SCC

之後作v次DFS拔邊，均攤O(E)

//******************************************

#include<stdio.h>
#define MAXV 100100
int T, n,  m, stamp, tt, a, b, cnt, eCnt, _tar;
int vst[MAXV], can;
struct edge{
	int i, j;
	edge *next;
	void set(int a, int b, edge **vv){
		edge *p= vv[a];
		vv[a]= this; i=a; j=b; next= p;
	}
}e[MAXV*20], *v[MAXV], *vr[MAXV];
void dfs(int now){
	vst[now]= 1;
	for(edge *p=v[now]; p; p=p->next)
		if(!vst[p->j])
			dfs(p->j);
	stamp= now; ++tt;
}
void dfsr(int now){
	vst[now]= 1; ++cnt;
	for(edge *p=v[now]; p; p=p->next)
		if(!vst[p->j])
			dfsr(p->j);
}
int dfs3(int now){
	int t;
	vst[now]= _tar;
	for(edge *p=v[now],*q=NULL; p; p=p->next){
		if(vst[p->j]== _tar){
			eCnt++;
			if(q)q->next= p->next;
			else v[now]= p->next;
			return p->j;
		}
		else{
			t= dfs3(p->j);
			if(t!=0){
				eCnt++;
				if(q){q->next= p->next;}
				else v[now]= p->next;
				if(t!=now){
					return t;
				}
			}else q=p;
		}
	}
	return 0;
}
int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d%d", &n, &m);
		//init
		for(int i=0; i<=n; i++){
			vst[i]= 0;
			v[i]= vr[i]= NULL;
		}
		can= 1; tt= cnt= eCnt= 0;
		//input
		for(int i=0; i<m; i++){
			scanf("%d%d", &a, &b); ++a; ++b;
			e[i].set(a, b, v);
			e[i+m].set(b, a, vr);
		}
		//dfs
		dfs(1);
		if(tt!= n){puts("NO"); continue;}
		for(int i=1; i<=n; i++) vst[i]= 0;
		dfsr(stamp);
		if(cnt!= n){puts("NO"); continue;}
		for(int i=1; i<=n; i++) vst[i]= 0;
		for(int i=1; i<=n; i++){
			_tar= i;
			dfs3(i);
		}
		puts(eCnt== m? "YES": "NO");
	}
}

TIOJ 1493 三個農夫

poao899   1493   Accepted   37884K   1510MS   G++   2.79K   2010-04-03 13:49:36                 .

死得亂七八糟==

反正就壓扁線段樹但是一直co炸= =

不會Stack Overflow超神奇

//************************************

#include<stdio.h>
#include<stdlib.h>
#define MAXV 1000100
int conv[MAXV][2], _opt, _t, _n, _m, _pos, a, b;
long long _adj;
char com[100];

template<class T>
T getnum(){
    T get = 0;
    char c = getchar();
    while(c == ' ' || c == '\n') c = getchar();
    while(c > 47 && c < 58){
        get = get * 10 + c - 48;
        c = getchar();
    }
    return get;
}

//Tree
struct edge{
    int j;
    edge *next;
}e[MAXV*2],*v[MAXV];
void set(int i, int j){
    static int cnt=0;
    edge *p= v[i], *q= e+cnt++;
    v[i]= q; q->j= j; q->next= p;
}
//DFS
void dfs(int now){
    conv[now][0]= ++_t;
    for(edge *p=v[now]; p; p=p->next){
        if(conv[p->j][0])continue;
        dfs(p->j);
    }
    conv[now][1]= ++_t;
}
//Segment_Tree 2/e
struct seg{
    int l, r; long long v[3];
    seg *lch, *rch;
    long long qry(int, int);
    void adj();
}s[MAXV*4],*st;
seg* get(int l, int r){
    static int cCnt=0;
    seg *p= s+cCnt++;
    p->l=l; p->r=r; p->v[0]=p->v[1]=p->v[2]=-1; p->lch=p->rch=NULL;
    return p;
}
long long seg::qry(int _l, int _r){
    if(_l<l|| _r>r)return 0;
    if(l==r)return v[_opt]==-1? v[_opt]=0: v[_opt];
    int mid= (l+r)/2;
    if(!lch)return 0;
    if(_l==l&& _r==r){
        if(v[_opt]== -1){
            return v[_opt]= lch->qry(l, mid) + rch->qry(mid+1, r);
        }else return v[_opt];
    }
    if(mid>= _r)return lch->qry(_l, _r);
    else if(mid< _l)return rch->qry(_l, _r);
    return lch->qry(_l, mid) + rch->qry(mid+1, _r);
}
void seg::adj(){
    if(_pos<l|| _pos>r)return;
    int mid= (l+r)/2;
    if(l==r){
        if(v[_opt]== -1)v[_opt]=0;
        v[_opt]+= _adj; return;
    }
    if(!lch){
        lch= get(l, mid);
        rch= get(mid+1, r);
    }
    if(v[_opt]!= -1)v[_opt]+= _adj;
    if(mid< _pos) rch->adj();
    else lch->adj();
}
int main(){
    _n = getnum<int>();
    //Init
    st= get(1, _n*2);
    for(int i=1; i<_n; i++){
        a= getnum<int>(); b= getnum<int>();
        set(a, b); set(b, a);
    }
    //DFS : to Seg Tree
    dfs(1);
    scanf("%d", &_m);
    for(int i=0; i<_m; i++){
        scanf("%s", com);
        switch(com[0]){
            case'Q':
                _pos= getnum<int>();
                a= conv[_pos][0]; b= conv[_pos][1];
                for(_opt=0; _opt<3; _opt++,putchar(_opt==3?'\n':' '))
                    printf("%I64d", st->qry(a,b));
                break;
            case'D':
                _pos= getnum<int>(); _opt=getnum<int>();
                _adj= getnum<long long>();
                a= conv[_pos][0]; b= conv[_pos][1];
                if(_pos==1&& _opt!=2 || _pos!=1&&b==a+1&&_opt==2){
                    puts("Error");
                }else{
                    long long q= st->qry(a, a);
                    //printf("Q %I64d\n", q);
                    if(q>= _adj){
                        _adj= -_adj;
                        _pos= a;
                        st->adj();
                    }else puts("Error");
                }
                break;
            case'G':
                _pos= getnum<int>(); _opt=getnum<int>();
                _adj= getnum<long long>();
                a= conv[_pos][0]; b= conv[_pos][1];
                if(_pos==1&& _opt!=2 || _pos!=1&&b==a+1&&_opt==2){
                    puts("Error");
                }else{
                    a= conv[_pos][0];
                    _pos= a;
                    st->adj();
                }
                break;
        }
    }
}

TIOJ 1603 胖胖殺蚯事件 [ RMQ ]

73346 poao899 5088K 374MS G++ 1.43K 2010-04-02 11:24:19 .

SKYLY: 想當年第一次出現這個大家都不會沒想到現在已經平民化了

試寫Segment Tree.

//**********************************************

#include<stdio.h>
unsigned  val[100010], n, q, a, b;
struct seg{
	unsigned l, r, v1, v2;
	seg *lch, *rch;
	unsigned max(unsigned,unsigned);
	unsigned min(unsigned,unsigned);
}s[300000];
seg *get(unsigned l, unsigned r){
	static int cnt=0;
	s[cnt].l=l; s[cnt].r=r; s[cnt].v1=0; s[cnt].v2=222222222u;
	return s+cnt++;
}
unsigned seg::max(unsigned _l, unsigned _r){
	//printf(">>%u %u\n",l,r);
	if(l== r)return v1= val[l];
	unsigned m1, m2, mid=(l+r)/2;
	if(!lch){
		lch= get(l, mid);
		rch= get(mid+1, r);
	}
	if(_l==l&& _r==r){
		if(!v1){
			m1= lch->max(l, mid);
			m2= rch->max(mid+1, r);
			v1= m1>m2?m1:m2;
		}return v1;
	}
	if(_l> mid)
		return rch->max(_l, _r);
	else if(_r<= mid)
		return lch->max(_l, _r);
	else{
		m1= lch->max(_l, mid);
		m2= rch->max(mid+1, _r);
		return m1>m2?m1:m2;
	}
}
unsigned seg::min(unsigned _l, unsigned _r){
	if(l== r)return v2= val[l];
	unsigned m1, m2, mid=(l+r)/2;
	if(_l==l&& _r==r){
		if(v2==222222222u){
			m1= lch->min(l, mid);
			m2= rch->min(mid+1, r);
			v2= m1<m2?m1:m2;
		}return v2;
	}
	if(_l> mid)
		return rch->min(_l, _r);
	else if(_r<= mid)
		return lch->min(_l, _r);
	else{
		m1= lch->min(_l, mid);
		m2= rch->min(mid+1, _r);
		return m1<m2?m1:m2;
	}
}
int main(){
	scanf("%u %u", &n, &q);
	for(int i=1; i<=n; i++)
		scanf("%u", val+i);
	get(1, n);
	while(q--){
		scanf("%u%u", &a, &b);;
		printf("%u\n", s[0].max(a,b)-s[0].min(a,b));
	}
}

訂閱：文章 (Atom)

2010年4月5日 星期一

2010年4月4日 星期日

2010年4月5日星期一

2010年4月4日星期日