A Coding E. Coli

2010年3月30日星期二

TIOJ 1244 序列問題 Sequences [DP]

poao899   28K   4840MS   G++    0.36K    2010-03-31 02:50:18                                                    .

頗有趣的DP。

雷:

狀態存法   dp[n大小][該序列尾數]   但是這樣是10^8記憶體會爆炸

所以滾動。

另外是%100000007所以小心溢位。

轉移方式: dp[i-1][k] + 結尾k or k+1    以及開頭+1~k

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

#include<stdio.h>
#define MODE 100000007
int dp[10010], n, t;
long long tmp;
int main(){
    scanf("%d", &n);
    dp[1]= 1;
    for(int i=2; i<=n; i++){
        for(int j=i; j>0; j--){
            dp[j+1]+= dp[j];
            dp[j+1]%= MODE;
            tmp= (long long)dp[j]*j;
            dp[j]= (int)(tmp%MODE);
        }
    }
    for(int i=1; i<=n; i++){
        t+= dp[i];
        t%= MODE;
    }
    printf("%d\n", t);
}

POI - PA 2006 Crayfish (精神+翻譯)

沒co出來的有趣圖論 .

Round 4的題目好有趣但是好難orz

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

翻譯

給你一張有向圖，n<=10^4個頂點，m<=10^5條邊

有些邊是特殊的邊。

現在假設我拿i為起點，一開始只能逆的走(i.e. a->b的邊只能從b走到a)

然後每經過一次特殊邊就得換方向(正走-> 逆走反之亦然)

問你對於每個點的val值，val值定義為從該點出發並要回到該點最多能經過多少其他的點

Input:

Output:

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

雷:

把除了特殊的邊以外的正向圖及反向圖皆分別建出來，

每一條特殊的邊ex: a -> b

那麼就會從正向圖的a和反向圖的b做雙向邊

建完圖後SCC, 判重(同時走過一個點的正向跟反向)

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

POI - PA 2007 Encyclopedia [B]

30-03-10   11:10     Encyclopedia [B]     OK        10                                                           .

頗白癡的題目我說= =

說實話有點不值得Round 3的水準

就是給你一個由n個1    n個0組成的序列，每次交換相鄰兩個

問你把它轉成101010....   或010101.... 最少要幾步

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

#include<stdio.h>
int in, n, pos, pos2;
long long ans, ans2;
long long abs(int a, int b){
	if(a> b)return (long long)a-b;
	return (long long)b-a;
}
int main(){
	scanf("%d", &n);
	pos= 1; pos2= 1;
	for(int i=0; i<2*n; i++){
		scanf("%d", &in);
		if(in== 0){
			ans+= abs(pos, i);
			pos+= 2;
		}else{
			ans2+= abs(pos2, i);
			pos2+= 2;
		}
	}
	printf("%lld\n", ans<ans2? ans: ans2);
}

2010年3月29日星期一

POI - PA 2008 Diagonals [B]

User:	Chen Kuei-yi (poao899)
Date:	2010-03-30 03:44:39
Points	10
Comment:	Algorithmic Engagements 2008, Round 3
Task:	prz/Diagonals [B]
Date:	2010-03-30 05:04:08
Points:	10/10
Files:	solution

Test case Status Time/Limit Points

0	OK	0.00s/1.00s	0/0
0a	OK	0.00s/1.00s	0/0
1a	OK	0.00s/1.00s	1/1
1b	OK	0.00s/1.00s	1/1
2a	OK	0.00s/1.00s	1/1
2b	OK	0.00s/1.00s	1/1
3a	OK	0.00s/1.00s	1/1
3b	OK	0.00s/1.00s
3c	OK	0.00s/1.00s
4a	OK	0.01s/1.00s	1/1
4b	OK	0.00s/1.00s
4c	OK	0.01s/1.00s
5a	OK	0.01s/1.00s	1/1
5b	OK	0.00s/1.00s
5c	OK	0.00s/1.00s
6a	OK	0.10s/1.00s	1/1
6b	OK	0.00s/1.00s
6c	OK	0.04s/1.00s
7a	OK	0.31s/3.00s	1/1
7b	OK	0.31s/3.00s	1/1
8a	OK	0.09s/1.00s	1/1
8b	OK	0.23s/3.00s	1/1
9a	OK	1.06s/8.00s	1/1
9b	OK	0.95s/8.00s
9c	OK	5.40s/8.00s
10a	OK	0.99s/8.00s	1/1
10b	OK	0.90s/8.00s
10c	OK	0.49s/8.00s
10d	OK	5.61s/8.00s

不對啊AC沒道理啊 O(m lg m)sort +O(n)stack

m<=10^7, n<=10^6

怎麼看都不會AC的複雜度

還有拿掉gn跑得比較快ˊˋ

勝利得一點都不開心orz

對了，測資大概灌水兩倍

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

#include<algorithm>
#define M 5000010
int n,m,q[M],r;
struct dia{
	int i, j, o;
	void get(int oo){
		scanf("%d%d", &i, &j); o=oo;
		if(i>j){i^=j^=i^=j;}
	}
	bool operator< (const dia &b)const{
		return i<b.i || i==b.i&&j>b.j;
	}
}d[M];
struct dia2{
	int i, j, o;
	void set(int ii, int jj, int oo){
		i=ii; j=jj; o=oo;
	}
	bool operator< (const dia2 &b)const{
		return j<b.j || j==b.j&&i>b.i;
	}
}d2[M];
int main(){
	scanf("%d%d", &n, &m);
	if(m>M)m=M;
	for(int i=0; i<m; i++){
		d[i].get(i+1);
		d2[i].set(d[i].i, d[i].j, i+1);
	}
	std::sort(d, d+m);
	std::sort(d2, d2+m);
	int di=0, di2=0;
	for(int i=1; i<=n; i++){
		for(; di2<m; di2++){
			if(d2[di2].j==i){
				if(q[r-1]== d2[di2].o){
					r--;
				}else{
					printf("%d %d\n",q[r-1], d2[di2].o);
					return 0;
				}
			}else break;
		}
		for(; di<m; di++){
			if(d[di].i==i){
				q[r]= d[di].o;
				r++;
			}else break;
		}
	}
	puts("NIE");
}

TIOJ 1132 Dark Horse Escape [Greedy]

poao899 1776K 265MS G++ 0.66K 2010-03-29 19:08:07 .

反正擋他的位置一定不會比拐馬腳差...

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

#include<stdio.h>
#include<algorithm>
bool map[1011][1011];
struct horse{
	int x, y;
	bool operator<(const horse &b)const{
		return x<b.x || x==b.x&&y<b.y;
	}
	void get(){
		scanf("%d%d", &x, &y);
		map[x][y]= 1;
	}
}h[100010];
int n, cnt;
int main(){
	while(~scanf("%d", &n)){
		cnt= 0;
		for(int i=0; i<1011; i++)
			for(int j=0; j<1011; j++)
				map[i][j]= 0;
		for(int i=0; i<n; i++)
			h[i].get();
		std::sort(h, h+n);
		for(int i=0; i<n; i++){
			int x= h[i].x, y= h[i].y;
			if(!map[x+1][y+2]&& !map[x][y+1])
			{map[x+1][y+2]= 1; cnt++;}
			if(!map[x+2][y+1]&& !map[x+1][y])
			{map[x+2][y+1]= 1; cnt++;}
		}
		printf("%d\n", cnt);
	}
}

2010年3月28日星期日

TIOJ 1528 一字千金 [Tree]

poao899   4420K   6666MS   G++    2.34K    2010-03-29 13:51:35                          .

本篇全部都是雷(?

阿思：就把他想成一棵樹多了8條邊，然後去枚舉就好了

說實話也不好枚舉orz

一開始很直覺的2^8= 256的枚舉

可以想一下以下這組測資

3 3
10 100 10
1 2
2 3
1 3

答案應該是100

但是3^8= 6561太大了會TLE

而且還有一組測資

3 4
10 10 10
1 2
2 3
3 1
1 2

答案絕對是10

然後下面那組真的是我自己的問題了orz

8 9
6 3 5 2 5 3 1 4
1 2
2 4
4 5
6 4
4 8
5 7
3 5
2 6
7 8

答案是18

所以就變成2^8 *(O(e)檢查 + O(v)DP)

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

#include<stdio.h>
long long dp[50100][2], max;
int deter[50100], speCnt, n, m, val[50100], a, b, ra, rb;
int root[50100], fa[50100];
int find(int a){return root[a]==a? a: root[a]=find(root[a]);}
//0= no 1= 一定要 2= 一定不能
struct edge{
    int i, j;
    edge *next;
}e[100100], spe[10], *p, *v[50100];
void dfs(int n){
    bool can= 1;
    dp[n][0]= dp[n][1]= 0;
    for(edge *ptr=v[n]; ptr; ptr=ptr->next){
        if(fa[n]== ptr->j)continue;
        fa[ptr->j]= n;
        dfs(ptr->j);
        if(deter[ptr->j]== 1)
            can= 0;
    }
    if(deter[n]!= 2&& can){
        dp[n][1]= val[n];
        for(edge *ptr=v[n]; ptr; ptr=ptr->next){
            if(fa[n]== ptr->j)continue;
            dp[n][1]+= dp[ptr->j][0];
        }
    }if(deter[n]!=1){
        for(edge *ptr=v[n]; ptr; ptr=ptr->next){
            if(fa[n]== ptr->j)continue;
            if(deter[ptr->j]==2)
                dp[n][0]+= dp[ptr->j][0];
            else if(deter[ptr->j]==1)
                dp[n][0]+= dp[ptr->j][1];
            else dp[n][0]+= dp[ptr->j][0]>dp[ptr->j][1]? dp[ptr->j][0]: dp[ptr->j][1];
        }
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
        root[i]= i;
        scanf("%d", val+i);
    }
    for(int i=0; i<m; i++){
        scanf("%d%d", &a, &b);
        ra= find(a);
        rb= find(b);
        if(ra==rb){
            spe[speCnt].i=a; spe[speCnt].j=b;
            speCnt++;
        }else{
            e[i].i=a; e[i].j=b;
            p=v[a]; v[a]=&e[i]; e[i].next=p;
            e[i+m].i=b; e[i+m].j=a;
            p=v[b]; v[b]=&e[i+m]; e[i+m].next=p;
            root[rb]= ra;
        }
    }

    int ii= 1<<speCnt;
    for(int i=0; i<ii; i++){
        //init
        bool can= 1;
        for(int j=1; j<=n; j++)
            fa[j]=j;
        for(int j=0; can&& j<speCnt; j++){
            if(i& (1<<j)){
                deter[spe[j].i]= 2;
                deter[spe[j].j]= 0;
            }else{
                deter[spe[j].i]= 1;
                deter[spe[j].j]= 2;
            }
        }
        for(int i=0; can&& i<m; i++)
            if(deter[e[i].i]== 1&& deter[e[i].j]== 1)
                can=0;
        for(int i=0; can&& i<speCnt; i++)
            if(deter[spe[i].i]== 1&& deter[spe[i].j]== 1)
                can=0;
        if(!can)continue;
        dfs(root[1]);
        for(int j=0; j<2; j++)
            if(dp[root[1]][j]> max)
                max=dp[root[1]][j];
    }

    printf("%I64d\n",max);
}

TIOJ 1325 倍因道 - EXTREME

    poao899   1948K   326MS   G++    0.89K    2010-03-29 00:10:54                                    .

我說code風格好醜= =

然後用1241來Debug...不行   思路不夠清楚

O(n ln n)+ T*O(1)

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

#include<stdio.h>
#include<algorithm>
#define MAX 100000
struct stuff{
    int ori, cmp;
    bool operator<(const stuff &b)const{
        return cmp<b.cmp;
    }
}s[100010];
int sieve[100010], dp[100010], get[100010], t, n;
int main(){

    for(int i=1; i<=MAX; i++)
        for(int j=i+i; j<=MAX; j+=i)
            sieve[j]++;

    for(int i=1; i<=MAX; i++){
        s[i-1].ori= i;
        s[i-1].cmp= (sieve[i]+1)* i;
    }
    std::sort(s, s+MAX);
    for(int i=1,j=0; i<=MAX; i++){
        dp[i]= dp[i-1];
        while(j<MAX&& s[j].cmp<=i){
            dp[i]-= sieve[s[j].ori];
            for(int z=s[j].ori*2; z<=MAX; z+=s[j].ori){
                if(z<i)dp[i]++;
                get[z]++;
            }
            j++;
        }
        dp[i]+= get[i];
    }
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        printf("%d\n", dp[n]);
    }
}

2010年3月30日 星期二

2010年3月29日 星期一

2010年3月28日 星期日

2010年3月30日星期二

2010年3月29日星期一

2010年3月28日星期日