---
# System prepended metadata

title: '2021 6 月 Ten Point Round #11 (Div. 2) 題解'

---

# 2021 6 月 Ten Point Round #11 (Div. 2) 題解

Hope you enjoyed the round!

<!---## Div.2--->
## pA Colten 所在的風原之路 (Fengyuan Road where Colten is located)
**Prepared By Colten**

其實觀察一下題目你會發現，一條道路連接著兩個圓環，也就代表有兩個圓環的道路數 $+1$，因此答案總是：$1959n + 3932m$

時間複雜度 $O(1)$

:::spoiler 參考解法 (C++) 
```cpp=
#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,m;
	
	cin >> n >> m;
	
	for(int i=0;i<m;i++)
	{
		int a,b;
		
		cin >> a >> b;
	}
	
	cout << 1959 * n + ( m * 2 ) * 1966 << "\n";
	
	return 0;
} 

```
:::

## pB 派對食物 (Party food)
**Prepared By Colten**

為了使最後每組套餐食物跟飲料的份數越多，因此我們要先求得 $GCD(x,y)$，$GCD(x,y)$ 就是我們所能分成的套餐組數，每組套餐的食物份數就是 $\frac{x}{GCD(x,y)}$，每組套餐的飲料份數就是 $\frac{y}{GCD(x,y)}$

時間複雜度：$O(\log(\min(x,y)))$

:::spoiler 參考解法 (C++) 
```cpp=
#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;
	
	int u = __gcd(a,b);
	
	cout << u << " " << a / u << " " << b / u << "\n";
	
	return 0;
}
```
:::

## pC Gunjyo 與骰子 (Gunjyo and dice)

**Prepared By Colten**

這題有一個重點是建表，如果你是在每一次輸入就去搜尋一次答案的話時間複雜度會是：$O(QN^3)$

因此我們在做任何輸入之前，就乾脆把 $1\sim100^3$ 的答案都先建好，花費 $N^3$ 的時間，接下來每組對答案的

詢問時間複雜度都只需要 $O(1)$，因此整體下來，時間複雜度 $O(N^3)$

:::spoiler 參考解法 (C++) 
```cpp=
#include <bits/stdc++.h>

#define int long long

using namespace std;

int check[1000005];

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	for(int i=1;i<=100;i++)
	{
		for(int k=1;k<=100;k++)
		{
			for(int j=1;j<=100;j++)
			{
				check[i*k*j]++;
				
				check[i+k+j]++;
				
				check[i+k*j]++;
				
				check[i*k+j]++;
			}
		}
	}
	
	int q;
	
	cin >> q;
	
	while(q--)
	{
		int n;
		
		cin >> n;
		
		cout << check[n] << "\n";
	}
	
	return 0;
} 
```
:::

## pD 序列交換 (Array swap)
**Prepared By Colten**

我們先觀察，如果我們要使相乘後所得到的結果越大，那麼我們一定是要使用 $a$ 中第 $i$ 大的值就跟 $b$ 中第 $i$ 大的值相乘

那麼要使結果越小，就是使 a 中第 $i$ 大的值跟 $b$ 中第 $i$ 小的值做相乘，如此以來，相加後的總合就會是最小的了。

時間複雜度：$O(N + NlogN)$

:::spoiler 參考解法 (C++) 
```cpp=
#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;
	
	cin >> q;
	
	while(q--)
	{
		int n;
		
		cin >> n;
		
		vector <int> a(n),b(n);
		
		for(int i=0;i<n;i++)
		{
			cin >> a[i];
		}
		for(int i=0;i<n;i++)
		{
			cin >> b[i];
		}
		
		sort(a.begin(),a.end());
		
		sort(b.begin(),b.end());
		
		int ans1 = 0,ans2 = 0;
		
		for(int i=0;i<n;i++)
		{
			ans1 += a[n-i-1] * b[n-i-1];
			
			ans2 +=  a[i] * b[n-i-1];
		}
		
		cout << ans1 << " " << ans2 << "\n";
	}
	
	return 0;
} 
```
:::

## pE 這就是我所認識的風原 (This is the Fengyuan I know)
**Prepared By Colten**

這題擴散的特性挺像 $BFS$ 的，做 $BFS$ 也可以，不過可能作法有點冗。

我們可以發現，不管對哪一個年級來說，只要每向外擴散一步，就是對那些還沒有到達的點的距離減少 $1$，因此我們
只要對每一個點與一二年級的起點，求出距離，距離越近，則代表該年級會最先到達那個點，如此一來就不用 $BFS$ 了。

感謝 $Dreamoon$ 提供此方法！

時間複雜度：$O(N^2)$

:::spoiler 參考解法 (C++) 
```cpp=
#include <bits/stdc++.h>

#define int long long

using namespace std;

int mp[1005][1005];

signed main(void)
{
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);
	
	int n;
	
	cin >> n;
	
	for(int i=0;i<n;i++)
	{
		for(int k=0;k<n;k++)
		{
			cin >> mp[i][k];
		}
	}
	
	int x1,x2,y1,y2;
	
	cin >> x1 >> y1 >> x2 >> y2;
	
	x1--;
	
	x2--;
	
	y1--;
	
	y2--;
	
	int ans1 = 0,ans2 = 0;
	
	for(int i=0;i<n;i++)
	{
		for(int k=0;k<n;k++)
		{
			if( mp[i][k] != 0 )
			{
				int u1 = abs(x1-i)+abs(y1-k);
				
				int u2 = abs(x2-i)+abs(y2-k);
				
				if( u1 <= u2 ) ans1 += mp[i][k];
				
				else ans2 += mp[i][k];
			}
		}
	}
	
	if( ans1 > ans2 ) cout << "Grade 1\n";
	
	else cout << "Grade 2\n";
	
	return 0;
} 
```
:::

## pF 凱莎密碼 (Kaisa cipher) 
**Prepared By Troy**
這題要根據輸入字串中某英文字母出現的次數，對某英文字母做往後偏移的動作，做法就是先讀入字串，然後去計每個字母出現的次數，再對原字串做偏移。

:::spoiler 參考解法 (C++) 
```cpp=
#include <bits/stdc++.h>
#define LoveRem ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
using namespace std;

int times[1010];
string dat;

signed main()
{
    LoveRem
    int n;
    cin>>n;
    while(n--){
        int i;
        cin>>i;
        cin.ignore();
        getline(cin,dat);
        for(int k=0;k<i;k++){
            memset(times,0,sizeof(times));
            if(dat[k]!=' '){
                int ch;
                ch = tolower(dat[k]);
                times[ch]++;
            }
        }//計出現次數
        for(int k=0;k<i;k++){
            if(dat[k]==' ') continue;
            else{
                if(dat[k]>='a'&&dat[k]<='z')
                    dat[k] = char((dat[k]+times[tolower(dat[k])]-'a')%26+'a');
                if(dat[k]>='A'&&dat[k]<='Z')
                    dat[k] = char((dat[k]+times[tolower(dat[k])]-'A')%26+'A');
            }
        }
        cout<<dat<<endl;
    }
}
```
:::

## pG 互動題 - 風原獎勵金 (Fengyuan reward)

**Prepared By Colten**

首先我們可以先詢問序列 $S$ 的長度。

接著我們再詢問 $[1,N]$ 取得此序列中最大值的數值。

再來我們慢慢去折半詢問，詢問左邊 $[1,\frac{(L+R)}{2}]$，後，假設回報的數值 $T$ 並不是序列中的最大值，則表示最大值的位置位於右邊，我們就可以將範圍限縮再 $[\frac{L+R}{2},R]$，反之亦然。

範圍縮到最後，$L = R$ 時，就為此序列最大值所在的位置。

:::spoiler 參考解法 (C++)
``` cpp
#include <bits/stdc++.h>

//#define int long long

using namespace std;

int ask(int l,int r)
{
	cout << "? " << l << ' ' << r << endl;
		
	int ans;
	
	cin >> ans;
	
	return ans;
}
int ask_size()
{
	int ans;
	
	cin >> ans;
	
	return ans;
}
signed main(void)
{	
	ios_base::sync_with_stdio(false);
	
	cin.tie(0);

	cout << '@' << endl;

	int n = ask_size();
	
	int l = 1,r = n;
	
	int mx = ask(1,n);
	
	while(1)
	{
		if( r == l )
		{
			cout << '!' << ' ' << r << endl;
			
			break;
		}
		
		int mid = ( l + r ) / 2;
		
		int u1 = ask(l,mid);
		
		if( u1 != mx )
		{
			l = mid + 1;
		}
		else
		{
			r = mid;
		}
	}
		
	return 0;
} 
```
:::

## pH 藤原千花與字串 (Chika Fujiwara and string)
**Prepared By Colten**

此題我們可以利用 set 內部元素為排序過後的特性，利用 prev 來取得上一個比新單詞還小的單詞，且這個單詞會是所有符合比新單詞還小的單詞中，字典序最大的一個。

時間複雜度：$O(NlogN)$

:::spoiler 參考解法 (C++) 
```cpp=
#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;
	
	cin >> q;
	
	set <string> s = {"A"};
	
	while(q--)
	{
		string input;
		
		cin >> input;
		
		if( s.count(input) != 0 )
		{
			cout << input << "\n";
			
			continue;
		}
		
		auto it = s.insert(input).first;
		
		string ans = *prev(it);
		
		if( ans == "A" ) cout << -1 << "\n";
		
		else cout << ans << "\n";
	}
	
	return 0;
} 

```
:::

## pI 複製，複製，再複製！(Copy copy copy！)
**Prepared By Colten**

我們定義 $dp[i]$ 表示操作 $i$ 次，最多能得到的字串數量。

初始狀態：

$dp[0] = dp[1] = 1$

$dp[2] = 2$

轉移：

$dp[i] = max(2dp[i-2],3dp[i-3])$

$2dp[i-2]$ 就是前兩次所能取得的最大字串數量，接著做全選 + 貼上。

$3dp[i-3]$ 則是前三次所能取得的最大字串數量，接著是全選 + 貼上 + 貼上。

時間複雜度：$O(logN)$

:::spoiler 參考解法 (C++) 
```cpp=
#include <bits/stdc++.h>

#define int long long

using namespace std;

int dp[60];

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

## pJ 道不相同 (Different tracks)
**Prepared By Fysty**

將兩個時間點的路線圖看成兩個圖 $G,H$。

可以利用 dfs 或是 dsu 找出一個圖中的所有連通塊。

令 $i$ 在 $G,H$ 所屬的連通塊為 $g_i,h_i$。

原題就變成對於每個 $i$，有多少個 $j$ 滿足 $g_i=g_j$ 且 $h_i=h_j$。

這可以利用 stl::map 實作。

總複雜度 $O(m+k+n\log n)$

:::spoiler 參考解法 (C++) 
```cpp=
#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 rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define F first
#define S second
const int MOD=1e9+7;
const ll INF=2e18;
const int N=2e5+5;
map<pll,ll> cnt;
vector<ll> ed[2][200005];
ll vis[2][200005],clr[2][200005],c=1;
void dfs(ll n,ll x)
{
    vis[x][n]=1;
    clr[x][n]=c;
    for(ll u:ed[x][n]) if(!vis[x][u]) dfs(u,x);
}
int main()
{
    MottoHayaku
    ll n,m,k;
    cin>>n>>m>>k;
    rep(i,m)
    {
        ll a,b;
        cin>>a>>b;
        ed[0][a].pb(b);
        ed[0][b].pb(a);
    }
    rep(i,k)
    {
        ll c,d;
        cin>>c>>d;
        ed[1][c].pb(d);
        ed[1][d].pb(c);
    }
    rep(j,2)
    {
        rep1(i,n)
        {
            if(!vis[j][i])
            {
                dfs(i,j);
                c++;
            }
        }
    }
    rep1(i,n) cnt[{clr[0][i],clr[1][i]}]++;
    rep1(i,n) cout<<cnt[{clr[0][i],clr[1][i]}]<<" ";
}
```
:::
