BNU Training 2015 07 27 題解
uva 12435 C. Consistent Verdicts
【題目大意】：給你二維平面一些人的坐標，每個人手上都有一把槍，求全部人同時開槍後所有人聽到槍聲的次數的可能數目。
【解題思路】：O(n^2)暴力枚舉+unique 函數去重相鄰元素。居然只跑了3ms，~~
代碼：
// C
#ifndef _GLIBCXX_NO_ASSERT
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
// C++
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
uva 12439 G. February 29
【題目大意】兩個日期之間求leap data的個數：ps:常規方法判斷會TE，因此換個思路，判斷閏年可以用除法 代碼：
// C
#ifndef _GLIBCXX_NO_ASSERT
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
// C++
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
uva 12442 J. Forwarding Emails
【題目大意】：酋長發一封信給部落的人，給出部落的人的關系，沒人只能收一次且發一次，求在信能傳遞的最長的的人數鏈的情況下第一次收到信的人的編號 【解題思路】： 網上看到一個比較直觀的思路過程，復制過來，便於理解：
Solution Description :
DFS problem
Read this line carefully in problem description -
they each pick one other person they know to email those things to every time - exactly one, no less, no more (and never themselves) i.e Each person send email only one. For each person has only one adjacency person. The input can not be (1 to 3, 2 to 3, 1 to 2) , because for person 1 here 2 adjacency person 3 and 2. So, you can represent this graph using one dimensional array adj[N]. Do not need to stack, you can use recursion.
Example:
4
1 2
2 1
4 3
3 2
The adjacency list, adj[1]=2, adj[2]=1, adj[3]=2, and adj[4]=3.
Use a boolean array visit[N]
visit[1]
visit[2]
visit[3]
visit[4]
False
False
False
False
At first start from 1
If visit[1]==false then run DFS in this time count the visited node and update the visit[] array
(Set visit[i]=True here i is a visited node).
Remember dot not use the array visit[] for cycle finding you can use another boolean array visit2[] for that purpose.
After run DFS the visit[] array is
visit[1]
visit[2]
visit[3]
visit[4]
True
True
False
False
And count_visited_node=2 (1->2)
Now 2
visit[2]==true so, do not need to do anything.
Now 3
visit[3]==false so, run the DFS. After that the visit[] array is
visit[1]
visit[2]
visit[3]
visit[4]
True
True
True
False
And count_visited_node=3 (3->2->1)
Now 4
visit[4]==false so, run the DFS. After that the visit[] array is
visit[1]
visit[2]
visit[3]
visit[4]
True
True
True
True
And count_visited_node=4 (4->3->2->1)
For 4, the count_visited_node is maximum. Ans is 4.
代碼：
#include
#define MAX 50005
int T,N;
int vis[MAX], f[MAX], c[MAX];
int ans, flag;
typedef long long LL;
inline LL read()
{
int c=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
return c*f;
}
int dfs(int u)
{
int v = f[u];/// 2=f[1];1=f[2];2=f[3];
int r = 0; ///
vis[u] = 1; /// vis[1]=1;vis[2]=1;vis[3]=1;
if(!vis[v]) r = dfs(v) + 1;///vis[2]=1,r=0+1=1;
vis[u] = 0;
c[u] = r; ///c[1]=1,c[2]=0,c[3]=2;
return r;
}
int main()
{
int u,v;
T=read();
for(int t=1; t<=T; t++){
N=read();
for(int i=1; i<=N; i++){
u=read(),v=read();
f[u] = v;
vis[u] = 0;
c[u] = -1;
}
ans = -1;
for(int i=1; i<=N; i++){
if(c[i]==-1) dfs(i);
if(c[i]>m)
{
m=c[i];
flag=i;
}
/* printf(vertex %d children %d
,i,c[i]);*/
}
printf(Case %d: %d
,t,flag);
}
return 0;
}
幾組數據：
7
3
1 2
2 3
3 1
4
1 2
2 1
4 3
3 2
5
1 2
2 1
5 3
3 4
4 5
2
1 2
2 1
3
1 2
2 3
3 1
4
4 2
2 1
4 3
3 2
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 1
Case 1: 1
Case 2: 4
Case 3: 3
Case 4: 1
Case 5: 1
Case 6: 4
Case 7: 1
