# UVA 10336 Rank the language
參考: http://knightzone.org/?p=1346 使用 DFS 去標記 再去計算數量 [crayon-5f9b8dd3031842799167…
# UVA 10110 Light, more light
原本全部都關著 第 i 次可以切 i 的倍數的燈泡 切偶數次是暗的 切奇數次是亮的 所以因數個數是奇數才會是亮的 只有完全平方數 因數個數會是奇數 [cray…
2015-09:Longest Increasing Subsequence
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <stdio.h> #include <stdlib.h> #include <iostream> #include <string.h> using namespace std; int main() { int n; while(cin>>n) { int input[n+1]; for(int i=1; i<n+1; i++) { cin>>input[i]; } int answer[n+1]; for(int i=0;i<n+1;i++) { answer[i]=1; } for(int i=1;i<n+1;i++) { for(int j=i+1;j<n+1;j++) { if(input[j]>input[i]) { answer[j]=((answer[i]+1)>answer[j])?(answer[i]+1):(answer[j]); } } } int max=1; for(int i=1;i<n+1;i++) { if(answer[i]>max)max=answer[i]; } cout<<max<<endl; } return 0; } |
# UVa 10042 Smith Numbers
建質數表 然後作質因數分解
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <stdio.h> #include <stdlib.h> #include <math.h> int digitsum( int number ) { int sum = 0; while( number > 0 ) { sum += number % 10; number /= 10; } return sum; } int main() { //建立質數表 int composite[50000] = {true, true, false}; for( int i = 2 ; i < 50000 ; ++i ) { if( !composite[i] ) { for( int j = i+i ; j < 50000 ; j += i ) { composite[j] = true; } } } int testcase; while( scanf("%d", &testcase) != EOF ) { int input; for( int i = 0 ; i < testcase ; ++i ) { scanf("%d", &input); int smith_number = input+1; while(1) { int left_sum=0; int right_sum=0; int temp = smith_number; int sqrt_temp = (int)sqrt(temp); for(int j=2; j<=sqrt_temp&&temp>1; ++j)//若此數本身為質數則下個if會處理掉 { if( !composite[j] ) { while( temp % j == 0 )//找質因數 { right_sum += digitsum(j); temp /= j; } } } if( temp != smith_number ) { if( temp > 1 ) //本身為質數的並不能算在內{ right_sum += digitsum(temp); } left_sum = digitsum(smith_number); if( left_sum == right_sum ) break;//找到 smith_number++;//沒找到繼續找 } printf("%d\n",smith_number); } } return 0; } |
參考
Recursion and Mod [2015-02]
這題與 big mod 有點像 都必須用遞迴方式去求 時間才不會超過
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <stdio.h> #include <stdlib.h> long long cal(int a,long long n,long long b) { if(n==1)return 3; else { long long result=cal(a,n/2,b); if(n%2==1) { return ((result*result*3))%b; } else { return ((result*result))%b; } } } int main() { long long n; while(scanf("%lld",&n)!=EOF) { n=cal(3,n,1000000009); printf("%lld\n",n-2);//可以透過觀察得知 i th ans = 3 的 i 次方 -2 } } |
 …
#UVA 10182 Bee Maja
就暴力法建表 參考這篇: http://using-c.blogspot.tw/2010/06/problem-10182-bee-maja.html [cra…
#UVA 245 Uncompress
先用手動跑一遍就可以知道 要使用 linked list 較好解題 讀取的時候分成三種情況 字母 數字 以及 其他 [crayon-5f9b8dd306bb14…
#UVA 1210 Sum of Consecutive Prime Numbers
先建立質數表 在暴力法把每個質數可加到的數暴力法加
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <stdio.h> #include <stdlib.h> #include <math.h> bool isprime[10001]; void buildprime() { //printf("ss"); int mid= (int)sqrt(10001); int num_prime; isprime[1]=true; for(int i=2;i<mid;i++) { if(!isprime[i]) {//把質數的倍數都標成不是質數 for(int j=i*i;j<10001;j+=i) { isprime[j]=true;//不是質數 } } } } int main() { int ans[10001]; int input; buildprime(); int prime[2000]; int num=0; for(int i=2;i<10001;i++)//把質數表存進prime { if(!isprime[i]) { prime[num]=i; num++; } } int sum; //printf("%d",num); for(int i=0;i<num;i++)//從2開始依序把可以照順序加的到的數 ans 都加 1 //就是暴力法做完 { sum=prime[i]; ans[sum]++; for(int j=i+1;j<num;j++) { sum+=prime[j]; if(sum>10000)break; ans[sum]++; } } while(scanf("%d",&input) && input!=0) { printf("%d\n",ans[input]); } return 0; } |
#UVA 10107 What is the median
就一直維持陣列為小到大 或是 大到小即可 簡單地計算中位數
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <stdio.h> #include <stdlib.h> int main() { int input; int median[10005], allnum = 0; while( scanf( "%d", &input ) != EOF ) { int i, j; for( i = 0 ; i < allnum ; i++ ) { if( input < median[i] ) { for(int j=allnum;j>=i;j--) { median[j+1]=median[j]; } break; } //printf("allnum: %d\n",allnum); } median[i] = input; allnum++; if( allnum % 2 ) printf( "%d\n", median[allnum/2] ); else printf( "%d\n", (median[allnum/2-1]+median[allnum/2]) / 2); } return 0; } |
#UVA 374 Big Mod
(A*B)%C = (A%C) * (B%C) (B^P)%M = (B^(P/2)%M) * (B^(P/2)%M) [crayon-5f9b8dd30775…