|
2008年10月10日
1 #include <iostream> 2 #include <map> 3 #include <vector> 4 #include <string> 5 #include <iomanip> 6 7 using namespace std; 8 enum PersonStyle {han_national,mongol_national,man_national,tibet,Sinkiang}; 9 string CityType[] = {"直辖市","省会","大城市"}; 10 string City[] = {"上海","沈阳","石家庄","西宁","西安","厦门","南京","南宁","广州","北京"}; 11 typedef multimap<string,string> USERTABLE; 12 typedef USERTABLE::const_iterator CIT; 13 map<PersonStyle,USERTABLE> map_city; 14 typedef map<PersonStyle,USERTABLE> ::const_iterator PER; 15 16 int main() 17 { 18 USERTABLE m_user1; 19 m_user1.insert(make_pair("直辖市","上海")); 20 m_user1.insert(make_pair("直辖市","北京")); 21 m_user1.insert(make_pair("直辖市","广州")); 22 23 map_city.insert(make_pair(han_national,m_user1)); 24 25 USERTABLE m_user2; 26 m_user2.insert(make_pair("省会","沈阳")); 27 m_user2.insert(make_pair("省会","西宁")); 28 m_user2.insert(make_pair("省会","南京")); 29 30 map_city.insert(make_pair(mongol_national,m_user2)); 31 32 33 for(PER it_per = map_city.begin();it_per != map_city.end();it_per++) 34 { 35 cout << "少数民族 " << it_per->first << " 所在的城市为:" << endl; 36 for(CIT it_cit = (it_per->second).begin();it_cit!=(it_per->second).end();it_cit++) 37 { 38 cout << setw(8) << "城市类型:" << it_cit->first << endl; 39 cout << setw(8) << " 城市:" << it_cit->second << endl; 40 } 41 } 42 system("pause"); 43 return 0; 44 } 45 46 47
2008年10月9日
摘要: 主流算法:
1.搜索 //回溯
2.DP(动态规划)
3.贪心
4.图论 //Dijkstra、最小生成树、网络流
5.数论 //解模线性方程
6.计算几何 //凸壳、同等安置矩形的并的面积与周长
7.组合数学 //Polya定理
8.模拟
9.数据结构 //并查集、堆
10.博弈论
//表示举例
非主流算法:
1.送分题
2.构造
3.高... 阅读全文
2008年10月8日
Problem Statement
You will be given two positive ints A and B.
Let C be the product of all integers between A and B,
inclusive.
The number C has a unique representation of the form C = D * 10^E, where D
and E are non-negative integers and the last digit of D is non-zero.
Write a method that will return the value of C formatted as a String of
the form "D * 10^E" (quotes for clarity only). Substitute the actual
values of D and E into the output. If D has more than 10 digits, only output
the first five and the last five digits of D, and separate them by three
periods.
Definition
Class:
|
PrettyPrintingProduct
|
Method:
|
prettyPrint
|
Parameters:
|
int, int
|
Returns:
|
String
|
Method signature:
|
String prettyPrint(int A, int B)
|
(be sure your method is public)
|
Notes
-The purpose of the last constraint is to disallow inputs
where precision problems could arise.
Constraints
-A will be between 1 and 1,000,000, inclusive.-B
will be between A and 1,000,000, inclusive.-If C has more than 10
digits, then the sixth most significant digit of C will be neither 0 nor
9.
Examples
0)
|
Returns: "36288 * 10^2"
|
1 * 2 * ... * 10 = 3628800 = 36288 * 10^2
|
|
1)
|
Returns: "7 * 10^0"
|
The product of all numbers between 7 and 7,
inclusive, is obviously 7.
|
|
2)
|
Returns: "2038974024 * 10^0"
|
For this input D has 10 digits.
|
|
3)
|
Returns: "28952...24024 * 10^0"
|
For this input D has 11 digits. Note that we
output three dots even if just one digit is missing in the output.
|
|
4)
|
Returns: "2923450236 * 10^1"
|
The actual value of C is larger than in the
previous example. However, C ends in a zero and therefore D only has 10
digits.
|
|
5)
|
Returns: "14806...28928 * 10^1163"
|
|
6)
|
Returns: "12164...08832 * 10^3"
|
Note that the last five digits of D can start with
a zero.
|
|
7)
|
Returns: "32382...26624 * 10^4"
|
1 2 #include <cmath> 3 #include <ctime> 4 #include <iostream> 5 #include <string> 6 #include <vector> 7 using namespace std; 8 9 typedef long long i64; 10 11 class PrettyPrintingProduct { 12 public: 13 string prettyPrint( int A, int B ); 14 }; 15 bool check(int A,int B,i64& D,i64& E){ 16 D=1;E=0; 17 for(int i=A;i<=B;i++){ 18 D*=i; 19 while(D%10LL==0LL) { 20 D/=10LL; 21 E++; 22 } 23 if(D>10000000000LL) return false; 24 } 25 return true; 26 } 27 28 string PrettyPrintingProduct::prettyPrint(int A,int B){ 29 i64 D,tens; 30 char str[256]; 31 32 if(check(A,B,D,tens)){ 33 cout<<D<<" "<<tens<<endl; 34 sprintf(str,"%lld * 10^%lld",D,tens); 35 return str; 36 } 37 38 i64 a=1,b=1; 39 tens=0; 40 for(int i=A;i<=B;i++){ 41 a*=i; 42 b*=i; 43 while(b%10LL==0LL) b/=10LL,tens++; 44 b%=1000000000000LL; 45 while(a>=1000000000000LL) a/=10LL; 46 } 47 while(a>=100000LL) a/=10LL; 48 b%=100000LL; 49 cout<<a<<" "<<b<<" "<<tens<<endl; 50 sprintf(str, "%lld%05lld * 10^%lld", a, b, tens); 51 return str; 52 } 53
1 #include <vector> 2 #include <list> 3 #include <map> 4 #include <set> 5 #include <deque> 6 #include <queue> 7 #include <stack> 8 #include <bitset> 9 #include <algorithm> 10 #include <functional> 11 #include <numeric> 12 #include <utility> 13 #include <sstream> 14 #include <iostream> 15 #include <iomanip> 16 #include <cstdio> 17 #include <cmath> 18 #include <cstdlib> 19 #include <cctype> 20 #include <string> 21 #include <cstring> 22 #include <cstdio> 23 #include <cmath> 24 #include <cstdlib> 25 #include <ctime> 26 27 using namespace std; 28 29 #define M 30 30 #define W 10 31 32 struct Node 33 { 34 int b[W]; 35 int head; 36 int ind; 37 }; 38 39 Node box[M]; 40 41 int cmp(const void *a,const void *b) 42 { 43 return (*(Node*)a).head-(*(Node*)b).head; 44 } 45 46 bool Isok(int a[],int b[],int m) 47 { 48 for (int i=0;i<m;i++) 49 { 50 if (a[i]>=b[i]) return false; 51 } 52 return true; 53 } 54 int main() 55 { 56 int n,m; 57 int p[M],q[M]; 58 while (scanf("%d%d",&n,&m)!=-1) 59 { 60 for (int i=0;i<n;i++) 61 { 62 for (int j=0;j<m;j++) 63 { 64 scanf("%d",&box[i].b[j]); 65 } 66 sort(box[i].b,box[i].b+m); 67 box[i].head=box[i].b[0]; 68 box[i].ind=i+1; 69 } 70 qsort(box,n,sizeof(box[0]),cmp); 71 72 p[0]=1; 73 q[0]=-1; 74 for (int i=1;i<n;i++) 75 { 76 int Max=0,t; 77 for (int j=i-1;j>=0;j--) 78 { 79 if (Isok(box[j].b,box[i].b,m)) 80 { 81 if (p[j]>Max) 82 { 83 Max=p[j]; 84 t=j; 85 } 86 } 87 } 88 if (Max) 89 { 90 p[i]=p[t]+1; 91 q[i]=t; 92 } 93 else 94 { 95 p[i]=1; 96 q[i]=-1; 97 } 98 } 99 100 vector<int> vi; 101 int Mi=0,Mii=0; 102 for (int i=0;i<n;i++) 103 if (Mii<p[i]) 104 { 105 Mi=i; 106 Mii=p[i]; 107 } 108 while (q[Mi]!=-1) 109 { 110 vi.push_back(box[Mi].ind); 111 Mi=q[Mi]; 112 } 113 vi.push_back(box[Mi].ind); 114 printf("%d\n%d",Mii,vi[vi.size()-1]); 115 for (int i=vi.size()-2;i>=0;i--) 116 printf(" %d",vi[i]); 117 printf("\n"); 118 } 119 return 0; 120 } 121
2008年10月7日
1 #include <vector> 2 #include <list> 3 #include <map> 4 #include <set> 5 #include <deque> 6 #include <queue> 7 #include <stack> 8 #include <bitset> 9 #include <algorithm> 10 #include <functional> 11 #include <numeric> 12 #include <utility> 13 #include <sstream> 14 #include <iostream> 15 #include <iomanip> 16 #include <cstdio> 17 #include <cmath> 18 #include <cstdlib> 19 #include <cctype> 20 #include <string> 21 #include <cstring> 22 #include <cstdio> 23 #include <cmath> 24 #include <cstdlib> 25 #include <ctime> 26 27 using namespace std; 28 29 int main(){ 30 int b1[3],b2[3],b3[3]; 31 char c[]="BGC"; 32 while(cin>>b1[0]>>b1[1]>>b1[2]>>b2[0]>>b2[1]>>b2[2]>>b3[0]>>b3[1]>>b3[2]){ 33 string s="zzzzzzz"; 34 int Min=2000000000; 35 for(int i=0;i<3;i++){ 36 for(int j=0;j<3;j++){ 37 if(i!=j){ 38 for(int k=0;k<3;k++){ 39 if(k!=i&&k!=j){ 40 string t=""; 41 t+=c[i]; 42 t+=c[j]; 43 t+=c[k]; 44 int s1=b2[i]+b3[i]; 45 int s2=b1[j]+b3[j]; 46 int s3=b1[k]+b2[k]; 47 48 if(s1+s2+s3<Min){ 49 Min=s1+s2+s3; 50 s=t; 51 } 52 else if(s1+s2+s3==Min){ 53 if(t<s){ 54 s=t; 55 } 56 } 57 } 58 } 59 } 60 } 61 } 62 cout<<s<<" "<<Min<<endl; 63 } 64 return 0; 65 } 66
摘要: 1. move a onto b在將a搬到b上之前,先將a和b上的積木放回原來的位置(例如:1就放回1的最開始位罝)2. move a over b在將a搬到b所在的那堆積木之上之前,先將a上的積木放回原來的位罝(b所在的那堆積木不動)3. pile a onto b將a本身和其上的積木一起放到b上,在搬之前b上方的積木放回原位4. pile a over b將a本身和其上的積木一起搬到到b所在的... 阅读全文
|