---
title: 2020 12 月 Ten Point Round 題解
lang: zh-tw
tags: 題解
---

# 2020 12 月 Ten Point Round #4 題解
:::warning
<div class=display >

</div>
<div class=display>
<font size=5px color=indigo>
<strong>以下資訊由NHDK南部資訊沙漠提供</strong>
</font>
</br>
<img src="https://i.imgur.com/KLFGxoU.jpg" weight=300 height=300>
</div>
<style>
.display {
text-align:center;
}
</style>
:::

---

## Div.2

### pA 零錢兌換

**Prepared By Colten**

考點 : 基本輸入輸出

由於 $N$ 可能 $<5$ 所以最穩定的做法為不管 $N$ 為多少，全部都使用 $1$ 元的零錢

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n;
	
	cin >> n;
	
	cout << n << " " << 0 << "\n";
	
	return 0;
} 

:::

### pB 三個數字比大小

**Prepared By Colten**

考點 : 條件判斷

備註 : 如果會使用自訂義 compare 的人這題的程式碼會較為精簡

可以一開始宣告三個變數去紀錄，比自己小或相等的數字有幾個

既然要找到第二大的數字，那麼就是找那三個用來紀錄的變數中第二大的

(也就是比自己小或相等的數字數量第二多的)

:::spoiler 參考解法 (C++) - if / else 版

#include <bits/stdc++.h>
 
#define int long long 
 
using namespace std;
 
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int a,b,c;
	
	cin >> a >> b >> c;
	
	int a2=0,b2=0,c2=0;
	
	if( a % 2 == 1 && b % 2 == 0 )
	{
		a2++;
	}
	if( a % 2 == 1 && c % 2 == 0 )
	{
		a2++;
	}
	if( b % 2 == 1 && a % 2 == 0 )
	{
		b2++;
	}
	if( b % 2 == 1 && c % 2 == 0 )
	{
		b2++;
	}
	if( c % 2 == 1 && a % 2 == 0 )
	{
		c2++;
	}
	if( c % 2 == 1 && b % 2 == 0 )
	{
		c2++;
	}
	
	if( a % 2 == b % 2 )
	{
		if( a > b )
		{
			a2++;
		}
		else if( b > a )
		{
			b2++;
		}
		else
		{
			a2++;
			
			b2++;
		}
	}
	if( a % 2 == c % 2 )
	{
		if( a > c )
		{
			a2++;
		}
		else if( c > a )
		{
			c2++;
		}
		else
		{
			a2++;
			
			c2++;
		}
	}
	if( b % 2 == c % 2 )
	{
		if( b > c )
		{
			b2++;
		}
		else if( c > b )
		{
			c2++;
		}
		else
		{
			b2++;
			
			c2++;
		}
	}
	
	if( a2 >= b2 && a2 <= c2 )
	{
		cout << a << "\n";
	}
	else if( a2 >= c2 && a2 <= b2 )
	{
		cout << a << "\n";
	}
	else if( b2 >= a2 && b2 <= c2 )
	{
		cout << b << "\n";
	}
	else if( b2 <= a2 && b2 >= c2 )
	{
		cout << b << "\n";
	}
	else
	{
		cout << c << "\n";
	}
	
	return 0;
} 

:::

### pC 矩形廣場圍欄模擬

**Prepared By Colten**

考點 : 迴圈 Loop

只要依照題目所給的要求去在該建設圍欄的地方輸出 $*$ 此題就解決了 !

:::spoiler 參考解法 (C++)

#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;
	
	int u = 1;
	
	while(q--)
	{
		int a,b,ans = 0;
		
		cin >> a >> b;
		
		cout << "Case " << u << ":\n";
		
		u++;
		
		for(i=0;i!=b;i++)
		{
			for(k=0;k!=a;k++)
			{
				if( k == 0 || k == a - 1 )
				{
					cout << "*";
					
					ans++;
				}
				else if( i == 0 || i == b - 1 )
				{
					cout << "*";
					
					ans++;
				}
				else
				{
					cout << " ";
				}
			}
			
			cout << "\n";
		}
		
		cout << "Use " << ans << " fences\n";
	}
	
	return 0;
}

:::

### pD 社團小遊戲

**Prepared By Colten**

考點 : 條件判斷 & 字元字串

此題如果單純使用整數去判斷的話可以取得 $80$ 分

不過如果要取得剩下的 $20$ 分必須使用 **字串** 來解決問題

$3$ 的倍數的判斷方法為該數每位的數字相加可整除 $3$ 則為 $3$ 的倍數

:::spoiler 參考解法 (C++)

#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;
	
	cin >> a;
	
	int i,k;
	
	int total = 0;
	
	for(i=0;i<a.size();i++)
	{
		total += (a[i]-'0');
	}
	
	if( total % 3 == 0 )
	{
		cout << "Win\n";
	}
	else
	{
		cout << "Lose\n";
	}
	
	return 0;
} 

:::

### pE 千萬伏特的分組

**Prepared By Colten**

考點 : 實作

題目想要進行分組且找到最小的 $RUB$ 且 $(RUB >= 0)$

我們可以先進行排序後，搜尋相鄰的兩個數字之間最小的差 $|a_i-a_{i+1}|$

最小的差即為最小的 $RUB$

參考編組如下 :

我們可以使第一組編成 $(a_1,a_2,a_3,...,a_{i-3},a_{i-2},a_{i+1})$ 此時因排序此組最大值為 $a_{i+1}$

第二組編成 $(a_{i},a_{i+2},a_{i+3},a_{i+4},...,a_n)$ 此組最小值為 $a_{i}$

$RUB = a_{i+1} - a_{i}$

:::spoiler 參考解法 (C++)

#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;
		
		vector <int> e;
		
		for(i=0;i<n;i++)
		{
			int input;
			
			cin >> input;
			
			e.emplace_back(input);
		}
		
		sort(e.begin(),e.end());
		
		int mn = 1e9;
		
		for(i=1;i<n;i++)
		{
			int check = e[i] - e[i-1];
			
			mn = min(mn,check);
		}
		
		cout << mn << "\n";
	}
	
	return 0;
} 

:::

### pF 風原特色圓環 Treffic Circle - II

**Prepared By Colten**

考點 : Greedy

只要兩種不同的圓環之間選兩個圓環蓋一條路($100$ 元)剩下的圓環都跟自己同種類的蓋道路 ($0$ 元) 這樣假如當兩種種類的圓環同時存在時最少花費必定為 $100$ 元，只存在單種種類的圓環則為 $0$ 元

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int a,b;
	
	cin >> a >> b;
	
	cout << ( a == 0 || b == 0 ? 0 : 100 ) << "\n";
	
	return 0;
}

:::

### pG 走廊折返跑

**Prepared By Colten**

**由於題目有所爭議，賽中決定刪除此題並延長比賽 1 小時**

### pH 風原評測系統

**Prepared By Colten**

考點 : 實作 & 字元字串

此題只要照著題目意思去進行模擬即可

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long

using namespace std;

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	string name;
	
	getline(cin,name);
	
	int n,i,k;
	
	cin >> n;
	
	int time;
	
	cin >> time;
	
	cout << name << "\n"; 
	
	for(i=1;i<=n;i++)
	{
		string a,b;
		
		int usetime;
		
		cin.ignore();
		
		getline(cin,a);
		
		getline(cin,b);
		
		cin >> usetime;
		
		cout << "Test " << i << ": ";
		
		if( usetime > time )
		{
			cout << "Time Limit Exceeded\n";
		}
		else
		{
			if( a == b )
			{
				cout << "Accepted\n";
			}
			else
			{
				cout << "Wrong Answer\n";
			}
		}
	}
	
	return 0;
} 

:::

## Div.1

### pA

**同 Div.2 pG**

### pB 寶石

**Prepared By Fysty**

第一批寶石融合完之後，剩下的寶石純度都非負，也就是說假設第$i$批寶石純度最高是$M_i$，則有$M_1\ge M_2\ge...$，所以答案直接取第一次融合完的最高純度就好，換句話說，答案就是$$max_{1\le i\le n}{a_i}-min_{1\le i\le n}{a_i}$$

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
const ll INF=2e18;
int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,mn=INF,mx=-INF;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            ll k;
            cin>>k;
            mn=min(mn,k);
            mx=max(mx,k);
        }
        cout<<mx-mn<<"\n";
    }
}

:::

### pC

**同 Div.2 pH**

### pD 聖誕節禮物

**Prepared By Colten**

考點 : 動態規劃

在選禮物的規則中我們可以推出轉移式

**$dp[i]$ 為考慮 $(a_1...a_i)$ 的最大總合**

$dp[i] = max(dp[i-2]+a[i],dp[i-1])$

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>

#define int long long 

using namespace std;

int a[100005],dp[100005];

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int q,n,i,k;
	
	cin >> q;
	
	while(q--)
	{
		cin >> n;
		
		memset(dp,0,sizeof dp);
		
		memset(a,0,sizeof a);
		
		for(i=1;i<=n;i++) cin >> a[i];
		
		dp[0] = 0;
		
		dp[1] = a[1];
		
		for(i=2;i<=n;i++)
		{
			dp[i] = max(dp[i-2] + a[i],dp[i-1]);
		}
		
		cout << dp[n] << "\n";
	}
	
	return 0;
} 

:::

### pE 貼紙

**Prepared By Fysty**

令$S=\sum a_i$。
假設有$x$個橫的$y$個直的($x+y=m,0\le x\le n,0\le y\le n$)。
若$x$個橫的是放在第$i_1,i_2,...,i_x$行，$y$個直的是放在第$j_1,j_2,...,j_y$列，令$A=\sum a_{i_k},B=\sum a_{j_k}$則$W=nS-xB-yA+AB$，
整理過後變成$W=nS+(A-x)(B-y)-xy$。
固定$x,y$時，因為$A\ge x,B\ge y$，所以$A,B$越大越好，故我們可以greedy取$a$裡面前$x$大的和前$y$大的和，事前sort完算前綴和就可以$O(1)$算出來了。
:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=LLONG_MAX;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,m,ans=-INF;
        cin>>n>>m;
        vector<ll> a(n),sum(n+1,0);
        rep(i,n) cin>>a[i];
        sort(a.begin(),a.end(),greater<ll>());
        rep1(i,n) sum[i]=sum[i-1]+a[i-1];
        rep(i,m+1)
        {
            if(i>n||m-i>n) continue;
            ans=max(ans,sum[n]*m+(sum[i]-i)*(sum[m-i]-m+i)-i*(m-i));
        }
        cout<<ans<<"\n";
    }
}

:::

### pF 菜月昴與XOR
**Prepared By Fysty**

透過觀察我們可以發現：$$f(n)=\left\{\begin{array}{ll}
n, & \mbox{if $n\equiv 0\mod 4$} \\
1, & \mbox{if $n\equiv 1\mod 4$} \\
n+1, & \mbox{if $n\equiv 2\mod 4$} \\
0, & \mbox{if $n\equiv 3\mod 4$}
\end{array} \right.$$
所以除了$x=0,1$的時候答案會是$\sum 4k+3,\sum4k+1$以外，
如果$x\equiv0\mod4$，那答案不是$0$就是$x$。
如果$x\equiv3\mod4$，那答案不是$0$就是$x-1$。
而其他全部都是$0$。
:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll x,n;
        cin>>x>>n;
        if(x==0)
        {
            ll k=n/4*4+3;
            if(k>n) k-=4;
            cout<<(k+3)*((k-3)/4+1)/2<<"\n";
        }
        else if(x==1)
        {
            ll k=n/4*4+1;
            if(k>n) k-=4;
            cout<<(k+1)*((k-1)/4+1)/2<<"\n";
        }
        else if(x%4==0&&x<=n) cout<<x<<"\n";
        else if(x%4==3&&x-1<=n) cout<<x-1<<"\n";
        else cout<<"0\n";
    }
}

:::

### pG 打擊成績
**Prepared By amano_hina**

首先，如果打擊率是0或1，答案分別是"0 1"和"1 1"

再來，如果打擊率並非以上兩種，則可由四捨五入的定義列出一條類似以下形式的不等式

$$?_{1}\le \frac{ans1}{ans2} < ?_{2}$$

之後再用輾轉相除法就可以了喔

注意在輾轉相除法時不等號的位置

時間複雜度$O(t\log M)$ $M$為小數點後面那一串所表示的數字

:::spoiler 參考解法 (C++)

#include<bits/stdc++.h>
using namespace std;
long long x=0,ans1,ans2,ans2too,t,a[20],n;
char c[20];
void findmin(long long x1,long long x2,long long y1,long long y2,long long way)
{
    if(way==2)
    {
        long long r;
        if(y2==0) r=LONG_LONG_MAX;
        else
        {
            r=y1/y2;
            if(y1%y2==0) r--;
        }
        long long l=x1/x2;
        if(x1%x2==0) l--;
        if(r!=l)
        {
            ans1=l+1;
            ans2=1;
            ans2too=ans2;
            return;
        }
        else
        {
            findmin(y2,y1-l*y2,x2,x1-l*x2,1);
            ans2too=ans2;
            ans2=ans1;
            ans1=ans2*l+ans2too;
            ans2too=ans2;
            return;
        }
    }
    else
    {
        long long r=y1/y2;
        long long l=x1/x2;
        if(r!=l)
        {
            ans1=l+1;
            ans2=1;
            ans2too=ans2;
            return;
        }
        else
        {
            findmin(y2,y1-l*y2,x2,x1-l*x2,2);
            ans2too=ans2;
            ans2=ans1;
            ans1=ans2*l+ans2too;
            ans2too=ans2;
            return;
        }
    }
}
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    a[0]=1;
    for(int i=1;i<=18;i++) a[i]=a[i-1]*10;
    cin>>t;
    while(t--)
    {
        x=0;
        cin>>n;
        for(int i=0;i<n+2;i++) cin>>c[i];
        if(c[0]=='1') cout<<"1 1"<<'\n';
        else
        {
            for(int i=2;i<n+2;i++) x=10*x+c[i]-'0';
            if(x==0) cout<<"0 1"<<'\n';
            else
            {
                findmin(a[n+1],10*x+5,a[n+1],10*x-5,1);
                cout<<ans2<<" "<<ans1<<'\n';
            }
        }
    }
}

:::

### pH 指尖
**Prepared By Fysty**

首先如果存在$a_i\ge i$，則答案一定是$-1$。
否則我們一定可以構造出唯一的答案。

若最終排名為$b_1,b_2,..,b_n$
考慮一個集合$S=\{1,2,...,n\}$，
我們從$b_n$構造到$b_1$，
構造$b_i$時，$S$裡面還剩$n-i+1$個數字，其中一個是$b_i$，剩下的$n-i$個數字一定是$b_1$到$b_{n-i}$，而我們希望$b_i$要恰好輸給前面$a_i$個人，所以會發現$b_i$就是$S$裡面目前第$a_i+1$大的數字。將$b_i$從$S$中刪除，然後$i:=i-1$繼續跑，直到$i=1$，如此一來就得到我們要的排列了。

比較難的是每次要求第$a_i+1$大的數，這有幾種實作方法，可以用線段樹或BIT或pbds(?)，官解用的是線段樹。

:::spoiler 參考解法 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define F first
#define S second
const ll INF=2e18;
const int N=200005;
ll st[4*N],a[N];
void build(ll l,ll r,ll id)
{
    if(l==r) st[id]=1;
    else
    {
        ll mid=(l+r)/2;
        build(l,mid,2*id+1);
        build(mid+1,r,2*id+2);
        st[id]=st[2*id+1]+st[2*id+2];
    }
}
void update(ll l,ll r,ll x,ll id)
{
    if(l==r) st[id]=0;
    else
    {
        ll mid=(l+r)/2;
        if(x<=mid) update(l,mid,x,2*id+1);
        else update(mid+1,r,x,2*id+2);
        st[id]=st[2*id+1]+st[2*id+2];
    }
}
ll query(ll l,ll r,ll k,ll id)
{
    if(l==r)
    {
        if(st[id]==k) return l;
        else return -1;
    }
    else
    {
        ll mid=(l+r)/2;
        if(st[2*id+1]>=k) return query(l,mid,k,2*id+1);
        else return query(mid+1,r,k-st[2*id+1],2*id+2);
    }
}
int main()
{
    MottoHayaku
    ll t;
    cin>>t;
    while(t--)
    {
        ll n;
        bool x=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]>=i) x=1;
        }
        if(x)
        {
            cout<<"-1\n";
            continue;
        }
        vector<ll> ans;
        build(1,n,0);
        for(int i=n;i>=1;i--)
        {
            ll pos=query(1,n,st[0]-a[i],0);
            ans.pb(pos);
            update(1,n,pos,0);
        }
        for(int i=ans.size()-1;i>=0;i--) cout<<ans[i]<<" ";
        cout<<"\n";
    }
}

:::