# 2020 年 10 月南區四校聯合初學者程式設計線上練習賽 題解

Div 1 Problem J 的題解跟題敘測資等等暫時不能提供
:)

## Div.2 Problem A

### By Fysty

**考點：大數輸入**

通常遇到輸入或處理大數時，不能用int或long long存，要用string存

::: spoiler 參考作法

#include <bits/stdc++.h>
using namespace std;
#define MotoHaiyaku ios::sync_with_stdio(false);cin.tie(0);
int main()
{
    MotoHaiyaku
    string s;
    cin>>s;
    cout<<s;
}

:::

## Div.2 Problem B 風原折價券問題

### By Colten

**考點：迴圈**

對於每種折價卷的配對最先注意的是補貼的金額須為最少

第二個是要從這些組合裡選出 500 元使用最多的方案

在賽中看到很多人都只拿了 30 分，很多人的錯誤都是

1. 500 元不是使用最多的一種方案
2. 題目敘述有說 500 元 或 200 元的使用最多 5 張

::: spoiler 參考作法

#include <iostream>  
  
#include <cmath>  
  
#include <algorithm>  
  
#define int long long  
  
using namespace std;  
  
signed main(void)  
{  
    int n,i,k;  
      
    int ans = 1e9;  
      
    int a,b,c;  
      
    cin >> n;  
      
    for(i=0;i<=5;i++)  
    {  
        for(k=0;k<=5;k++)  
        {  
            if(n-(i*500+k*200) >= 0)  
            {  
                if(ans >= n-(i*500+k*200))  
                {  
                    ans = n-(i*500+k*200);  
                      
                    a = i;  
                      
                    b = k;  
                      
                    c = ans;  
                }  
            }  
        }  
     }  
       
     cout << a << " " << b << " " << c << "\n";   
      
    return 0;  
}

:::

## Div.2 Problem C
### By Fysty
首先從$AND$和$XOR$的定義可以發現：對於任何的兩個數$x,y$，$a=x\&y$和$b=x\oplus y$的二進位表示中同一個位數不會都是$1$。
所以若輸入的$a,b$滿足$a\&b\neq0$則沒有答案，輸出$-1$。
否則注意到對於任何的兩個數$x,y$，$x+y=2(x\&y)+(x\oplus y)$
所以答案即為$2a+b$。

::: spoiler 參考作法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MotoHaiyaku ios::sync_with_stdio(false);cin.tie(0);
int main()
{
    MotoHaiyaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll a,b;
        cin>>a>>b;
        if(a&b) cout<<"-1\n";
        else cout<<2*a+b<<"\n";
    }
}

:::
## Div.2 Problem D
### By Fysty
我們定義相鄰為之間不存在其他還活著的大兔。
經過觀察可以發現若某隻大兔$A$的飢餓度小於所有大兔中最大飢餓度$M$，則$A$一定在某步中被吃掉。
所以到最後只會剩下飢餓度為$M$的所有大兔。
換句話說，這題的答案就是$M$出現的所有位置。

::: spoiler 參考作法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=2*1e18;
#define MotoHaiyaku ios::sync_with_stdio(false);cin.tie(0);
ll a[200005];
int main()
{
    MotoHaiyaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,mx=-INF;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            mx=max(mx,a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            if(a[i]==mx) cout<<i<<" ";
        }
        cout<<"\n";
    }
}

:::

## Div.2 Problem E 電子日曆 1
### By joylintp

對於字串中的每個字元，如果該字元為數字，就將答案加上點亮該數字需要的燈管數；否則就忽略該字元。

可以將每個數字需要的燈管數存在陣列中以加快實作。

::: spoiler 參考作法

#include<bits/stdc++.h>
using namespace std;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int arr[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    string s, t;
    cin >> s >> t;

    int ans = 0;
    for (char c : s)
        if (isdigit(c))
            ans += arr[c - '0'];
    for (char c : t)
        if (isdigit(c))
            ans += arr[c - '0'];
    cout << ans << '\n';

    return 0;
}

:::

## Div.2 Problem F / Div. 1 Problem A 綠幹線公車的完美比例

### By Colten

**考點: 迴圈 & 實作**

對於每個查詢的 OuO 數，我們可以先利用雙重迴圈去搜每個區段間的值

加入 set 裡 當在搜尋時即利用 count 去做查詢

當 count 的值為不等於 $0$ 時，輸出 $Yes$ ，反之則輸出 $No$

::: spoiler 參考作法

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int q,n,i,k;
	
	cin >> q;
	
	while(q--)
	{
		cin >> n;
		
		set <int> a;
		
		vector <int> v;
		
		while(n--)
		{
			int input;
			
			cin >> input;
			
			v.push_back(input); 
		}
		
		for(i=0;i<v.size();i++)
		{
			for(k=i+1;k<v.size();k++)
			{
				a.insert(v[i]+v[k]);
			}
		}
		
		int t;
		
		cin >> t;
		
		while(t--)
		{
			int ouo;
			
			cin >> ouo;
			
			if(a.count(ouo) != 0)
			{
				cout << "Yes\n";
			}
			else
			{
				cout << "No\n";
			}
		}
		
		a.clear();
		
		v.clear();
	}
	
	return 0;
} 

:::

## Div.2 Problem G / Div. 1 Problem B 電子日曆 2
### By joylintp

可以發現需要最少燈管的時間為 `2111/11/11 11:11:11`，需要 31 根燈管；最多燈管的時間為 `2888/08/08 08:08:08`，需要 91 根燈管。故當 $n < 31$ 或 $n > 91$ 時無解，輸出 `-1` 即可，可得 5 分。

枚舉 2020 年中的每一秒，計算該秒所需的燈管數，可得 35 分。

可以發現，年分的後三位數和小時、分鐘、秒鐘的個位數不管其他位置的情況為何皆可設定成 0 ~ 9 之間的任何數字。故當 $n \le 61$ 時，可以從 `2111/11/11 11:11:11` 開始，每多一個燈管就將上述的其中一位數改成多使用一個燈管的數字；而若 $n \ge 61$ 時，可以從 `2111/08/08 01:01:01` 開始，每多一個燈管就將上述其中一位數改成多使用一個燈管的數字。

::: spoiler 參考作法

#include<bits/stdc++.h>
using namespace std;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    if (n < 31 || n > 91)
        cout << "-1\n";
    else
    {
        int t, idx[] = {1, 2, 3, 12, 15, 18};
        string s, arr = "174208";
        if (n > 61)
            t = n - 61, s = "2111/08/08\n01:01:01";
        else
            t = n - 31, s = "2111/11/11\n11:11:11";

        for (int i = 0; i < 6; i++)
            s[idx[i]] = arr[min(t, 5)], t -= min(t, 5);

        cout << s << '\n';
    }

    return 0;
}

:::

## Div.2 Problem H / Div. 1 Problem C 字母加法問題

### By Colten

**考點: 字元 & 實作**

此題提供其中一種思考路線

1. 判斷字元是否為0~9的數字，如果是可以直接將數字接上，否則須將大寫字母轉成數字
2. 如果接數字時該數字 $>=10$ 則必須將數字做分解再將其接上
3. 最後將兩組接玩的數字相加

特別注意 : 賽中發現有人忘記開 long long 導致 WA 請記得在做此題目時要開 long long

::: spoiler 參考作法

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	string a,b;
	
	int i,n,k;
	
	cin >> a >> b;
	
	int x = 0,y = 0;
	
	for(i=0;i<a.size();i++)
	{
		if(a[i]>='A' && a[i] <= 'Z')
		{
		    if(a[i]>='J')
		    {
		        int u = (a[i]-'A'+1);
		        
		        vector <int> c;
		        
		        while(u!=0)
		        {
		            c.push_back(u%10);
		            
		            u /= 10;
		        }
		        
		        for(k=c.size()-1;k>=0;k--)
		        {
		            x *= 10;
		            
		            x += c[k];
		            
		        }
		    }
		    else
		    {
		        x *= 10;
		        
		        x += (a[i]-'A'+1);
		    }
		}
		else
		{
		    x *= 10;
		    
			x += (a[i]-'0');
		}
	}
	for(i=0;i<b.size();i++)
	{
		if(b[i]>='A' && b[i] <= 'Z')
		{
		    if(b[i]>='J')
		    {
		        int u = (b[i]-'A'+1);
		        
		        vector <int> c;
		        
		        while(u!=0)
		        {
		            c.push_back(u%10);
		            
		            u /= 10;
		        }
		        
		        for(k=c.size()-1;k>=0;k--)
		        {
		            y *= 10;
		            
		            y += c[k];
		            
		        }
		    }
		    else
		    {
		        y *= 10;
		        
		        y += (b[i]-'A'+1);
		    }
		}
		else
		{
		    y *= 10;
		    
			y += (b[i]-'0');
		}
	}
	
	cout << x + y << "\n";
	
	return 0;
}

:::

## Div.2 Problem I / Div. 1 Problem D Colten 與 貢丸 的優先客人系統

### By Colten

**考點: STL-Set**

可以將非 $-1,-2$ 的數字加進 set 集合內 對於每筆查詢

可以利用 begin,rbegin,*max_element,*min_element 等等...

去取得最大值以及最小值

特別注意 :
1. set 必須開 multiset
2. 如果是直接把最大值或最小值 erase 的人記得要先查好剩下的還有幾個 erase 完後要 insert 回去

::: spoiler 參考作法 (element)

#include <iostream>  
  
#include <set>  
  
#include <algorithm>  
  
using namespace std;  
  
int main(void)  
{  
    cin.tie(0);  
      
    ios_base::sync_with_stdio(false);  
      
    multiset <long long int> myset;  
      
    long long int q,n,i,k;  
      
    cin >> q;  
      
    while(q--)  
    {  
        while(cin>>n)  
        {  
            if(n==0)  
            {  
                cout << "\n";  
                  
                myset.clear();  
                  
                break;  
            }  
            else if(n<0) 
            {
            	if(myset.size() == 0)
            	{
            		cout << -1 << " ";
            		
            		continue;
				}
            	
                if(n==-2)  
                { 
                    long long int count = 0,big= *max_element(myset.begin(),myset.end());  
                  
                    count = myset.count(big) - 1;  
                      
                    cout << big << " ";  
                      
                    myset.erase(big);  
                      
                    for(i=0;i!=count;i++)  
                    {  
                        myset.insert(big);  
                    }   
                }  
                else if(n==-1)  
                {  
                    long long int count = 0,small= *min_element(myset.begin(),myset.end());  
                  
                    count = myset.count(small) - 1;  
                      
                    cout << small << " ";  
                      
                    myset.erase(small);  
                      
                    for(i=0;i!=count;i++)  
                    {  
                        myset.insert(small);  
                    }  
                }  
            }  
            else if(n>0)  
            {  
                myset.insert(n);  
            }  
        }  
    }  
      
    return 0;  
}

:::

## Div.2 Problem J / Div. 1 Problem E 西北望鄉何處是 東南見月幾回圓

### By Colten

**考點: 數論 & 實作**

如果暴力解的話可能只會拿到部分的分數，這時我們就要來想想如何優化

對於 $(S_i=b_i*a_1*b_i*a_2*...*b_i*a_n)$ 我們可以將其化簡成

$S_i=(a_1+a_2+...+a_n)*b_i^n$

對於取得 $b_i^n$ 的值時我們可以使用 **快速冪** 來提升效率

這麼一來程式的執行效率就提升了很多 !

::: spoiler 參考作法

#include <bits/stdc++.h>

#define ll long long

using namespace std;

ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll ans=fpow(a*a%m,b/2,m);
    return (b%2?ans*a%m:ans);
}
#define MotoHaiyaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(ll i=0;i<n;i++)
signed main()
{
    MotoHaiyaku
    ll n,m,ans1=1,ans2=1,MOD=1e8+7;
    cin>>n>>m;
    rep(i,n+m)
    {
        ll a;
        cin>>a;
        if(i<n) ans1=ans1*a%MOD;
        else ans2=ans2*a%MOD;
    }
    cout<<fpow(ans1,m,MOD)*fpow(ans2,n,MOD)%MOD;
}

:::

## Div. 1 Problem F 風原資訊社分組問題

### By Colten

**考點: 數論**

在進行分組的時候要讓 $GCD>1$ 最簡單的想法應該是讓每個分組的數

相加都為偶數，這麼一來就可以確保 $GCD >= 2$

所以我們只要確保以下幾點

1. 奇數 + 奇數 = 偶數
2. 偶數 + 偶數 = 偶數

開兩個陣列先把雞樹根偶數分類出來最後在依照以上兩點去做分組

如此一來即可達成題目對分組的要求

::: spoiler 參考作法

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	int n,i,k;
	
	cin >> n;
		
	int need = n - 1;
		
	vector <int> odd;
		
	vector <int> even;
		
	for(i=0;i<2*n;i++)
	{
		int input;
			
		cin >> input;
			
		if( input % 2 == 1 )
		{
			odd.push_back(i+1);
		}
		else
		{
			even.push_back(i+1);
		}
	}
		
	for(i=1;i<odd.size()&&need!=0;i+=2,need--)
	{
		cout << odd[i] << " " << odd[i-1] << "\n";
	}
		
	for(i=1;i<even.size()&&need!=0;i+=2,need--)
	{
		cout << even[i] << " " << even[i-1] << "\n";
	}
	
	return 0;
}

:::

## Div. 1 Problem G 風原飛鏢之中強大的 Qum 值

### By Colten

**考點: 思維 & 實作**

題目要求每個數之間的差不能小於 $2$

這題其實算一個梗題，提供兩種做法
1. 使用 deque 分別依序重複做 push_back 以及 push_front
2. 先輸出基數再輸出偶數 ex.(1 3 5 7 9 2 4 6 8 10)

以上兩點都可以達成題目的需求

特別注意 : 使用第一個作法時須先將 5 個數字排好再進行 push 的動作

這邊提供其中一種排法 (3 1 4 2 5)

::: spoiler 參考作法

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int q,n,i,k;
	
	cin >> q;
	
	while(q--)
	{
		deque <int> a;
		
		cin >> n;
		
		a.push_back(3);
		
		a.push_back(1);
		
		a.push_back(4);
		
		a.push_back(2);
		
		a.push_back(5);
		
		for(i=6;i<=n;i++)
		{
			if( i % 2 == 0 )
			{
				a.push_front(i);
			}
			else
			{
				a.push_back(i);
			}
		}
		
		for(i=0;i<n;i++)
		{
			cout << a[i] << " ";
		}
		
		cout << "\n";
	}
	
	return 0;
} 

:::

## Div. 1 Problem H

本題中二進位魔咒即為 de Bruijn sequence。

令子字串 $S(i, n)$ 轉換成整數的值為 $a_i$。對於所有 $i > 1$，$a_i$ 必為 $a_{i-1}\ mod\ 2^{n-1} \times 2$ 或 $a_{i-1}\ mod\ 2^{n-1} \times 2 + 1$，其中 $a\ mod\ b$ 表示 $a$ 除以 $b$ 的餘數。

暴力枚舉並檢查排列可得約 9 分。亦可人工枚舉並輸出 $n$ 值較小的結果。

其中一種快速的構造方式為，$a_1 = 0$，對於 $i > 1$，若 $a_{i-1}\ mod\ 2^{n-1} \times 2 + 1$ 尚未出現在序列 $a$ 中，則 $a_i = a_{i-1}\ mod\ 2^{n-1} \times 2 + 1$；否則，$a_i = a_{i-1}\ mod\ 2^{n-1} \times 2$。

在判斷一數是否已出現在序列中時，若使用 `set` 等資料結構會導致 $n$ 較大時 `Time Limit Exceeded`，可得到約 73 分。使用 `bool` 陣列即可得到滿分。

:::spoiler 參考作法

#include<bits/stdc++.h>
using namespace std;

bool use[1 << 25];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i < n; i++)
        cout << 0;

    int t = 1 << n, now = 0;
    while (t--)
    {
        use[now] = true;
        cout << (now & 1);

        int tt = (now & ((1 << (n - 1)) - 1)) << 1;
        if (!use[tt + 1])
            now = tt + 1;
        else
            now = tt;
    }
    cout << '\n';

    return 0;
}

:::

## Div. 1 Problem I
### By amano_hina
(working in progress)
這題很簡單吧~
先來講講要怎麼拿各個子題的分好了
子題1:題目範例
跳過
子題2:$y$是質數
注意到在$x$和$y$之間一定不存在一數被含有質數$y$的因子，根據一些簡單的數論知識，在這個子題中一定沒有滿足題意的解，故直接輸出$-1$即可通過這個子題
子題3:$y\le 10^{6}$
這個子題就直接把在$x$跟$y$之間的所有數看能不能整除，假設能整除就直接輸出此數和$xy$除以此數，假設跑到最後沒有任何數可整除$xy$，就輸出$-1$
最差時間複雜度為$O(yt)$
子題4:$y\le 10^{7}$
注意到

:::spoiler 參考程式碼

:::