随笔 - 6, 文章 - 0, 评论 - 3, 引用 - 0
数据加载中……

2008年10月10日

No_name

 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 

posted @ 2008-10-10 13:38 水牛♂Toto 阅读(156) | 评论 (0)编辑 收藏

2008年10月9日

PKU_算法_分类

     摘要: 主流算法: 1.搜索 //回溯 2.DP(动态规划)  3.贪心  4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya定理 8.模拟  9.数据结构 //并查集、堆 10.博弈论  //表示举例   非主流算法: 1.送分题  2.构造  3.高...  阅读全文

posted @ 2008-10-09 13:52 水牛♂Toto 阅读(3335) | 评论 (1)编辑 收藏

2008年10月8日

SRM_420_div2_1000pt

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)    

1

10

 

Returns: "36288 * 10^2"

1 * 2 * ... * 10 = 3628800 = 36288 * 10^2

 

1)    

7

7

 

Returns: "7 * 10^0"

The product of all numbers between 7 and 7, inclusive, is obviously 7.

 

2)    

211

214

 

Returns: "2038974024 * 10^0"

For this input D has 10 digits.

 

3)    

411

414

 

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)    

412

415

 

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)    

47

4700

 

Returns: "14806...28928 * 10^1163"

 

 

6)    

1

19

 

Returns: "12164...08832 * 10^3"

Note that the last five digits of D can start with a zero.

 

7)    

13

25

 

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 


posted @ 2008-10-08 16:41 水牛♂Toto 阅读(193) | 评论 (0)编辑 收藏

UVA_103

  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 

posted @ 2008-10-08 10:06 水牛♂Toto 阅读(222) | 评论 (0)编辑 收藏

2008年10月7日

UVA_102

 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 

posted @ 2008-10-07 23:51 水牛♂Toto 阅读(257) | 评论 (0)编辑 收藏

UVA_101

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

posted @ 2008-10-07 23:50 水牛♂Toto 阅读(513) | 评论 (2)编辑 收藏