|
|
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所在的... 阅读全文
|