重復(fù)小っ后面單字的首字母就可以了，或者可以直接打ltu，也可以出現(xiàn)小型的つ、其他的小型字母可以仿照此法。
很巧妙的算法，自愧不如啊
當(dāng)初就想著二分啊二分，結(jié)果還是沒有分出來，而且情況很復(fù)雜
下面的代碼的算法很巧妙，充分利用了有一個(gè)數(shù)出現(xiàn)的次數(shù)大于總數(shù)的一半這一條性質(zhì)
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)
就這么一個(gè)簡(jiǎn)單的剪枝，時(shí)間從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 }
一看就是一個(gè)遞推的題目，自己推了一會(huì)兒，推出來一個(gè)遞推公式，有點(diǎn)搓
F[i][j]，表示的是第一個(gè)的樓梯高度是i的情況下，用j塊積木的堆積方案
結(jié)果發(fā)現(xiàn)好像要用O(n^3)的時(shí)間復(fù)雜度才能解決，不過好在這個(gè)遞推公式對(duì)了
但是怎么都WA，自己驗(yàn)證了幾組比較小的數(shù)據(jù)，都對(duì)了
然后只能去Google一下，后來發(fā)現(xiàn)有個(gè)人說，這道題目有大數(shù)陷阱，用double就過了
一試，沒過-_-!!!，懷疑自己的地推公式對(duì)不對(duì)……
后來想了想，是不是我的輸出有問題，原來是cout << sum <<ｅｎｄｌ；
改成了ｐｒｉｎｔｆ（＂％０．０ｌｆ＼ｎ＂，ｓｕｍ）；
ＡＣ了，很神奇……
為什么在我自己的電腦上面，運(yùn)算出來的結(jié)果顯示的都是整數(shù)呢……，非得用個(gè)０．０ｌｆ這種東西才能過
看來還是對(duì)ｇｃｃ不了解……
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
一道很普通的搜索題目，但是必須剪枝，否則會(huì)超時(shí)
if(value!=w[i] && value!=w[j] && value!=w[k])
如果沒有這句剪枝就會(huì)超時(shí)……
剪枝很強(qiáng)大～
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 }
參考了別人的算法，數(shù)學(xué)果然是王道！
2001.11.4的 月+日= 11 + 4 = 奇數(shù)。。
由于無論是月加一還是日加一月日和的奇偶性都會(huì)發(fā)生變化, 除了2.28、9.30和11.30.
2.28、9.30、11.30明顯有必勝的策略:
2.28->3.28,
9.30->10.1,
11.30->12.1
所以除了剩余的兩個(gè)特殊的情況以外，其余只要滿足月+日等于偶數(shù)就有必勝的策略。
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吧
算法很簡(jiǎn)單，先按照來的時(shí)間和報(bào)酬排序
然后在一個(gè)一個(gè)的處理，未處理的就加入到suspend里面，等到下一輪處理
有個(gè)地方比較特殊，就是為處理的任務(wù)，如果他的截止時(shí)間在F之前，那么會(huì)算懲罰，如果超出了，就不算了
剛開始這個(gè)地方?jīng)]注意，所以貢獻(xiàn)了幾次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
這個(gè)Hello World過于牛逼了！
讓人崩潰的輸入格式
另外，數(shù)據(jù)量很大，用cin會(huì)超時(shí)
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
評(píng)論：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)
隨筆分類
隨筆檔案
相冊(cè)
搜索
最新評(píng)論
|
|