第九場比賽 題解
=
> 快來不及了

# [z081](https://judge.cp.ccns.io/problem/z081)：
簡單來說是做前綴和，在提示中有提到 xor 其實是在數某個 bit 的 1 到底出現過奇數次還是偶數次，也就是說 xor 運算有各種有的沒的交換結合率，並且 $(a \oplus b \oplus c \oplus d) \oplus (a \oplus b) = c \oplus d$ 也就是說可以透過再 xor 運算一次逆運算出 $c \oplus d$ 的結果

定義 $a \oplus \oplus b = X_{a} \oplus X_{a+1} \oplus ... \oplus X_{b}$
$(0 \oplus \oplus b) \oplus (0 \oplus \oplus a-1) 其實就等於 a \oplus \oplus b$ 也就是消去掉 $0 \oplus \oplus a-1$ 的部分

#include <bits/stdc++.h>
using namespace std;
int data[100010];
int quian[100010];
int main() {
    int n, m, i, j, k;

    quian[0] = 0;
    cin >> n >> m;
    for (i = 0; i < n; i++) {
        cin >> data[i];
    }
    for (i = 1; i <= n; i++) {
        quian[i] = quian[i - 1] ^ data[i - 1];
    }
    int a, b;
    while (m--) {
        cin >> a >> b;
        cout << (quian[b] ^ quian[a - 1]) << endl;
    }

    return 0;
}

# [z082](https://judge.cp.ccns.io/problem/z082)：
這題改編的意義就是，考慮到大家對於圖的陌生與熟悉度不足，希望藉由這題讓同學可以勇於思考，在不考慮複雜度的情況下想辦法解決問題。可以使用簡單的 BFS 過這題。
加油！！
# [z083](https://judge.cp.ccns.io/problem/z083)：
貪心法，因為比最低效益的圖書館效益高的蓋不蓋並不會影響整體效益，因此都可以蓋。
一直取最大效益的圖書館蓋直到針對每一個城市都擁有或其鄰近城市擁有圖書館為止。
則此時的整體效益為最大值，再往後依序建造圖書館就能求出第 K 大的整體效益。

#include <bits/stdc++.h>
using namespace std;
bool p[35050];
int v, e, k, x, y, q;
long long n[35050], ans;
vector<int> b[35050];
pair<int, long long> l[35050];
bool cmp(pair<int, long long> a,pair<int, long long> b){
	return a.second > b.second;
}
int main() {
  memset(p, 0, sizeof(p));
  cin >> v >> e >> k;
  q = v;
  for(int i = 0; i < v; ++i) {
    cin >> n[i];
    l[i].first = i;
    l[i].second = 0;
  }
  for(int i = 0; i < e; ++i) {
    cin >> x >> y;
    --x;
    --y;
    b[x].push_back(y);
    b[y].push_back(x);
    l[x].second += n[y];
    l[y].second += n[x];
  }
  sort(l, l + v, cmp);
  ans = l[0].second;
  int i = 0;
  while(q) {
    if(!p[l[i].first]) {
      --q;
      p[l[i].first] = 1;
    }
    for(int j:b[l[i].first]) {
      if(!p[j]){
        --q;
        p[j] = 1;
      }
    }
    ans = l[i].second;
    ++i;
  }
  while(--k) {
    while(l[i].second >= ans)
	  ++i;
    ans = l[i].second;
  }
  cout << m << '\n';
  return 0;
}

# [z084](https://judge.cp.ccns.io/problem/z084)：
核心想法是如果 A 在一個比賽中他是最強的選手， A 一定可以拿冠軍。
如果 B 在任何比賽可以贏 A ，那 B 一定可以拿冠軍。

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define _s second
#define _f first
using namespace std;

int n, q;
vector< pii > a[3];
vector< int > fa[3];
vector< bool > ans;
vector< int > qu;

int main() {
  cin >> n >> q;
  ans.resize(n);
  for(int i = 0; i < 3; i++) {
    a[i].resize(n);
    fa[i].resize(n);
  }

  for(int i = 0; i < 3; i++) for(int j = 0; j < n; j++) {
    int tmp; cin >> tmp;
    a[i][j] = mp(tmp, j);
  }
  for(int i = 0; i < 3; i++) sort(a[i].begin(), a[i].end());
  for(int i = 0; i < 3; i++) {
    if(ans[a[i][n-1]._s] == 0) qu.pb(a[i][n-1]._s);
    ans[a[i][n-1]._s] = 1;
  }

  for(int i = 0; i < 3; i++) for(int j = 0; j < n; j++) fa[i][a[i][j]._s] = j;

  int lst[3] = {n, n, n};
  for(int idx = 0; idx < qu.size(); idx++) {
    for(int i = 0; i < 3; i++) {
      int start = fa[i][qu[idx]];
      if(start >= lst[i]) continue;
      for(int j = start+1; j < lst[i]; j++) if(ans[a[i][j]._s] == 0) {
        ans[a[i][j]._s] = 1;
        qu.pb(a[i][j]._s);
      }
      lst[i] = start+1;
    }
  }
  for(int i = 0; i < q; i++) {
    int tmp; cin >> tmp;
    cout << (ans[tmp-1]?"Y":"N") << endl;
  }
  return 0;
}

# [z085](https://judge.cp.ccns.io/problem/z085)：
$a<b$ 若 $a$ 與 $b$ **相連** 代表：
1. $a$ 整除 $b$
2. $a$ **不整除** $b$ 的其他**因數**

若只考慮第一點，則 $a$ 只要**乘上任意數** $p$ 就能構造出這樣的 $b$
而第二點則限制了 $p$ 必須是個**質數**
> 請自行證明吧 很簡單的 XD

也就是說，給定 $r = p_1^{t_1}\cdot p_2^{t_2}\cdot ... \cdot p_k^{t_k}$ ( $p_i$ 為 $r$ 的質因數 )
從 $a = 1$ 開始，每次乘上 $r$ 的**一個質因數**，就能畫出哈斯哈斯圖的一條邊
> 再欣賞一次花快兩小時用小畫家畫的圖

例如對於 $0 \le x < t_1$
$\mathbf{p_1^x} \cdot p_2^{m_2}\cdot p_3^{m_3} \cdot ..\cdot p_k^{m_k}$ 與 $\mathbf{p_1^{x+1}} \cdot p_2^{m_2}\cdot p_3^{m_3} \cdot ..\cdot p_k^{m_k}$ 之間有一條邊
而這裡各 $m_i$，範圍在 $0$ 到 $t_i$ 之間

所以 $r$ 的哈斯哈斯圖邊數為
$$
\begin{split}
&\underline{t_1}\cdot (t_2 + 1) \cdot (t_3 + 1) \cdot ... \cdot (t_k+1) + \\
&(t_1 + 1) \cdot \underline{t_2} \cdot (t_3 + 1) \cdot ... \cdot (t_k+1) + \\
&(t_1 + 1) \cdot (t_2 + 1) \cdot \underline{t_3} \cdot ... \cdot (t_k+1) + \\
&\quad\quad\quad\quad\quad\quad \vdots \\
&(t_1 + 1)\cdot (t_2 + 1) \cdot (t_3 + 1) \cdot ... \cdot \underline{t_k}
\end{split}
$$

#include<bits/stdc++.h>
using namespace std;
typedef long long Int;

Int r;

int main()
{
  int n;
  scanf("%d", &n);

  while(n--) {
    scanf("%lld", &r);

    vector<Int> exp;
    for(Int i = 2; i*i <= r; i++) {
      int t = 0;
      while(r % i == 0) r /= i, t++;
      if(t) exp.push_back(t);
    }
    if(r > 1) exp.push_back(1);

    Int edge = 0, fac = 1;
    for(int i = 0; i < exp.size(); i++) fac *= exp[i] + 1;
    for(int i = 0; i < exp.size(); i++) edge += exp[i] * fac/(exp[i]+1);

    printf("%lld\n", edge);
  }

  return 0;
}