# S3 演算法 week 5
###### tags: `S3 公開資源`
:::info
時間：12/11 9:00 ~ 17:00
地點：成大資工系新館 **65203** 教室
主題：基礎數論與資料結構
直播連結：https://youtu.be/OR0Z_fVyKAs
:::
## 課程內容
- 進位制
- 餘數
- 建表
- stack
- queue
- linked list
- 講義連結：https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FrJpY0i7PS
## 注意事項
1. 接下來的課程都是演算法的內容，請學員務必熟悉基本語法的運用
2. 之後的助教時間將固定舉辦於每週五 20:00 ~ 22:00（段考週可能會暫停），運作模式如下：
- 採自由練習 / 討論的方式，學員們可在任意語音討論區討論，每個語音頻道限制 10 人，請盡量開啟畫面直播以方便助教查看
- 每次助教時間都有至少一名值班助教，會不定時關心練習狀況，如果練習途中遇到問題了可以開麥克風跟同頻道的夥伴們討論，或是呼叫助教幫忙
- 如果該堂課有額外題解或是其他事務，會在 22:00 左右將學員集中至某個語音頻道
3. 所有上課相關連結都會放在資源彙整裡：https://hackmd.io/@SCIST/rykldedMj
4. 上課期間請全程配戴口罩
5. 請假表單：https://forms.gle/2ESVuTezcHCK959H6
# 必作題題解
[TOC]
## 第二章－第三節
### [No_Judge - 擲骰結果](https://hackmd.io/@sa072686/cp/%2F4uO2GyfGTi2a4vP0rUtZXA#%E6%93%B2%E9%AA%B0%E7%B5%90%E6%9E%9C)
撰寫者：fishhh
這一題其實有很多種解法，那因為章節是進位制，故使用這種方法~
這其實有一個名稱 叫做位元枚舉。
詳細的解法可以在講義裡看到~ 那我這邊就提供程式碼。
:::spoiler
```cpp=
#include "iostream"
using namespace std;
int main(){
int n,t;
cin>>n>>t;
int ans=0;
int all = 1; // 所有可能
for(int i=0;i<n;i++){
all*=6;
}
for(int i=0;i<=all;i++){
int temp=i;
int now_tot=0;
while(temp){
now_tot+=(temp%6+1); // 加1 是因為在六進位下 只會有 0~5 所以全部平移 1 就會是骰子的點數~
temp/=6;
}
if(now_tot>=t)ans++;
}
cout<<ans;
}
```
:::
---
### [TOJ 292 - Jessica好仁慈](https://toj.tfcis.org/oj/pro/292/)
撰寫者：Eason
主要想法就是先轉成十進位
再轉成題目要求的進位
:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
int a, b, c;
int to_decimal (int origin, int num){ // 轉十進位
int sum = 0, pow = 0;
int tmp = 1;
while (num != 0){
sum += num % 10 * tmp;
num /= 10;
tmp *= origin;
}
return sum;
}
int transform (int dis, int num){// 轉題目要求的進位制
int sum = 0, cnt = 1;
while (num != 0){
sum += num % dis * cnt;
num /= dis;
cnt *= 10;
}
return sum;
}
void solve(){
cin >> a >> b >> c;
int ans = c;
if (a != 10) ans = to_decimal (a, c); // 原本是十進位就不用轉換
if (b != 10) ans = transform (b, ans); // 要求如果是十進位就不用再轉換
cout << ans << '\n';
return;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
solve();
return 0;
}
```
:::
---
### [費氏數列．改](https://hackmd.io/@sa072686/cp/%2FUDa8rLAPTOqv-FZ_KwlVgQ#%E8%B2%BB%E6%B0%8F%E6%95%B8%E5%88%97%EF%BC%8E%E6%94%B9)
撰寫者：fishhh
在做費氏(~~事~~)數列的時候如果只有要求單純一項，就不用儲存不需要的東西
例如：你要求第 4 項，那麼你就只需要第 2、3 項
第0、1項就完全沒有用(明確來說 是用過後就沒用ㄌ)
那就可以稍微用個滾動陣列來處理它~程式碼就會變得十分簡潔。
:::spoiler 正常版
```cpp
#include "iostream"
using namespace std;
long long int fib[10010]={0,1,1};
int main(){
long long int n,m;
cin>>n>>m;
for(int i=3;i<=n;i++)fib[i]=(fib[i-1]+fib[i-2])%m;
cout<<fib[n];
}
```
:::
:::spoiler 滾動陣列版
```cpp
#include "iostream"
using namespace std;
int main(){
long long int n,m;
cin>>n>>m;
long long int fib[2]={1,1};
for(int i=3;i<=n;i++){
fib[i%2]=(fib[i%2]+fib[1-(i%2)])%m;
}
cout<<fib[n%2];
}
```
:::
---
### [AtCoder typical90_bf - Original Calculator（★4）](https://hackmd.io/@sa072686/AtCoder_typical90_bf)
撰寫者：fishhh
可以發現一件事情，就是所有數字會在 10^5 裡面。
然後，一個數一直按按鈕A 一定會有循環。
可以這樣想，就是一個數 $x$ 按了按鈕後，就會變成 $z$
那這個 $z$ 一定會符合 ($0 \leq z \leq 10^5-1$)
(因為$z$會被模$1e5$)
那麼，假設今天按了按鈕 $1e5$ 次後，接下來出現的數一定會在之前出現過。
了解了為什麼會有循環後，就可以來分析一下循環的種類。
第一種：
一開始是 n 最後一樣會回到 n
第二種：
最後的 loop 並不會回到 n 而是在某個點開始循環。
知道循環會有以下兩種可能後，或許下面的程式就會比較好懂ㄌ!
:::spoiler 參考程式碼
```cpp
#include "iostream"
using namespace std;
long long int circle[100100]={};
int vis[100100]={}; //第一次出現在 cycle ary 裡面的 index
int main(){
long long int n,k,tp=0; //tp => circle 陣列的最上面那一項(待填進去的地方)
cin>>n>>k;
long long int now=n,loop;
while(!vis[now]){
vis[now]=tp;
circle[tp++]=now;
long long temp=now,nxt=0;
while(temp){
nxt+=temp%10;
temp/=10;
}
now=(nxt+now)%100000;
}
loop=vis[now]; // loop => 從circle 陣列的第幾個點開始循環。
//假設是第一種情況 那麼 loop 就會是0
cout<<circle[(k-loop)%(tp-loop)+loop]<<"\n";
}
```
:::
---
### [Kattis Drunk Vigenère](https://open.kattis.com/problems/drunkvigenere)
撰寫者：小麥
奇數用減的，偶數用加的。
奇數減的時候要注意，因為C++的負數MOD並不會變成正的，所以要自己加26
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
string str;
string str2;
cin >> str >> str2;
string ans = "";
int len = str.length();
for (int i = 0; i < len; i++) {
str[i] -= 'A';
str2[i] -= 'A';
if (i % 2 == 0) {
int k = str[i] - str2[i];
if (k < 0) {
k += 26;
}
ans += k % 26;
}
else {
ans += (str[i] + str2[i]) % 26;
}
}
for (int i = 0; i < len; i++) {
cout << (char) (ans[i] + 'A');
}
cout << '\n';
return 0;
}
```
:::
---
### [Kattis trollhunt - Troll Hunt](https://open.kattis.com/problems/trollhunt)
撰寫者：fishhh
其實只要按照題意去寫即可。
:::spoiler
```cpp
#include<iostream>
#include<cmath>
using namespace std;
int main(){
unsigned long long t,a,b,c;
double per;
cin>>a>>b>>c;
a--;
per=b/c;
cout<<ceil(a/per)<<"\n";
return 0;
}
```
:::
---
### [UVa 12468 - Zapping](http://domen111.github.io/UVa-Easy-Viewer/?12468)
撰寫者：fishhh
分別去找哪一種方案所需要的次數最少就好~
:::spoiler 參考程式碼
```cpp
#include "iostream"
using namespace std;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int a,b;
while (cin>>a>>b){
if(a==-1)return 0;
int ans=b-a;
if(ans<0){
ans+=100;
}
int nans=a-b;
if(nans<0)nans+=100;
ans=min(ans,nans);
cout<<ans<<"\n";
}
}
```
:::
---
### [Kattis friday - Friday the 13th](https://open.kattis.com/problems/friday)
撰寫者：fishhh
就 直接寫即可 主要是判斷範例程式中的 $w$ 可以會有循環 直接 %7 即可。
:::spoiler 參考程式碼
```cpp
#include<iostream>
using namespace std;
int main(){
int w,n,d,m,day,tot;
cin>>n;
while(n--){
cin>>d>>m;
w=7,tot=0;
for(int i=0;i<m;i++){
cin>>day;
if(day<13){
w+=day;
continue;
}
w+=12;
if(w%7==5){
tot++;
}
w+=day-12;
}
cout<<tot<<"\n";
}
}
```
:::
---
### [Kattis Ptice](https://open.kattis.com/problems/ptice)
撰寫者：fishhh
利用餘數循環的性質算出個別每一題選什麼即可~
:::spoiler
```cpp
#include<iostream>
using namespace std;
int main(){
int max=-999,n,t1,t2,t3;
// cout<<0%1;
string k;
t1=t2=t3=0;
cin>>n>>k;
char adr[]={'A','B','C'},br[]={'B','A','B','C'},gor[]={'C','C','A','A','B','B'};// 3 4 6
for(int i=0;i<n;i++){
if(k[i]==adr[i%3]){
t1++;
}
if(k[i]==br[i%4]){
t2++;
}
if(k[i]==gor[i%6]){
t3++;
}
}
if(t1>t2)max=t1;
if(t3>max)max=t3;
if(t1>max)max=t1;
if(t2>max)max=t2;
cout<<max<<"\n";
if(t1==max)cout<<"Adrian\n";
if(t2==max)cout<<"Bruno\n";
if(t3==max)cout<<"Goran\n";
}
```
:::
---
### [Kattis Spavanac](https://open.kattis.com/problems/spavanac)
撰寫者：fishhh
先把全部轉成分的單位 然後減45 如果變成負的再加上一天即可~
:::spoiler
```cpp
#include<iostream>
using namespace std;
int main(){
int h,m;
cin>>h>>m;
m+=60*h;
m-=45;
if(m<0){
m+=60*24;
}
cout<<m/60<<" "<<m%60;
}
```
:::
---
### [toj405](https://toj.tfcis.org/oj/pro/405/)
撰寫者：fishhh
主要觀念就是進位制轉換，可以參考前面的 TOJ292。
:::spoiler 參考程式碼
```cpp
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int a,b,k=1,oct=0,te=0,g,d=0,h;
cin>>a>>b;
h=b;
while(h){ //算長度
d++;
h/=10;
}
while(b){
g=1;
for(int i=0;i<d;i++){ //做次方
g*=(b%10);
}
te=g;
oct+=(b%10)*k; //算十進位
k*=a;
b/=10;
}
if(te==oct){
cout<<"YES\n";
return 0;
}
cout<<"NO\n";
}
```
:::
---
### [UVa445](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=386)
撰寫者：fishhh
直接做就好。
:::spoiler 參考程式碼
```cpp
#include "iostream"
using namespace std;
int main(){
string s;
while(getline(cin,s)){
int cnt=0;
for(int i=0;i<s.size();i++){
if(s[i]<='9'&&s[i]>='0'){
cnt+=(s[i]-'0');
}
else if(s[i]=='!'){
cout<<"\n";
}
else{
if(s[i]=='b')s[i]=' ';
for(int j=0;j<cnt;j++)cout<<s[i];
cnt=0;
}
}
cout<<"\n";
}
}
```
:::
---
### [UVa10929](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1870)
撰寫者：Eason
1. 因為這題題目有說可能會到1000位數(非常的大)
所以絕對不是讀入數字直接取餘數
2. 判斷11的倍數可以利用一個特質
**偶數位數的總和減掉奇數位數的總和 必須是11的倍數**
:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
string s;
while (cin >> s){
if (s == "0") break;
int len = s.size();
int odd = 0, even = 0;
for (int i = 0; i < len; i++){
if (i % 2 == 0){
even += (int)(s[i] - '0');
}
else{
odd += (int)(s[i] - '0');
}
}
if ((odd - even) % 11 == 0){
cout << s << " is a multiple of 11.\n";
}
else{
cout << s << " is not a multiple of 11.\n";
}
}
return 0;
}
```
:::
---
### [UVa 11879](http://domen111.github.io/UVa-Easy-Viewer/?11879)
撰寫者：小麥
102 = (1 * 100) + (0 * 10) + (2 * 1)
的原理，所以可以使用MOD一位一位的取模。
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
string str;
while (cin >> str && str != "0") {
int sum = 0;
int len = str.length();
for (int i = 0; i < len; i++) {
sum *= 10;
sum += str[i] - '0';
sum %= 17;
}
cout << (sum == 0) << '\n';
}
return 0;
}
```
:::
---
## 二章－第四節
### [No_Judge 總價格](https://hackmd.io/18aJIgTtSxiZ4K7vLmlyHw#%E7%B8%BD%E5%83%B9%E6%A0%BC)
撰寫者：fishhh
全部相加後輸出。
請觀察題目下面附的[連結](https://docs.google.com/spreadsheets/d/1Ze1A6ir3bia4PMpFgP_VHM92gMyNwUlSN-hMiMc0wSw/edit?usp=sharing)
---
### [No Judge - 次高級硬體](https://hackmd.io/18aJIgTtSxiZ4K7vLmlyHw#%E6%AC%A1%E9%AB%98%E7%B4%9A%E7%A1%AC%E9%AB%94)
撰寫者：fishhh
基礎的請去看講義下面附的code
這裡提供一個較為簡潔的程式。
:::spoiler
```cpp
#include "iostream"
using namespace std;
int main(){
int n;
cin>>n;
int ary[200]={};
for(int i=0;i<n;i++)cin>>ary[i];
int tmax=0,secmax=0;
for(int i=0;i<n;i++){
if(ary[i]>tmax){
secmax=tmax;
tmax=ary[i];
}
else if(ary[i]>secmax&&ary[i]!=tmax)secmax=ary[i];
}
cout<<secmax<<"\n";
}
```
:::
---
### [No Judge - 位數判斷](https://hackmd.io/fmJHEIwIR0q9ms7kM-DjOQ#%E4%BD%8D%E6%95%B8%E5%88%A4%E6%96%B7)
撰寫者：fishhh
寫完再來看><
:::spoiler 答案程式碼
wrang case n=11
```cpp
#include <iostream>
using namespace std;
int main()
{
int n, t, r; // r 要初始化
cin >> n;
for (t=n; t>0; t--) //把 t--弄掉
{
r++;
t /= 10;
}
cout << r << '\n';
return 0;
}
```
:::
---
### [No Judge - 質數判別](https://hackmd.io/fmJHEIwIR0q9ms7kM-DjOQ#%E8%B3%AA%E6%95%B8%E5%88%A4%E5%88%A5)
撰寫者：fishhh
寫完再來看><
:::spoiler 答案程式碼
```cpp
#include <iostream>
using namespace std;
int main()
{
int n, i, p;
cin >> n;
for (i=1, p=1; i*i<n; i++) // i start form 2(wrang case :all) , i*i<=n(wrang ase : 49)
{
if (n % i == 0)
{
p = 0;
break;
}
}
if (p)
{
cout << "prime\n";
}
else
{
cout << "not prime\n";
}
return 0;
}
```
:::
---
### [TOJ 120](https://toj.tfcis.org/oj/pro/120/)
撰寫者：小麥
前綴合裸題，唯一要注意的是頭尾有可能反過來。
:::spoiler
```cpp=
#include <bits/stdc++.h>
using namespace std;
int arr[(int) 2e6 + 5];
long long pf[(int) 2e6 + 5];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
for (int i = 1; i <= n; i++) {
pf[i] = pf[i-1] + arr[i-1];
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
if (a > b) {
int c = a;
a = b;
b = c;
}
cout << (pf[b] - pf[a - 1]) << '\n';
}
return 0;
}
```
:::
---
Sign in with Wallet
Connect another wallet