Life of xhu

About

HOJ_1084 & HOJ_1408

Jan 24, 2014

  |   #C++   |   #Algorithm

今天早上在被窝里,突然想用手机看看我的这个博客,然后打开欧朋输入网址,幸运的是今天Heroku没有被墙,可是在欧朋打开的页面上,左下角的四个导航按键却不能点击,奇了怪了。

想了一下,恍然大悟,原来都是因为我自己偷懒,这四个按键都是用的p文字段落元素加上Javascript控制的页面跳转语句,而欧朋经过服务器的压缩之后,是会去掉Javascript脚本的,所以在欧朋上,这个按键是无法进行点击和跳转的。

想到原因,当然就要解决了,我还是老老实实用a放在p里了,这样欧朋上点击链接就可以跳转了。

然后照例是HOJ上的水题:

  1. 1084: 理解题目以后并不难,就是把一本书的每一页在两倍大小的纸上打印出来,稍微想一下就能知道大概是什么情况,但是要注意的是,如果书只有一页,只会打印第一张纸的正面,而不会打印反面,只有一行输出。

    代码如下:

     #include <iostream>
     using namespace std;
    
     int main(){
         int pages, sheets;
         while(cin >> pages){
             if(pages == 0)
                 break;
             else{
                 if(pages == 1)
                     cout << "Printing order for 1 pages:\nSheet 1, front: Blank, 1" << endl;
                 else{
                     cout << "Printing order for " << pages << " pages:" << endl;
                     sheets = pages % 4 == 0 ? pages / 4 : pages / 4 + 1;
                     //cout << sheets << endl;
                     for(int i = 1, j = 4 * sheets; i != j + 1; i++, j--){
                         if(i % 2 == 1){
                             cout << "Sheet " << (i + 1) / 2 << ", front: ";
                             if(j > pages)
                                 cout << "Blank, ";
                             else
                                 cout << j << ", ";
                             cout << i << endl;
                         }else{
                             cout << "Sheet " << i / 2 << ", back : ";
                             cout << i << ", ";
                             if(j > pages)
                                 cout << "Blank" << endl;
                             else
                                 cout << j << endl;
                         }
                     }
                 }
             }
         }
     }
    
  2. 1408: 同样是一道读懂题目就非常简单的问题,做这个题的时候我想了一下判断互质的方法,觉得就我这脑子很难想出非常完美的算法,于是google了一下,结果发现了一个非常牛逼的判断互质的算法,时间省的令人发指,于是放到了代码中,果然一次就AC

    话不多说,放代码:

     #include <iostream>
     #include <iomanip>
     #include <math.h>
     using namespace std;
    
     bool coprime(int a, int b){
         //cout << a << ' ' << b << endl;
         int tmp;
         //下面这个循环就是这个判断互质算法的精髓所在,好好体会一下,必须要说的是,我并没有看懂。。。
         while(b != 0){
             tmp = a % b;
             a = b;
             b = tmp;
         }
         if(a == 1)
             return true;
         else
             return false;
     }
    
     int main(){
         int N, tmp, num[50], coprime_num;
         double pi;
         while(cin >> N){
             coprime_num = 0;
             for(int i = 0; i < 50; i++)
                 num[i] = 0;
             if(N == 0)
                 break;
             else{
                 tmp = N;
                 while(tmp){
                     tmp--;
                     cin >> num[tmp];
                 }
                 for(int i = 0; i < N; i++){
                     for(int j = i + 1; j < N; j++){
                         if(coprime(num[i], num[j]))
                             coprime_num++;
                     }
                 }
                 if(coprime_num == 0)
                     cout << "No estimate for this data set." << endl;
                 else{
                     pi = sqrt((double)(6.0 * (double)((N - 1) * N / 2) / (double)coprime_num));
                     cout << fixed << setprecision(6) << pi << endl;
                 }
             }
         }
     }