问题 C: 老王赛马
时间限制: 1 Sec 内存限制: 128 MB提交: 50 解决: 28
[提交][状态][讨论版]
题目描述
赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。
赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。”
孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。
比赛前田忌按照孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马，与齐王的上等马比赛。第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国王的马前面，结果二比一，田忌赢了国王。
就是这么简单，现在老王也来赛一赛马。假设每匹马都有恒定的速度，所以速度大的马一定比速度小的马先到终点（没有意外！！）。不允许出现平局。最后谁赢的场数多于一半(不包括一半)，谁就是赢家(可能没有赢家)。老王有N(1≤N≤1000)匹马参加比赛。对手的马的数量与渊子马的数量一样，并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果，看看老王能否赢得比赛。
输入
输入有多组测试数据。
每组测试数据包括3行：
第一行输入N(1≤N≤1000)。表示马的数量。
第二行有N个整型数字，即渊子的N匹马的速度。
第三行有N个整型数字，即对手的N匹马的速度。
当N为0时退出。
输出
若通过聪明的你精心安排，如果渊子能赢得比赛，那么输出“YES”。
否则输出“NO”。
样例输入
5 2 3 3 4 5 1 2 3 4 5 4 2 2 1 2 2 2 3 1 0
样例输出
YES NO代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 const int MAXN=1010; 6 int a[MAXN],b[MAXN]; 7 int cmp(int x,int y){ 8 return x>y; 9 } 10 int main(){ 11 int N,x,y,bu,top; 12 while(scanf("%d",&N),N){ 13 x=y=0; 14 for(int i=0;i<N;i++)scanf("%d",&a[i]); 15 for(int i=0;i<N;i++)scanf("%d",&b[i]); 16 sort(a,a+N,cmp); 17 sort(b,b+N,cmp); 18 bu=N-1;top=0; 19 for(int i=0;i<=bu;){ 20 for(int j=0;j<N;j++){ 21 if(a[i]>b[j]){ 22 x++; 23 i++; 24 } 25 else if(a[bu]<b[j]){ 26 bu--; 27 y++; 28 } 29 else bu--; 30 } 31 } 32 // printf("%d %d ",x,y); 33 if(x>y)puts("YES"); 34 else if(x==y&&x>(N+1)/2)puts("YES"); 35 else puts("NO"); 36 } 37 return 0; 38 }
问题 E: 最后一个1
时间限制: 1 Sec 内存限制: 128 MB提交: 62 解决: 37
[提交][状态][讨论版]
题目描述
对于一个十进制的数字x，将他转化为2进制，他的2进制将由0和1组成，求里面的最后一个1在第几位
输入
第一行输入T，代表T组数据，
接下来T行，每行输入一个X。
0<T<1e7
0<X<1e9
输出
输入x的2进制中最后一个1在第几位，
不存在输出0
样例输入
3 0 3 8
样例输出
0 2 1代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 int main(){ 5 int x,T,flot,m,num; 6 scanf("%d",&T); 7 while(T--){ 8 num=flot=0; 9 scanf("%d",&x); 10 m=x; 11 while(m%2==0&&m){ 12 m/=2; 13 flot++; 14 }m=x; 15 while(m){ 16 m/=2; 17 num++; 18 } 19 printf("%d ",num-flot); 20 } 21 return 0; 22 }
问题 F: 参观城市
时间限制: 1 Sec 内存限制: 128 MB提交: 34 解决: 19
[提交][状态][讨论版]
题目描述
有N个城市，这N个城市间只有N-1条路把这个N个城市连接起来。现在，小明在第S号城市，他有张该国地图，他想知道如果自己要去参观第T号城市，必须经过的前一个城市是几号城市（假设你不走重复的路）。
输入
第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000)，N表示城市的总个数，S表示参观者所在城市的编号
随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a号城市和第b号城市之间有一条路连通。
输出
每组测试数据输N个正整数，其中，第i个数表示从S走到i号城市，必须要经过的上一个城市的编号。（其中i=S时，请输出-1）
样例输入
1 10 10 1 2 1 9 1 8 3 7 8 6 8 10 9 5 10 3 10 4
样例输出
8 1 10 10 9 8 3 10 1 -1
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 #include<algorithm> 5 #define MIN(x,y)(x<y?x:y) 6 using namespace std; 7 const int INF=0x3f3f3f3f; 8 const int MAXN=100010; 9 const int MAXM=200010; 10 int top,N,S; 11 struct Edge 12 { 13 int from,to,val,next; 14 }; 15 Edge edg[MAXM]; 16 int head[MAXM],dis[MAXN],vis[MAXN]; 17 void add(int u,int v,int w) 18 { 19 Edge E={u,v,w,head[u]}; 20 edg[top]=E; 21 head[u]=top++; 22 } 23 int SPFA(int now) 24 { 25 queue<int>q; 26 memset(vis,0,sizeof(vis)); 27 memset(dis,INF,sizeof(dis)); 28 q.push(S); 29 dis[S]=0; 30 vis[S]=1; 31 while(!q.empty()) 32 { 33 int u=q.front(); 34 q.pop(); 35 vis[u]=0; 36 for(int i=head[u];i!=-1;i=edg[i].next) 37 { 38 int v=edg[i].to; 39 if(dis[v]>dis[u]+edg[i].val) 40 { 41 dis[v]=dis[u]+edg[i].val; 42 if(v==now)return u; 43 if(!vis[v]) 44 { 45 vis[v]=1; 46 q.push(v); 47 } 48 } 49 } 50 } 51 } 52 int main(){ 53 int M,a,b; 54 scanf("%d",&M); 55 while(M--){ 56 top=0; 57 scanf("%d%d",&N,&S); 58 memset(head,-1,sizeof(head)); 59 for(int i=0;i<N-1;i++){ 60 scanf("%d%d",&a,&b); 61 add(a,b,1); 62 add(b,a,1); 63 } 64 for(int i=1;i<=N;i++){ 65 if(i!=1)printf(" "); 66 if(i==S){ 67 printf("-1");continue; 68 } 69 int x=SPFA(i); 70 printf("%d",x); 71 } 72 puts(""); 73 } 74 return 0; 75 }
问题 J: Hidden Number
时间限制: 1 Sec 内存限制: 32 MB提交: 25 解决: 4
[提交][状态][讨论版]
题目描述
Your job is to find out the secret number hidden in a matrix, each of whose element is a digit ('0'-'9') or a letter ('A'-'Z'). You can see an example matrix in Figure 1.
The hidden number and other non-secret ones are coded in a matrix as sequences of digits in a decimal format. You should only consider sequences of digits D1 D2 ... Dn such that Dk+1 (1 <= k < n) is either right next to or immediately below Dk in the matrix. The secret you are seeking is the largest number coded in this manner.
Four coded numbers in the matrix in Figure 1, i.e., 908820, 23140037, 23900037, and 9930, are depicted in Figure 2. As you may see, in general, two or more coded numbers may share a common subsequence. In this case, the secret number is 23900037, which is the largest among the set of all coded numbers in the matrix.
In contrast, the sequences illustrated in Figure 3 should be excluded: 908A2 includes a letter; the fifth digit of 23149930 is above the fourth; the third digit of 90037 is below right of the second.
Write a program to figure out the secret number from a given matrix.
输入
The input consists of multiple data sets, each data set representing a matrix. The format of each data
set is as follows.
W H
C11C12 ... C1W
C21C22 ... C2W
...
CH1CH2 ... CHW
In the first line of a data set, two positive integers W and H are given. W indicates the width (the number
of columns) of the matrix, and H indicates the height (the number of rows) of the matrix. W+H is less
than or equal to 70.
H lines follow the first line, each of which corresponds to a row of the matrix in top to bottom order. The
i-th row consists of W characters Ci1Ci2 ... CiW in left to right order. You may assume that the matrix
includes at least one non-zero digit.
Following the last data set, two zeros in a line indicate the end of the input.
输出
For each data set, print the hidden number on a line. Leading zeros should be suppressed.
样例输入
7 4 9R2A993 0E314A0 8A900DE 820R037 6 7 JH03HE ID7722 0DA1AH 30C9G5 99971A CA7EAI AHLBEM 20 2 A1234567891234CBDEGH BDEDF908034265091499 0 0
样例输出
23900037 771971 12345908034265091499
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 using namespace std; 5 int vis[80][80]; 6 struct Node{ 7 int x,y; 8 char s[80]; 9 }; 10 queue<Node>dl; 11 Node a,b; 12 char map[80][80]; 13 int disx[2]={0,1}; 14 int disy[2]={1,0}; 15 int W,H; 16 bool judge(char *a,char *b){ 17 int t1,t2; 18 t1=strlen(a);t2=strlen(b); 19 if(t1>t2)return true; 20 else if(t1<t2)return false; 21 else if(strcmp(a,b)<0)return false; 22 else return true; 23 } 24 char ans[80]; 25 void cat(char *a,char b){ 26 int t1=strlen(a); 27 a[t1]=b; 28 a[t1+1]=' '; 29 } 30 void bfs(int sx,int sy){ 31 memset(vis,0,sizeof(vis)); 32 memset(a.s,0,sizeof(a.s)); 33 memset(b.s,0,sizeof(b.s)); 34 a.x=sx;a.y=sy; 35 cat(a.s,map[sx][sy]); 36 vis[sx][sy]=1; 37 dl.push(a); 38 while(!dl.empty()){ 39 a=dl.front(); 40 dl.pop(); 41 vis[a.x][a.y]=1; 42 if(judge(a.s,ans))strcpy(ans,a.s); 43 for(int i=0;i<2;i++){ 44 b.x=a.x+disx[i];b.y=a.y+disy[i]; 45 if(!vis[b.x][b.y]&&b.x>=0&&b.x<H&&b.y>=0&&b.y<W&&map[b.x][b.y]>='0'&&map[b.x][b.y]<='9') 46 { 47 strcpy(b.s,a.s); 48 cat(b.s,map[b.x][b.y]); 49 dl.push(b); 50 } 51 } 52 } 53 } 54 int main(){ 55 while(~scanf("%d%d",&W,&H),W||H){ 56 memset(ans,0,sizeof(ans)); 57 while(!dl.empty())dl.pop(); 58 for(int i=0;i<H;i++)scanf("%s",map[i]); 59 for(int i=0;i<H;i++) 60 for(int j=0;j<W;j++){ 61 if(map[i][j]>'0'&&map[i][j]<='9')bfs(i,j); 62 while(!dl.empty())dl.pop(); 63 } 64 printf("%s ",ans); 65 } 66 return 0; 67 }