A Coding E. Coli: 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;
		}
	}
}

2009年11月21日星期六

TIOJ 1256 砲打皮皮4 [Graph]

poao899 1900K 166MS G++ 1.72K 2009-11-19 23:06:02 .

好慚愧QQ

這題只是複製TIOJ 1137 4.收費站設置問題的code當初只想用分帳玩一下開錯就AC了

蚯蚓：不是很明顯是AP點嗎

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

#include<stdio.h>
#include<algorithm>
#define MAX 200200
#define MAXV 10010
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 Edge{
	int j;
	Edge *next;
}E[MAX],*V[MAXV];
int edgeCnt,APCnt;
int dateBack[MAXV];
int AP[MAXV],ttime;
int visited[MAXV];
int t,n,m,a,b;
void setEdge(int i,int j){
	Edge *p,*now;
	p=V[i];
	V[i]=&E[++edgeCnt];
	E[edgeCnt].j=j;
	E[edgeCnt].next=p;
	p=V[j];
	V[j]=&E[++edgeCnt];
	E[edgeCnt].j=i;
	E[edgeCnt].next=p;
}
int FindAP(int now,int depth){
	Edge *p=V[now];
	int next,count=0;
	bool isAP=0;
	visited[now]=++ttime;
	dateBack[now]=2147483647;
	while(p!=NULL){
		next=p->j;
		if(!visited[next]){
			count++;
			int son=FindAP(next,depth+1);
			if(son>=visited[now]){
				dateBack[now]=son;
				if(depth){
					isAP=1;
				}
			}
			dateBack[now]<?=son;
		}
		else{
			dateBack[now]<?=visited[next];
		}
		p=p->next;
	}
	if(depth==0&&count>1 || isAP){
		AP[APCnt++]=now;
	}
	return dateBack[now];
}
int caseCnt;
main(){
	while(scanf("%d%d",&n,&m),n+m){
		//Initialize
		for(int i=0;i<MAXV;i++){
			visited[i]=0;
			V[i]=NULL;
		}
		edgeCnt=-1;APCnt=0;ttime=0;
		//Construct a graph
		for(int i=0;i<m;i++){
			a=getint();
			b=getint();
			setEdge(a,b);
		}
		//Find AP
		for(int i=1;i<=n;i++)
			if(!visited[i])
				FindAP(i,0);
		//Output
		std::sort(AP,AP+APCnt);
		printf("Case #%d:",++caseCnt);
		printf("%d ",APCnt);
		if(!APCnt)puts("0");
		for(int i=0;i<APCnt;i++,putchar(i==APCnt?'\n':32)){
			printf("%d",AP[i]);
		}
	}
}

TIOJ 1432 骨牌遊戲 [Binary Search]

poao899 4K 15MS G++ 0.53K 2009-11-19 22:55:22 .

純粹為了練coding速度(咦

對答案二分搜。

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

#include<stdio.h>
int n,w,s[1000000],val;
bool test(int max){
	int cost=0,sum=0;
	for(int i=0;i<n;i++){
		sum+=s[i];
		if(sum>max){
			sum=s[i];
			cost++;
			if(cost>w)return 0;
		}
	}
	return 1;
}
main(){
	while(scanf("%d%d",&n,&w),n+w){
		int l=0,r=0;
		for(int i=0;i<n;i++){
			scanf("%d",s+i);
			if(s[i]>l)l=s[i];
			r+=s[i];
		}
		while(l!=r){
			int mid=(l+r)/2;
			if(!test(mid))
				l=mid+1;
			else r=mid;
		}
		printf("%d\n",l);
	}
}

TIOJ 1241 倍因道 Factor and Points [Sieve...?]

poao899 -4K 61MS G++ 0.44K 2009-11-19 17:11:34 .

還是應該算Greedy(咦

Greedy檢查每個數適合當因數還是倍數

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

#include<stdio.h>
#include<algorithm>
int fac[2001];
int n,t,total;
main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		total=0;
		for(int i=0;i<2001;i++)
			fac[i]=0;
		for(int i=1;i<=n;i++){
			int m=n/i-1;
			if(m>fac[i])
				for(int j=i+i;j<=n;j+=i)
					fac[j]++;
			else total+=fac[i];
		}
		printf("%d\n",total);
	}
}

TIOJ 1582 A TRIVIAL physical problem

poao899 0K 150MS G++ 1.18K 2009-11-19 16:57:37 .

排序大賽最陰險的一題(汗

超糟糕的輸入本來想練習scanf的不過最後還是gets()進來慢慢處理

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

#include<stdio.h>
#include<algorithm>
struct mul{
	int base,exp;
	bool operator<(const mul &b)const{
		return exp>b.exp||exp==b.exp&&base>b.base;
	}
}Mu[1000];
int cnt;
void set(int b,int e){
	mul *p=&Mu[cnt];
	p->base=b;
	p->exp=e;
}
char in[10000];
main(){
	gets(in);
	int base,exp,s;
	for(int i=0;in[i];cnt++){
		base=0;
		exp=0;
		s=1;
		if(in[i]=='-'){s=-1;i++;}
		if(in[i]=='+'){i++;}
		if(in[i]=='x'){base=1;}
		for(;in[i]!='x'&&in[i]!='-'&&in[i]!='+'&&in[i];i++){
			base=base*10+in[i]-48;
		}
		base*=s;
		if(in[i]==0)break;
		if(in[i]!='x'){cnt--;continue;}
		i++;
		if(in[i]!='^'){set(base,1);continue;}
		i++;
		s=1;
		if(in[i]=='-'){s=-1;i++;}
		if(in[i]=='+')i++;
		for(;in[i]!='-'&&in[i]!='+'&&in[i];i++){
			exp=exp*10+in[i]-48;
		}
		exp*=s;
		//printf("<base%d exp%d>\n",base,exp);
		if(!exp){cnt--;continue;}
		set(base,exp);
	}
	if(!cnt)putchar('0');
	else{
		std::sort(Mu,Mu+cnt);
		for(int i=0;i<cnt;i++){
			int b=Mu[i].base;
			int e=Mu[i].exp;
			if(b*e>0&&i)putchar('+');
			printf("%d",b*e);
			if(e-1!=0){
				putchar('x');
				if(e-1!=1){
					putchar('^');
					printf("%d",e-1);
				}
			}
		}
	}
	puts("");
}

TIOJ 1584 Doraemon and Dorayaki [sort]

poao899 1452K 46MS G++ 1.07K 2009-11-19 11:26:57 .

Manhattan Distance.[曼哈頓距離(?]

然後注意如果剛好0吃到也不行

(是要保留一點力氣吃嗎orz)

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

#include<stdio.h>
#include<algorithm>
#define abs(x) ((x)>0?(x):-(x))
struct node{
	int x,y;
	int dis;
	int dist(node &b){
		return abs(x-b.x)+abs(y-b.y);
	}
	bool operator<(const node &b)const{
		return dis<b.dis;
	}
	void set(int i,int j){
		x=i;y=j;
	}
}dora,yaki[1000010];
int h,w,hp,g,yakiCnt,c,t;
main(){
	scanf("%d",&t);
	while(t--){
	yakiCnt=0;
	scanf("%d%d%d%d\n",&h,&w,&hp,&g);
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			c=getchar();
			switch(c){
				case 'D':
					dora.set(i,j);
				break;
				case 'e':
					yaki[yakiCnt++].set(i,j);
				break;
			}
		}
		getchar();
	}
	for(int i=0;i<yakiCnt;i++)
		yaki[i].dis=dora.dist(yaki[i]);

	std::sort(yaki,yaki+yakiCnt);
	int i;
	for(i=0;i<yakiCnt;i++){
		if(hp-yaki[i].dis>0){
			hp-=yaki[i].dis;
			hp+=g;
			if(hp-yaki[i].dis>0)
				hp-=yaki[i].dis;
			else{
				//printf("%d\n",i);
				break;
			}
		}
		else{
			//printf("%d\n",i);
			break;
		}
	}
	printf("%d\n",i);
}
}

TIOJ 1581 KUKUKU Game [DFS]

poao899 -8K 150MS G++ 1.75K 2009-11-18 20:36:55 .

總算不是排序了(咦

這題比TIOJ 1025 數獨問題 ( 96校內賽 prob 2 ) 還陰多了QQ

會有一開始不合法、甚至0~4以外的數字出現

雖然如果吃過RE不難想到xD

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

#include<stdio.h>
int sudo[4][4];
int cnt;
void dfs(int i,int j){
	//printf("%d %d\n",i,j);
	if(i==4){
		cnt++;
		if(cnt!=1)return;
		for(int k=0;k<4;k++){
			for(int l=0;l<4;l++)
				putchar(sudo[k][l]+48);
			puts("");
		}
		puts("");
		return;
	}
	bool find=0;
	for(;i<4;i++){
		for(;j<4;j++){
			//printf("%d %d:%d\n",i,j,sudo[i][j]);
			if(sudo[i][j]==0){
				find=1;
				break;
			}
		}
		if(find)break;
		j=0;
	}
	if(i==4){
		dfs(i,j);
		return;
	}
	bool used[5]={};
	for(int k=0;k<4;k++){
		used[sudo[k][j]]=1;
		used[sudo[i][k]]=1;
	}
	for(int k=0;k<2;k++)
		for(int l=0;l<2;l++)
			used[sudo[k+i/2*2][l+j/2*2]]=1;
	for(int k=1;k<5;k++){
		//printf("%d %d:%d\n",i,j,k);
		if(!used[k]){
			//printf("%d %d:%d\n",i,j,k);
			sudo[i][j]=k;
			dfs(i,j);
		}
	}
	sudo[i][j]=0;
}
main(){
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++){
			scanf("%d",&sudo[i][j]);
			if(sudo[i][j]>4||sudo[i][j]<0){
				puts("I can not solve!!");
				return 0;
			}
		}
	bool used[5]={};
	for(int i=0;i<4;i++){
		for(int j=0;j<5;j++)used[j]=0;
		for(int j=0;j<4;j++){
			int c=sudo[i][j];
			if(c&&used[c]){
				puts("I can not solve!!");
				return 0;
			}
			used[c]=1;
		}
		for(int j=0;j<5;j++)used[j]=0;
		for(int j=0;j<4;j++){
			int c=sudo[j][i];
			if(c&&used[c]){
				puts("I can not solve!!");
				return 0;
			}
			used[c]=1;
		}
	}
	for(int i=0;i<3;i+=2)
		for(int j=0;j<3;j+=2){
			for(int k=0;k<5;k++)used[k]=0;
			for(int k=0;k<2;k++)
				for(int l=0;l<2;l++){
					int c=sudo[i+k][j+l];
					if(c&&used[c]){
						puts("I can not solve!!");
						return 0;
					}
					used[c]=1;
				}
		}
	dfs(0,0);
	if(cnt)printf("We have %d way(s) to solve it!!\n",cnt);
	else puts("I can not solve!!");
}

TIOJ 1583 SLIM KING [sort]

poao899 0K 182MS G++ 0.54K 2009-11-18 19:46:38 .

排序大賽pB 當然還是排序orz

反正只要排前十大那就Insertion比較快xD

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

#include<stdio.h>
struct people{
	char name[50];
	int kg,cm;
	double bmi;
	void get(){
		scanf("%s%d%d",name,&kg,&cm);
		bmi=kg/((double)cm/100*(double)cm/100);
	}
	bool operator<(people &b){
		return bmi<b.bmi;
	}
}s[11],in,sw;
void puts(people &a){
	puts(a.name);
	//printf("%lf\n",a.bmi);
}
int n;
main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		in.get();
		int j;
		for(j=0;j<i&&j<11;j++){
			if(s[j]<in){
				sw=s[j];
				s[j]=in;
				in=sw;
			}
		}
		s[j]=in;
	}
	for(int i=0;i<n&&i<10;i++)
		puts(s[i]);
}

TIOJ 1585 Strange Sorting [sort]

poao899 1100K 46MS G++ 0.69K 2009-11-18 19:34:59 .

排序大賽(誤)的最後一題

當然還是排序XD

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

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define abs(a) (a>0?a:-a)
struct String{
	char s[1100];
	int len;
	bool operator<(const String &b)const{
		int min=len<b.len?len:b.len;
		for(int i=0;i<min;i++){
			if(s[i]!=b.s[i]){
				int ra=-abs((s[i]-'a'-13));
				int rb=-abs((b.s[i]-'a'-13));
				return ra==rb?s[i]>b.s[i]:ra<rb;
			}
		}
		if(len>b.len)return 0;
		else return 1;
	}
}S[1100];
int n;
main(){
	//for(int i='a';i<='z';i++)
	//	printf("%c:%d\n",i,-abs((i-'a'-13)));
	while(~scanf("%d",&n)){
		getchar();
		for(int i=0;i<n;i++){
			gets(S[i].s);
			S[i].len=strlen(S[i].s);
		}
		std::sort(S,S+n);
		for(int i=0;i<n;i++)
			puts(S[i].s);
	}
}

TIOJ 1388 好強的史來姆 [DP]

poao899 28K 906MS G++ 0.52K 2009-11-18 09:09:04 .

跟正直DE(矩陣乘法最小花費)一樣類型

不過卡得頗緊|||

O(n^3)但是得壓常數Q

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

//1388

#include<stdio.h>
long long dp[100][100];
int slime[100],n;
main(){
 while(~scanf("%d",&n)){
  for(int i=0;i<n;i++){
   scanf("%d",slime+i);
   for(int j=0;j<n;j++)
    dp[i][j]=i==j?slime[i]:0;
  }
  for(int j=2;j<=n;j++)
   for(int i=0;i+j<=n;i++){
    int z=i+j-1;
    for(int k=i;k<z;k++){
     dp[i][z]>?=(j&1)?dp[i][k]*dp[k+1][z]:dp[i][k]+dp[k+1][z];
    }
   }
  printf("%I64d\n",dp[0][n-1]);
 }
}

TIOJ 1577 萬用字元（wildcard） ( 97北市賽 prob 2 )

poao899 -16K 1763MS G++ 0.48K 2009-11-17 11:16:49 .

暴力會過，不過聽說可以Greedyˊˋ

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

#include<stdio.h>
#include<string.h>
char find[30],in[30];
int flen,len;
bool chk(int i,int j){
	//printf("%d %d \n",i,j);
	if(i==flen&&j==len)return 1;
	if(find[i]=='$'){
		for(int k=j;k<=len;k++)
			if(chk(i+1,k))
				return 1;
		return 0;
	}
	if(i==flen||j==len)return 0;
	if(find[i]==in[j])
		return chk(i+1,j+1);
	return 0;
}
main(){
	gets(find);
	flen=strlen(find);
	//printf("%d\n",flen);
	while(gets(in)){
		len=strlen(in);
		if(chk(0,0))
			puts(in);
	}

TIOJ 1580 火星圍棋（go） ( 97北市賽 prob 5 )

poao899 44K 123MS G++ 2.31K 2009-11-17 10:51:02 .

當年噁爆的防破台題|||

凸包+Graph= =

被捏很大才寫得出來囧

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

//go ( prob 5 ) Convex Hull + Floyd Warshall

#include<stdio.h>
#include<algorithm>
struct node{
	int x,y;
	bool outPoly;
	bool operator<(const node &b)const{
		return x==b.x?y<b.y:x<b.x;
	}
}R[101],B[101];
int r,b;
struct edge{
	int i,j;
	edge *next;
}E[20000],*V[101];
int dis[101][101];
int edgeCnt;
int cross(node p,node a,node b){
	a.x-=p.x;
	a.y-=p.y;
	b.x-=p.x;
	b.y-=p.y;
	//printf("cross %d\n",a.x*b.y - a.y*b.x);
	return a.x*b.y - a.y*b.x;
}
void test(int a,int b){
	//printf("%d %d\n",a,b);
	for(int i=0;i<r;i++)
		if(!R[i].outPoly)
			if(cross(B[a],B[b],R[i])>0)
				return;
	edge *p=&E[edgeCnt++];
	p->i=a;
	p->j=b;
	edge *q=V[a];
	V[a]=p;
	p->next=q;
	dis[a][b]=1;
	//printf("construct!!\n");
}
int stack[2000],top;
main(){
	//Initialize
	edgeCnt=0;
	top=0;
	for(int i=0;i<101;i++)
		for(int j=0;j<101;j++)
			dis[i][j]=100000;
	//Input
	scanf("%d%d",&b,&r);
	for(int i=0;i<b;i++)
		scanf("%d%d",&B[i].x,&B[i].y);
	for(int i=0;i<r;i++){
		scanf("%d%d",&R[i].x,&R[i].y);
		R[i].outPoly=0;
	}
	//Convex Hull
	std::sort(B,B+b);
	stack[top++]=0;
	stack[top]=1;
	for(int i=2;i<b;i++){
		while(top>0&&cross(B[stack[top-1]] , B[stack[top]] , B[i])>=0)
			top--;
		top++;
		stack[top]=i;
	}
	int nTop=top;
	for(int i=b-2;i>=0;i--){
		while(top>nTop&&cross(B[stack[top-1]] , B[stack[top]] , B[i])>=0)
			top--;
		top++;
		stack[top]=i;
	}
	//printf("nTop %d %d\n",nTop,top);
	//for(int i=0;i<=top;i++)
		//printf("%d %d\n",B[stack[i]].x,B[stack[i]].y);
	//InPoly
	int c=0;
	for(int i=0;i<r;i++){
		int dir=cross(B[stack[0]],B[stack[1]],R[i])>0?1:-1;
		for(int j=2;j<=top;j++)
			if(dir*(cross(B[stack[j-1]],B[stack[j]],R[i]))<0){
				R[i].outPoly=1;
				c++;
				break;
		}
		//printf("%d %d Outpoly?%d\n",R[i].x,R[i].y,R[i].outPoly);
	}
	if(c==r){printf("%d\n",r*111);return 0;}
	//Construct
	for(int i=0;i<b;i++){
		//printf("%d %d\n",B[i].x,B[i].y);
		for(int j=0;j<b;j++)
			if(i!=j)
				test(i,j);
	}
	//Floyd Warshall
	for(int k=0;k<b;k++)
		for(int i=0;i<b;i++)
			for(int j=0;j<b;j++)
				if(dis[i][k]+dis[k][j]<dis[i][j])
					dis[i][j]=dis[i][k]+dis[k][j];
	//Output
	int cnt=0,minCycle=100000;
	for(int i=0;i<r;i++)
		if(R[i].outPoly)
			cnt++;
	for(int i=0;i<b;i++)
		minCycle<?=dis[i][i];
	printf("%d\n",cnt*111+minCycle*20);

}

TIOJ 1578 調和三角（triangle） ( 97北市賽 prob 3 )

poao899 -8K 75MS G++ 0.23K 2009-11-17 09:05:00 .

學長：用Math竟然沒有比DP快|||

(1<=r,c<=28)

所以測資應該大一點取mod或大數(誤

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

#include<stdio.h>
int dp(int r,int c){
	if(r==c||c==1)return r;
	else{
		int a=dp(r-1,c-1);
		int b=dp(r,c-1);
		return (int)((long long)b*a/(b-a));
	}
}
main(){
	int r,c;
	scanf("%d%d",&r,&c);
	printf("%d\n",dp(r,c));
}

TIOJ 1576 餅乾製作（cookie） ( 97北市賽 prob 1 )

poao899 -8K 75MS G++ 0.28K 2009-11-17 08:59:09 .

暴力O(n)枚舉

聽說O(n^3)在北市賽會過orz?

#include<cstdio>
int a,b,c,d,s1,s2,s3,t,m1,m2,m3,max;
main(){
	scanf("%d%d%d%d",&a,&b,&c,&d);
	for(int i=0;i<=b;i++){
		s2=i<?a;
		s1=a-s2<?c;
		s3=b-s2<?d;
		t=s1*80+s2*100+s3*60;
		if(t>max){
			m1=s1;m2=s2;m3=s3;max=t;
		}
	}
	printf("%d %d %d\n%d\n",m1,m2,m3,max);
}

TIOJ 1212 圖論之最小圈測試

poao899 1124K 8531MS G++ 0.94K 2009-11-17 08:50:50 .

應該有很多方法可以加速不過先算了xD

Floyd-Warshall掃過去O(n^3)就過了囧

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

#include<stdio.h>
#define INF 50000
#define MV 501
#define ME 250100
int getint(){
	int g=0,c=getchar();
	while(c=='\n'||c==32||c==9)c=getchar();
	while(c>='0'&&c<='9'){
		g=g*10+c-48;
		c=getchar();
	}
	return g;
}
int n,m,dis[MV][MV],min;
struct edge{
	int j;
	edge *next;
}E[ME],*V[MV];
void set(edge *p){
	int i=getint();
	p->j=getint();
	edge *q=V[i];
	V[i]=p;
	p->next=q;
	dis[i][p->j]=1;
}
main(){
	while(1){
		n=getint();
		m=getint();
		if(!n&&!m)break;
		//Initialize
		min=INF;
		for(int i=0;i<MV;i++)
			for(int j=0;j<MV;j++)
				dis[i][j]=INF;
		//Construct
		for(int i=0;i<m;i++)
			set(E+i);
		//Floyd Warshall
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++)
					if(dis[i][k]+dis[k][j]<dis[i][j])
						dis[i][j]=dis[i][k]+dis[k][j];
		//Cycle
		for(int i=1;i<=n;i++)
			if(dis[i][i]<min)
				min=dis[i][i];
		if(min!=INF)printf("%d\n",min);
		else puts("0");
	}
}

2009年11月13日星期五

TIOJ 1122 最大子矩陣 ( 93北市賽 prob 3 )

poao899   -8K   31MS   G++    0.76K    2009-11-14 01:02:26                                 .

很直觀的O(n^3)DP...

是說小乃：O(n^6)爆搜也會過啦

不過DP co起來美觀一點點ˊˇˋ

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

//93 prob 3

#include<stdio.h>
int matrix[22][22];
int sum[22][22],pre,max,n;
main(){
    while(~scanf("%d%d",&n,&matrix[1][1])){
        max=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(j==1){
                    if(i!=1)matrix[i][j]=matrix[1][1]+i;
                }
                else{
                    matrix[i][j]=(matrix[i][j-1]*17)%103;
                    if((i+j)%2)matrix[i][j]=-matrix[i][j];
                }
                sum[i][j]=sum[i-1][j]+matrix[i][j];
            }
        }
        for(int top=0;top<n;top++){
            for(int but=top+1;but<=n;but++){
                pre=0;
                for(int i=1;i<=n;i++){
                    if(pre<0){
                        pre=sum[but][i]-sum[top][i];
                        max>?=pre;
                    }
                    else{
                        pre+=sum[but][i]-sum[top][i];
                        max>?=pre;
                    }
                }
            }
        }
        printf("%d\n",max);
    }
}

TIOJ 1025 數獨問題 ( 96校內賽 prob 2 )

poao899   -8K   122MS   G++    0.92K    2009-11-13 22:38:26                                   .

感謝小可魚>//////////<

唔暴力DFS也沒有特別剪枝

絕對是因為忘了數獨怎麼拼才取這種變數名稱(?

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

#include<stdio.h>
int surwdkgo[9][9],cnt;
void dfs(int i,int j){
    int ni=i,nj=j;
    if(ni==8&&nj==8){
        cnt++;
        for(int p=0;p<9;p++)
            for(int q=0;q<9;q++,putchar(q==9?'\n':32))
                printf("%d",surwdkgo[p][q]);
        puts("");
        return;
    }
    bool can=0;
    for(;ni<9&&!can;ni++){
        for(;nj<9&&!can;nj++){
            if(surwdkgo[ni][nj]==0)can=1;
            if(can)break;
        }
        if(can)break;
        nj=0;
    }
    if(!can){
        dfs(8,8);
        return;
    }
    bool used[10]={0};
    for(int k=0;k<9;k++){
        used[surwdkgo[k][nj]]=1;
        used[surwdkgo[ni][k]]=1;
    }
    for(int p=0;p<3;p++)
        for(int q=0;q<3;q++)
            used[surwdkgo[p+(ni/3*3)][q+(nj/3*3)]]=1;
    for(int k=1;k<10;k++){
        if(!used[k]){
            surwdkgo[ni][nj]=k;
            dfs(ni,nj);
        }
    }
    surwdkgo[ni][nj]=0;
}
main(){
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++){
            if(scanf("%d",&surwdkgo[i][j])==EOF)return 0;
        }
    dfs(0,0);
    printf("there are a total of %d solution(s).\n",cnt);
}

我要引用

我要回應

儲存至「書籤」

TIOJ 1491 G.丁丁共和國 ( NPSC 2007 )

poao899   580K   15MS   G++    1.41K    2009-11-13 15:45:31                                 .

字串處理 + 最遠距離點對

唔順便練一下map XD 比想像中的好用太多了orz

之前寫過兩次DFS這次改寫樹型DP

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

//1491
//Tree DP + map

#include<stdio.h>
#include<map>
#include<string.h>
struct name{
    char n[200];
    bool operator<(const name &b)const{
        return strcmp(n,b.n)>0;
    }
}c1,c2;
struct edge{
    int i,j;
    edge *next;
}E[6000],*V[3000];
int eCnt;
void set(int i,int j){
    edge *p;
    E[eCnt].i=i;
    E[eCnt].j=j;
    p=V[i];
    V[i]=&E[eCnt];
    E[eCnt].next=p;
    eCnt++;
    E[eCnt].i=j;
    E[eCnt].j=i;
    p=V[j];
    V[j]=&E[eCnt];
    E[eCnt].next=p;
    eCnt++;
}
int DP[3000];
int k,n,cnt,maxLen;
bool visited[3000];
int treeDP(int now){
    visited[now]=1;
    if(!DP[now]){
        int max=0,max2=0,n;
        edge *p=V[now];
        while(p!=NULL){
            if(visited[p->j]==0){
                //printf("now%d son %d\n",now,p->j);
                n=treeDP(p->j)+1;
                if(n>max){
                    max2=max;
                    max=n;
                }
                else if(n>max2){
                    max2=n;
                }
            }
            p=p->next;
        }
        maxLen>?=max+max2;
        DP[now]=max;
        //printf("DP%d %d\n",now,DP[now]);
    }
    return DP[now];
}
main(){
    scanf("%d",&k);
    while(k--){
        //Initialize
        std::map<name,int> city;
        scanf("%d",&n);
        maxLen=0;
        for(int i=0;i<3000;i++){
            DP[i]=0;
            V[i]=NULL;
            visited[i]=0;
        }
        eCnt=0;
        cnt=1;
        //Input
        while(1){
            scanf("%s%s",c1.n,c2.n);
            if(!strcmp(c1.n,"=") && !strcmp(c2.n,"="))break;
            int n1=city[c1],n2=city[c2];
            if(n1==0)n1=city[c1]=cnt++;
            if(n2==0)n2=city[c2]=cnt++;
            set(n1,n2);
        }
        treeDP(1);
        printf("%d\n",maxLen);
    }
}

TIOJ 1107 繁複的二元樹

poao899   15672K   203MS   G++    0.62K    2009-11-13 14:42:42                                     .

唔卡特蘭數

不過不知道這個遞迴式怎麼證明

本來想寫矩陣乘法

是說重載運算子真的這麼慢嗎@@

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

//1107 Catalan Number

#include<stdio.h>
struct num{
    double real;
    int exp;
    num operator*(int x){
        num t=*this;
        t.real*=x;
        while(t.real>10){
            t.real/=10;
            t.exp++;
        }
        return t;
    }
    num operator/(int x){
        num t=*this;
        t.real/=x;
        while(t.real<1){
            t.real*=10;
            t.exp--;
        }
        return t;
    }
    void set(int x){
        real=x;
        while(real>10){
            real/=10;
            exp++;
        }
    }
}Cat[1000010];
int n;
main(){
    num *cat=Cat;
    cat[0].set(1);
    for(int i=1;i<1000010;i++){
        cat[i]=(cat[i-1]*(4*i-2))/(i+1);
    }
    while(scanf("%d",&n),n){
        printf("%.3lfE+%d\n",cat[n].real,cat[n].exp);
    }
}

2009年11月12日星期四

TIOJ 1162 5.小氣又愛現的老薑

poao899   72K   31MS   G++   1.32K    2009-11-12 23:36:19                                        .

唔囧純粹MST

本來想要鍊map不過看起來挑錯題了囧

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

//1162 MST + map

#include<stdio.h>
#include<algorithm>
char city[60][40];
struct road{
    char name[40];
    int i,j,len,order;
    bool use;
    void set(int o){
        order=o;
        scanf("%s%d%d%d",name,&i,&j,&len);
        use=0;
    }
    bool operator<(const road &b)const{
        return len==b.len?order<b.order:len<b.len;
    }
}E[3000];
bool cmp(road a,road b){
    return a.order<b.order;
}
int n,root[60],m,edgeAdded,total;
int find(int a){
    return a==root[a]?a:root[a]=find(root[a]);
}
main(){
    while(scanf("%d",&n),n){
        //Initialize
        for(int i=0;i<60;i++){
            root[i]=i;
        }
        edgeAdded=0;total=0;
        //Input CityName
        for(int i=0;i<n;i++)
            scanf("%s",city[i]);
        //Input Edge
        scanf("%d",&m);
        for(int i=0;i<m;i++)
            E[i].set(i);
        scanf("%*s");
        //MST
        std::sort(E,E+m);
        for(int i=0;i<m&&edgeAdded<n-1;i++){
            int ra=find(E[i].i),rb=find(E[i].j);
            if(ra!=rb){
                E[i].use=1;
                edgeAdded++;
                root[ra]=rb;
                total+=E[i].len;
            }
        }
        //Output
        int cnt=1;
        std::sort(E,E+m,cmp);
        for(int i=0;i<m;i++)
            if(E[i].use)
                printf("#%d Road is named %s, connect %s and %s,length=%d\n",cnt++,E[i].name,city[E[i].i<?E[i].j],city[E[i].i>?E[i].j],E[i].len);

        printf("Jiang will spend %d TMTdollars.\n",total*100);
    }
}

TIOJ 1384 抵抗異形軍

poao899 1548K 686MS G++ 0.66K 2009-11-12 15:24:01 .

題目敘述不太好懂Q

二維的LIS

不過二分搜竟然寫炸=口=

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

//1384

#include<stdio.h>
#include<algorithm>
struct ship{
	int t,h;
	bool operator<(const ship &b)const{
		return t==b.t?h<b.h:t<b.t;
	}
}S[100050],leng[100050];
int n;
main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d",&S[i].t,&S[i].h);
	std::sort(S,S+n);
	int len=0;
	
	for(int i=0;i<n;i++){
		if(S[i].h >= leng[len].h){
			len++;
			leng[len]=S[i];
			continue;
		}
		int l=0,r=len;
		while(l!=r){
			int mid=(l+r)/2;
			if(leng[mid].h <= S[i].h)
				l=mid+1;
			else
				r=mid;
		}
		leng[l]=S[i];
	}
	printf("%d\n",n-len);
}

訂閱：文章 (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日 星期二

2009年11月21日 星期六

2009年11月13日 星期五

2009年11月12日 星期四