# 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]}]<<" ";
}
```
:::
Sign in with Wallet
Connect another wallet