DFS问题。 Continue reading
CategoryACM
ACM的各类题解以及相关算法
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
该来的总是会来的，写一道最头痛的网络流问题。
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; } |
浙ICP备15034340号 | 浙公网安备 33011802000441号
| 阿里云提供计算服务 | 本站由WordPress驱动
© 2019 落絮飞雁的个人网站
Theme by Anders Norén — Up ↑