采矿
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;
}
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 27 | 28 | 29 | 30 | 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 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
导航
统计
- 随笔： 100
- 文章： 0
- 评论： 2
- 引用： 0
常用链接
留言簿
随笔分类
随笔档案
博客
搜索
最新评论
阅读排行榜
评论排行榜
|
|