无界 - BlogJava

重复小っ后面单字的首字母就可以了，或者可以直接打ltu，也可以出现小型的つ、其他的小型字母可以仿照此法。

posted @ 2008-06-07 20:20 杨磊阅读(191) | 评论 (0) | 编辑收藏

很巧妙的算法，自愧不如啊

当初就想着二分啊二分，结果还是没有分出来，而且情况很复杂

下面的代码的算法很巧妙，充分利用了有一个数出现的次数大于总数的一半这一条性质

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 }

posted @ 2008-06-05 17:12 杨磊阅读(170) | 评论 (0) | 编辑收藏

原来拒信是这个样子的

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

posted @ 2008-06-04 23:38 杨磊阅读(222) | 评论 (0) | 编辑收藏

ZJU Online Judge 1204

剪枝是王道！！！

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 }

posted @ 2008-06-03 19:57 杨磊阅读(481) | 评论 (0) | 编辑收藏

ZJU Online Judge 1163

一看就是一个递推的题目，自己推了一会儿，推出来一个递推公式，有点搓
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

posted @ 2008-06-02 01:40 杨磊阅读(266) | 评论 (0) | 编辑收藏

ZJU Online Judge 1101

一道很普通的搜索题目，但是必须剪枝，否则会超时

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 }

posted @ 2008-05-29 20:53 杨磊阅读(194) | 评论 (0) | 编辑收藏

ZJU Online Judge 1024

参考了别人的算法，数学果然是王道！

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 }

posted @ 2008-05-29 12:36 杨磊阅读(301) | 评论 (0) | 编辑收藏

ZJU Onlie Judge 1012

这就是传说中的蘑菇题

题目的大意我就不说了，大家自己去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 }

posted @ 2008-05-27 14:06 杨磊阅读(325) | 评论 (0) | 编辑收藏

囧 To Death

http://www.fitzrovian.com/hello.html

这个Hello World过于牛逼了！

posted @ 2008-05-22 16:59 杨磊阅读(148) | 评论 (0) | 编辑收藏

ZJU Online Judge 2351

让人崩溃的输入格式

另外，数据量很大，用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 }

posted @ 2008-05-22 10:23 杨磊阅读(204) | 评论 (0) | 编辑收藏

留言簿(1)

随笔分类

随笔档案

相册

搜索

最新评论