采礦
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 694 Accepted Submission(s): 385
Special Judge
Problem Description
某天gameboy玩魔獸RPG。有一個任務是在一個富含金礦的圓形小島上建一個基地，以最快的速度采集完這個小島上的所有金礦。這個小島上有n(0<n<1000000)個金礦，每個金礦的礦藏量是相等的。而且這個小島的地勢非常平坦，所以基地可以建在小島的任何位置，每個金礦的采礦速度只跟礦藏到基地的路程長度有關。為了不讓這個任務太無聊，游戲設計者對這個小島施了個“魔法”，規定礦工在小島上只能正南正北正西正東走。也就是說礦工不能斜著在島上走。
這個小島在一個二維直角坐標系中描述。
你的任務就是幫gameboy找一個建造基地的位置，使礦工能以最快的速度采完所有礦。
Input
輸入數據有多組。每組數據的第一行是一個正整數n(0<n<1000000),表示小島上有n個金礦。在接下來的n行中，每行有兩個實數x,y，表示其中一個金礦的坐標。n=0表示輸入數據結束。
Output
每一組輸入數據對應一行輸出，輸出兩個實數x，y（保留小數點后兩位），也就是你找到的建造基地的位置坐標。如果坐標不唯一，可以任選一個輸出。
Sample Input
4
1.0 1.0
3.0 1.0
3.0 3.0
1.0 3.0
0
Sample Output
Source
很簡單，其實把x坐標和y坐標排序，然后找中位數就是答案了！！！
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1000005;
double a[MAXN],b[MAXN];
int main()
{
int i,n;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
scanf("%lf%lf",&a[i],&b[i]);
sort(a,a+n);
sort(b,b+n);
printf("%.2lf %.2lf\n",a[n/2],b[n/2]);
}
return 0;
}
驗證角谷猜想
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2209 Accepted Submission(s): 1137
Problem Description
數論中有許多猜想尚未解決，其中有一個被稱為“角谷猜想”的問題，該問題在五、六十年代的美國多個著名高校中曾風行一時，這個問題是這樣描述的：任何一個大于一的自然數，如果是奇數，則乘以三再加一；如果是偶數，則除以二；得出的結果繼續按照前面的規則進行運算，最后必定得到一。現在請你編寫一個程序驗證他的正確性。
Input
本題有多個測試數據組，第一行為測試數據組數N，接著是N行的正整數。
Output
輸出驗證“角谷猜想”過程中的奇數，最后得到的1不用輸出；每個測試題輸出一行；每行中只有兩個輸出之間才能有一個空格；如果沒有這樣的輸出，則輸出：No number can be output !。
Sample Input
Sample Output
5
9 7 11 17 13 5
No number can be output !
11 17 13 5
Author
Cai Minglun
Source
Recommend
lcy
#include<stdio.h>
int main()
{
int N;
int m;
scanf("%d",&N);
while(N--)
{
bool flag=false;
scanf("%d",&m);
while(m>1)
{
if(m%2==0) m/=2;
else
{
if(flag==false) printf("%d",m);
else printf(" %d",m);
flag=true;
m=m*3+1;
}
}
if(flag==false)printf("No number can be output !");
printf("\n");
}
return 0;
}
回文數猜想
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1524 Accepted Submission(s): 945
Problem Description
一個正整數，如果從左向右讀（稱之為正序數）和從右向左讀（稱之為倒序數）是一樣的，這樣的數就叫回文數。任取一個正整數，如果不是回文數，將該數與他的倒序數相加，若其和不是回文數，則重復上述步驟，一直到獲得回文數為止。例如：68變成154（68+86），再變成605（154+451），最后變成1111（605+506），而1111是回文數。于是有數學家提出一個猜想：不論開始是什么正整數，在經過有限次正序數和倒序數相加的步驟后，都會得到一個回文數。至今為止還不知道這個猜想是對還是錯。現在請你編程序驗證之。
Input
每行一個正整數。
特別說明：輸入的數據保證中間結果小于2^31。
Output
對應每個輸入，輸出兩行，一行是變換的次數，一行是變換的過程。
Sample Input
Sample Output
3
27228--->109500--->115401--->219912
2
37649--->132322--->355553
Author
SmallBeer(CML)
Source
Recommend
lcy
#include<stdio.h>
int change(int n)
{
int a[20];
int k=0;
while(n!=0)
{
k++;
a[k]=n%10;
n/=10;
}
int res=0;
for(int i=1;i<=k;i++)
{
res*=10;
res+=a[i];
}
return res;
}
int main()
{
int n,i,cnt;
int result[100];
while(scanf("%d",&n)!=EOF)
{
cnt=0;
result[0]=n;
while(n!=change(n))
{
n=n+change(n);
result[++cnt]=n;
}
printf("%d\n",cnt);
for(i=0;i<cnt;i++)
printf("%d--->",result[i]);
printf("%d\n",result[cnt]);
}
return 0;
}
最簡單的計算機
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1781 Accepted Submission(s): 1054
Problem Description
一個名叫是PigHeadThree的研究組織設計了一臺實驗用的計算機，命名為PpMm。PpMm只能執行簡單的六種命令A，B，C，D，E，F；只有二個內存M1，M2；三個寄存器R1，R2，R3。六種命令的含義如下：
命令A：將內存M1的數據裝到寄存器R1中；
命令B：將內存M2的數據裝到寄存器R2中；
命令C：將寄存器R3的數據裝到內存M1中；
命令D：將寄存器R3的數據裝到內存M2中；
命令E：將寄存器R1中的數據和寄存器R2中的數據相加，結果放到寄存器R3中；
命令F：將寄存器R1中的數據和寄存器R2中的數據相減，結果放到寄存器R3中。
你的任務是：設計一個程序模擬PpMm的運行。
Input
有若干組，每組有2行，第一行是2個整數，分別表示M1和M2中的初始內容；第二行是一串長度不超過200的由大寫字母A到F組成的命令串，命令串的含義如上所述。
Output
對應每一組的輸入，輸出只有一行，二個整數，分別表示M1，M2的內容；其中M1和M2之間用逗號隔開。
其他說明：R1，R2，R3的初始值為0，所有中間結果都在-2^31和2^31之間。
Sample Input
100 288
ABECED
876356 321456
ABECAEDBECAF
Sample Output
Author
SmallBeer(CML)
Source
Recommend
lcy
#include<stdio.h>
#include<string.h>
char str[210];
int main()
{
int M1,M2,R1,R2,R3;
int i,len;
while(scanf("%d%d",&M1,&M2)!=EOF)
{
R1=R2=R3=0;
scanf("%s",&str);
len=strlen(str);
for(i=0;i<len;i++)
{
if(str[i]=='A')R1=M1;
else if(str[i]=='B') R2=M2;
else if(str[i]=='C') M1=R3;
else if(str[i]=='D') M2=R3;
else if(str[i]=='E') R3=R1+R2;
else if(str[i]=='F') R3=R1-R2;
}
printf("%d,%d\n",M1,M2);
}
return 0;
}
Agri-Net
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 22951 |
|
Accepted: 9047 |
Description
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.
Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.
Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.
Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output
28
Source
#include<stdio.h>
#include<string.h>
#define MAXN 210
int cost[MAXN][MAXN];
const int INF=0x3f3f3f3f;
int vis[MAXN];
int lowc[MAXN];
int prim(int cost[][MAXN],int n)//編號從1-n
{
int i,j,p;
int minc,res=0;
memset(vis,0,sizeof(vis));
vis[1]=1;
for(i=1;i<=n;i++)
lowc[i]=cost[1][i];
for(i=1;i<n;i++)
{
minc=INF;
p=-1;
for(j=1;j<=n;j++)
if(vis[j]==0&&minc>lowc[j])
{minc=lowc[j];p=j;}
if(minc==INF)return -1;
res+=minc;vis[p]=1;
for(j=1;j<=n;j++)
if(vis[j]==0&&lowc[j]>cost[p][j])
lowc[j]=cost[p][j];
}
return res;
}
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
printf("%d\n",prim(cost,n));
}
return 0;
}
Constructing Roads
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 14128 |
|
Accepted: 5682 |
Description
There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.
We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.
Input
The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.
Then there is an integer Q (0 <= Q <= N * (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.
Output
You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.
Sample Input
3
0 990 692
990 0 179
692 179 0
1
1 2
Sample Output
179
Source
#include<stdio.h>
#include<string.h>
#define MAXN 210
int cost[MAXN][MAXN];
const int INF=0x3f3f3f3f;
int vis[MAXN];
int lowc[MAXN];
int prim(int cost[][MAXN],int n)//編號從1-n
{
int i,j,p;
int minc,res=0;
memset(vis,0,sizeof(vis));
vis[1]=1;
for(i=1;i<=n;i++)
lowc[i]=cost[1][i];
for(i=1;i<n;i++)
{
minc=INF;
p=-1;
for(j=1;j<=n;j++)
if(vis[j]==0&&minc>lowc[j])
{minc=lowc[j];p=j;}
if(minc==INF)return -1;
res+=minc;vis[p]=1;
for(j=1;j<=n;j++)
if(vis[j]==0&&lowc[j]>cost[p][j])
lowc[j]=cost[p][j];
}
return res;
}
int main()
{
int n,i,j;
int m,a,b;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
cost[a][b]=0;
cost[b][a]=0;
}
printf("%d\n",prim(cost,n));
}
return 0;
}
Popular Cows
| Time Limit: 2000MS |
|
Memory Limit: 65536K |
| Total Submissions: 13835 |
|
Accepted: 5484 |
Description
Every cow's dream is to become the most popular cow in the herd. In a herd of N (1 <= N <= 10,000) cows, you are given up to M (1 <= M <= 50,000) ordered pairs of the form (A, B) that tell you that cow A thinks that cow B is popular. Since popularity is transitive, if A thinks B is popular and B thinks C is popular, then A will also think that C is
popular, even if this is not explicitly specified by an ordered pair in the input. Your task is to compute the number of cows that are considered popular by every other cow.
Input
* Line 1: Two space-separated integers, N and M
* Lines 2..1+M: Two space-separated numbers A and B, meaning that A thinks B is popular.
Output
* Line 1: A single integer that is the number of cows who are considered popular by every other cow.
Sample Input
3 3
1 2
2 1
2 3
Sample Output
1
Hint
Cow 3 is the only cow of high popularity.
Source
/*
POJ2186
1.求出所有的強連通分量，用Korasaju算法
2.每個強連通分量縮成一點，則形成一個有向無環圖DAG。
3.DAG上面如果有唯一的出度為0的點，則改點能被所有的點可達。
那么該點所代表的連通分量上的所有的原圖中的點，都能被原圖中
的所有點可達 ，則該連通分量的點數就是答案。
4.DAG上面如果有不止一個出度為0的點，則這些點互相不可達，原問題
無解，答案為0；
（此外DAG肯定是一個有向無環圖，則至少存在一個出度為0的點，上面
兩種情況包括了所有可能。
此題用了鄰接表存圖，并利用鄰接表進行DFS，需要學習下。）
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define MAXN 10005 //結點的最大數
struct Node
{
int to,next;
}edge1[MAXN*5],edge2[MAXN*5];
//edge1用來存原圖G，edge2用來存GT，即逆圖
//都是用鄰接表來儲存的圖，
int head1[MAXN];//原圖的鄰接表的頭結點
int head2[MAXN];//逆圖的鄰接表的頭結點
int mark1[MAXN],mark2[MAXN];
int tot1,tot2;
int cnt1,cnt2,st[MAXN],belong[MAXN];
int num,setNum[MAXN];
struct Edge
{
int l,r;
}e[MAXN*5];//儲存邊
void add(int a,int b)//添加邊a->b，在原圖和逆圖都需要添加
{
edge1[tot1].to=b;edge1[tot1].next=head1[a];head1[a]=tot1++;//鄰接表存的原圖
edge2[tot2].to=a;edge2[tot2].next=head2[b];head2[b]=tot2++;//鄰接表存的逆圖
}
void DFS1(int x)//深度搜索原圖
{
mark1[x]=1;
for(int i=head1[x];i!=-1;i=edge1[i].next)
if(!mark1[edge1[i].to]) DFS1(edge1[i].to);
st[cnt1++]=x;//st數組是按照完成時間從小到大排序的
}
void DFS2(int x)//深度搜索逆圖
{
mark2[x]=1;
num++;
belong[x]=cnt2;
for(int i=head2[x];i!=-1;i=edge2[i].next)
if(!mark2[edge2[i].to]) DFS2(edge2[i].to);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
tot1=tot2=1;
for(int i=1;i<=n;i++)//初始化
{
head1[i]=head2[i]=-1;
mark1[i]=mark2[i]=0;
}
for(int i=1;i<=m;i++)
{
int w,v;
scanf("%d%d",&w,&v);
e[i].l=w;e[i].r=v;//儲存邊
add(w,v);//建立鄰接表
}
cnt1=cnt2=1;
for(int i=1;i<=n;i++)
{
if(!mark1[i])DFS1(i);
}
for(int i=cnt1-1;i>=1;i--)
{
if(!mark2[st[i]])
{
num=0;
DFS2(st[i]);
setNum[cnt2++]=num;
}
}
int de[MAXN];//計算出度
memset(de,0,sizeof(de));
for(int i=1;i<=m;i++)//計算各個DAG圖的出度
{
if(belong[e[i].l]!=belong[e[i].r])//原圖的邊不屬于同一連通分支
de[belong[e[i].l]]++;
}
//計算DAG出度為0的個數
int cnt=0,res;
for(int i=1;i<cnt2;i++)
if(!de[i]){cnt++;res=i;}
if(cnt>1) printf("0\n");
else printf("%d\n",setNum[res]);
}
return 0;
}
/*
Kosaju算法比較好理解，就是先對逆圖作一遍dfs，計算后序編號定義頂點的排列（如果有向圖是一個DAG，
這一過程產生一個拓撲排序序列）。然后在圖上再一次DFS，不過是按照具有最高后序編號的未訪問的頂點的順
序。
這樣得到的就是一個強連通分量了。因為在訪問逆圖的時候，只有當原圖中w點可以到達v點的時候，
逆圖中的dfs樹中V才可能是W的父節點，也就是說逆圖中V可到達w，這樣，v的編號將大于w。再在原圖中作DFS
，
由于是按照先訪問最高后序未訪問編號的次序，這樣如果在原圖中w可以到達v,那么在逆圖中就有V可以到達w
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#define M 10005 //結點數
using namespace std;
struct node{
int to,next;
}edge1[M*10],edge2[M*10];
int mark1[M],mark2[M],head1[M],head2[M];
int tot1,tot2;
int cnt1,st[M],cnt2,belong[M];
int num,setNum[M];
struct nn{
int l,r;
}e[M*10];
void add(int a,int b){ //每個點的前端結點 和 后端結點
edge1[tot1].to=b, edge1[tot1].next=head1[a], head1[a]=tot1++;//鄰接表存的原圖
edge2[tot2].to=a, edge2[tot2].next=head2[b], head2[b]=tot2++;//鄰接表存的逆圖
}
void DFS1(int x) {
mark1[x]=1;
for(int i=head1[x]; i!=-1; i=edge1[i].next) //正向
if(!mark1[edge1[i].to]) DFS1(edge1[i].to);
st[cnt1++]=x;
}
void DFS2(int x) {
mark2[x]=1;
num++;
belong[x]=cnt2; //正向能到，反向也能到的是在同一聯通分量里
for(int i=head2[x]; i!=-1; i=edge2[i].next) //逆向
if(!mark2[edge2[i].to]) DFS2(edge2[i].to);
}
int main() {
int n,m;
while(scanf("%d%d",&n,&m) != EOF){
tot1=tot2=0;
for(int i=0; i<n; i++){
head1[i]=head2[i]=-1;
mark1[i]=mark2[i]=0;
}
for(int i=0; i<m; i++){
int w,v;
scanf("%d%d",&w,&v);
w--, v--; //結點從0開始編號
e[i].l=w; e[i].r=v;
add(w,v);
}
cnt1=cnt2=0;
for(int i=0; i<n; i++){
if(!mark1[i]) DFS1(i);
}
for(int i=cnt1-1; i>=0; i--){
if(!mark2[ st[i] ]) {
num=0;
DFS2(st[i]);
setNum[cnt2++]=num;
}
}
int de[M];
memset(de,0,sizeof(de));
for(int i=0; i<m; i++){
if(belong[ e[i].l ] != belong[ e[i].r ])
de[ belong[e[i].l] ]++;
}
int cnt=0,res;
for(int i=0; i<cnt2; i++){
if(!de[i]) {
cnt++; res=i;
}
}
if(cnt>1) printf("0\n");
else printf("%d\n",setNum[res]);
}
return 0;
}
這個結合上題，類似的代碼解決的：http://www.cnblogs.com/kuangbin/archive/2011/08/07/2130062.html
Network of Schools
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 5354 |
|
Accepted: 2106 |
Description
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.
Input
The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.
Output
Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.
Sample Input
5
2 4 3 0
4 5 0
0
0
1 0
Sample Output
1
2
Source
強連通分量縮點求入度為0的個數和出度為0的分量個數
題目大意：N(2<N<100)各學校之間有單向的網絡，每個學校得到一套軟件后，可以通過單向網絡向周邊的學校傳輸，問題1：初始至少需要向多少個學校發放軟件，使得網絡內所有的學校最終都能得到軟件。2，至少需要添加幾條傳輸線路(邊)，使任意向一個學校發放軟件后，經過若干次傳送，網絡內所有的學校最終都能得到軟件。
也就是：
? 給定一個有向圖，求：
1) 至少要選幾個頂點，才能做到從這些頂點出發，可以到達全部頂點
2) 至少要加多少條邊，才能使得從任何一個頂點出發，都能到達全部頂點
? 頂點數<= 100
解題思路：
? 1. 求出所有強連通分量
? 2. 每個強連通分量縮成一點，則形成一個有向無環圖DAG。
? 3. DAG上面有多少個入度為0的頂點，問題1的答案就是多少
在DAG上要加幾條邊，才能使得DAG變成強連通的，問題2的答案就是多少
加邊的方法：
要為每個入度為0的點添加入邊，為每個出度為0的點添加出邊
假定有 n 個入度為0的點，m個出度為0的點，如何加邊？
把所有入度為0的點編號 0,1,2,3,4 ....N -1
每次為一個編號為i的入度0點可達的出度0點，添加一條出邊，連到編號為(i+1)%N 的那個出度0點,
這需要加n條邊
若 m <= n，則
加了這n條邊后，已經沒有入度0點，則問題解決，一共加了n條邊
若 m > n，則還有m-n個入度0點，則從這些點以外任取一點，和這些點都連上邊，即可，這還需加m-n條邊。
所以，max(m,n)就是第二個問題的解
此外：當只有一個強連通分支的時候，就是縮點后只有一個點，雖然入度出度為0的都有一個，但是實際上不需要增加清單的項了，所以答案是1，0；
程序：
/*
POJ 1236
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define MAXN 110
struct Node
{
int to,next;
}edge1[MAXN*100],edge2[MAXN*100];
int head1[MAXN];
int head2[MAXN];
int mark1[MAXN],mark2[MAXN];
int tot1,tot2;
int cnt1,cnt2,st[MAXN],belong[MAXN];
int num,setNum[MAXN];
struct Edge
{
int l,r;
}e[MAXN*100];
void add(int a,int b)
{
edge1[tot1].to=b;edge1[tot1].next=head1[a];head1[a]=tot1++;
edge2[tot2].to=a;edge2[tot2].next=head2[b];head2[b]=tot2++;
}
void DFS1(int x)//搜索原圖
{
mark1[x]=1;
for(int i=head1[x];i!=-1;i=edge1[i].next)
if(!mark1[edge1[i].to]) DFS1(edge1[i].to);
st[cnt1++]=x;
}
void DFS2(int x)
{
mark2[x]=1;
num++;
belong[x]=cnt2;
for(int i=head2[x];i!=-1;i=edge2[i].next)
if(!mark2[edge2[i].to]) DFS2(edge2[i].to);
}
int main()
{
int n;
int m;//邊數
while(scanf("%d",&n)!=EOF)
{
int w,v;
tot1=tot2=1;
for(int i=1;i<=n;i++)
{
head1[i]=head2[i]=-1;
mark1[i]=mark2[i]=0;
}
m=0;
for(w=1;w<=n;w++)
{
while(scanf("%d",&v),v)
{
m++;
e[m].l=w;e[m].r=v;
add(w,v);
}
}
cnt1=cnt2=1;
for(int i=1;i<=n;i++)
{
if(!mark1[i])DFS1(i);
}
for(int i=cnt1-1;i>=1;i--)
{
if(!mark2[st[i]])
{
num=0;
DFS2(st[i]);
setNum[cnt2++]=num;
}
}
int out[MAXN],in[MAXN];//計算出度和入度
memset(out,0,sizeof(out));
memset(in,0,sizeof(in));
for(int i=1;i<=m;i++)
{
if(belong[e[i].l]!=belong[e[i].r])
{
out[belong[e[i].l]]++;
in[belong[e[i].r]]++;
}
}
int res1=0;//出度為0的個數
int res2=0;//入度為0的個數
for(int i=1;i<cnt2;i++)
{
if(!out[i]) res1++;
if(!in[i]) res2++;
}
//下面這個是關鍵，整張圖就一個連通分量時，輸出0，1.WR了好幾次呢
if(cnt2==2) {printf("1\n0\n");continue;}
printf("%d\n",res2);
printf("%d\n",res1>res2?res1:res2);
}
return 0;
}
The Cow Prom
| Time Limit: 1000MS |
|
Memory Limit: 65536K |
| Total Submissions: 643 |
|
Accepted: 384 |
Description
The N (2 <= N <= 10,000) cows are so excited: it's prom night! They are dressed in their finest gowns, complete with corsages and new shoes. They know that tonight they will each try to perform the Round Dance.
Only cows can perform the Round Dance which requires a set of ropes and a circular stock tank. To begin, the cows line up around a circular stock tank and number themselves in clockwise order consecutively from 1..N. Each cow faces the tank so she can see the other dancers.
They then acquire a total of M (2 <= M <= 50,000) ropes all of which are distributed to the cows who hold them in their hooves. Each cow hopes to be given one or more ropes to hold in both her left and right hooves; some cows might be disappointed.
For the Round Dance to succeed for any given cow (say, Bessie), the ropes that she holds must be configured just right. To know if Bessie's dance is successful, one must examine the set of cows holding the other ends of her ropes (if she has any), along with the cows holding the other ends of any ropes they hold, etc. When Bessie dances clockwise around the tank, she must instantly pull all the other cows in her group around clockwise, too. Likewise,
if she dances the other way, she must instantly pull the entire group counterclockwise (anti-clockwise in British English).
Of course, if the ropes are not properly distributed then a set of cows might not form a proper dance group and thus can not succeed at the Round Dance. One way this happens is when only one rope connects two cows. One cow could pull the other in one direction, but could not pull the other direction (since pushing ropes is well-known to be fruitless). Note that the cows must Dance in lock-step: a dangling cow (perhaps with just one rope) that is eventually pulled along disqualifies a group from properly performing the Round Dance since she is not immediately pulled into lockstep with the rest.
Given the ropes and their distribution to cows, how many groups of cows can properly perform the Round Dance? Note that a set of ropes and cows might wrap many times around the stock tank.
Input
Line 1: Two space-separated integers: N and M
Lines 2..M+1: Each line contains two space-separated integers A and B that describe a rope from cow A to cow B in the clockwise direction.
Output
Line 1: A single line with a single integer that is the number of groups successfully dancing the Round Dance.
Sample Input
5 4
2 4
3 5
1 2
4 1
Sample Output
1
Hint
Explanation of the sample: ASCII art for Round Dancing is challenging. Nevertheless, here is a representation of the cows around the stock tank:
_1___
/**** \
5 /****** 2
/ /**TANK**|
\ \********/
\ \******/ 3
\ 4____/ /
\_______/
Cows 1, 2, and 4 are properly connected and form a complete Round Dance group. Cows 3 and 5 don't have the second rope they'd need to be able to pull both ways, thus they can not properly perform the Round Dance. Source
題目看了好久沒有看懂，然后看了大牛的解題報告，說是求結點大于等于2的強連通分量個數
于是套用模板：
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define MAXN 10005 //結點的最大數
struct Node
{
int to,next;
}edge1[MAXN*5],edge2[MAXN*5];
//edge1用來存原圖G，edge2用來存GT，即逆圖
//都是用鄰接表來儲存的圖，
int head1[MAXN];//原圖的鄰接表的頭結點
int head2[MAXN];//逆圖的鄰接表的頭結點
int mark1[MAXN],mark2[MAXN];
int tot1,tot2;
int cnt1,cnt2,st[MAXN],belong[MAXN];
int num,setNum[MAXN];
struct Edge
{
int l,r;
}e[MAXN*5];//儲存邊
void add(int a,int b)//添加邊a->b，在原圖和逆圖都需要添加
{
edge1[tot1].to=b;edge1[tot1].next=head1[a];head1[a]=tot1++;//鄰接表存的原圖
edge2[tot2].to=a;edge2[tot2].next=head2[b];head2[b]=tot2++;//鄰接表存的逆圖
}
void DFS1(int x)//深度搜索原圖
{
mark1[x]=1;
for(int i=head1[x];i!=-1;i=edge1[i].next)
if(!mark1[edge1[i].to]) DFS1(edge1[i].to);
st[cnt1++]=x;//st數組是按照完成時間從小到大排序的
}
void DFS2(int x)//深度搜索逆圖
{
mark2[x]=1;
num++;
belong[x]=cnt2;
for(int i=head2[x];i!=-1;i=edge2[i].next)
if(!mark2[edge2[i].to]) DFS2(edge2[i].to);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
tot1=tot2=1;
for(int i=1;i<=n;i++)//初始化
{
head1[i]=head2[i]=-1;
mark1[i]=mark2[i]=0;
}
for(int i=1;i<=m;i++)
{
int w,v;
scanf("%d%d",&w,&v);
e[i].l=w;e[i].r=v;//儲存邊
add(w,v);//建立鄰接表
}
cnt1=cnt2=1;
for(int i=1;i<=n;i++)
{
if(!mark1[i])DFS1(i);
}
for(int i=cnt1-1;i>=1;i--)
{
if(!mark2[st[i]])
{
num=0;
DFS2(st[i]);
setNum[cnt2++]=num;
}
}
int cnt=0;
for(int i=1;i<cnt2;i++)
if(setNum[i]>=2)cnt++;
printf("%d\n",cnt);
}
return 0;
}
Ancient Printer
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 704 Accepted Submission(s): 309
Problem Description
The contest is beginning! While preparing the contest, iSea wanted to print the teams' names separately on a single paper.
Unfortunately, what iSea could find was only an ancient printer: so ancient that you can't believe it, it only had three kinds of operations:
● 'a'-'z': twenty-six letters you can type
● 'Del': delete the last letter if it exists
● 'Print': print the word you have typed in the printer
The printer was empty in the beginning, iSea must use the three operations to print all the teams' name, not necessarily in the order in the input. Each time, he can type letters at the end of printer, or delete the last letter, or print the current word. After printing, the letters are stilling in the printer, you may delete some letters to print the next one, but you needn't delete the last word's letters.
iSea wanted to minimize the total number of operations, help him, please.
Input
There are several test cases in the input.
Each test case begin with one integer N (1 ≤ N ≤ 10000), indicating the number of team names.
Then N strings follow, each string only contains lowercases, not empty, and its length is no more than 50.
The input terminates by end of file marker.
Output
For each test case, output one integer, indicating minimum number of operations.
Sample Input
Sample Output
21
Hint
The sample's operation is:
f-r-e-e-o-p-e-n-Print-Del-Del-Del-Del-r-a-d-i-a-n-t-Print
Author
iSea @ WHU
Source
Recommend
zhouzeyong
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
string w[10005];
int calc(string a,string b)
{
int i;
for(i=0;i<a.length()&&i<b.length()&&a[i]==b[i];i++);
return a.length()-i+b.length()-i;
}
int main()
{
int n,i;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++) cin>>w[i];
sort(w,w+n);
int sum=w[0].length()+1;
int MAX=w[0].length();
for(i=1;i<n;i++)
{
sum+=calc(w[i],w[i-1])+1;
if(w[i].length()>MAX)
MAX=w[i].length();
}
printf("%d\n",sum+w[n-1].length()-MAX);
}
return 0;
}
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 31 | 1 | 2 | 3 | 4 | 5 | 6 | | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | 14 | 15 | 16 | 17 | 18 | 19 | 20 | | 21 | 22 | 23 | 24 | 25 | 26 | 27 | | 28 | 29 | 30 | 31 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
公告
導航
統計
- 隨筆： 100
- 文章： 0
- 評論： 2
- 引用： 0
常用鏈接
留言簿(2)
隨筆分類
隨筆檔案
博客
搜索
最新評論
閱讀排行榜
評論排行榜
|
|