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


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


		
          
		
          第一次做是用一張hash表記錄的所有的數是否為所謂的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;
          }
          

          
	
          
	


          
	    
    




          








          

				
			
          
		          		
	
          
	
          
		
			


		
	
          

          



    







          
        
	




主站蜘蛛池模板：
和平县|
新蔡县|
循化|
古交市|
贵阳市|
临澧县|
灯塔市|
准格尔旗|
鲁甸县|
阿拉善左旗|
百色市|
留坝县|
新巴尔虎右旗|
正宁县|
阜阳市|
安仁县|
道孚县|
措勤县|
商南县|
从江县|
丁青县|
黔西县|
天门市|
鄂伦春自治旗|
达拉特旗|
长顺县|
平定县|
临汾市|
北宁市|
衡阳县|
康平县|
平江县|
顺平县|
大竹县|
桦南县|
平利县|
阿克陶县|
东山县|
萨嘎县|
南木林县|
广灵县|