posts - 403, comments - 310, trackbacks - 0, articles - 7
          
	
 
BlogJava ::
首頁 ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理


          
		          		
	
          
	
          
		
			
          
	
		

          

          日歷
          

          
	
          
		
          <2007年5月>
          
	
          日一二三四五六
          293012345
          6789101112
          13141516171819
          20212223242526
          272829303112
          3456789
          

          

          

		
	
	
	



		
	
		
	
		
	
		
          
		
          相冊
          
		
				
			
          
	
		
	
		
	
		
	



          

          搜索
          

            
	
          •  
          

          

          

          積分與排名
          

            
	
          • 
		積分 -
		337499
	
          • 
		排名 -
		167
	
            • 

          

          




          

          最新評論
	
          

          
	
			
		

          

          






          
		          		
		
			
          
				
					
	
          
		
          
			
          
				USACO 1.1.4 Arithmetic Progressions 
			
          
 			Posted on 2007-05-30 22:18 ZelluX 閱讀(633) 評論(0)  編輯  收藏  所屬分類: Algorithm 
			
			


		
          
		
          第一次做是用一張hash表記錄的所有的數(shù)是否為所謂的bisquare，然后先枚舉公差，再枚舉首項，本來想這樣做就不用再對結果排序了，沒想到效率很低。
          改為先枚舉首項，再枚舉第二項，然后計算公差后，速度提高不少。
          另外第一次使用sort方法。
          

          /*
          PROG: ariprog
          ID: 06301031
          LANG: C++
          */

          #include           <iostream>
          #include           <fstream>
          #include           <vector>
          #include           <algorithm>

          using namespace std;

          struct Ans {
                        int start;
                        int step;
          }          ;

          bool compareOp(const Ans& ans1, const Ans& ans2);

          int main() {
              ifstream fin(          "ariprog.in");
              ofstream fout(          "ariprog.out");
                        int n, m, i, j, k;
                        bool solved = false;
              fin           >> n >> m;

                        // generate Arithmetic Progressions sequence
              bool seq[250*250*2 + 1];    
                        for (i = 0; i <= m * m * 2; i++) {
                  seq[i]           = false;
              }
                        for (i = 0; i <= m; i++) {
                            for (int j = 0; j <= i; j++) {
                      seq[i          *i + j*j] = true;
                  }
              }

              vector          <Ans> result;
                        int step;
                        for (i = 0; i <= m * m * 2; i++) {
                            if (!seq[i]) {
                                continue;
                  }
                            for (j = i + 1; j <= m * m * 2; j++) {
                                if (!seq[j]) {
                                    continue;
                      }
                      step           = j - i;
                                if (i + step * (n - 1) > m * m * 2) {
                                    break;
                      }

                                bool flag = true;
                                for (k = 1; k < n; k++) {
                                    if (!seq[i + step * k]) {
                              flag           = false;
                                        break;
                          }
                      }
                                if (flag) {
                          Ans ans;
                          ans.start           = i;
                          ans.step           = step;
                          result.push_back(ans);
                          solved           = true;
                      }
                  }
              }
                        if (!solved) {
                  fout           << "NONE" << endl;
              }

              sort(result.begin(), result.end(), compareOp);
              vector          <Ans>::iterator iter;
                        for (iter = result.begin(); iter != result.end(); iter++) {
                  fout           << iter->start << " " << iter->step << endl;
              }
              fout.close();
                        return 0;
          }

          bool compareOp(const Ans& ans1, const Ans& ans2) {
                        return ans1.step < ans2.step;
          }
          

          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          

51La

    







          
        
	




主站蜘蛛池模板：
克山县|
镇平县|
哈巴河县|
溧水县|
淮北市|
皮山县|
彭阳县|
区。|
灵川县|
汾西县|
汨罗市|
广灵县|
涡阳县|
高碑店市|
衡阳市|
石河子市|
许昌市|
河池市|
新竹县|
敖汉旗|
长治县|
元氏县|
吉林市|
绥棱县|
上杭县|
浠水县|
茂名市|
齐齐哈尔市|
双柏县|
白河县|
宁远县|
广水市|
东港市|
曲麻莱县|
简阳市|
松原市|
白玉县|
诸暨市|
托克托县|
怀集县|
同心县|