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));
	}
}

TIOJ 1099 B.射手座之日 [BFS] [NPSC 2006]

poao899    1099    Accepted    24048K    10281MS    G++    1.83K    2010-04-02 10:18:25                 .



本來想寫Bi-BFS的但好像寫炸了

            x+y+z= k            這個剪枝太強大了











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

#include<stdio.h>
#define QLEN 2000000
bool chk[3010][3010][2], can;
int q[QLEN][3], front, rear;
int n, x1, y1, z1, x2, y2, z2, sum, a, b, t1, t2, aa[3];
inline int max2(int i, int j, int k, int &m1, int &m2){
    int max=(i>j)?(i>k?i:k):(j>k?j:k), min=(i<j)?(i<k?i:k):(j<k?j:k);
    m1= min; m2= i+j+k-max-min;
}
inline void push(int x, int y, int op){
    if(x>=0&&x<=n&&y>=0&&y<=n&&(sum-x-y)>=0&&(sum-x-y)<=n){
        if(chk[x][y][!op]){can=1; return;}
        if(!chk[x][y][op]){
            chk[x][y][op]= 1;
            q[rear][0]= x; q[rear][1]= y; q[rear][2]= op;
            rear= ++rear%QLEN;
        }
    }
}
int main(){
    while(~scanf("%d%d%d%d%d%d%d", &n, &x1, &y1, &z1, &x2, &y2, &z2), n){
        if(x1+y1+z1!= x2+y2+z2){puts("No"); continue;}
        sum= x1+y1+z1;
        for(int i=0; i<=n; i++)
            for(int j=0; j<=n; j++)
                chk[i][j][0]= chk[i][j][1]= 0;
        front=0; rear=2; can=0;
        max2(x1,y1,z1,q[0][0],q[0][1]); q[0][2]= 0;
        max2(x2,y2,z2,q[1][0],q[1][1]); q[1][2]= 1;
        chk[q[0][0]][q[0][1]][0]= chk[q[1][0]][q[1][1]][1]= 1;
        while(!can&& front!=rear){
            int x= q[front][0], y= q[front][1], opt= q[front][2];
            if(chk[x][y][!opt]){can=1; break;}
            aa[0]= x; aa[1]= y; aa[2]= sum-x-y;
            if(opt==0){
                for(int i=0; i<3; i++)
                    for(int j=0; j<3; j++){
                        if(i==j)continue;
                        x=aa[i]; y=aa[j];
                        t1= (y*2)-x+1; t2= (x*2)-y-1;
                        max2(t1, t2, sum-t1-t2, a, b);
                        push(a, b, opt);
                    }
            }else{
                for(int i=0; i<3; i++)
                    for(int j=0; j<3; j++){
                        if(i==j)continue;
                        x=aa[i]; y=aa[j];
                        t1= (x*2)+y+1; t2= (y*2)+x-1;
                        if(t1%3==0 && t2%3==0){
                            t1/=3; t2/=3;
                            max2(t1, t2, sum-t1-t2, a, b);
                            push(a, b, opt);
                        }
                    }
            }
            front= ++front%QLEN;
        }
        if(can)puts("Yes");
        else puts("No");
    }
}

TIOJ 1144 5.快遞服務 [95 全國賽]

poao899    1144    Accepted    496K    591MS    G++    1.12K    2010-04-01 16:06:45                          .








狀態   O(n^3 m ) *   轉移  O(     1    )      ==>      狀態   O(n^2 m ) *   轉移  O(     1    ) 


然後就可以過了ˊˇˋ



每個狀態一定要有一個司機在上一個點上嘛ˇ












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

#include<stdio.h>
#define INF 1000000000
struct dp{
    int a[210][210];
}d1, d2, *now, *pre, *tmp;
int m, dist[210][210], n, pn;
int main(){
    now=&d1, pre=&d2;
    scanf("%d", &m);
    for(int i=0; i<m; i++)
        for(int j=0; j<m; j++){
            scanf("%d", &dist[i][j]);
            now->a[i][j]= pre->a[i][j]= INF;
        }
    for(int i=0;;i++){
        if(scanf("%d", &n)==EOF)break;
        --n;
        if(i==0){
            now->a[0][1]= dist[2][n];
            now->a[1][2]= dist[0][n];
            now->a[0][2]= dist[1][n];
        }else{
            for(int j=0; j<m; j++)
                for(int k=0; k<m; k++)
                    if(pre->a[j][k]!= INF){
                        if(now->a[j][k]> pre->a[j][k]+ dist[pn][n])now->a[j][k]= pre->a[j][k]+ dist[pn][n];
                        if(now->a[pn][k]> pre->a[j][k]+ dist[j][n])now->a[pn][k]= pre->a[j][k]+ dist[j][n];
                        if(now->a[pn][j]> pre->a[j][k]+ dist[k][n])now->a[pn][j]= pre->a[j][k]+ dist[k][n];
                        pre->a[j][k]= INF;
                    }
        }
        tmp=pre; pre=now; now=tmp; pn=n;
    }
    int min =INF;
    for(int i=0; i<m; i++)
        for(int j=0; j<m; j++)
            if(pre->a[i][j]< min)
                min= pre->a[i][j];
    printf("%d\n", min);
}

TIOJ 1444 郵局設置問題 [Tree] = UVa 10459

poao899    1444    Accepted    280K    181MS    G++    1.43K    2010-03-31 15:04:42                         .




同UVa 10459The  Tree Root

不過那題輸出好機車= =

Best Roots  : 1
Worst Roots : 4 5 6 7

第一行是兩個空白啦囧囧囧



Tree DP　O(n)    結束























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

#include<stdio.h>
#define MAX 1000000
int DP[MAX*2+1],n,sum,max;
int getint(){
    int g=0,c=getchar();
    while(c==10||c==9||c==32)c=getchar();
    if(c==EOF)return -1;
    while(c>='0'&&c<='9'){
        g=g*10+c-48;
        c=getchar();
    }
    return g;
}
int get(){
    char c=getchar();int a=1;
    while(c==10||c==32||c==9)c=getchar();
    if(c=='-')a=-1;
    if(c=='0')a=0;
    while(c!=10)c=getchar();
    return a;
}
main(){
    int *dp=DP;
    while(~(n=getint())){
        for(int i=-n;i<=n;i++)
            dp[i+MAX]=-1;
        sum=max=0;
        dp[MAX]=0;
        for(int i=0;i<n;i++){
            sum+=get();
            dp[sum+MAX]==-1?dp[sum+MAX]=i+1:max>?=i-dp[sum+MAX]+1;
        }
        printf("%d\n",max);
    }
}

TIOJ 1161 4.虛擬番茄online

poao899    1161    Accepted    11748K    1373MS    G++    0.87K    2010-03-31 11:08:14                       .




聽說這題可以線性解O(n)



不過                Heap     O(      n lg n      )              頗直覺

















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

#include<algorithm>
struct skill{
	int s, a;
	bool operator< (const skill &b)const{return a< b.a;}
	void get(){scanf("%d%d", &s, &a);}
}s[1000010], h[1000010];
bool cmp(skill a, skill b){return a.s< b.s;}
int t, k, n, min, top;
int main(){
	scanf("%d", &t);
	while(t--){
		top= 0; min= 2147483647;
		scanf("%d%d", &n, &k);
		for(int i=0; i<n; i++)
			s[i].get();
		std::sort(s, s+n, cmp);
		for(int i=0; i<n; ){
			int ns= s[i].s;
			while(i<n && s[i].s== ns){
				h[top++]= s[i];
				std::push_heap(h, h+top);
				i++;
			}
			if(top< k)continue;
			while(top> k){
				std::pop_heap(h, h+top--);
			}
			ns+= h[0].a;
			if(ns< min)min= ns;
		}
		printf("%d\n", min);
	}
}

TIOJ 1191 直到夢的盡頭

    poao899    -16K    31MS    G++    0.23K     2010-03-31 03:21:56                                     .


有趣但不難的題目


阿書: 轉九進位就AC了                                       (雷)




























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

char buf[30];
long long val;
int main(){
	while(gets(buf)){
		if(buf[0]=='0')break;
		val=0;
		for(int i=0; buf[i]; i++){
			if(buf[i]>'6')buf[i]--;
			val= val*9+buf[i]-48;
		}
		printf("%I64d\n",val);
	}
}