A Coding E. Coli: 12月 2009

2009年12月24日星期四

TIOJ 1438 好多星星ver 1.6 [Math]

nolonger   -16K   246MS   G++    0.39K    2009-12-24 20:22:56                                        .

唔原來跟怎麼共線沒差(驚

是說記憶體限制好小不能建表...

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

#include<stdio.h>
int n,m,k;
long long t;
main(){
    while(scanf("%d",&n),n){
        t=(long long)n*(n-1)*(n-2)/6;
        scanf("%d",&m);
        while(m--){
            scanf("%d",&k);
            t-=(long long)(k)*(k-1)*(k-2)/6;
        }
        t>0?printf("%I64d\n",t):puts("IMPOSSIBLE");
    }
}

2009年12月21日星期一

TIOJ 1344 Miners [IOI 2007, Day 2]

poao899 -8K 1103MS G++ 1.26K 2009-12-21 22:08:54 .

一開始以為是Greedy

發現是 DP 就秒殺orz

狀態數4^4*100000(要滾動)

狀態轉移O(1)

唔不過快遞不能這樣寫啊ˊˋ

測資200

不附code了。

2009年12月18日星期五

TIOJ 1302 撿鞋問題─強化死筆之路！ [Hash]

nolonger 1302 Accepted 5988K 217MS G++ 1.92K 2009-12-19 01:21:51 .

int tohash(char *s){
return s[0];
}

咦等一下這樣的hash就過了= =

反正就基本Hash操作啊

小乃：開map啦

唔如果考出類似題我一定開map

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

#include<stdio.h>
#include<string.h>
#define HV 33331
#define LEN 30
struct hash{
	char s[LEN];
	int dir;
	hash *next,*topair;
}H[HV];
char com[10],s1[LEN],s2[LEN];
//dir 0 NULL 'n' name 'w' death
int tohash(char *s){
	
	int val=0;
	for(int i=0;s[i];i++)
		val=(val*31+s[i])%HV;
	return val;
	
	return s[0];
}
void push(char *name,char *death){
	int nh=tohash(name),dh=tohash(death);
	hash *p=&H[nh],*q,*r;
	if(p->dir){
		r=p->next;
		p->next=new hash;
		p=p->next;
		p->next=r;
	}
	strcpy(p->s,name);
	p->dir='n';
	
	q=&H[dh];
	if(q->dir){
		r=q->next;
		q->next=new hash;
		q=q->next;
		q->next=r;
	}
	strcpy(q->s,death);
	q->dir='w';
	
	q->topair=p;
	p->topair=q;
}
hash* find(char *s,int d){
	int v=tohash(s);
	hash *p=&H[v];
	while(p&&(strcmp(s,p->s)||p->dir!=d)){
		p=p->next;
	}
	if(p==NULL || p->dir!=d)return NULL;
	return p;
}
bool del(char *s,int d){
	int v=tohash(s);
	hash *p=&H[v],*pre=NULL;
	while(p&&(strcmp(s,p->s)||p->dir!=d)){
		pre=p;
		p=p->next;
	}
	if(p==NULL || p->dir!=d)return 0;
	if(pre==NULL){
		if(p->dir==d){
			p->dir=0;
			del(p->topair->s,d=='n'?'w':'n');
		}
		return 0;
	}
	pre->next=p->next;
	del(p->topair->s,d=='n'?'w':'n');
	delete p;
	return 1;
}
main(){
	while(~scanf("%s%s",com,s1)){
		if(!strcmp(com,"add")){
			scanf("%s",s2);
			push(s1,s2);
		}
		else if(!strcmp(com,"chk")){
			hash *p=find(s1+1,s1[0]);
			if(p==NULL || p->dir!=s1[0])puts("Not found.");
			else{
				if(p->dir=='w')
					p=p->topair;
				printf("%s %s\n",p->s,p->topair->s);
			}
		}
		else{
			del(s1+1,s1[0]);
		}
	}
}

UVa 10819 Trouble of 13-Dots [DP]

10819 Trouble of 13-Dots Accepted C++ 0.344 2009-12-18 03:25:15 .

背包

有一個很可愛的條件是說，如果總花費會超過2000的話limit會+200

那就記剛好花那麼多錢的最大滿意度吧

一樣沒code

2009年12月16日星期三

TIOJ 1569 8 Puzzle - the Hyper version [IDA*]

poao899 1569 Accepted -8K 244MS G++ 1.08K 2009-12-16 16:15:50 .

第二題IDA*(咦

H():一樣漢米頓距離不過注意有穿透所以行列上線都是1 所以每個數字的答案都只可能是012中的一個

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

#include<stdio.h>
/*
0 1 2
3 4 5
6 7 8
*/
int dir[9][4]={
	1,3,10,10,
	0,2,4,7,
	1,5,10,10,
	0,4,6,5,
	1,3,5,7,
	2,4,8,3,
	3,7,10,10,
	4,6,8,1,
	5,7,10,10,
};
inline void sw(int &a,int &b){
	a^=b^=a^=b;
}
inline int abs(int a){
	return a>0?a:-a;
}
int puz[10],ans[10],dmax,z;
int h(){
	int sum=0;
	for(int i=0;i<9;i++){
		if(puz[i]){
			//printf("puz%d ans%d\n",puz[i],ans[puz[i]]);
			sum+=((puz[i]-1)%3!=i%3)+((puz[i]-1)/3!=i/3);
		}
	}
	return sum;
}
int dfsid(int depth,int pre){
	int hv=h(),rp;
	if(depth+hv>dmax)return -1;
	if(hv==0)return depth;
	for(int i=0;i<9;i++){
		if(puz[i]==0){
			//printf("puz %d\n",i);
			for(int j=0;j<4;j++){
				if(dir[i][j]!=10 && dir[i][j]!=pre){
					sw(puz[dir[i][j]],puz[i]);
					//if(h()<hv){
					rp=dfsid(depth+1,i);
					//}else rp=-1;
					sw(puz[dir[i][j]],puz[i]);
					if(~rp)return rp;
				}
			}
			return -1;
		}
	}
}
main(){
	for(int i=0;i<9;i++)scanf("%d",puz+i);
	int way;
	for(dmax=0;;dmax++){
		//printf("%d\n",dmax);
		way=dfsid(0,-1);
		if(~way)break;
	}
	printf("%d\n",way);
}

TIOJ 1198 8-puzzle [IDA*]

poao899 -8K 106MS G++ 1.46K 2009-12-16 16:09:01 .

第一題IDA*>//<

H() : 每個數字到正確位置的漢米頓距離

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

#include<stdio.h>
/*
0 1 2
3 4 5
6 7 8
*/
int dir[9][4]={
	1,3,10,10,
	0,2,4,10,
	1,5,10,10,
	0,4,6,10,
	1,3,5,7,
	2,4,8,10,
	3,7,10,10,
	4,6,8,10,
	5,7,10,10,
};
inline void sw(int &a,int &b){
	a^=b^=a^=b;
}
inline int abs(int a){
	return a>0?a:-a;
}
int puz[10],ans[10],dmax,z;
int h(){
	int sum=0;
	for(int i=0;i<9;i++){
		if(puz[i]){
			sum+=abs((ans[puz[i]])%3-i%3)+abs((ans[puz[i]])/3-i/3);
		}
	}
	return sum;
}
int dfsid(int depth,int pre){
	int hv=h(),rp;
	if(depth+hv>dmax)return -1;
	if(hv==0)return depth;
	for(int i=0;i<9;i++){
		if(puz[i]==0){
			//printf("puz %d\n",i);
			for(int j=0;j<4;j++){
				if(dir[i][j]!=10 && dir[i][j]!=pre){
					sw(puz[dir[i][j]],puz[i]);
					rp=dfsid(depth+1,i);
					sw(puz[dir[i][j]],puz[i]);
					if(~rp)return rp;
				}
			}
			return -1;
		}
	}
}
main(){
	for(int i=0;i<9;i++)scanf("%d",puz+i);
	for(int i=0;i<9;i++){
		scanf("%d",&z);
		ans[z]=i;
	}
	int way;
	for(dmax=0;;dmax+=2){
		way=dfsid(0,-1);
		if(~way)break;
	}
	printf("%d\n",way);
}

UVa 10779 - Collector's Problem [Flow]

10779   Collectors Problem   Accepted   C++   0.004   2009-12-16 03:48:22                           .

這題好酷XD

應該是因為我少寫Flow題吧

來講一下題目敘述好了

=============無雷線=============

有很多人(2<=n<=20)，很多種類的火柴(5<=m<=25)。

每個人都有一定數量的火柴(ki<=50)。

現在你的目標是跟大家交換火柴，

交換成功的條件是 那個人沒有你給他的那種火柴 並且他給你的那種火柴他自己有超過一隻(>2)。

請問你最多可以交易到幾種火柴。

=============有雷線=============

建圖。

源點 -> 每種火柴    容量是你手上有那種火柴的數量

每種火柴 -> 每個其他人    容量是1   當那個人沒有那種火柴時

每個其他人 -> 每種火柴    容量是那個人擁有的那種火柴數量-1 當那個人有那種火柴且(>2隻)

每種火柴 -> 匯點   容量是1

然後最大流過去ˊˇˋ

SKYLY好威蚯蚓好威阿書好威

=============止雷線=============

Rank 12耶>///<

2009年12月14日星期一

4. 工作順序問題 [97全國賽]

DP. .

不依啦zerojudge會MLE

算了

#include<stdio.h>
long long dp[10000010],n,m;
main(){
	freopen("4.in","r",stdin);
	freopen("4.out","w",stdout);
	scanf("%I64d%I64d",&n,&m);
	dp[1]=1;dp[0]=0;
	for(int i=2;i<=n;i++)
		dp[i]=((dp[i-1]*(i-1))%m+(dp[i-2])*(i-2))%m;
	printf("%I64d\n",dp[n]);
}

遞推式子不會很難想

就前一個*(n-1)個位置插入

+

前一個剛好有一組不合法的(即兩個相鄰->結合成一個點

大概這樣XD

3. 找關鍵人物 [97全國賽]

頗單純的樹型DPˊˇˋ .

寫得爛爛的orz

應該是O(n^2)吧不會估XD

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

#include<stdio.h>
int n,a,b;
struct edge{
	int j;
	edge *next;
	void set(int jj,edge *n){
		j=jj;next=n;
	}
}E[40020],*V[20010];
int edgeCnt;
void set(int i,int j){
	//printf("set %d %d\n",i,j);
	edge *p=E+edgeCnt++,*q=E+edgeCnt++,*r;
	r=V[i];
	V[i]=p;
	p->set(j,r);
	r=V[j];
	V[j]=q;
	q->set(i,r);
}
int dp[20010],max[20010],son[20010];
int treedp(int now,int fa){
	//printf("treedp %d %d\n",now,fa);
	if(max[now])return son[now];
	int sub=0,tmp;
	for(edge *p=V[now];p;p=p->next){
		if(p->j == fa)continue;
		//printf("now %d now %d\n",now,p);
		sub++;
		son[now]+=treedp(p->j,now)+1;
		//printf("now %d son %d %d\n",now,p->j,son[p->j]);
		if(dp[now]<dp[p->j] || dp[now]==dp[p->j]&&max[now]>max[p->j]){
			dp[now]=dp[p->j];
			max[now]=max[p->j];
		}
	}
	if(sub==0){
		max[now]=-1;
		return son[now]=dp[now]=0;
	}
	tmp=son[now]*(n-son[now]-1);
	for(edge *p=V[now];p;p=p->next){
		if(p->j == fa)continue;
		for(edge *q=p;q;q=q->next){
			if(q->j == fa)continue;
			if(p->j!=q->j){
				tmp+=(1+son[p->j])*(1+son[q->j]);
			}
		}
	}
	if(tmp>dp[now] || tmp==dp[now]&&now<max[now]){
		max[now]=now;
		dp[now]=tmp;
	}
	return son[now];
}
main(){
	freopen("3.in","r",stdin);
	freopen("3.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&a,&b);
		set(a,b);
	}
	treedp(1,1);
	//for(int i=1;i<=n;i++)
	//	printf("node %d son %d dp %d max %d\n",i,son[i],dp[i],max[i]);
	printf("%d %d\n",max[1],dp[1]);
}

TIOJ 1096 E.漢米頓的麻煩 [NPSC2006初賽]

poao899   36K   234MS   G++    0.51K    2009-12-14 15:56:11                                            .

Floyd-Warshall就過了orz

跟之前那題TIOJ 1212 圖論之最小圈測試一模一樣orz

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

#include<stdio.h>
#define INF 1000000000
int dist[110][110],n,min;
main(){
    while(scanf("%d",&n),n){
        min=INF;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                scanf("%d",&dist[i][j]);
                if(!dist[i][j])
                    dist[i][j]=INF;
            }
        for(int k=0;k<n;k++)
            for(int i=0;i<n;i++)
                for(int j=0;j<n;j++)
                    if(dist[i][k]+dist[k][j]<dist[i][j])
                        dist[i][j]=dist[i][k]+dist[k][j];
        for(int i=0;i<n;i++)
            if(min>dist[i][i])
                min=dist[i][i];
        min==INF?puts("-1"):printf("%d\n",min);
    }
}

2009年12月12日星期六

UVa 200 Rare Order

200   Rare Order   poao899   Accepted   C++   0.012   2009-12-12 11:28:09                            .

不難不過覺得好有趣(?

寫過太多奇怪的算法好久沒有好好想一題了雖然這是我的問題XD

算是...最短路...吧

找出相鄰兩列可以知道的大小關係

再去建圖

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

//UVa 200
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 100000
struct alpha{
    int cha,rank,in,out;
    bool operator<(const alpha &b)const{
        return rank<b.rank;
    }
}A[30];
int dist[30][30],nlen,plen,st,cnt;
char S1[30],S2[30];
main(){
    char *now=S1,*pre=S2,*t;
    //Initialize
    for(int i=0;i<30;i++){
        A[i].cha='A'+i;
        for(int j=0;j<30;j++)
            dist[i][j]=INF;
    }
    //Input
    while(1){
        gets(now);
        if(now[0]=='#')break;
        nlen=strlen(now);
        for(int i=0;i<nlen&&i<plen;i++)
            if(now[i]!=pre[i]){
                dist[pre[i]-'A'][now[i]-'A']=-1;
                A[now[i]-'A'].in++;
                A[pre[i]-'A'].out++;
                break;
            }
        plen=nlen;
        t=now;now=pre;pre=t;
    }
    //Find Start
    for(int i=0;i<30;i++){
        if(A[i].in+A[i].out >0 && A[i].in==0){
            st=i;
            break;
        }
    }
    dist[st][st]=0;
    //Floyd-Warshall
    for(int k=0;k<30;k++)
        for(int i=0;i<30;i++)
            for(int j=0;j<30;j++)
                if(dist[i][k]+dist[k][j] < dist[i][j])
                    dist[i][j]=dist[i][k]+dist[k][j];
    //Rank
    for(int i=0;i<30;i++){
        if(dist[st][i]<=0)
            A[i].rank=-dist[st][i];
        else A[i].rank=10000;
    }
    //Sort
    std::sort(A,A+30);
    //Output
    for(int i=0;i<30;i++){
        if(A[i].rank==10000)break;
        printf("%c",A[i].cha);
    }
    printf("\n");
}

2009年12月11日星期五

UVa 11045 My T-shirt suits me [Flow]

11045   My T-shirt suit...   poao899   Accepted   C++   0.020   2009-12-12 05:59:59                      .

花了半小時co

不過少打一個括號debug半小時= =

是說同TIOJ 1469 制服發放問題

不過貌似有其他解法= =看TIOJ大家的速度...還有code length

應該是有辦法greedy?

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

//13:04 - 13:31
#include<stdio.h>
#include<string.h>
#define MAX 1000
#define INF 100000
struct arc{
    int j,con;
    arc *topair,*next;
    void set(int to,int c,arc *t,arc *n){
        j=to;con=c;
        topair=t;next=n;
    }
}A[MAX],*N[MAX],*from[MAX];
int arr[INF],t;
struct queue{
    int front,rear,*ar;
    void init(){
        front=rear=0;
        ar=arr;
    }
    int deq(){
        int a=ar[front];
        front=++front%INF;
        return a;
    }
    void enq(int a){
        ar[rear]=a;
        rear=++rear%INF;
    }
}q;
int arcCnt,n,m,max,fa[MAX];
char s[10];
arc* get(){
    return A+arcCnt++;
}
void build(int i,int j,int c){
    arc *p=get(),*q=get(),*r;
    r=N[i];
    N[i]=p;
    p->set(j,c,q,r);
    r=N[j];
    N[j]=q;
    q->set(i,0,p,r);
}
/*
S 0
T MAX-1
size
XXL - XS    201 - 206
*/
main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d\n",&n,&m);
        //Initialize
        arcCnt=max=0;
        for(int i=0;i<MAX;i++){
            A[i].topair=A[i].next=N[i]=NULL;
        }
        // S & T
        n/=6;
        for(int i=201;i<207;i++)
            build(0,i,n);
        //Input
        for(int i=1;i<=m;i++){
            int toSet;
            for(int j=0;j<2;j++){
                scanf("%s",s);
                if(s[0]=='X'){
                    if(s[1]=='X')
                        toSet=201;
                    else if(s[1]=='L')
                        toSet=202;
                    else if(s[1]=='S')
                        toSet=206;
                }
                else{
                    switch(s[0]){
                        case'L':
                            toSet=203;
                            break;
                        case'M':
                            toSet=204;
                            break;
                        case'S':
                            toSet=205;
                            break;
                    }
                }
                build(toSet,i,1);
            }
            build(i,999,1);
        }
        //Max-Flow
        while(1){
            int flow=INF;
            //Initialize
            for(int i=0;i<MAX;i++){
                fa[i]=-1;
                from[i]=NULL;
            }
            q.init();
            q.enq(0);
            //BFS
            while(q.front!=q.rear){
                int now=q.deq();
                for(arc *p=N[now];p;p=p->next){
                    if(p->con > 0 && fa[p->j]==-1){
                        q.enq(p->j);
                        fa[p->j]=now;
                        from[p->j]=p;
                    }
                }
            }
            if(fa[999]==-1)break;
            //flow
            for(int now=999;now;now=fa[now]){
                if(flow>from[now]->con)
                    flow=from[now]->con;
            }
            if(!flow)break;
            for(int now=999;now;now=fa[now]){
                from[now]->con-=flow;
                from[now]->topair->con+=flow;
            }
            max+=flow;
        }
        puts(max==m?"YES":"NO");
    }
}

UVa 567 Risk [Shortest Path]

567   Risk   poao899   Accepted   C++   0.084   2009-12-11 15:33:06                          .

昨天看題目看了十幾分鐘竟然是無腦題=口=

20個點沒有權重的最短路orz

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

#include<stdio.h>
#define INF 1000000
int dist[30][30],cnt,a,b,n;
main(){
    for(int z=1;~scanf("%d",&cnt);z++){
        printf("Test Set #%d\n",z);
        for(int i=0;i<30;i++)
            for(int j=0;j<30;j++)
                dist[i][j]=i==j?0:INF;
        for(int i=1;i<20;i++){
            while(cnt-->0){
                scanf("%d",&n);
                dist[i][n]=dist[n][i]=1;
            }
            scanf("%d",&cnt);
        }
        //Floyd –Warshall
        for(int k=1;k<=20;k++)
            for(int i=1;i<=20;i++)
                for(int j=1;j<=20;j++)
                    if(dist[i][k]+dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k]+dist[k][j];
        for(int i=0;i<cnt;i++){
            scanf("%d%d",&a,&b);
            printf("%2d to %2d:%2d\n",a,b,dist[a][b]);
        }
        puts("");
    }
}

TIOJ 1174 The Shortest Distance

nolonger 896K 478MS G++ 0.29K 2009-12-11 16:03:17 .

唔很像Mearge Sort的作法...

排序後O(n)

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

#include<algo.h>
int a[200000],b[200000],n,m,z;
main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)
		scanf("%d",a+i);
	for(int i=0;i<m;i++)
		scanf("%d",b+i);
	sort(a,a+n);
	sort(b,b+m);
	z=1<<31-1;
	for(int i=0,j=0;i<n&&j<m;a[i]>b[j]?j++:i++)
		z<?=abs(a[i]-b[j]);
	printf("%d\n",z);
}

TIOJ 1061 井字遊戲(TTT) [ 95北市賽 ] [DFS]

poao899    0K    167MS    G++     0.84K     2009-12-11 15:29:25                                           .

DFS + Hash判重(咦好像不是這樣用

是說co了四次QQ

有兩次在DFS時不printf()會跑不起來超詭異

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

#include<stdio.h>
short way[8][3]={
    0,1,2,
    3,4,5,
    6,7,8,
    0,3,6,
    1,4,7,
    2,5,8,
    0,4,8,
    2,4,6,
};
short n,st,cnt[3],a[10],o,x,c;
bool H[19683];
bool hash(){
    int h=0;
    for(int i=0;i<9;i++)
        h=h*3+a[i];
    if(H[h])return 1;
    H[h]=1;return 0;
}
int chk(){
    short x;
    for(int i=0;i<8;i++)
        if((x=a[way[i][0]]) == a[way[i][1]] && a[way[i][1]] == a[way[i][2]] && x)
            return x;
    return 0;
}
void dfs(bool pl){
    int b=0,x=chk();
    if(x){
        if(!hash())
            cnt[x]++;
        return;
    }
    for(int i=0;i<9;i++){
        if(a[i]==0){
            a[i]=pl+1;
            dfs(!pl);
            a[i]=0;
            b=1;
        }
    }
    if(!b && !hash())
        cnt[x]++;
}

main(){
    for(int z=0;z<9;z++){
        c=getchar();
        if(c=='O'){o++;a[z]=1;}
        else if(c=='X'){x++;a[z]=2;}
        else a[z]=0;
    }
    dfs(o>x);
    printf("%hd %hd %hd %hd\n",cnt[0]+cnt[1]+cnt[2],cnt[1],cnt[2],cnt[0]);
}

TIOJ 1042 E.老問題 [ NPSC2003初賽 ] [Flow]

poao899    716K    140MS    G++     1.94K     2009-12-11 11:59:34                             .

Minimum-Cost Maximum Flow.

第一題最小花費最大流>//<

是說相鄰矩陣比相鄰串列好寫多了

一開始WA得莫名重co一次就過了= =

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

#include<stdio.h>
#define MAX 2147483647
#define NODE 300
#define QLEN 1000000
int con[NODE][NODE],cost[NODE][NODE],dist[NODE],from[NODE];
bool inq[NODE];
int arr[QLEN];
struct queue{
    int front,rear,*ar;
    void init(){
        front=rear=0;
        ar=arr;
    }
    int deq(){
        int x=ar[front];
        front=++front%QLEN;
        return x;
    }
    void enq(int a){
        ar[rear]=a;
        rear=++rear%QLEN;
    }
}q;
int n,t,max;
main(){
    while(scanf("%d",&n),n){
        //Initialize
        max=0;
        for(int i=0;i<NODE;i++)
            for(int j=0;j<NODE;j++)
                con[i][j]=cost[i][j]=0;
        for(int i=1;i<=n;i++)
            con[0][i]=con[i+150][NODE-1]=1;
        //Input
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                scanf("%d",&t);
                con[i][j+150]=1;
                cost[i][j+150]=-t;
                cost[j+150][i]=t;
                if(!t)con[i][j+150]=1;
            }
        while(1){
            //Initialize
            q.init();q.enq(0);
            int flow=MAX,now,m=0;
            for(int i=0;i<NODE;i++){
                dist[i]=MAX;inq[i]=0;
                from[i]=-1;
            }
            //SPFA
            dist[0]=0;inq[0]=1;
            while(q.front!=q.rear){
                now=q.deq();
                for(int i=0;i<=NODE;i++){
                    if(con[now][i]>0 && dist[i]>dist[now]+cost[now][i]){
                        dist[i]=dist[now]+cost[now][i];
                        from[i]=now;
                        if(!inq[i]){
                            inq[i]=1;
                            q.enq(i);
                        }
                    }
                }
                inq[now]=0;
            }
            if(from[NODE-1] == -1)break;
            for(now=NODE-1;now;now=from[now]){
                if(flow>con[from[now]][now])
                    flow=con[from[now]][now];
            }
            for(now=NODE-1;now;now=from[now]){
                m+=cost[from[now]][now];
                con[from[now]][now]-=flow;
                con[now][from[now]]+=flow;
            }
            if(m<=0)
                max+=m;
        }
        printf("%d\n",-max);
    }
}

2009年12月10日星期四

TIOJ 1236 工廠生產問題 [ TOI 2006 ] [Flow]

poao899 184K 289MS G++ 1.62K 2009-12-10 16:13:52 .

一樣是Flow =w=

唔MAX一開始調10^9會WA

哪家工廠生產這麼有效率啦（翻桌

是說這題要拆點、沒給測資範圍

然後就沒什麼特別了(?

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

#include<stdio.h>
#define QLEN 1000100
#define MAX 2147483647
#define NMAX 1000
struct arc{
	int j,con;
	arc *next,*topair;
	void set(int to,int c,arc* n,arc* t){
		j=to;con=c;
		next=n;topair=t;
	}
}A[1000000],*N[NMAX],*from[NMAX];
int que[QLEN];
struct queue{
	int front,rear;
	int *ar;
	void init(){
		ar=que;
		front=rear=0;
	}
	void enq(int a){
		ar[rear]=a;
		rear=++rear%QLEN;
	}
	int deq(){
		int x=ar[front];
		front=++front%QLEN;
		return x;
	}
}q;
arc* get(){
	static int cnt=0;
	return A+cnt++;
}
void build(int i,int j,int con){
	arc *p=get(),*q=get(),*r;
	r=N[i];
	N[i]=p;
	p->set(j,con,r,q);
	r=N[j];
	N[j]=q;
	q->set(i,0,r,p);
}
int n,m,a,b,f,max,indeg[NMAX],outdeg[NMAX],fa[NMAX],c;
int bfs(){
	for(int i=0;i<NMAX;i++)
		fa[i]=-1;
	q.init();
	q.enq(0);
	int flow=MAX;
	while(q.front!=q.rear){
		int now=q.deq();
		for(arc *p=N[now];p;p=p->next){
			if(fa[p->j]==-1 && p->con > 0){
				q.enq(p->j);
				fa[p->j]=now;
				from[p->j]=p;
				if(flow > p->con)
					flow=p->con;
			}
		}
	}
	if(fa[999]==-1)return 0;
	return flow;
}
void resi(int flow){
	for(int now=999;now;now=fa[now]){
		from[now]->con-=flow;
		from[now]->topair->con+=flow;
	}
}
main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&c);
		build(i,i+500,c);
	}
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);
		build(a+500,b,MAX);
		indeg[b]++;
		outdeg[a]++;
	}
	for(int i=1;i<=n;i++){
		if(!indeg[i])
			build(0,i,MAX);
		if(!outdeg[i])
			build(i+500,999,MAX);
	}
	while(1){
		f=bfs();
		if(!f)break;
		resi(f);
		max+=f;
	}
	printf("%d\n",max);
}

UVa 820 Internet Bandwidth [Flow]

820 Internet Bandwidth Accepted C++ 0.056 2009-12-10 07:04:16 .

第一題Flow =w=

超基本的Maximum Flow

是說原來大家都寫相鄰矩陣好犯規

相鄰串列有一點不好co QQ

是說被雙向邊表好久QQ

反正就這樣啦ˊˇˋ

唔code在筆電沒辦法貼...

2009年12月8日星期二

TIOJ 1094 C.幼稚國王的獎賞 [DP...?]

poao899 5124K 4656MS G++ 0.45K 2009-12-08 23:34:40 .

過是過了但是這速度...

算了(?

暴力用背包(汗

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

#include<stdio.h>
bool can[1048576];
int last[1048576];
int n,x,max;
void set(int x,int i){
	if(!can[x]){
		can[x]=1;
		last[x]=i;
	}
}
main(){
	while(scanf("%d",&n),n){
		for(int i=0;i<1048576;i++)
			can[i] = last[i] = 0;
		set(0,max=0);
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			for(int j=0;j<1048576;j++)
				if(can[j] && last[j]!=i){
					set(j^x,i);
					if((j^x)>max)
						max=(j^x);
				}
		}
		printf("%d\n",max);
	}
}

TIOJ 1088 [Interactive] 取石頭(二) [Math]

poao899 4K 184MS G++ 0.28K 2009-12-08 15:46:09 .

唔神奇xor

不過石頭堆是1~3我把他當0~2炸了n次orz

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

#include<stdio.h>
#include<1088_stone.h>
int a[3],t,p,x;
main(){
	Initialize(a,a+1,a+2);
	while(1){
		x=a[0]^a[1]^a[2];
		for(int i=0;i<3;i++)
			if(a[i] && (x^a[i])<a[i]){
				Take_Stone(i+1,a[i]-(x^a[i]),&t,&p);
				a[i]=x^a[i];
				a[t-1]-=p;
				break;
			}
	}
}

TIOJ 1045 A.細菌培養 [discretization]

poao899 1520K 515MS G++ 1.37K 2009-12-08 13:58:43 .

離散化暴力。

//如果用二維線段樹複雜度會多lg^2 n耶XD也沒有比較好coˊˋ

你可以假設這個數字小於8*10^18 看成8*10^8是哪招orz

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

//1045

#include<stdio.h>
#include<algorithm>
struct seq{
	int ar[440],cnt;
	int put(int v){
		ar[cnt++]=v;
	}
	void show(){
		for(int i=0;i<cnt;i++)
			printf("%d\n",ar[i]);
		puts("");
	}
	int bs(int val){
		int l=0,r=cnt-1,mid;
		while(l!=r){
			mid=(l+r)/2;
			if(ar[mid]<val)l=mid+1;
			else r=mid;
		}
		return l;
	}
}w,h;
long long val[440][440],n;
int wi[440][2],he[440][2];
main(){
	while(scanf("%d",&n),n){
		//Initialize
		for(int i=0;i<440;i++)
			for(int j=0;j<440;j++)
				val[i][j]=1;
		w.cnt = h.cnt = 0;
		//Input
		w.put(0);w.put(10000);
		h.put(0);h.put(10000);
		for(int i=0;i<n;i++){
			scanf("%d%d%d%d",&wi[i][0],&he[i][0],&wi[i][1],&he[i][1]);
			w.put(wi[i][0]);
			w.put(wi[i][1]);
			h.put(he[i][0]);
			h.put(he[i][1]);
		}
		std::sort(w.ar,w.ar+w.cnt);
		std::sort(h.ar,h.ar+h.cnt);
		for(int i=0;i<n;i++){
			int wl=w.bs(wi[i][0]),wr=w.bs(wi[i][1]),hl=h.bs(he[i][0]),hr=h.bs(he[i][1]);
			for(int j=wl;j<wr;j++)
				for(int k=hl;k<hr;k++)
					val[j][k]*=2;
		}
		//w.show();h.show();
		long long total=0;
		for(int i=0;i<w.cnt-1;i++)
			for(int j=0;j<h.cnt-1;j++)
				total+=(long long)(w.ar[i+1]-w.ar[i])*(h.ar[j+1]-h.ar[j])*val[i][j];
		printf("%I64d\n",total);
	}
}

2009年12月7日星期一

TIOJ 1382 約瑟問題 [segment tree]

poao899 3904K 1718MS G++ 0.80K 2009-12-07 20:09:32 .

線段樹越寫越簡陋=口=

是說poloo5582 3072K 1576MS G++ 0.50K 2009-11-10 22:36:00

小鬼學長超強!!

很好奇怎麼用平衡樹來寫

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

#include<stdio.h>
#define MAX 100010
struct seg{
	seg *lch,*rch;
	int l,r,rest;
	int nth(int);
}s[MAX*2];
int n,pre,now,segCnt;
seg* get(int a,int b){
	seg *p =s+segCnt++;
	p->l=a;p->r=b;p->rest=b-a+1;
	p->lch = p->rch = NULL;
	return p;
}
int seg::nth(int i){
	if(l==r){rest=0;return l;}
	int mid=(l+r)/2,rp;
	if(!lch){
		lch=get(l,mid);
		rch=get(mid+1,r);
	}
	if(lch->rest < i)
		rp=rch->nth(i - lch->rest);
	else
		rp=lch->nth(i);
	if(rp)rest--;
	return rp;
}
main(){
	while(~scanf("%d",&n)){
		//Initialize
		segCnt = 0;pre = 1;
		get(1,n);
		//Input
		for(;n;putchar(--n?32:'\n') , pre=now){
			scanf("%d",&now);
			now = (now+pre-1)%n;
			if(!now)now=n;
			printf("%d",s->nth(now));
		}
	}
}

TIOJ 1272 The Agency [segment tree]

poao899 6496K 511MS G++ 2.10K 2009-12-07 18:51:45 .

DFS + segment tree

唔笨了好久不開心~"~

是說沒被捏就不好想~"~

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

#include<stdio.h>
int stamp[200010],time=1;
int trans[100010][2];
int getint(){
	int g=0,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;
}
struct node{
	node *bro,*son;
	void set(node *p){
		node *q = son;
		son=p;
		p->bro = q;
	}
}N[100010],*s[100010];
struct segment{
	segment *lch,*rch;
	int l,r;
	int change;
	void sneeze(int,int);
	int query(int);
}Seg[400080];
segment* get(int l,int r){
	static int cnt = 1;
	segment* p = Seg+cnt;
	cnt++;
	p->l = l;p->r = r;
	return p;
}
void segment::sneeze(int _l , int _r){
	if(l==_l && r==_r){change++;return;}
	int mid = (l+r)/2;
	if(lch == NULL){
		lch = get(l , mid);
		rch = get(mid+1 , r);
	}
	if(_r<=mid){
		lch->sneeze(_l , _r);
	}else if(_l>mid){
		rch->sneeze(_l , _r);
	}else{
		lch->sneeze(_l , mid);
		rch->sneeze(mid+1 , _r);
	}
}
int segment::query(int i){
	if(!lch)return change;
	int mid = (l+r)/2;
	if(i>mid)return rch->query(i)+change;
	else return lch->query(i)+change;
}
int stack[100010],top=1;
int n,m,a,b;
int main(){
	n=getint();
	m=getint();
	//Input
	for(int i=1;i<=n;i++){
		a=getint();
		while(a--)(N+i)->set(N+getint());
	}
	//DFS
	stack[top]=1;s[top]=(N+1)->son;
	while(top){
		if(!trans[stack[top]][0]){
			stamp[time]=stack[top];
			trans[stack[top]][0]=time++;
		}
		if(s[top]==NULL){
			//printf("%d over top=%d\n",stack[top],top);
			stamp[time]=stack[top];
			trans[stack[top]][1]=time++;
			top--;
		}
		else{
			node *p=s[top];
			s[top]=s[top]->bro;
			top++;
			stack[top]=p-N;
			s[top]=p->son;
		}
	}
	//Initialize
	Seg->l=1;Seg->r=time-1;Seg->change=0;
	//Query
	while(m--){
		a=getint();
		b=getint();
		if(a){
			putchar(((Seg->query(trans[b][0]))&1)+48);
			putchar('\n');
		}else{
			Seg->sneeze(trans[b][0] , trans[b][1]);
		}
	}
}

2009年12月1日星期二

TIOJ 1305 啊嘶起啦集合 [segment tree]

poao899 6372K 417MS G++ 2.62K 2009-12-01 17:43:27 .

離散化 + segment tree

是說是不是用兩個map來離散化頗詭異(?

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

#include<stdio.h>
#include<map>
#include<algorithm>
#define MAX 300000
std::map<int,int> keyToVal;
std::map<int,int> valToKey;
struct segment{
	int  l,r,sub;
	bool inSet;
	segment *seg_l,*seg_r;
}Seg[MAX];
segment* set(int l,int r){
	static int cnt = 1;
	Seg[cnt].l=l;
	Seg[cnt].r=r;
	return Seg+cnt++;
}
bool insert(segment *p,int i){
	int l=p->l,r=p->r;
	if(l==r-1){
		if(! p->inSet){
			p->inSet=1;
			p->sub=1;
			return true;
		}
		return false;
	}
	segment *q;
	int mid = ( l + r + 1 )/2;
	if(mid > i){
		if(p->seg_l==NULL){
			q = set(l,mid);
			p->seg_l=q;
		}
		q=p->seg_l;
	}
	else{
		if(p->seg_r==NULL){
			q = set(mid,r);
			p->seg_r=q;
		}
		q=p->seg_r;
	}
	if(insert(q,i)){
		p->sub++;
		return true;
	}
	return false;
}
bool remove(segment *p,int i){
	int l=p->l,r=p->r;
	if(l==r-1){
		if(p->inSet){
			p->inSet=0;
			p->sub=0;
			return true;
		}
		return false;
	}
	segment *q;
	int mid = ( l + r + 1 )/2;
	if(mid > i){
		if(p->seg_l==NULL)
			return false;
		q=p->seg_l;
	}
	else{
		if(p->seg_r==NULL)
			return false;
		q=p->seg_r;
	}
	if(remove(q,i)){
		p->sub--;
		return true;
	}
	return false;
}
int ask(segment *p,int i){
	int l=p->l,r=p->r;
	if(l==r-1){return l;}
	if(p->seg_l!=NULL){
		if(p->seg_l->sub>=i){
			return ask(p->seg_l,i);
		}
	}
	if(p->seg_r!=NULL){
		if(p->seg_l!=NULL){
			return ask(p->seg_r,i-p->seg_l->sub);
		}
		return ask(p->seg_r,i);
	}
}
void get(char &c,int &n){
	c=getchar();
	int s=1;n=0;
	char g=getchar();
	while((g<'0'||g>'9') && g!='-'){
		if(g=='\n')return;
		g=getchar();
	}
	if(g=='-')g=getchar(),s=-1;
	while(g>='0'&&g<='9'){
		n=n*10+g-48;
		g=getchar();
	}
	n*=s;
}
char com[MAX];
int num[MAX];
int comCnt,keyCnt;
int dsc[MAX];
int kCnt=1;
int main(){
	while(1){
		get(com[comCnt],num[comCnt]);
		if(com[comCnt]=='e')break;
		if(com[comCnt]!='a'){
			dsc[keyCnt]=num[comCnt];
			keyCnt++;
		}
		comCnt++;
	}
	std::sort(dsc,dsc+keyCnt);
	for(int i=0;i<keyCnt;i++){
		if(valToKey[dsc[i]]==0){
			valToKey[dsc[i]]=kCnt;
			keyToVal[kCnt]=dsc[i];
			kCnt++;
		}
	}
	Seg->sub=0;
	Seg->l=1;
	Seg->r=kCnt;
	for(int i=0;i<comCnt;i++){
		switch(com[i]){
			case'a':
				if(num[i]<=0 || num[i]>Seg->sub)
					puts("error");
				else printf("%d\n" ,keyToVal[ask(Seg,num[i])]);
				break;
			case'i':
				insert (Seg,valToKey[num[i]]);
				break;
			case'r':
				remove(Seg,valToKey[num[i]]);
				break;
		}
	}
}

訂閱：文章 (Atom)

2009年12月24日 星期四

2009年12月21日 星期一

2009年12月18日 星期五

2009年12月16日 星期三

2009年12月14日 星期一

2009年12月12日 星期六

2009年12月11日 星期五

2009年12月10日 星期四

2009年12月8日 星期二

2009年12月7日 星期一

2009年12月1日 星期二