2014年5月19日 星期一
2014年5月18日 星期日
UVA 10199 - Tourist Guide
10199 - Tourist Guide
在一座城市中有n個區塊，m條雙向的道路將區塊連結起來，而假如兩個區塊間必須經過另一個區塊，則那個區塊會有一台測速照相機。
你的朋友不太會開車，他想知道所有相機的位置，請寫個程式幫幫他。
輸入一開始給n，接著n個區塊的名字，然後是m跟每條道路連接的區塊。
Sample Input
6 sugarloaf maracana copacabana ipanema corcovado lapa 7 ipanema copacabana copacabana sugarloaf ipanema sugarloaf maracana lapa sugarloaf maracana corcovado sugarloaf lapa corcovado 5 guanabarabay downtown botanicgarden colombo sambodromo 4 guanabarabay sambodromo downtown sambodromo sambodromo botanicgarden colombo sambodromo 0
Sample Output
City map #1: 1 camera(s) found sugarloaf City map #2: 1 camera(s) found sambodromo
這題是個滿基本的找割點問題。在沒有環的情況下，假如一個點連接兩個以上的點，那就是割點( 移除他後整張圖會被割開 )。
用dfs向下搜尋，每搜尋一個點就幫他編號，如果搜尋到編號比自己小的(之前編號過)就代表有環。
要注意這題可能一開始就沒有完全相連，所以可能要dfs多次
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
map<string,int> trans;
int low[110],dfn[110],t;
vector<int> v[110],ans;
char s[110][50];
bool used[110];
int compare(const void *a,const void *b){
return strcmp((char *)a,(char *)b);
}
void dfs(int pa,int cur){
int next,children=0,i;
bool flag=false;
low[cur]=t;
dfn[cur]=t;
used[cur]=true;
t++;
for(i=0;i<v[cur].size();i++){
next=v[cur][i];
if(dfn[next]==0){
children++;
dfs(cur,v[cur][i]);
if(low[cur]>low[next])low[cur]=low[next];
if(low[next]>=dfn[cur]){
flag=true;
}
}
else if (pa != next){
if(dfn[next]<low[cur])low[cur]=dfn[next];
}
}
if(flag && (children>1 || pa!=-1)){
ans.push_back(cur);
}
return;
}
int main()
{
int n,i,j,cur,m,a,b,c=1;
char s1[50],s2[50];
while(scanf("%d",&n)!=EOF){
if(n==0)break;
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(used,false,sizeof(used));
t=1;
for(i=0;i<n;i++){
scanf("%s",s[i]);
}
qsort(s,n,sizeof(char[50]),compare);
for(i=0;i<n;i++){
trans[s[i]]=i;
}
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%s %s",s1,s2);
a=trans[s1]; b=trans[s2];
v[a].push_back(b);
v[b].push_back(a);
}
for(i=0;i<n;i++){
if(!used[i])dfs(-1,i);
}
sort(ans.begin(),ans.end());
if(c!=1)printf("\n");
printf("City map #%d: %d camera(s) found\n",c++,ans.size());
for(i=0;i<ans.size();i++){
printf("%s\n",s[ans[i]]);
}
for(i=0;i<n;i++){
v[i].clear();
}
ans.clear();
trans.clear();
}
return 0;
}
2014年5月7日 星期三
UVA 670 - The dog task
670 - The dog task
Bob喜歡跟他的狗一起散步，但狗狗跑得比較快，所以狗狗會在散步的過程中跑到其他有趣的地方，只要在每個會合點跟Bob相遇就好了。狗狗的速度是Bob的兩倍，而在兩個會合點之間狗狗頂多只能去一個有趣的地方。
輸入的第一行是有幾筆資料，每筆開頭給兩個數字(<=100)，第一個n是Bob會經過多少個會合點，第二個m是地圖上有多少有趣的地方。
接下來第一行是每個會合點的座標，下一行是有趣的點的座標。(最標是絕對值<=1000的int)
輸出先輸出狗狗總共會經過幾個點(會合點+有趣的點)，下一行是照順序印出他經過的座標。這個題目可能有多種答案，每一種都可以。
Sample Input
1 4 5 1 4 5 7 5 2 -2 4 -4 -2 3 9 1 2 -1 3 8 -3
Sample Output
6 1 4 3 9 5 7 5 2 1 2 -2 4
想法
簡單的說就是個二分匹配的題目，每個會合點配對一個有趣點(記得最後一個沒有)。
其實題目根本沒什麼，但卻WA了好幾次......
最後發現的問題真的很令人困惑，竟然是出在比較距離的地方，我一開始沒有開根號。
像這樣：
int dis(int a,int b,int c,int d){
int xx=x[a][b]-x[c][d];
int yy=y[a][b]-y[c][d];
return xx*xx+yy*yy;
}
結果加了sqrt後就AC了.....但是這根本不合理啊啊啊！直接用平方比較應該比浮點運算更沒有誤差，而且題目的座標在1000以內，應該也不會有overflow的問題才對啊！
總之是謎啊......
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int n,m,x[2][110],y[2][110];
bool select[110];
int match[2][110]={0};
double dis(int a,int b,int c,int d){
int xx=x[a][b]-x[c][d];
int yy=y[a][b]-y[c][d];
return sqrt(xx*xx+yy*yy);
}
bool reach(int a,int b)
{
if(2*dis(0,a+1,0,a)>=dis(1,b,0,a)+dis(0,a+1,1,b))return true;
else return false;
}
bool find(int no)
{
int i;
for(i=1;i<=m;i++){
if(select[i])continue;
if(!reach(no,i))continue;
select[i]=true;
if(match[1][i]==0){
match[0][no]=i; match[1][i]=no;
return true;
}
else {
if(find(match[1][i])){
match[0][no]=i; match[1][i]=no;
return true;
}
}
}
return false;
}
int main()
{
int N,t,ans,i,j;
scanf("%d",&N);
for(t=1;t<=N;t++){
scanf("%d %d",&n,&m);
memset(match,0,sizeof(match));
ans=0;
for(i=1;i<=n;i++){
scanf("%d %d",&x[0][i],&y[0][i]);
}
for(i=1;i<=m;i++){
scanf("%d %d",&x[1][i],&y[1][i]);
}
for(j=1;j<n;j++){
memset(select,false,sizeof(select));
if(find(j)){
ans++;
}
}
printf("%d\n",n+ans);
for(i=1;i<=n;i++){
printf("%d %d",x[0][i],y[0][i]);
if(match[0][i]!=0){
printf(" %d %d",x[1][match[0][i]],y[1][match[0][i]]);
}
if(i!=n)printf(" ");
}
printf("\n");
if(t<N)printf("\n");
}
return 0;
}
2014年4月26日 星期六
UVA 674 -Coin Change
674 - Coin Change
大意：
簡單來說就是你有幣值1,5,10,25,50的5種硬幣，題目會給你7489以內的數字，問你有幾種排列組合的方式 ( 例：10元有 一個10，兩個5，一個5五個1，和十個1 四種，所以答案是4 )
Sample Input
11 26
Sample Output
413
解法：
可以想成是背包問題的變形，一次考慮一種硬幣。以第二個範例的26為例：
只考慮一塊錢時，不論多少錢都只有一種換法：
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
多考慮5塊：
1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6
每個可能性=只考慮一塊的可能+五格前的可能性(稍後解釋)
10塊：
1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6 6 6 9 9 9 9 9 12 12
怎麼算的呢？以26塊的12為例：12=6+6
第一個6是只考慮一塊和五塊時，26塊有幾種換法
第二個6是看十格前，也就是考慮1，5，10塊時，16塊有幾種換法
第一個6包含沒有10塊的所有組合，也就是說之後的可能至少要有一個十塊
而26塊至少有一個十塊的換法 = 16塊全部的換法
兩個相加就是答案了~~
25塊和50塊也如法炮製~~要注意的是這題其實只要一次算出1到7489的所有換法，之後題目給什麼數字就可以直接印出答案，不用每次都算一遍喔 QWQ
程式碼：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int coin[5]={1,5,10,25,50};
int bag[7500];
int main()
{
int num,ans,i,j;
for(i=0;i<7500;i++){
bag[i]=1;
}
for(i=1;i<5;i++){
for(j=1;j<7500;j++){
if(j>=coin[i]){
bag[j]+=bag[j-coin[i]];
}
}
}
while(scanf("%d",&num)!=EOF){
ans=bag[num];
printf("%d\n",ans);
}
return 0;
}
訂閱：
文章 (Atom)