# 2025/5/5 小考題解
## 題目都在cchs OJ上。
## 1. 簽到題 (相乘為積 無限為極) by 唐狗針
小觀察：
> 如果 $a=b$ 且 $ax=by$ 且 $abxy> 0$ 則 $x=y$ 成立

第二個觀察：
> 對於任意數對$(x,y),x\neq y,xy> 0$ 有 $x\times \frac{xy}{x} =y\times \frac{xy}{y}$ 且 $\frac{xy}{x}\neq\frac{xy}{y}$

因此對於一數列 $A_1,A_2,\dots,A_n$ 只要滿足$\forall \ (i,j),\ 1\le i<j\le n,\ A_i\neq A_j$ 則有 $\forall \ (i,j),\ 1\le i< j \le n,\ A_i\times \frac{\prod_{k=1}^{n}A_k}{A_i}=A_j\times \frac{\prod_{k=1}^{n}A_k}{A_j}$ 且 $\forall \ (i,j),\ 1\le i< j \le n, \ \frac{\prod_{k=1}^{n}A_k}{A_i}\neq\frac{\prod_{k=1}^{n}A_k}{A_j}$，因此必有解。

且根據第一個觀察可知，若取出的序列有兩項相同元素必無解。

答案即為數列中的相異元素個數。

- AC code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,x;
    set<int> s;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        s.insert(x);
    }
    cout<<s.size()<<'\n';
}

## 2. 遞迴 (在異世界如何處理朋友關係呢) by flightz
小觀察 :
> $1 \le n \le 20$，考慮 $2^n$ 的作法。

考慮遞迴枚舉，枚舉到第 $i$ 項時，分兩堆紀錄總和到第 $i$ 項的總和，做完最後一項的時候去算兩堆的差，求最小的差，發現到結果是好的。

* AC CODE

#include <bits/stdc++.h>
 
#define ll long long
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
long long solve(int idx, ll* arr, ll sum1, ll sum2, int x) {
    if(idx==x) {
        return abs(sum1-sum2);
    }
    return min(solve(idx+1, arr, sum1+arr[idx], sum2, x), solve(idx+1, arr, sum1, sum2+arr[idx], x)); 
} 
int main(){
	fast
    int x;
    cin>>x;
    ll arr[x];
    for(int i=0;i<x;i++) {
        cin>>arr[i];
    }
	cout<<solve(0, arr, 0, 0, x);
}

## 3. STL (第五人格) by flightz
小觀察 :
> 這其實就是約瑟夫問題的實作。

注意到我們需要的資料結構需要刪除及查找最前項以及插入到最後面。考慮 $\text{linked-list}$ or $\text{queue}$。

* AC CODE (using $\text{queue}$)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll x;
    cin>>x;
    queue<ll> q;
    for(int i=1;i<=x;i++) q.push(i);
    bool t=0;
    while(!q.empty()) {
        ll k=q.front();
        q.pop();
        if(t) cout<<k<<" ";
        else q.push(k);
        t=!t;
    }
	return 0;
}

## 4. 圖論(因果終章) by 唐狗針
小觀察 :
> 反圖中點 $v$ 到點 $u$ 等價於正圖中點 $u$ 到點 $v$

根據這個觀察，從 $K$ 個點到點 $T$ 等價於從點 $T$ 到 $K$ 個點。

所以做法就是反向建邊，然後從 $T$ 作為起點BFS，之後取 $K$ 個點中距離最近的即為答案。

- AC code

#include <bits/stdc++.h>
using namespace std;
int n, m, k, t;
int hd[200500], to[200500], nxt[200500];
int a[200500];
int dis[200500];
int cnt = 1;
void addE(int a, int b) {
  nxt[cnt] = hd[a];
  to[cnt] = b;
  hd[a] = cnt++;
}
signed main() {
  cin >> n >> m >> k >> t;
  int x, y;
  for (int i = 1; i <= m; i++) {
    cin >> x >> y;
    addE(y, x);
  }
  for (int i = 1; i <= k; i++)
    cin >> a[i];
  queue<int> q;
  q.push(t);
  dis[t] = 1;
  while (q.size()) {
    auto tp = q.front();
    q.pop();
    for (int e = hd[tp]; e; e = nxt[e]) {
      if (dis[to[e]] == 0) {
        dis[to[e]] = dis[tp] + 1;
        q.push(to[e]);
      }
    }
  }
  int ans = 1e9;
  for (int i = 1; i <= k; i++) {
    if (dis[a[i]])
      ans = min(ans, dis[a[i]] - 1);
  }
  if (ans == 1e9)
    cout << -1 << '\n';
  else
    cout << ans << '\n';
}

另一種做法是，把 $K$ 個點都丟進queue中作為起點，去做BFS，也能通過但我沒有寫。

也可以 $K$ 個點都作為起點做 $K$ 次BFS，時間複雜度是 $O(K(N+M))$ ，理論上不能過，但我沒有特別卡。
## 5. DP (轉生異世界成為國手又統一世界那檔事) by flightz
小觀察 :
> $1 \le nk \le 10^8$，可以考慮 $O(nk)$的作法。

第二個觀察：
> 在第 $i$ 元沒有對應的幣值時，定義 $dp[i]$ 是湊成 $i$ 元所要用的最少硬幣數量 ，如果 $dp[i-p_j], 1 \le j \le n$ 是湊成 $i-p_j$ 元所要用的最少硬幣數量，則 $dp[i]=\min (dp[i-p_j]+1) 1 \le j \le n$，即去找最小的 $dp[i-p_j], 1 \le j \le n$

第三個觀察：
> 如果 $\forall n,1\le n \le i-1, dp[n]$ 都已經好了，那 $dp[i]$ 的最少硬幣數就可以透過枚舉透過哪一種硬幣從 $dp[i-p_j]$ 來轉移。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long n, x;
    cin >> n >> x;
    vector <long long> c(n), dp(x+1,INT_MAX);
    for(long long &a : c) cin >> a;
    dp[0] = 0;
    for(int i = 1;i <= x;i++){
        for(int j = 0;j < n;j++){
            if(i-c[j] >= 0){
                dp[i] = min(dp[i], dp[i-c[j]]+1);
            }
        }
    }
    if(dp[x] == INT_MAX) cout << "-1\n";
    else cout << dp[x] << '\n';
}

## 6. 二分搜(在光暈交錯之處) by 唐狗針

又是小觀察 :
> 半徑越大，交點數量也會越多，半徑越小，交點數量也越少。

因此如果設 $f(r)$ 為半徑為 $r$ 時的交點數量，這個函數會具有單調性，就能夠二分搜。
實作 $f(r)$ 時直接枚舉所有點對，計算他們間的距離，如果小於 $2r$ 就代表有交點。

那會有兩圓相切的問題嗎?
會，但問題不大，因為精度只要求到 $10^{-6}$。

每次檢查時是枚舉所有點對，時間複雜度是 $O(N^2)$，再套上二分搜，總複雜度是 $O(N^2logC)$，其中$C$是所有點對距離中最大的再乘上精度。

還有二分搜要對浮點數二分搜，你們可能沒寫過~~而且好像不在APCS範圍~~，所以我把這題當作滅台題，不過除了這點剩下應該都不難。

- AC code :

#include <bits/stdc++.h>
using namespace std;
int n, k;
int x[1050], y[1050];
double dis(int i, int j) {
  return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
int chk(double nw) {
  int ret = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (dis(i, j) == 2 * nw)
        ret++;
      else if (dis(i, j) < 2 * nw)
        ret += 2;
    }
  }
  return ret;
}
signed main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
    cin >> x[i] >> y[i];
  double l = 0, r = 2000;
  while (r - l > 1e-8) {
    double mid = (l + r) / 2;
    if (chk(mid) >= k)
      r = mid;
    else
      l = mid;
  }
  cout << fixed << setprecision(8) << l << '\n';
}