重復小っ后面單字的首字母就可以了，或者可以直接打ltu，也可以出現小型的つ、其他的小型字母可以仿照此法。
很巧妙的算法，自愧不如啊
當初就想著二分啊二分，結果還是沒有分出來，而且情況很復雜
下面的代碼的算法很巧妙，充分利用了有一個數出現的次數大于總數的一半這一條性質
1 #include<stdio.h>
2 int main()
3 {
4 int i,counter,answer,n,data;
5 while(scanf("%d",&n)!=EOF)
6 {
7 counter=0;
8 for(i=1;i<=n;i++)
9 {
10 scanf("%d",&data);
11 if (counter == 0)
12 {
13 answer=data;
14 counter=1;
15 }
16 else if (answer == data)
17 {
18 counter++;
19 }
20 else
21 counter--;
22 }
23 printf("%d\n",answer);
24 }
25 return 0;
26 }
Hi Lei Yang,
It was a pleasure meeting you and we
want to thank you for taking the time to interview with us for the Software
Engineering Intern - Beijing position. The interview team was
impressed with your background and accomplishments, and enjoyed getting to know
you. We carefully reviewed your
background and experience, and though we do not have a position that is a
strong match with your qualifications at this time, we will be keeping your
resume active in our system. We will
continue to use our database to match your profile with new opportunities and
will reach out to you if we find an opening for which you may be qualified.
Thanks again for your interest in Google's
careers and unique culture; we hope you will remain enthusiastic about our
company. If you have any questions,
please feel free to contact me at libin@google.com.
Kind Regards,
Bin Li
Google People Operations
剪枝是王道！！！
if (sum+number[j]<=Max)
就這么一個簡單的剪枝，時間從10+秒變成了0.85
1 #include <iostream>
2 #include <algorithm>
3 using namespace std;
4
5 int number[31];
6
7 bool used[31];
8
9 int get[31];
10
11 int Max;
12
13 bool foundone = false;
14
15 bool compare(int a, int b)
16 {
17 return a < b;
18 }
19
20 bool binarysearch(int beg, int end,int value)
21 {
22 bool found = false;
23 int mid = 0;
24
25 while ( beg <= end )
26 {
27 mid = ( beg + end ) / 2 ;
28 if ( number[mid] > value )
29 end = mid-1 ;
30 else if ( number[mid] < value )
31 beg = mid+1 ;
32 else
33 {
34 found = true;
35 break;
36 }
37 }
38 return found;
39 }
40 void solve(int total,int start,int deep,int target,long sum)
41 {
42 if (deep==target)
43 {
44 if (binarysearch(0,total-1,sum)==true)
45 {
46 foundone = true;
47 for (int i = 0; i < target; i++)
48 {
49 if (i!=target-1)
50 printf("%d+",get[i]);
51 else
52 printf("%d=",get[i]);
53 }
54 printf("%d\n",sum);
55 }
56 }
57 else
58 for (int j = start; j < total; j++)
59 if (used[j]==false)
60 {
61 if (sum+number[j]<=Max)
62 {
63 sum+=number[j];
64 used[j] = true;
65 get[deep] = number[j];
66 solve(total,j+1,deep+1,target,sum);
67 get[deep] = 0;
68 sum-=number[j];
69 used[j] = false;
70 }
71 }
72 }
73 int main()
74 {
75 int N;
76 cin >> N;
77 for (int i = 0; i < N; i++)
78 {
79 int M;
80 cin >> M;
81 foundone = false;
82
83 for (int j = 0; j < M; j++)
84 scanf("%d",&number[j]);
85
86 sort(number,number+M,compare);
87
88 for (int j = 0; j < M; j++)
89 used[j] = false;
90
91 Max = number[M-1];
92
93 for (int j = 2; j < M; j++)
94 solve(M,0,0,j,0);
95
96 if (!foundone)
97 cout << "Can't find any equations." << endl;
98
99 cout << endl;
100 }
101 //system("pause");
102 return 0;
103 }
一看就是一個遞推的題目，自己推了一會兒，推出來一個遞推公式，有點搓
F[i][j]，表示的是第一個的樓梯高度是i的情況下，用j塊積木的堆積方案
結果發現好像要用O(n^3)的時間復雜度才能解決，不過好在這個遞推公式對了
但是怎么都WA，自己驗證了幾組比較小的數據，都對了
然后只能去Google一下，后來發現有個人說，這道題目有大數陷阱，用double就過了
一試，沒過-_-!!!，懷疑自己的地推公式對不對……
后來想了想，是不是我的輸出有問題，原來是cout << sum <<ｅｎｄｌ；
改成了ｐｒｉｎｔｆ（＂％０．０ｌｆ＼ｎ＂，ｓｕｍ）；
ＡＣ了，很神奇……
為什么在我自己的電腦上面，運算出來的結果顯示的都是整數呢……，非得用個０．０ｌｆ這種東西才能過
看來還是對ｇｃｃ不了解……
1 #include <iostream>
2
3 using namespace std;
4
5 double F[505][505];
6
7 int main()
8 {
9
10 for (int i = 1; i < 505; i++)
11 for (int j = 1; j < 505; j++)
12 {
13 if (i!=j)
14 F[i][j] = 0;
15 else
16 F[i][j] = 1;
17 }
18
19 for (int i = 3; i < 505; i++)
20 for (int j = 1; j <= (i-1)/2; j++)
21 for (int k = j + 1; k <= i - 1; k++)
22 F[j][i] += F[k][i-j];
23
24 int N;
25 while (cin >> N && N!=0)
26 {
27 double sum = 0.0;
28 for (int i = 1; i <= (N-1)/2;i++)
29 sum+=F[i][N];
30 printf("%0.0lf\n",sum);
31 }
32
33 return 0;
34 }
35
一道很普通的搜索題目，但是必須剪枝，否則會超時
if(value!=w[i] && value!=w[j] && value!=w[k])
如果沒有這句剪枝就會超時……
剪枝很強大～
1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 long w[1000];
7
8 int compare (const void * a, const void * b)
9 {
10 return ( *(int*)a - *(int*)b );
11 }
12
13 int main()
14 {
15 int N;
16 while (cin >> N && N!=0)
17 {
18 int found = false;
19
20 if (N<4)
21 {
22 cout << "no solution" << endl ;
23 continue ;
24 }
25 for (int i = 0; i < N; i++)
26 cin >> w[i];
27
28 qsort(w,(size_t)N,sizeof(long),compare);
29
30 for (int i = N - 1; i >=0; i--)
31 {
32 for (int k = N - 1; k >=0; k--)
33 {
34 if (i == k) continue;
35 for (int j = k - 1; j >=0; j--)
36 {
37 if (j == i) continue;
38 long value = w[i] - w[j] - w[k];
39 if(value!=w[i] && value!=w[j] && value!=w[k])
40 {
41 int mid ;
42 int beg = 0;
43 int end = N - 1;
44 bool searchfound = false;
45 while ( beg <= end )
46 {
47 mid = ( beg + end ) / 2 ;
48 if ( w[mid] > value )
49 end = mid-1 ;
50 else if ( w[mid] < value )
51 beg = mid+1 ;
52 else
53 {
54 searchfound = true;
55 break;
56 }
57 }
58 if (searchfound==true)
59 {
60 cout << w[i] << endl;
61 found = true;
62 goto out;
63 }
64 }
65 }
66 }
67 }
68 out:if (!found)
69 cout << "no solution" << endl;
70 }
71 return 0;
72 }
參考了別人的算法，數學果然是王道！
2001.11.4的 月+日= 11 + 4 = 奇數。。
由于無論是月加一還是日加一月日和的奇偶性都會發生變化, 除了2.28、9.30和11.30.
2.28、9.30、11.30明顯有必勝的策略:
2.28->3.28,
9.30->10.1,
11.30->12.1
所以除了剩余的兩個特殊的情況以外，其余只要滿足月+日等于偶數就有必勝的策略。
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 int N;
8 cin >> N;
9 for (int i = 0;i < N; i++)
10 {
11 int yy,mm,dd;
12 cin >> yy >> mm >> dd;
13 bool flag = false;
14 if (mm==2 && dd==28)
15 flag = true;
16 else if (mm==9 && dd==30)
17 flag = true;
18 else if (mm==11 && dd==30)
19 flag = true;
20 else
21 {
22 if ((mm+dd)%2==0)
23 flag = true;
24 }
25 if (flag)
26 cout << "YES" << endl;
27 else
28 cout << "NO" << endl;
29 }
30 }
這就是傳說中的蘑菇題
題目的大意我就不說了，大家自己去google一下吧，有人說過了
就算鍛煉了一下用vector,algorithm吧
算法很簡單，先按照來的時間和報酬排序
然后在一個一個的處理，未處理的就加入到suspend里面，等到下一輪處理
有個地方比較特殊，就是為處理的任務，如果他的截止時間在F之前，那么會算懲罰，如果超出了，就不算了
剛開始這個地方沒注意，所以貢獻了幾次WA
1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4 using namespace std;
5
6 struct rect
7 {
8 public:
9 rect(int a,int b,int c,int d,int e,int f,int g):m_a(a),m_b(b),m_c(c),m_d(d),m_e(e),m_f(f),m_g(g){}
10 int m_a,m_b,m_c,m_d,m_e,m_f,m_g;
11 };
12
13 vector<rect> job,suspend;
14 vector<rect>::iterator it;
15
16 bool compare(rect a,rect b)
17 {
18 if (a.m_c<b.m_c)
19 return 1;
20 else if (a.m_c>b.m_c)
21 return 0;
22 else
23 {
24 if (a.m_e>b.m_e)
25 return 1;
26 else
27 return 0;
28 }
29 }
30
31 int main()
32 {
33 int F;
34 int Case = 1;
35
36 cin >> F;
37 while (F!=0)
38 {
39 int M,N,L;
40 cin >> M >> N >> L;
41
42 //count the number of job
43 int totaljob = 0;
44
45 //initialize
46 job.clear();
47 suspend.clear();
48
49 //input
50 for (int i = 0; i < L; i++)
51 {
52
53 int a,b,c,d,e,f,g;
54
55 cin >> a >> b >> c >> d >> e >> f >> g;
56
57 //Arraive before timeline
58 if (c<F)
59 {
60 rect *temp = new rect(a,b,c,d,e,f,g);
61 job.push_back(*temp);
62 totaljob++;
63 }
64 }
65
66 //sort the jobs according to the arriving time
67 sort(job.begin(),job.end(),compare);
68
69 it = job.begin();
70 long totalvalue = 0;
71
72 for (int time = 0; time < F; time++)
73 {
74 int mm = M;
75 int nn = N;
76
77 while (it != job.end() && time >= it->m_c)
78 {
79 suspend.push_back(*it);
80 it++;
81 }
82
83 vector<rect>::iterator temp;
84 temp = suspend.begin();
85
86 while (temp!=suspend.end())
87 {
88 if (mm>=temp->m_a && nn>=temp->m_b)
89 {
90 mm-=temp->m_a;
91 nn-=temp->m_b;
92 totalvalue+=temp->m_e;
93 if (time + 1< temp->m_d)
94 totalvalue+=temp->m_f*(temp->m_d - time - 1 );
95 else if (time + 1 > temp->m_d)
96 totalvalue-=temp->m_g*(time + 1 - temp->m_d);
97 suspend.erase(temp);
98 temp = suspend.begin();
99 }
100 else
101 temp++;
102
103 }
104 }
105
106 vector<rect>::iterator temp;
107
108 if (!suspend.empty())
109 {
110 for (temp = suspend.begin();temp!=suspend.end();temp++)
111 {
112 if (temp->m_d<=F)
113 totalvalue-=(F - temp->m_d)*temp->m_g;
114 }
115 }
116 //for (it = job.begin(); it!=job.end(); it++)
117 // cout << it->m_a << " " << it->m_b << " " << it->m_c << " " << it->m_d << " " << it->m_e
118 // << " " << it->m_f << " " << it->m_g << endl;
119
120
121
122 cout << "Case " << Case++ << ": " << totalvalue << endl << endl;
123 cin >> F;
124 }
125 return 0;
126 }
http://www.fitzrovian.com/hello.html
這個Hello World過于牛逼了！
讓人崩潰的輸入格式
另外，數據量很大，用cin會超時
1 #include <iostream>
2 #include <cmath>
3
4 using namespace std;
5
6 int main()
7 {
8 int N;
9 cin >> N;
10 getchar();
11 for (int i = 0; i < N; i++)
12 {
13 double ka,b;
14 int m,n;
15 scanf("%lf %lf %d %d",&ka,&b,&m,&n);
16 //cin >> ka >> b >> m >> n;
17 while (ka!=0.0 && b!=0.0 && m!=0 && n!=0)
18 {
19 double x = ((-1)*ka+sqrt(ka*ka+4*m*n*ka*b))/(2*m*n);
20 double pH = -log10(m*x);
21 printf("%.3f\n",pH);
22 scanf("%lf %lf %d %d",&ka,&b,&m,&n);
23 //cin >> ka >> b >> m >> n;
24 }
25
26 if (i!=N-1) {
27 printf("\n");
28 getchar();
29 }
30 }
31 //system("pause");
32 return 0;
33 }
|
|
|
隨筆：99
文章：-1
評論：17
引用：0
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 29 | 30 | 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 | 1 | 2 | | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
留言簿(1)
隨筆分類
隨筆檔案
相冊
搜索
最新評論
|
|