Zerojudge a228: 就少一個插座用很不方便

2015 年 02 月 13 日2015 年 02 月 19 日 / timbian / 2 則迴響

題目來源:

http://zerojudge.tw/ShowProblem?problemid=a228

http://acm.hdu.edu.cn/showproblem.php?pid=1693

題目大意:

在n*m的地圖中，有些格子有樹，没有樹的格子不能到達，找一條或多條迴路，吃完所有的樹，求有多少種方法。

解題心得:

這是我第一次接觸插頭DP，也有人稱作輪廓線DP，我花了幾個小時才弄懂，因此特別寫下我的心得。

輪廓線表示的是當下插頭的狀態。如果兩個格子間有插頭，即代表兩個格子相連
，反之亦然。換句話說，輪廓線記錄在這條線兩邊的格子的關係。

這題顯然一個格子要嘛有兩個插頭(經過這個格子)，要嘛沒有插頭(不經過這個格子)。
因為迴路上每一個格子各有一進一出，且不可斜著走。

我們用1表示有插頭，0表示沒有插頭。而圖中綠線為插頭，紅線為當下的輪廓線，虛線則是上一個輪廓線，叉叉(第二列第三格)為當下決策的格子。

以下分三種情況來討論: 繼續閱讀 →

Zerojudge d653: VAC+ _ 社費問題

2015 年 02 月 12 日2015 年 02 月 19 日 / timbian / 發表迴響

http://zerojudge.tw/ShowProblem?problemid=d653

這題要用到剪枝，一個情況是，在同一狀態下別選擇用過的數字，另一個情況則是，如果剩下的數字全選的話都還不夠，那就別再遞迴會下去了，因為根本不可能是答案。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int n, m;
int num[100], ans[100];

void DFS(int now, int index)
{
	if(now == m)
	{
		for(int i = 0; i < m; i ++)
			printf("%d ", ans[i]);
		printf("\n");

		return;
	}

	int last = -1;
	for(int i = index; i < n; i ++)
	{
		if(n - index < m - now) return;

		if(num[i] != last)
		{
			last = num[i];
			ans[now] = num[i];
			DFS(now + 1, i + 1);
		}
	}

}

int main()
{
	while(scanf("%d %d", &n, &m) == 2)
	{
		if(n == 0 && m == 0) break;

		for(int i = 0; i < n; i ++)
			scanf("%d", &num[i]);

		sort(num, num + n);

		DFS(0, 0);
	}

    return 0;
}

Zerojudge d591: D. 阿里不達轟!!

2015 年 02 月 11 日2015 年 02 月 19 日 / timbian / 發表迴響

http://zerojudge.tw/ShowProblem?problemid=d591

因為炸彈數很少，所以直接暴力搜索，詳情請看Code

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

const int MAXM = 20, MAXN = 10;
const int INF = 1000000;

struct Element
{
	int x, y, r;
};

Element bomb[MAXM];
Element enemy[MAXN];
int cover[MAXM];
int M, N;
int ALL;

bool in_range(const Element& B, const Element& E)
{
	int distance = (B.x - E.x) * (B.x - E.x) + (B.y - E.y) * (B.y - E.y);
	int radius_sum = (B.r + E.r) * (B.r + E.r);
	return distance <= radius_sum;
}

void init()
{
	cin >> M >> N;
	
	ALL = (1 << N) - 1;	
	for(int i = 0; i < M; i ++)
		cin >> bomb[i].x >> bomb[i].y >> bomb[i].r;
	for(int i = 0; i < N; i ++)
		cin >> enemy[i].x >> enemy[i].y >> enemy[i].r;
	
	fill(cover, cover + M, 0);
	
	for(int i = 0; i < M; i ++)
		for(int j = 0; j < N; j ++)
			if(in_range(bomb[i], enemy[j]))
				cover[i] |= (1 << j);
}

int DFS(int now, int cnt, int range)
{
	if(now == M)
	{
		if(range == ALL) 
			return cnt;
		else
			return INF;
	}
	
	int num1 = DFS(now + 1, cnt, range); 
	
	range |= cover[now];
	int num2 = DFS(now + 1, cnt + 1, range);
	
	return min(num1, num2);
}

void solve()
{	
	int bombs = DFS(0, 0, 0);
	
	if(bombs == INF)
		cout << "Impossible";
	else
		cout << bombs;
		
	cout << "\n";
}


int main()
{
	int T;

	cin >> T;
	while(T--)
	{	
		init();
		solve();
	}
	
	return 0;
}

Zerojudge a266: 校內賽

2015 年 02 月 07 日2015 年 02 月 19 日 / timbian / 發表迴響

http://zerojudge.tw/ShowProblem?problemid=a266

這題還蠻有巧思的，以前從來沒遇見過。可以把題目給的資訊存成一張圖，強弱的傳遞性就好像是A可以到B、B可以到C，所以A可以到C這樣，然後對每一名參賽者DFS找實力比他弱的有幾個(當然也可以找實力比他強的)，途中順便更新其他參賽者。

我的Code:

#include <iostream>
using namespace std;

const int MAXN = 101;

bool graph[ MAXN ][ MAXN ];
bool visit[ MAXN ];
int W[ MAXN ], L[ MAXN ];

int N, M;

void DFS(int s, int u)
{
	visit[ u ] = true;
	 
	for(int v = 1; v <= N; v ++)
	{
		if(!visit[ v ] && graph[ u ][ v ])
		{
			W[ s ] ++;
			L[ v ] ++;
			DFS(s, v);
		}
	}
}

int main()
{
	int A, B;
	
	cin >> N >> M;
	
	for(int Mi = 1; Mi <= M; Mi ++)
	{
		cin >> A >> B;
		graph[ A ][ B ] = true;
	}
	
	for(int Ni = 1; Ni <= N; Ni ++)
	{
		fill(visit, visit + MAXN, false);
		DFS(Ni, Ni);
	}
	
	bool flag = false;
	
	for(int Ni = 1; Ni <= N; Ni ++)
	{
		if(W[ Ni ] + L[ Ni ] == N - 1)
		{
			flag = true;
			cout << Ni << " ";
		}	
	}
	
	if( !flag ) cout << "non";
	
	cout << "\n";

	return 0;	
}