TOJ--3352--素数求和（双指针）

换了个头像--ex 在hp的头像

以作弥补~~

这题怎么说呢我一开始以为是要进行搜索的想了下感觉双重for就可以完事。。。

然后我的AC时间是大概700多ms 那边OJ最快的是15ms 。。。

郁闷叻。。。。

touch me

题意很简单就是给你一个正整数n 问你能不能用一连串的素数之和来表示然后一共有几种表示方案...

我不想介绍我那么渣的代码了~ = 我可以优化到30ms的时候再来讲~

先上下这有待改善的 code

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int size = 10010;
 5 int prime[size];
 6 int cnt;
 7 
 8 bool judge( int x )
 9 {
10     if( x==1 )
11         return false;
12     for( int i = 2 ; i*i<=x ; i++ )
13     {
14         if( x%i == 0 )
15             return false;
16     }
17     return true;
18 }
19 
20 void inital()
21 {
22     for( int i = 1 ; i<size ; i++ )
23     {
24         if( judge(i) )
25             prime[cnt++] = i;
26     }
27 }
28 
29 int main()
30 {
31     int n;
32     inital();
33     int sum , value;
34     cnt = 0;
35     while( ~scanf("%d",&n) &&n )
36     {
37         sum = 0;
38         for( int i = 0 ; prime[i]<=n ; i++ )
39         {
40             value = 0;
41             for( int j = i ; prime[j]<=n ; j++ )
42             {
43                 value+=prime[j];
44                 if( value>n )
45                     break;
46                 else if( value==n )
47                 {
48                     sum++;
49                     break;
50                 }
51             }
52         }
53         printf( "%d
",sum );
54     }
55     return 0;
56 }

View Code

OK 刚刚完成了一步优化~ 成功地将主函数中O(N^2)的时间复杂度降低到 O（N )

很深感触就是 --指针真的很灵活又让我想起了指针与引用我的理解----指针灵活性引用安全性（ possiblely it is wrong)

我这边采用的方法是使用2个指针 left 和 right 分别开始指向数组头它们维护的区间是 [ left , right-1 ]

这边做法是基于预处理完 1~10000区间内的素数后并将素数存于一个prime数组后进行的操作

其实这个时候这题就转换成了给你一个数组寻找这个数字中一串连续的数使它的和 == n

我觉得这个方法告诉你之后其实手动模拟个数据就不难了我当时模拟了下 1 2 3 5 6 11（数组）----11（和）

当你的value<n时区间向右前进一格由right++

当你的value>=n时区间最左边元素去掉同时left++

这边值得一提的是 left == right 可以看成此时该集合内无任何元素 *（right-1)即这个集合此时的最大元素

over

继续贴下代码可能我还会对素数的处理进行下优化先去lol了~

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int size = 10010;
 5 int prime[size];
 6 int cnt;
 7 
 8 bool judge( int x )
 9 {
10     if( x==1 )
11         return false;
12     for( int i = 2 ; i*i<=x ; i++ )
13     {
14         if( x%i == 0 )
15             return false;
16     }
17     return true;
18 }
19 
20 void inital()
21 {
22     prime[0] = 2;
23     for( int i = 1 ; i<size ; i+=2 )
24     {
25         if( judge(i) )
26             prime[cnt++] = i;
27     }
28 }
29 
30 int main()
31 {
32     int n; 
33     cnt = 1;
34     inital();
35     int sum , value;
36     int* left;
37     int* right; 
38     while( ~scanf("%d",&n) &&n )
39     {
40         value = sum = 0;
41         left = prime;
42         right = prime;
43         while( left == right || *(right-1)<=n ) 
44         {
45             if( value<n )
46             {
47                 value+=*right;
48                 right++;
49             }
50             else if( value>n )
51             {   
52                 value-=*left;
53                 left++;
54             }
55             else if( value==n )
56             {
57                 sum++;
58                 value-=*left;
59                 left++;     
60             }
61         }
62         printf( "%d
",sum );
63     }
64     return 0;
65 }
66 
67 /*
68 上面分开写 容易理解
69 else if( value>=n )
70 {
71     value-=*left;
72     left++;
73     if( value==n )
74         sum++;
75 }
76 */

View Code

但是今天看到了一段很凄美的话~ 第一次介绍来源: 一个--韩寒

today:

　　敢挑战的自己

　　死在5岁时的幼儿园阿姨面前

　　诚实的自己

　　死在9岁的那次罚站之后

　　勇敢的自己

　　死在16岁时的地铁上

　　想当艺术家的自己

　　死在18岁时爸爸的责骂里

　　相信爱情的自己

　　死在19岁时学校附近的小旅馆床上

　　觉得还有公平的自己

　　死在21岁时的面试中

　　骗自己说世上还有好男人的自己

　　死在23岁时老板的汽车里

　　27岁的许小姐真不知道

　　这会有多少个自己死在这一生的路上

---- 太悲观了~世界如此美好值得我们为此奋斗

~~~ 我相信后面这句---------

just follow your heart