資訊學科能力競賽

筆試

數字系統

10進制 → n進制：連除(乘)n

n進制 → 10進制：從n的0次方開始加總

2進制 → 2ⁿ進制：n位變一位

2ⁿ進制 → 2進制：一位變n位

定址空間

32 bits = 2³² = 2² 2³⁰ = 4KKK = 4G

( K =  2¹⁰ ≒ 10³ )

#47

(K)₁₀₌(1024)₁₀=(2¹⁰)₁₀₌(10000000000)₁₀=(400)₁₆

(24)₁₀₌(18)₁₆

(24K)₁₀=(6000)₁₆

程式

TIOJ code

http://snowyojworld.blogspot.tw

DFS vs BFS

http://programmermagazine.github.io/201406/htm/focus1.html

練習網站 http://thspc.csie.ntnu.edu.tw:8888

帳號密碼 THSPC01 ~ THSPC10

算出質數.cpp

• #include <iostream>
• #include <vector>
• using namespace std;
•  
• int main()
• {
•     int N;
•     cin >> N; //輸入要算出是否為質數的最大正整數
•  
•     bool not_a_prime[ N + 1 ];
•     for (int i = 0; i < N + 1; i++) //從0到N都設為質數
•         not_a_prime[ i ] = false;
•  
•     vector<int> primes; //用vector<int>宣告長度未定的整數串primes
•  
•     for (int i = 2; i <= N; i++) //i從2到N走一遍
•     {
•         if (not_a_prime[i] == false) //若i是質數就把i接到primes串的後面
•             primes.push_back(i);
•         for (int j = 0; j < primes.size(); j++) //primes串走一遍
•         {
•             if (i * primes.at(j) > N) //若i乘以primes串裡面的質數超過N了就跳出
•                 break;
•             not_a_prime[ i * primes.at(j) ] = true; //將i乘以primes串裡面的質數的結果設為非質數
•         }
•     }
•  
•     for (int i = 0; i < primes.size(); i++) //印出primes串
•         cout << primes.at(i) << endl;
•  
•     return 0;
• }

Prime.cpp

• #include <iostream>
• #include <bitset>
• #include <vector>    //http://mropengate.blogspot.tw/2015/07/cc-vector-stl.html
• #include <algorithm>
•  
• using namespace std;
•  
• const int N = 1000001;
• vector<int> prime, ans;
• bitset<N> pr;
•  
• bool solve(int i, int prv) {
•     if (!i) return true;
•     for (auto k = lower_bound(prime.begin(), prime.end(), min(i, prv - 1), greater<int>()); ~*k; k++) {
•         if (solve(i - *k, *k)) {
•             ans.push_back(*k);
•             return true;
•         }
•     }
•     return false;
• }
•  
• int main()
• {
•     pr.set(1);
•     for (int i = 2; i < N; i++) {
•         if (!pr[i]) prime.push_back(i);
•         for (int& a : prime) {
•             if (a * i >= N) break;
•             pr.set(a * i);
•             if (!(i % a)) break;
•         }
•     }
•     reverse(prime.begin(), prime.end());
•     prime.push_back(-1);
•  
•     int q, a;
•     cin >> q;
•  
•     while (q--) {
•         cin >> a;
•         if (pr[a]) cout << "0\\n";
•         else {
•             ans.clear();
•             if (solve(a, a))
•                 for (auto i = ans.rbegin(); i != ans.rend(); i++) cout << *i << ’ ’;
•             else cout << a;
•             cout << endl;
•         }
•     }
• }

Party.cpp

• #include <iostream>
• using namespace std;
•  
• int m, n, dp[1001][1001];
• bool A[1001], B[1001];
• int main()
• {
•     cin>>m>>n;
•     for(int i=1; i<=m; i++)
•         cin>>A[i];
•     for(int i=1; i<=n; i++)
•         cin>>B[i];
•     for(int i=1; i<=m; i++)
•         for(int j=1; j<=n; j++)
•         {
•             if(A[i]!=B[j])
•                 dp[i][j]=dp[i-1][j-1]+1;
•             else
•                 dp[i][j]=max(dp[i][j-1], dp[i-1][j]);
•         }
•     cout<<dp[m][n];
•     return 0;
• }

Fee.cpp

• #include <iostream>
• #include <algorithm>
• using namespace std;
• int main()
• {
•   int n, fee=0;
•   cin >> n;
•   int point[n];
•   for(int i=0; i<n; i++)
•     cin >> point[i];
•   sort(point, point+n);
•   int points = point[0];
•   for(int i=1; i<n; i++)
•   {
•     points += point[i];
•     fee += points;
•   }
•   cout << fee;
•   return 0;
• }
• /*輸入數字為同數時 3數是5倍 4數是9倍 5數是14倍 6數是20倍 7數是27倍 n+(n-1) */