## 薄荷巧克力 (Icecream)
白話一點，就是找出有哪些數字有出現在$b$中但沒有出現在$a$中。因為題目有說$a_i,b_i\le 10^3$所以可以各開一個$10^3$的陣列紀錄個數字有沒有出現過。
有人想成圖論，如果對於每組$a_i,b_i$視為一條從$a_i\rightarrow b_i$的邊，那就是找出度為$0$的所有節點。
時間複雜度$O(n+sz)$
（$sz=10^3$）
### AC code
:::spoiler AC code
```cpp=
#include <bits/stdc++.h>
using namespace std;
signed main() { cin.tie(0) -> sync_with_stdio(0);
int n, sz = 1e3 + 5;
cin >> n;
vector<bool> a(sz), b(sz);
for(int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
a[x] = b[y] = true;
}
for(int i = 0; i < sz; ++i) {
if(b[i] && !a[i]) cout << i << ' ';
}
}
```
:::
## 數字轉換 (Password)
實作題，照著題目要求就可以AC了
本來評估實作時間為30-40分鐘，預計是你們都可以拿到，但好像有點慘
話說某人的AC code只有不到30行，你們還不AC是在幹嘛
### AC code
by chrislaiisme
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
#define LL loli
#define loli long long
using namespace std;
template<typename T> using Vec = vector<T>;
template<typename T> using Mat = Vec<Vec<T> >;
LL op;
string S;
Mat<LL> mat(4,Vec<LL>(4)), mat2[2] = {
{{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}},
{{2,1,1,3},{3,2,1,1},{1,3,2,1},{1,1,3,2}}
};
int main() {
cin >> op >> S;
for(LL i=0; i<4; i++) for(LL j=0; j<4; j++) mat[i][j] = stoi(S.substr((i*4+j)*2, 2));
for(LL T=0; T<10; T++) {
for(LL i=0; i<4; i++) for(LL t=0; t<i; t++) for(LL k=0; k<3; k++) swap(mat[i][k], mat[i][k+1]);
Mat<LL> tmp(4,Vec<LL>(4,0));
for(LL i=0; i<4; i++) for(LL j=0; j<4; j++) for(LL k=0; k<4; k++) tmp[i][j] = (tmp[i][j] + mat2[op-1][i][k]*mat[k][j])%64;
mat = tmp;
}
string str = "";
for(char chr='A'; chr<='Z'; chr++) str += chr;
for(char chr='a'; chr<='z'; chr++) str += chr;
for(char chr='0'; chr<='9'; chr++) str += chr;
str += '+', str += '/';
for(auto &i : mat) for(auto &j : i) cout << str[j]; cout << endl;
}
```
:::
## 怪物遊戲 (Monster)
首先可以有一個很直覺的greedy想法是將所有怪物對於$a_i$由小排到大(令排序完後怪物等級為陣列$a$，獲得等級為陣列$b$)
可以觀察到如果初始等級越大，能擊敗的怪物就越多，但是題目給定初始等級，而不是打倒幾隻怪物的最小初始等級
這時候可以有一個想法是開一個陣列(令陣列名稱為$dp$)預處理打倒$i$隻怪物所需要的最小等級，可以發現
$$
dp[i] =
\begin{cases}
b[0], & i = 0 \\
\min(dp[i-1], a[i]-\sum_{j=0}^{i-1}b_i), & else
\end{cases}
$$
之後對$dp$陣列用二分搜(std::upper_bound)出$L_j$能打倒幾隻怪物即可
時間複雜度:$O(nlogn+qlogn)$
### AC code
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define F first
#define S second
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define int long long
void solve(){
int n,q;cin>>n>>q;
vector<pii>v(n);
for(auto &i:v) cin>>i.F;
for(auto &i:v) cin>>i.S;
sort(all(v));
vector<int>dp(n);
dp[0]=v[0].F;
int cnt=v[0].S;
for(int i=1;i<n;i++){
dp[i]=max(dp[i-1],v[i].F-cnt);
cnt+=v[i].S;
}
while(q--){
int x;cin>>x;
cout<<upper_bound(all(dp),x)-dp.begin()<<'\n';
}
}
signed main(){
// cin.exceptions(cin.failbit);
IO;
int tt=1;
// cin>>tt;
while(tt--){
solve();
}
}
```
:::
## 移動數字 (Number)
這題最初想到的時候感覺不難，出題者自己寫一寫發現好像不太對（那個移動怎麼要那麼長啊啊啊雖然都是複製貼上但還是好長啊啊啊），最終考試裡不意外地完全沒人碰。
（只看行數，原來這題才是實作題嗎）
$40\%$解：用$\text{BFS}$，每種狀態當成一個節點，紀錄空格的位置，每次轉移（移動木塊）就是推入新的節點。要記錄有沒有遇過的$\text{bool}$陣列要用$\text{map}$。
令$n=3$，則我的寫法時間複雜度應該是$O((n^2)!\times n^2)$
$(n^2)!$是最差情況下，每種可能性都跑過；再乘以$n^2$是判斷是否到達終點。
註：有電神提出用雙向$\text{BFS}$，但我不會 :poop:
$100\%$解：注意到棋盤上只有九個一位數字，所以我們可以用一個$\text{long long}$變數代表棋盤。這樣的話常數和複雜度都會變小。
$\text{AC code}$中的$\text{getBit}$是提取出第$p$位數字，$\text{swapBit}$是交換第$z$和第$tar$個$\text{bit}$。至於裡面的$\text{auto}$是$\text{lambda function}$，有興趣的可以自行學習。
### code
#### 陣列版（40%）
若結果為-1，約需7500ms
:::spoiler 陣列版
```cpp=
#include <bits/stdc++.h>
//#include <ctime>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
//clock_t tStart, tEnd;
signed main() { cin.tie(0) -> sync_with_stdio(0);
vector<vector<int>> board(3, vector<int>(3));
pii zero; // position of blank square
for(int i = 0; i < 3; ++i) {
for(int j = 0; j < 3; ++j) {
cin >> board[i][j];
if(board[i][j] == 0) zero = make_pair(i, j);
}
}
//tStart = clock();
vector<vector<int>> goal = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
map<vector<vector<int>>, bool> vst;
queue<pair<pair<vector<vector<int>>, pii>, int>> q;
// {{gameBoard, zeroPos}, steps}
q.push({{board, zero}, 0});
vst[board] = true;
while(!q.empty()) {
auto cur = q.front();
q.pop();
if(cur.f.f == goal) {
cout << cur.s;
return 0;
}
vector<vector<int>> tmp = cur.f.f;
int a = cur.f.s.f, b = cur.f.s.s;
// push 1 square
vector<int> dx = {-1, 0, 0, 1}, dy = {0, -1, 1, 0};
for(int i = 0; i < 4; ++i) {
int x = a + dx[i], y = b + dy[i];
if(x >= 0 && x < 3 && y >= 0 && y < 3) {
swap(tmp[a][b], tmp[x][y]);
if(!vst[tmp]) q.push({{tmp, {x, y}}, cur.s + 1}), vst[tmp] = true;
swap(tmp[a][b], tmp[x][y]);
}
}
// push 2 squares
if(a == 0) {
swap(tmp[0][b], tmp[1][b]);
swap(tmp[1][b], tmp[2][b]);
if(!vst[tmp]) q.push({{tmp, {2, b}}, cur.s + 1}), vst[tmp] = true;
swap(tmp[1][b], tmp[2][b]);
swap(tmp[0][b], tmp[1][b]);
}
if(a == 2) {
swap(tmp[1][b], tmp[2][b]);
swap(tmp[0][b], tmp[1][b]);
if(!vst[tmp]) q.push({{tmp, {0, b}}, cur.s + 1}), vst[tmp] = true;
swap(tmp[0][b], tmp[1][b]);
swap(tmp[1][b], tmp[2][b]);
}
if(b == 0) {
swap(tmp[a][0], tmp[a][1]);
swap(tmp[a][1], tmp[a][2]);
if(!vst[tmp]) q.push({{tmp, {a, 2}}, cur.s + 1}), vst[tmp] = true;
swap(tmp[a][1], tmp[a][2]);
swap(tmp[a][0], tmp[a][1]);
}
if(b == 2) {
swap(tmp[a][1], tmp[a][2]);
swap(tmp[a][0], tmp[a][1]);
if(!vst[tmp]) q.push({{tmp, {a, 0}}, cur.s + 1}), vst[tmp] = true;
swap(tmp[a][0], tmp[a][1]);
swap(tmp[a][1], tmp[a][2]);
}
}
cout << -1;
//tEnd = clock();
//cout << "\nrun time: " << tEnd - tStart << "ms";
}
```
:::
#### 狀壓版（100%）
若結果為-1，約需120ms
:::spoiler 狀壓版
```cpp=
#include <bits/stdc++.h>
//#include <ctime>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
//clock_t tStart, tEnd;
signed main() { cin.tie(0) -> sync_with_stdio(0);
ll board = 0, zero;
for(int i = 0; i < 9; ++i) {
int k;
cin >> k;
board = 10 * board + k;
if(k == 0) zero = 8 - i;
}
//tStart = clock();
vector<ll> pow10 = {1};
for(int i = 0; i < 10; ++i) pow10.push_back(pow10.back() * 10);
auto getBit = [&pow10](ll &n, int &p) {
return n / pow10[p] % 10;
};
auto swapBit = [&getBit, &pow10](ll &n, int z, int tar) {
int k = getBit(n, tar), l = getBit(n, z);
n -= k * pow10[tar], n += k * pow10[z];
n -= l * pow10[z], n += l * pow10[tar];
};
ll goal = 123456780;
unordered_map<ll, bool> vst;
queue<pair<pair<ll, int>, int>> q;
// {{board, zeroPos}, steps}
q.push({{board, zero}, 0});
while(!q.empty()) {
auto pt = q.front();
q.pop();
ll cur = pt.f.f;
int z = pt.f.s, step = pt.s;
if(cur == goal) {
cout << step;
return 0;
}
if(z + 3 < 9) {
swapBit(cur, z, z + 3);
if(!vst[cur]) q.push({{cur, z + 3}, step + 1}), vst[cur] = true;
swapBit(cur, z, z + 3);
}
if(z - 3 >= 0) {
swapBit(cur, z, z - 3);
if(!vst[cur]) q.push({{cur, z - 3}, step + 1}), vst[cur] = true;
swapBit(cur, z, z - 3);
}
if(z / 3 == 0) {
swapBit(cur, z, z + 3);
swapBit(cur, z + 3, z + 6);
if(!vst[cur]) q.push({{cur, z + 6}, step + 1}), vst[cur] = true;
swapBit(cur, z + 3, z + 6);
swapBit(cur, z, z + 3);
}
if(z / 3 == 2) {
swapBit(cur, z, z - 3);
swapBit(cur, z - 3, z - 6);
if(!vst[cur]) q.push({{cur, z - 6}, step + 1}), vst[cur] = true;
swapBit(cur, z - 3, z - 6);
swapBit(cur, z, z - 3);
}
if(z % 3 > 0) {
swapBit(cur, z, z - 1);
if(!vst[cur]) q.push({{cur, z - 1}, step + 1}), vst[cur] = true;
swapBit(cur, z, z - 1);
}
if(z % 3 < 2) {
swapBit(cur, z, z + 1);
if(!vst[cur]) q.push({{cur, z + 1}, step + 1}), vst[cur] = true;
swapBit(cur, z, z + 1);
}
if(z % 3 == 0) {
swapBit(cur, z, z + 1);
swapBit(cur, z + 1, z + 2);
if(!vst[cur]) q.push({{cur, z + 2}, step + 1}), vst[cur] = true;
swapBit(cur, z + 1, z + 2);
swapBit(cur, z, z + 1);
}
if(z % 3 == 2) {
swapBit(cur, z, z - 1);
swapBit(cur, z - 1, z - 2);
if(!vst[cur]) q.push({{cur, z - 2}, step + 1}), vst[cur] = true;
swapBit(cur, z - 1, z - 2);
swapBit(cur, z, z - 1);
}
}
cout << -1;
//tEnd = clock();
//cout << "\nrun time: " << tEnd - tStart << "ms";
}
```
:::
## 一起走過的路 (Path)
note:第一個子測資只要輸出$0$就能拿到1分
我們可以先預處理從節點$1$走到節點$i(1\leq i \leq n)$所需時間
對於數對$(i,j),1\leq i< j\leq n$可以發現兩人分離的地方恰好是節點$i$與$j$的最近共同祖先，但若是出所有節點$i$與$j$求出最近共同祖先再一個一個加總答案，時間複雜度會是$O(n^2logn)$，會吃TLE
我們可以換另一個角度思考題目:對於所有數對$(i,j)$，節點$i$與$j$的最近共同祖先為節點$node$的數量有多少
於是，答案為
$$
\sum{}^{}最近共同祖先為節點node的次數 \times 從節點1走到節點node所需時間
$$
若是將節點$node$拔除，對於所有數對$(i,j)$，節點$i$與$j$在需要不同的樹中；或是一個節點為$node$，另一節點為以$node$為根的子樹，兩節點的最近共同祖先才會是$node$
這時候需要用排列組合，最近共同祖先為節點node的次數為「任兩子樹大小相乘後的加總」，但此一作法最差為$O(n^2)$，所以要改用另一計算方法為「以$node$為子樹中所有節點$i$與$j$中所有可能數量，減去節點$i$與$j$在同一子樹中的可能」
時間複雜度:$O(n)$
### AC code
記得 $mod\ 1000000007$
:::spoiler AC code
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define F first
#define S second
#define pii pair<int,int>
#define int long long
const int mod=1e9+7;
const int inf=9e18;
void dfs(vector<vector<pii>>&v,vector<int>&sbtsz,vector<int>&weight,int n){
for(auto i:v[n]){
weight[i.F]+=weight[n]+i.S;
dfs(v,sbtsz,weight,i.F);
sbtsz[n]+=sbtsz[i.F];
}
}
void solve(){
int n;cin>>n;
vector<int>a(n-1),b(n-1);
for(auto &i:a) cin>>i;
for(auto &i:b) cin>>i;
vector<vector<pii>>v(n+1);
for(int i=2;i<=n;i++){
v[a[i-2]].push_back({i,b[i-2]});
}
vector<int>sbtsz(n+1,1),weight(n+1);
dfs(v,sbtsz,weight,1);
int ans=0;
for(int i=1;i<=n;i++){
int cnt=sbtsz[i]-1;
cnt=cnt*(cnt-1)>>1;
for(auto j:v[i]){
cnt=cnt-(sbtsz[j.F]*(sbtsz[j.F]-1)>>1);
}
cnt+=sbtsz[i]-1;
ans=(ans+(((weight[i]%mod)*(cnt%mod))%mod)%mod);
}
cout<<ans%mod<<'\n';
}
signed main(){
// cin.exceptions(cin.failbit);
IO;
int tt=1;
// cin>>tt;
while(tt--){
solve();
}
}
```
:::
## 後記
出題者一覽:
薄荷巧克力 (Icecream):Boling
數字轉換 (Password):mattwu
怪物遊戲 (Monster):Vandrin
移動數字 (Number):Boling
一起走過的路 (Path):Vandrin
感謝william1010121的judge架設及chrislaiisme的驗題，所有人都幫了Vandrin很多忙
對於第二題與第三題題序有誤，十分抱歉
這一次的子任務沒有很多，若未來還有機會出題應該會增加子任務
在第三題有些$O(nq)$解可以通過子任務2，可能是常數太小通過(DDJ也會過)，但是所有submissions結果皆以提交在cms競賽中的結果為主
雖然這次題目有大概按照難度排序，但是很多競賽其實都不太會對題目難度做排序，在沒有計分板的情況下，建議在每次競賽先確保了解所有題目題意後再決定作答
Sign in with Wallet
Connect another wallet