A Coding E. Coli: 5月 2010

2010年5月12日星期三

IOI '07 Pairs

2   75971   poao899   49440K   4656MS   G++    3.16K    2010-04-26 08:47:55                        .

Inspired by warehouse?

不過三維作法很有趣，竟然有一個n維曼哈頓轉Chebyshev distance的作法，

可惜依現在硬體技術，作用有限

事實上這兩個都有優點，可惜自由轉換僅限於1或2維

算是個遺憾吧(?

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

#include<algorithm>
#define N 100010
#define lb(x) ((x)&-(x))
struct ele{
    int i, j, k, w, x, y, z;
    void _2get();
    void _3get();
}_ar[N];
int ar[N], front, rear;
int b, n, d, m, nmax; long long ans;
int getint(){
    int g=0; char c=getchar();
    while(c==10||c==32||c==9)c=getchar();
    while(c>='0'&&c<='9'){
        g= g*10+c-48;
        c=getchar();
    }
    return g;
}
//case 2
#define _2LEN 75010
void ele::_2get(){
    i= getint(); j= getint();
    x= i+j; y= i-j;
}
bool _2cmp(ele a, ele b){
    return a.y<b.y;
}
int _2bit[_2LEN*3];
inline int _2qry(int a){
    if(a<0) return 0;
    int ret= 0;
    while(a>0){
        ret+= _2bit[a];
        a-= lb(a);
    }
    return ret;
}
inline int _2find(int l, int r){
    return _2qry(r)-_2qry(l-1);
}
inline void _2adj(int a, int r){
    while(a<=nmax){
        _2bit[a]+= r;
        a+= lb(a);
    }
}
//case 3
#define _3LEN 76
void ele::_3get(){
    i= getint(); j= getint(); k= getint();
    w= i-j-k; x= i+j-k+m; y= i-j+k+m; z= i+j+k;
}
bool _3cmp(ele a, ele b){
    return a.w<b.w;
}
int _3bit[_3LEN*3+1][_3LEN*3+1][_3LEN*3+1];
inline int _3qry(int x, int y, int z){
    int ret= 0;
    for(int xx=x; xx>0; xx-=lb(xx))
        for(int yy=y; yy>0; yy-=lb(yy))
            for(int zz=z; zz>0; zz-=lb(zz))
                ret+= _3bit[xx][yy][zz];
    return ret;
}
inline int _3find(int lx, int ly, int lz, int rx, int ry, int rz){
    if(rx> nmax)rx= nmax;
    if(ry> nmax)ry= nmax;
    if(rz> nmax)rz= nmax;
    int ret= _3qry(rx,ry,rz);
    ret= ret- _3qry(lx-1,ry,rz)- _3qry(rx,ly-1,rz)- _3qry(rx,ry,lz-1);
    ret= ret+ _3qry(rx,ly-1,lz-1)+ _3qry(lx-1,ry,lz-1)+ _3qry(lx-1,ly-1,rz);
    ret= ret- _3qry(lx-1,ly-1,lz-1);
    return ret;
}
inline void _3adj(int x, int y, int z, int r){
    for(int xx=x; xx<=nmax; xx+=lb(xx))
        for(int yy=y; yy<=nmax; yy+=lb(yy))
            for(int zz=z; zz<=nmax; zz+=lb(zz))
                _3bit[xx][yy][zz]+= r;
}
int main(){
    b= getint(); n= getint(); d= getint(); m= getint();
    //case 1
    if(b==1){
        for(int i=0; i<n; i++) ar[i]= getint();
        std::sort(ar, ar+n);
        for(front=rear=0; rear<n; rear++){
            while(ar[front]+d< ar[rear]) front++;
            ans+= rear-front;
        }
    }
    //case 2
    else if(b==2){
        nmax= _2LEN*3;
        for(int i=0; i<n; i++) _ar[i]._2get();
        std::sort(_ar, _ar+n, _2cmp);
        for(front=rear=0; rear<n; rear++){
            while(_ar[front].y+d< _ar[rear].y){
                _2adj(_ar[front].x, -1);
                front++;
            }
            ans+= _2find(_ar[rear].x-d, _ar[rear].x+d);
            _2adj(_ar[rear].x, 1);
        }
    }
    //case 3
    else if(b==3){
        nmax= _3LEN*3;
        for(int i=0; i<n; i++) _ar[i]._3get();
        std::sort(_ar, _ar+n, _3cmp);
        for(front=rear=0; rear<n; rear++){
            while(_ar[front].w+d< _ar[rear].w){
                _3adj(_ar[front].x, _ar[front].y, _ar[front].z, -1);
                front++;
            }
            ans+= _3find(_ar[rear].x-d, _ar[rear].y-d, _ar[rear].z-d, _ar[rear].x+d, _ar[rear].y+d, _ar[rear].z+d);
            _3adj(_ar[rear].x, _ar[rear].y, _ar[rear].z, 1);
        }
    }
    printf("%I64d\n", ans);
}

POI 13rd Warehouse

25-04-10 14:01 Warehouse OK 100 .

有趣的題目XD

很神秘的圖片: 圖片

p=1是曼哈頓距離
p=2是歐式距離
p=∞就是這個題目問的問題了，Chebyshev distance

反正這張圖很好用(?

然後會做了還是會有一個盲點，反正很帥的題目˙//˙

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

#include<algorithm>
int n, i, xx, yy, ax, ay, _x, _y; long long sum, now, t;
struct pl{
	int i,j,c,x,y;
	void get(){
		scanf("%d%d%d", &x, &y, &c);
		sum+= (long long)c;
		i= x+y;
		j= x-y;
	}
}p[100000];
bool cmp(pl a, pl b){return a.i<b.i;}
bool cmp2(pl a, pl b){return a.j<b.j;}
int main(){
	scanf("%d", &n);
	for(i=0; i<n; i++)
		p[i].get();
	std::sort(p, p+n, cmp);
	for(now=0, i=0; i<n; i++){
		now+= (long long)p[i].c;
		if(now> sum/2){
			xx= p[i].i;
			break;
		}
	}
	std::sort(p, p+n, cmp2);
	for(now=0, i=0; i<n; i++){
		now+= (long long)p[i].c;
		if(now> sum/2){
			yy= p[i].j;
			break;
		}
	}
	ax= (xx+yy)/2; ay= (xx-yy)/2;
	for(now=9223372036854775807LL,xx=0; xx<2; xx++)
		for(yy=0; yy<2; yy++){
			int x=ax+xx, y=ay+yy, tx, ty;
			for(t=0,i=0; i<n; i++){
				tx=(x>p[i].x?x-p[i].x:p[i].x-x);
				ty=(y>p[i].y?y-p[i].y:p[i].y-y);
				t+= (long long)(tx>ty?tx:ty)*p[i].c;
			}
			if(t<now){
				now= t;
				_x= x;
				_y= y;
			}
		}
	printf("%d %d\n", _x, _y);
}

POI 14th Offices

24-04-10 15:57 Offices OK 100 .

這題作法好多XD

學了一種新建圖方式，不用struct的adjacent list

反正就是開一個Linked-list 維護沒走過的點

這樣bfs均攤O(V)

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

#include<algorithm>
#define V 100100
#define E 4000200
int ej[E], st[V], enx[E], n, m, cnt, nxt[V], pre[V], a, b, p, c[V], q[V], v[V];
int s[3000], pp[V];
int main(){
	scanf("%d%d", &n, &m);
	for(int i=0; i<=n; i++){nxt[i]= i+1; pre[i+1]= i;}
	for(int i=1; i<=m; i++){
		scanf("%d%d", &a, &b);
		ej[i]= b; p= st[a]; st[a]= i; enx[i]= p;
		ej[i+m]= a; p= st[b]; st[b]= i+m; enx[i+m]= p;
	}
	for(int i=1; i<=n; i= nxt[i]){
		a=b=0;
		q[b]= i; b++;
		while(a!=b){
			p= q[a]; a++;
			v[p]= i; pp[i]++;
			for(int j=st[p]; j; j=enx[j])c[ej[j]]= p;
			for(int j=nxt[i]; j<=n; j=nxt[j])
				if(c[j]!= p){
					q[b]= j; b++;
					nxt[pre[j]]= nxt[j];
					pre[nxt[j]]= pre[j];
				}
		}
	}
	for(int i=1; i<=n; i++)
		if(v[i]==i){
			s[cnt]= pp[i];
			cnt++;
		}
	std::sort(s, s+cnt);
	printf("%d\n", cnt);
	for(int i=0; i<cnt; i++, putchar(i==cnt? '\n': ' '))
		printf("%d",s[i]);
}

TIOJ 1149 4.滿漢全席 [2-SAT]

3 75828 poao899 -8K 75MS G++ 1.01K 2010-04-22 17:40:51 .

轉一轉就變2-SAT了

這是2-SAT經典文：按我

其實我覺得最麻煩是建圖很容易建歪˙˙

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

#include<stdio.h>
bool con[40][40], pos, v[40];
char buf[100], c, d;
int n, m, K, a, b, $;
/*
m 0~n-1  h n~2n-1
*/
bool dfs(int now){
	v[now]= 1;
	if(now-$==n|| $-now==n)return 0;
	for(int i=0; i<2*n; i++)
		if(con[now][i]&& !v[i]&& !dfs(i))
			return 0;
	return 1;
}
int main(){
	gets(buf);
	sscanf(buf, "%d", &K);
	while(K--){
		pos= 1;
		gets(buf);
		sscanf(buf, "%d%d", &n, &m);
		for(int i=0; i<n*2; i++)
			for(int j=0; j<n*2; j++)
				con[i][j]= 0;
		for(int i=0; i<m; i++){
			gets(buf);
			sscanf(buf, "%c%d %c%d", &c, &a, &d, &b);
			con[a+(c=='h'?n:0)-1][b+(d=='m'?n:0)-1]= 1;
			con[b+(d=='h'?n:0)-1][a+(c=='m'?n:0)-1]= 1;
		}
		for($=0; pos&&$<n; $++){
			for(int j=0; j<2*n; j++)v[j]= 0;
			pos= dfs($);
			if(!pos){
				for(int j=0; j<2*n; j++)v[j]= 0;
				$+=n; pos= dfs($); $-=n;
			}
		}
		puts(pos? "GOOD": "BAD");
	}
}

TIOJ 1204 E.魔法部的任務 [Matching]

17    75514    poao899    1004K    8203MS    G++     0.79K     2010-04-17 21:12:26                       .

DAG 最小路徑覆蓋 == 最大匹配

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

#include<stdio.h>
int T, n, match[1010], cnt, p[1010][2], t[1010];
bool vst[1010], con[1010][1010];
inline int abs(int a, int b){return a>b? a-b: b-a;}
bool aug(int now){
    if(vst[now]) return 0;
    vst[now]= 1;
    for(int i=1; i<=n; i++)
        if(con[now][i]){
            if(match[i]==-1|| aug(match[i])){
                match[i]= now;
                return 1;
            }
        }
    return 0;
}
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        cnt= 0;
        for(int i=1; i<=n; i++){
            scanf("%d%d%d", &t[i], &p[i][0], &p[i][1]);
            match[i]= -1;
        }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                con[i][j]= (i!=j)&& (abs(p[i][0], p[j][0])+ abs(p[i][1], p[j][1])+ t[i]<= t[j]);

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++) vst[j]= 0;
            if(aug(i)) cnt++;
        }
        printf("%d\n", n-cnt);
    }
}

TIOJ 1204 樹狀的堆積結構 [Cartesian Tree]

4 75128 poao899 456K 156MS G++ 0.86K 2010-04-10 16:01:38 .

第一次寫笛卡兒樹

其實比想像好寫(?

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

#include<stdio.h>
int top, n, cnt;
struct node{
	node *lch, *rch;
	int val;
}N[10020], *st[10020];
void dfs(node *now){
	if(now==NULL)return;
	printf("%d%c", now->val, ++cnt==n? '\n': ' ');
	dfs(now->lch);
	dfs(now->rch);
}
int main(){
	N[0].val= -1;
	while(~scanf("%d", &n)){
		if(!n) break;
		cnt= 0;
		top= 0; N[0].lch= N[0].rch= NULL;
		for(int i=1; i<=n; i++){
			scanf("%d", &N[i].val);
			N[i].lch= N[i].rch= NULL;
		}
		st[top]= N;
		for(int i=1; i<=n; i++){
			while(top> -1&& st[top]->val>N[i].val){
				N[i].lch= st[top];
				--top;
			}
			st[top]->rch= &N[i];
			st[++top]= &N[i];
		}
		dfs(N[0].rch);
	}
}

TIOJ 1483 電腦檢查 [BIT]

4 75098 poao899 15712K 10230MS G++ 1.06K 2010-04-10 12:42:54 .

第一次寫樹狀數組

然後就愛上他了˙////////˙

是說一開始陣列開太小一直RE

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

#include<algorithm>
#define MOD 1000000007
#define lb(x) ((x)&(-x))
int bit[1010][1010], r, c, T, cnt;
int qry(int i, int j){
	int ret= 0;
	for(; i>0; i-=lb(i))
		for(int jj=j; jj>0; jj-=lb(jj)){
			ret+= bit[i][jj];
			ret%=MOD;
		}
	return ret;
}
void adj(int i, int j, int v){
	for(; i<=r; i+=lb(i))
		for(int jj=j; jj<=c; jj+=lb(jj)){
			bit[i][jj]+= v;
			bit[i][jj]%=MOD;
		}
}
struct com{
	int i,j,h;
	bool operator<(const com &b)const{
		return h<b.h|| ( h==b.h&& (i>b.i|| i==b.i&&j>b.j ) );
	}
	void get(int a, int b){
		scanf("%d", &h);
		i= a; j= b;
	}
}cc[1001000];
int main(){
	scanf("%d", &T);
	while(T--){
		scanf("%d%d", &r, &c);
		//Init
		cnt= 0;
		for(int i=1; i<=r; i++)
			for(int j=1; j<=c; j++)
				bit[i][j]= 0;
		for(int i=1; i<=r; i++)
			for(int j=1; j<=c; j++)
				cc[cnt++].get(i, j);
		std::sort(cc, cc+cnt);
		for(int i=0; i<cnt; i++){
			int ii=cc[i].i, jj=cc[i].j;
			adj(ii, jj, qry(ii, jj)+1);
		}
		printf("%d\n", qry(r, c));
	}
}

TIOJ 1136 3.熱鍋上的螞蟻 [Matrix]

76695    nolonger    3136K    1591MS    G++     1.19K     2010-05-12 23:24:38                                .

蚯蚓：「看到範圍10^9不是很明顯嗎？」

然後就瞬間領悟了。

第二題co 矩陣相乘

是說最後模考還是寫爆了orz

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

#include<stdio.h>
bool con[110][110];
int n, t, a, b, cnt[110], c, pre, x;
double tmp[110][110];
struct Matrix{
    double a[110][110];
    void operator*= (Matrix b){
        for(int i=1; i<=t; i++)
            for(int j=1; j<=t; j++)
                tmp[i][j]= .0;
        for(int i=1; i<=t; i++)
            for(int j=1; j<=t; j++)
                for(int k=1; k<=t; k++)
                    tmp[i][j]+= a[i][k]*b.a[k][j];
        for(int i=1; i<=t; i++)
            for(int j=1; j<=t; j++)
                a[i][j]= tmp[i][j];
    }
}n2[40], ans;

int main(){
    while(~scanf("%d%d", &t, &n)){
        if(!n&&!t)break;
        scanf("%d", &c);
        //Init
        for(int i=1; i<=t; i++){
            cnt[i]= 0;
            for(int j=1; j<=t; j++){
                con[i][j]= 0;
                ans.a[i][j]= .0;
            }
            ans.a[1][i]= 1./t;
        }
        //Input
        while(c--){
            scanf("%d%d", &a, &b);
            ++cnt[a]; ++cnt[b];
            con[a][b]= con[b][a]= 1;
        }
        //Construct
        for(int i=1; i<=t; i++)
            for(int j=1; j<=t; j++)
                n2[0].a[i][j]= (cnt[i]&& con[i][j])? (1./cnt[i]): .0;
        //Matrix
        for(pre=1; (1<<pre)<=n; pre++){
            n2[pre]= n2[pre-1];
            n2[pre]*=n2[pre-1];
        }
        //Compute
        for(; pre>=0; pre--){
            if((1<<pre)<=n){
                n-=(1<<pre);
                ans*= n2[pre];
            }
        }
        scanf("%d", &x);
        printf("%.4lf\n", ans.a[1][x]);
    }
}

訂閱：文章 (Atom)

2010年5月12日 星期三

2010年5月12日星期三