DFS问题。 Continue reading
CategoryHDOJ
Problem Description
Once there was a special graph. This graph had n vertices and some edges. Each edge was either white or black. There was no edge connecting one vertex and the vertex itself. There was no two edges connecting the same pair of vertices. It is special because the each vertex is connected to at most two black edges and at most two white edges.
One day, the demon broke this graph by copying all the vertices and in one copy of the graph, the demon only keeps all the black edges, and in the other copy of the graph, the demon keeps all the white edges. Now people only knows there are w0 vertices which are connected with no white edges, w1 vertices which are connected with 1 white edges, w2 vertices which are connected with 2 white edges, b0 vertices which are connected with no black edges, b1 vertices which are connected with 1 black edges and b2 vertices which are connected with 2 black edges.
The precious graph should be fixed to guide people, so some people started to fix it. If multiple initial states satisfy the restriction described above, print any of them.
Input
The first line of the input is a single integer T (T≤700), indicating the number of testcases.
Each of the following T lines contains w0,w1,w2,b0,b1,b2. It is guaranteed that 1≤w0,w1,w2,b0,b1,b2≤2000 and b0+b1+b2=w0+w1+w2.
It is also guaranteed that the sum of all the numbers in the input file is less than 300000.
Output
For each testcase, if there is no available solution, print −1. Otherwise, print m in the first line, indicating the total number of edges. Each of the next m lines contains three integers x,y,t, which means there is an edge colored t connecting vertices x and y. t=0 means this edge white, and t=1 means this edge is black. Please be aware that this graph has no self-loop and no multiple edges. Please make sure that 1≤x,y≤b0+b1+b2.
Sample Input
2
1 1 1 1 1 1
1 2 2 1 2 2
Sample Output
-1
6
1 5 0
4 5 0
2 4 0
1 4 1
1 3 1
2 3 1
题目大意是构造一个无向图。先考虑白色边，构造常链连接1和2即可。注意排重。
参考代码：
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; #define sf scanf int T; int a[5],b[5]; int d[1000005]; int main() { sf("%d",&T); while(T--) { for(int i = 0;i<3;i++)sf("%d",a+i); for(int i = 0;i<3;i++)sf("%d",b+i); int sum = 0; for(int i = 0;i<3;i++)sum+=a[i]; if( (a[1]&1) || (b[1]&1) ) { puts("-1"); continue; } if(sum==4) { puts("4\n1 2 0\n1 3 0\n2 3 1\n3 4 1"); continue; } printf("%d\n",a[1]/2+a[2]+b[1]/2+b[2]); int t = 1; while(a[2]!=-1){printf("%d %d 0\n",t,t+1);t++;a[2]--;}t++; while(a[1]!=2){printf("%d %d 0\n",t,t+1);t+=2;a[1]-=2;} int tt = 0; for(int i = 1;i<=sum;i+=2) d[tt++] = i; for(int i = 2;i<=sum;i+=2)d[tt++] = i; t = 0; while(b[2]!=-1){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t++;b[2]--;}t++; while(b[1]!=2){printf("%d %d 1\n",min(d[t],d[t+1]),max(d[t],d[t+1]));t+=2;b[1]-=2;} } } |
Problem Description
We all know that Bin-Laden is a notorious terrorist, and he has disappeared for a long time. But recently, it is reported that he hides in Hang Zhou of China!
“Oh, God! How terrible! ”
Don’t be so afraid, guys. Although he hides in a cave of Hang Zhou, he dares not to go out. Laden is so bored recent years that he fling himself into some math problems, and he said that if anyone can solve his problem, he will give himself up!
Ha-ha! Obviously, Laden is too proud of his intelligence! But, what is his problem?
“Given some Chinese Coins (硬币) (three kinds– 1, 2, 5), and their number is num_1, num_2 and num_5 respectively, please output the minimum value that you cannot pay with given coins.”
You, super ACMer, should solve the problem easily, and don’t forget to take $25000000 from Bush!
Input
Input contains multiple test cases. Each test case contains 3 positive integers num_1, num_2 and num_5 (0<=num_i<=1000). A test case containing 0 0 0 terminates the input and this test case is not to be processed.
Output
Output the minimum positive value that one cannot pay with given coins, one line for one case.
Sample Input
1 1 3
0 0 0
Sample Output
4
参考代码：
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<cstdio> #include<cstring> #include<cmath> int c1[1000],c2[10000]; int main() { int n1,n2,n5; while(scanf("%d%d%d",&n1,&n2,&n5)==3,n1+n2+n5) { int n,i,j,k; n=n1+n2*2+n5*5; for(i=0;i<=n;i++)//init c1 c2 { c1[i]=0;c2[i]=0; } for(i=0;i<=n1;i++)//只有 1 { c1[i]=1; } for(i=0;i<=n1;i++)//存在1和2 { for(j=0;j<=n2*2;j+=2) { c2[i+j]+=c1[i]; } } for(k=0;k<=n1+n2*2;k++) { c1[k]=c2[k];c2[k]=0; } for(j=0;j<=n1+n2*2;j++)//存在1、2、5 { for(k=0;k<=n5*5;k+=5) { c2[k+j]+=c1[j]; } } for(i=0;i<=5*n5+2*n2+n1;i++) { c1[i]=c2[i];c2[i]=0; } bool flag=0; for(i=0;i<=n;i++) { if(c1[i]==0) { printf("%d\n",i); flag=1; break; } } if(!flag) printf("%d\n",n+1); } return 0; } |
Problem Description
Most bicycle speedometers work by using a Hall Effect sensor fastened to the front fork of the bicycle. A magnet is attached to one of the spokes on the front wheel so that it will line up with the Hall Effect switch once per revolution of the wheel. The speedometer monitors the sensor to count wheel revolutions. If the diameter of the wheel is known, the distance traveled can be easily be calculated if you know how many revolutions the wheel has made. In addition, if the time it takes to complete the revolutions is known, the average speed can also be calculated.
For this problem, you will write a program to determine the total distance traveled (in miles) and the average speed (in Miles Per Hour) given the wheel diameter, the number of revolutions and the total time of the trip. You can assume that the front wheel never leaves the ground, and there is no slipping or skidding.
Input
Input consists of multiple datasets, one per line, of the form:
diameter revolutions time
The diameter is expressed in inches as a floating point value. The revolutions is an integer value. The time is expressed in seconds as a floating point value. Input ends when the value of revolutions is 0 (zero).
Output
For each data set, print:
Trip #N: distance MPH
Of course N should be replaced by the data set number, distance by the total distance in miles (accurate to 2 decimal places) and MPH by the speed in miles per hour (accurate to 2 decimal places). Your program should not generate any output for the ending case when revolutions is 0.
Constants
For p use the value: 3.1415927.
There are 5280 feet in a mile.
There are 12 inches in a foot.
There are 60 minutes in an hour.
There are 60 seconds in a minute.
There are 201.168 meters in a furlong.
Sample Input
26 1000 5
27.25 873234 3000
26 0 1000
Sample Output
Trip #1: 1.29 928.20
Trip #2: 1179.86 1415.84
一道数学题。简单水过。注意格式即可。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include<stdio.h> #define Pi 3.1415927 int main() { int n,c=0; double t,d,v,s; while(scanf("%lf%d%lf",&d,&n,&t)!=EOF && n!=0) { s=n*Pi*d/12/5280; v=s/(t/60/60); printf("Trip #%d: %.2lf %.2lf\n",++c,s,v); } return 0; } |
该来的总是会来的，写一道最头痛的网络流问题。
Continue reading
Problem Description
Reverse Polish notation (RPN) is a method for representing expressions in which the operator symbol is placed after the arguments being operated on.
Polish notation, in which the operator comes before the operands, was invented in the 1920s by the Polish mathematician Jan Lucasiewicz.
In the late 1950s, Australian philosopher and computer scientist Charles L. Hamblin suggested placing the operator after the operands and hence created reverse polish notation.
RPN has the property that brackets are not required to represent the order of evaluation or grouping of the terms.
RPN expressions are simply evaluated from left to right and this greatly simplifies the computation of the expression within computer programs.
As an example, the arithmetic expression (3+4)*5 can be expressed in RPN as 3 4 + 5 *.
Reverse Polish notation, also known as postfix notation, contrasts with the infix notation of standard arithmetic expressions in which the operator symbol appears between the operands. So Polish notation just as prefix notation.
Now, give you a string of standard arithmetic expressions, please tell me the Polish notation and the value of expressions.
Input
There’re have multi-case. Every case put in one line, the expressions just contain some positive integers(all less than 100, the number of integers less than 20), bi-operand operators(only have 3 kinds : +,-,*) and some brackets'(‘,’)’.
you can assume the expressions was valid.
Output
Each case output the Polish notation in first line, and the result of expressions was output in second line.
all of the answers are no any spaces and blank line.the answer will be not exceed the 64-signed integer.
Sample Input
1+2-3*(4-5)
1+2*(3-4)-5*6
Sample Output
Case 1:
– + 1 2 * 3 – 4 5
6
Case 2:
– + 1 * 2 – 3 4 * 5 6
-31
题目考察表达式的转换将中缀表达式转换成前置表达式（波兰式），并计算出结果。可以直接套模板……需要注意表达式中空格的位置；字符串需要用__int64存贮。
关于前置表达式和后置表达式的转换方法可以参考这篇博文：波兰式、逆波兰式与表达式求值
参考代码：
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
#include <iostream> #include <string> #include <algorithm> using namespace std; char stack[500]; int top; //栈顶指针 char output[500], input[500]; int outLen; int priority(char op) //定义运算符优先级 { if (op=='+' || op=='-') return 1; if (op=='*' || op=='/') return 2; else return 0; } bool isOperator(char op) { return (op=='+' || op=='-' || op=='*' || op=='/'); } void Polish(char *s,int len) { memset(output,'\0',sizeof output); outLen = 0; for (int i=len-1; i >= 0; --i) { if (isdigit(s[i])) { output[outLen++] = s[i]; while (i-1 >= 0 && isdigit(s[i-1])) { output[outLen++] = s[i-1]; --i; } output[outLen++] = ' '; } if (s[i]==')') { ++top; stack[top] = s[i]; } while (isOperator(s[i])) { if (top==0 || stack[top]==')' || priority(s[i]) >= priority(stack[top])) { ++top; stack[top] = s[i]; break; } else { output[outLen++] = stack[top]; output[outLen++] = ' '; --top; } } if (s[i]=='(') { while (stack[top]!=')') { output[outLen++] = stack[top]; output[outLen++] = ' '; --top; } --top; } } while (top!=0) { output[outLen++] = stack[top]; output[outLen++] = ' '; --top; } } char DstBuf[200]; char* OP(char* op1,char* op2,char op) { __int64 res = 0; if (op=='+') res = _atoi64(op1) + _atoi64(op2); else if (op=='-') res = _atoi64(op1) - _atoi64(op2); else if (op=='*') res = _atoi64(op1) * _atoi64(op2); else if (op=='/') res = _atoi64(op1) / _atoi64(op2); _i64toa(res,DstBuf,10); return DstBuf; } char cSt1[200][80], cSt2[200][80]; __int64 calc(char *s) { int top1=0, top2=0, i; for (i=0; s[i]; ++i) { if (s[i] && s[i] != ' ') { ++top1; sscanf(s+i,"%s",cSt1[top1]); while (s[i] && s[i] != ' ') ++i; } } while (top1 != 0) { if (!isdigit(cSt1[top1][0])) { OP(cSt2[top2], cSt2[top2-1], cSt1[top1][0]); memcpy(cSt2[top2-1],DstBuf,sizeof DstBuf); --top2; --top1; } else { ++top2; memcpy(cSt2[top2],cSt1[top1],sizeof cSt1[top1]); --top1; } } return _atoi64(cSt2[1]); } int main() { int T = 1; while (gets(input)) { Polish(input, strlen(input)); reverse(output,output+outLen-1); output[outLen-1] = '\0'; printf("Case %d:\n%s\n",T++,output); printf("%I64d\n",calc(output));//注意要__int64 } return 0; } |
Problem Description
Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!
Input
One N in one line, process to the end of file.
Output
For each N, output N! in one line.
Sample Input
1
2
3
Sample Output
1
2
6
要求计算10000以内的阶乘,典型的大数问题.这里用的是 五位一存的方法. 关于X位一存的解释可以看这篇文章. 注意特殊情况(0,1)下的处理.
|
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 32 33 34 35 |
#include <stdio.h> #include <string.h> #define MOD 100000 int main() { int a[8000]; int i,k,n,t,la; while(~scanf("%d",&n)) { if(n==0||n==1) {printf("1\n");continue;} a[0] = 1; la = 1; t = 0; for(k=2; k<=n; k++) { for(i=0; i<la; i++) { t += k * a[i]; a[i] = t%MOD; t = t/MOD; } if (t > 0) { a[la++] = t; t = 0; } } printf("%d",a[la-1]); for(i=la-2; i>=0; i--) printf("%05d",a[i]); printf("\n"); } return 0; } |
Here is a famous story in Chinese history.
“That was about 2300 years ago. General Tian Ji was a high official in the country Qi. He likes to play horse racing with the king and others.”
“Both of Tian and the king have three horses in different classes, namely, regular, plus, and super. The rule is to have three rounds in a match; each of the horses must be used in one round. The winner of a single round takes two hundred silver dollars from the loser.”
“Being the most powerful man in the country, the king has so nice horses that in each class his horse is better than Tian’s. As a result, each time the king takes six hundred silver dollars from Tian.”
“Tian Ji was not happy about that, until he met Sun Bin, one of the most famous generals in Chinese history. Using a little trick due to Sun, Tian Ji brought home two hundred silver dollars and such a grace in the next match.”
“It was a rather simple trick. Using his regular class horse race against the super class from the king, they will certainly lose that round. But then his plus beat the king’s regular, and his super beat the king’s plus. What a simple trick. And how do you think of Tian Ji, the high ranked official in China?”
Were Tian Ji lives in nowadays, he will certainly laugh at himself. Even more, were he sitting in the ACM contest right now, he may discover that the horse racing problem can be simply viewed as finding the maximum matching in a bipartite graph. Draw Tian’s horses on one side, and the king’s horses on the other. Whenever one of Tian’s horses can beat one from the king, we draw an edge between them, meaning we wish to establish this pair. Then, the problem of winning as many rounds as possible is just to find the maximum matching in this graph. If there are ties, the problem becomes more complicated, he needs to assign weights 0, 1, or -1 to all the possible edges, and find a maximum weighted perfect matching…
However, the horse racing problem is a very special case of bipartite matching. The graph is decided by the speed of the horses — a vertex of higher speed always beat a vertex of lower speed. In this case, the weighted bipartite matching algorithm is a too advanced tool to deal with the problem.
In this problem, you are asked to write a program to solve this special case of matching problem.
Input
The input consists of up to 50 test cases. Each case starts with a positive integer n (n <= 1000) on the first line, which is the number of horses on each side. The next n integers on the second line are the speeds of Tian’s horses. Then the next n integers on the third line are the speeds of the king’s horses. The input ends with a line that has a single 0 after the last test case.
Output
For each input case, output a line containing a single number, which is the maximum money Tian Ji will get, in silver dollars.
Sample Input
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
Sample Output
200
0
0
贪心问题的简单应用.首先将田忌的马和齐王的马做个排序.然后分类讨论
放上代码:
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<stdio.h> #include<stdlib.h> #include<algorithm> int cmp(const void*a ,const void*b) { return *(int *)b-*(int *)a; } int main() { int i,n; int tian,king; int fa,fb,la,lb; while(~scanf("%d",&n)&&n!=0) { int a[1001]={0},b[1001]={0}; getchar(); tian=king=0; for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++) scanf("%d",&b[i]); qsort(a,n,sizeof(int),cmp); qsort(b,n,sizeof(int),cmp); fa=fb=0; la=lb=n-1; while(fa!=la) { if(a[fa]>b[fb]) { tian++; fa++; fb++; } else if(a[la]>b[lb]) { tian++; la--; lb--; } else if(a[la]<b[fb]) { king++; la--; fb++; } else break; } if(a[fa]>b[fb]) tian++; else if(a[fa]<b[fb]) king++; printf("%dn",(tian-king)*200); } return 0; } |
Problem Description
《Shui Hu Zhuan》，also 《Water Margin》was written by Shi Nai’an — an writer of Yuan and Ming dynasty. 《Shui Hu Zhuan》is one of the Four Great Classical Novels of Chinese literature. It tells a story about 108 outlaws. They came from different backgrounds (including scholars, fishermen, imperial drill instructors etc.), and all of them eventually came to occupy Mout Liang(or Liangshan Marsh) and elected Song Jiang as their leader.
In order to encourage his military officers, Song Jiang always made a rank list after every battle. In the rank list, all 108 outlaws were ranked by the number of enemies he/she killed in the battle. The more enemies one killed, one’s rank is higher. If two outlaws killed the same number of enemies, the one whose name is smaller in alphabet order had higher rank. Now please help Song Jiang to make the rank list and answer some queries based on the rank list.
Input
There are no more than 20 test cases.
For each test case:
The first line is an integer N (0<n&<200), indicating that there are N outlaws.
Then N lines follow. Each line contains a string S and an integer K(0<k<300), meaning an outlaw’s name and the number of enemies he/she had killed. A name consists only letters, and its length is between 1 and 50(inclusive). Every name is unique.
The next line is an integer M (0<m<200) ,indicating that there are M queries.
Then M queries follow. Each query is a line containing an outlaw’s name.
The input ends with n = 0
Output
For each test case, print the rank list first. For this part in the output ,each line contains an outlaw’s name and the number of enemies he killed.
Then, for each name in the query of the input, print the outlaw’s rank. Each outlaw had a major rank and a minor rank. One’s major rank is one plus the number of outlaws who killed more enemies than him/her did.One’s minor rank is one plus the number of outlaws who killed the same number of enemies as he/she did but whose name is smaller in alphabet order than his/hers. For each query, if the minor rank is 1, then print the major rank only. Or else Print the major rank, blank , and then the minor rank. It’s guaranteed that each query has an answer for it.
Sample Input
5
WuSong 12
LuZhishen 12
SongJiang 13
LuJunyi 1
HuaRong 15
5
WuSong
LuJunyi
LuZhishen
HuaRong
SongJiang
0
Sample Output
HuaRong 15
SongJiang 13
LuZhishen 12
WuSong 12
LuJunyi 1
3 2
5
3
1
2
简单排序，直接上代码：
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<algorithm> #include<iostream> #include<map> #include<string.h> using namespace std; #define N 205 struct hero_t{ string s; int i, n; } heros[N]; struct node_t { int mmin, mmax; node_t() {} node_t(int a, int b) { mmin = a; mmax = b; } } node; //struct heros[N]; bool comp(hero_t a, hero_t b) { if (a.n == b.n) return a.s < b.s; else return a.n > b.n; } int main() { int n, m; int i, j, k, id = 0; string s; node_t nd; while (cin>>n && n) { for (i=0; i<n; ++i) { heros[i].i = i; cin>>heros[i].s>>heros[i].n; } sort(heros, heros+n, comp); for (i=0; i<n; ++i) cout <<heros[i].s<<' '<<heros[i].n<<endl; map<string,node_t> tb; i = 0; while (i < n) { j = 1; while ((i+j)<n && heros[i+j].n == heros[i].n) ++j; if (j > 1) { for (k=0; k<j; ++k) { tb[heros[i+k].s] = node_t(k+1, i+1); } i += j; } else { tb[heros[i].s] = node_t(1, i+1); ++i; } } cin >>m; while (m--) { cin >>s; nd = tb[s]; if (nd.mmin == 1) cout <<nd.mmax<<endl; else cout <<nd.mmax<<' '<<nd.mmin<<endl; } id = 0; } return 0; } |
浙ICP备15034340号 | 浙公网安备 33011802000441号
| 阿里云提供计算服务 | 本站由WordPress驱动
© 2019 落絮飞雁的个人网站
Theme by Anders Norén — Up ↑