# 113學年度資訊讀書會模擬競賽[-1] 題解

預估難度 : pH < pB < pD < pE < pA < pC < pF < pG

## pA. owoovo太巨砲了
problem setter : pooh
題解 : pooh
first AC : fatman at 3\:44:42
題目的意思大概是給你兩個01字串 $A, B$，每次可以做操作
1. `01`變`10`
2. `10`變`01`

問你在$k$次操作時能不能兩個字串長一樣。

然後我們先講一件重要的事，
:::success
Lemma A.1
對於一個01字串 $S$ ，進行了上面的操作 $k$ 次時，$$k + \sum_{i = 1}^{\lvert S \rvert} i \times S_i \mod 2$$ 是不變量。
proof :
對於操作1. $$k + \sum_{i = 1}^{\lvert S \rvert} i \times S_i \equiv (k + 1) + ((\sum_{i = 1}^{\lvert S \rvert} i \times S_i) - 1) \mod 2$$
對於操作2. $$k + \sum_{i = 1}^{\lvert S \rvert} i \times S_i \equiv (k + 1) + ((\sum_{i = 1}^{\lvert S \rvert} i \times S_i) + 1) \mod 2$$
:::

### Subtask 1
兩個字串一開始是一樣的。
所以操作偶數次一定可以變成一樣的(兩個位置輪流換)，奇數次則一定不行(因為Lemma A.1)。

### Subtask 2
這是拿來嗆沒開 long long 的人的

### Subtask 3
應該沒辦法只過這個吧

### Subtask 4
首先一件顯然的事情是一定要 $A$ 中 1 的數目與 $B$ 中 1 的數目一樣才可以達成，令 $A$ 中 1 的位置為數列 $a$, $B$ 中 1 的位置為數列 $b$。
我們知道
:::success
Lemma A.2
假設將 $A$ 操作到與 $B$ 相同的最短步數為 $m$，則
答案為可行 $\iff k = m + 2n \ (n \in \mathbb{N} + \{0\})$
proof :
($\Rightarrow$) :
因為 Lenma A.1，所以所有可行步數奇偶都應相同。
($\Leftarrow$) :
花 $m$ 步到達相同後即變回 Subtask 1
:::
因此只需要求出 $m$ 即可。
:::success
Lemma A.3
$$m = \sum_{i = 1}^{\lvert a \rvert} \ \lvert a_i - b_i \rvert$$
proof:
首先因為沒有交換兩個 1 的相對位置的操作，所以一定是在 $a_i$ 的那個 1 跑到 $b_i$，因此有 $$m \ge \sum_{i = 1}^{\lvert a \rvert} \ \lvert a_i - b_i \rvert$$
接著用數歸證下界可以到達，當$\lvert a \rvert = 1$時顯然，若在 $\lvert a \rvert = k$ 時成立，對於$\lvert a \rvert = k + 1$，
case 1 : $a_{k + 1} > b_{k + 1}$
先用$\sum_{i = 1}^{k} \ \lvert a_i - b_i \rvert$ 次操作將前 k 個都移到指定位置，又 $b_{k + 1} > b_k$，所以在移到 $b_k$ 時不會需要交錯，只需花 $\lvert a_{k + 1} - b_{k + 1} \rvert$ 次操作，原假設成立。
case 2 : $a_{k + 1} < b_{k + 1}$
直接花 $\lvert a_{k + 1} - b_{k + 1} \rvert$ 次操作向後移，原假設成立。

因為 base case 跟 induction step 都成立，所以透過 MI 得證。
:::

所以你現在會做了。
:::spoiler AC code

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

int main(){
    long long A, B, k, x = 0;
    cin >> A >> B >> k;
    vector <int> a, b;
    for (int i = 0; i <= 63; i++){
        if(A & (1LL << i))
            a.push_back(i);
        if(B & (1LL << i))
            b.push_back(i);
    }
    if(a.size() != b.size()){
        cout << "No\n";
        uwu
    }
    for (int i = 0; i < a.size(); i++){
        x += abs(a[i] - b[i]);
    }
    (k >= x && ((k - x) % 2 == 0)) ? cout << "Yes\n" : cout << "No\n";
}

:::

複雜度$O(\log(\max(A,B)))$

## pB. pooh 愛拋物線
problem setter : pooh
題解 : pooh
first AC : pyting at 0:10:27
爛梗題 = =

### Subtask 1
先讓你手構看看的，構一下就會發現...

### Subtask 2
一種好的構造法是第 $i$ 條拋物線是 $a_i = b_i = c_i = i$，為啥呢?
因為第 $i$ 條與第 $j$ 一定沒有交點。
proof:
令$t = i - j$
求交點相當於求$0 = tx^2+tx+t$ 的根，判別式$t^2 - 4t^2 = -3t^2 < 0$，無實數解。

:::spoiler AC code

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

int main(){
    int N, P;
    cin >> N >> P;
    for (int i = 1; i <= N; i++){
        cout << i << ' ' << i << ' ' << i << '\n';
    }
    uwu
}

:::

複雜度$O(N)$

## pC. 山脈沒有山谷
problem setter : pooh
題解 : pooh
first AC :

### Subtask 1
暴力詢問找
詢問次數 $N$

### Subtask 2
發現若只有遞增或遞減，可以二分搜找大所求的答案，因此只需要先三分搜或差分二分搜找到山峰，就可以將它拆成兩段分別是遞增與遞減的了!

詢問次數 $4 \log N$ (差分二分搜) 或 $5.17 \log N$ (三分搜)

:::spoiler AC code

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

int get(int x){
    int a;
    cout << "? " << x << endl;
    cin >> a;
    return 1;
}

int find_peak(int R){
    int L = 1, m1, m2;
    while(L != R){
        m1 = L + (R - L) / 3;
        m2 = R - (R - L) / 3;
        if(get(m1) < get(m2))
            L = m1 + 1;
        else
            R = m2 - 1;
    }
    return L;
}

int main(){
    int N, x;
    cin >> N >> x;
    int peak = find_peak(N);
    int L, R, M, ans = 0;
    L = 1, R = peak;
    while(L != R){
        M = (L + R + 1) / 2;
        if(get(M) <= x)
            L = M;
        else
            R = M - 1;
    }
    ans = get(L);
    L = peak, R = N;
    while(L != R){
        M = (L + R) / 2;
        if(get(M) <= x)
            R = M;
        else
            L = M + 1;
    }
    ans = max(ans, get(L));
    cout << "! " << ans << endl;
}

:::

## pD. Product Modulo mod P
problem setter : 餘切
題解 : 餘切
first AC : tim415 at 0:32:19

### Subtask 1
因為$P=1$，所以輸出$0$就好。
### Subtask 2
因為$N \le 5000$，所以可以枚舉$i, j$直接算。
### Subtask 3
題目有說有$\frac{N(N-1)}{2}$組，所以答案是$(A_1^2 \times \frac{N(N-1)}{2}) \text{ mod } P$。
### Subtask 4
把式子好好寫出來：
$$
\begin{aligned}
\sum_{j=1}^N{\sum_{i=1}^{j-1}{A_i \times A_j}}
=\sum_{j=1}^N{A_j \times (\sum_{i=1}^{j-1}{A_i})}
\end{aligned}
$$
發現可以用前綴和優化，時間複雜度$O(N)$。

## pE. 我速度是誰的兩倍==
idea : 餘切
problem setter : porzorzh
題解 : 餘切
first AC : tingpeng1055 at 0:56:35
### Subtask 1
因為$2 \le N \le 5000$，所以可以$O(N)$幫每個人算，總共$O(N^2)$。
### Subtask 2
可以改對每個$V_i$算答案，所以對每個不是奇數的$V_i$來說，你只在意速度是$\frac{V_i}{2}$的那些人。可以開一個陣列存所有速度是$V$的人的編號的$\text{xor}$和，注意如果速度是$0$的話會多$\text{xor}$到自己。時間複雜度$O(N)$。
### Subtask 3
把Subtask 2的作法的陣列換成map就過了。時間複雜度$O(N \log N)$。

:::spoiler AC code

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int SIZE = 2e5 + 5;

int N;

map <int, int> mp;

int arr[SIZE];

int main(){
    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> arr[i];
        mp[arr[i]] ^= i;
    }
    for (int i = 1; i <= N; i++){
        if((arr[i] % 2) != 0)
            cout << 0 << ' ';
        else if(arr[i] == 0)
            cout << (mp[0] ^ i) << ' ';
        else
            cout << mp[arr[i] / 2] << ' ';
    }
    cout << '\n';
}

:::

## pF. pooh 的好區間
problem setter : pooh
題解 : pooh
first AC : weakweakkekw at 1:04:35

痾防不住 pyting 的防破台題

### Subtask 1
暴力，複雜度 $O(NQ)$ 或 $O(NQ\log N)$ 都會過。

### Subtask 2 & 3
這題原本是只有 $b = 0$ 的，但我不太想看到有人用線段樹過了，所以加了 $b = 1$，但是發現多維護一點東西就好了，所以就便現在這樣，線段樹可做但超麻煩。
> 可是線段樹還沒教欸 (痾就是針對pyt(可是我也被針對了))

### Subtask 4
首先發現每次修改你會對區間造成的影響只有將一個區間變兩個或兩個區間變一個(左右分開看的話)，因次你就用一個STL去維護區間就好了，可能是 map 或 set，然後再拿個 multiset 去維護區間長度的種類，你就 AC 了。
$O((N + Q) \log N)$
:::spoiler AC code

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int SIZE = 2e5 + 5, INF = 1e9 + 7;

set <int> cuts;

multiset <int> lengths;

int N, Q;

int arr[SIZE];

void cuts_remove(int pos){
    auto it = cuts.find(pos);
    lengths.erase(lengths.lower_bound(pos - (*prev(it))));
    lengths.erase(lengths.lower_bound((*next(it)) - pos));
    lengths.insert((*next(it)) - (*prev(it)));
    cuts.erase(pos);
    return;
}

void cuts_insert(int pos){
    cuts.insert(pos);
    auto it = cuts.find(pos);
    lengths.erase(lengths.lower_bound(((*next(it)) - (*prev(it)))));
    lengths.insert(pos - (*prev(it)));
    lengths.insert((*next(it)) - pos);
    return;
}

int main(){
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> N >> Q;
    arr[0] = INF;
    for (int i = 1; i <= N; i++){
        cin >> arr[i];
        if(arr[i - 1] > arr[i])
            cuts.insert(i);
    }
    cuts.insert(N + 1);
    for (auto it = cuts.begin(); it != prev(cuts.end()); it++){
        lengths.insert((*next(it)) - (*it));
    }
    lengths.insert(0);
    while (Q--){
        int op, p, x, a;
        cin >> op;
        if(op == 1){
            cin >> p >> x;
            if(cuts.count(p) && arr[p - 1] <= x){
                cuts_remove(p);
            }
            if(cuts.count(p + 1) && x <= arr[p + 1]){
                cuts_remove(p + 1);
            }
            if((!cuts.count(p)) && arr[p - 1] > x){
                cuts_insert(p);
            }
            if((!cuts.count(p + 1)) && x > arr[p + 1]){
                cuts_insert(p + 1);
            }
            arr[p] = x;
        }
        if(op == 2){
            cin >> a;
            if(a == 0){
                cout << *prev(lengths.end()) << '\n';
            }
            if(a == 1){
                cout << *prev(lengths.lower_bound(*prev(lengths.end()))) << '\n';
            }
            if(a == 2){
                cout << *prev(prev(lengths.end())) << '\n';
            }
        }
    }
}

:::

## pG. 速度是別人的兩倍!!!
problem setter : pooh
題解 : pooh
first AC :
因為 zzw 的速度是別人的兩倍，因此以這句話命名的題目也是兩題。

### Subtask 1
應該可以發現你關心的只有最左跟最右兩個人，所以答案就是$$\frac {p_N - p_1} {2(1 + \frac K N)}$$

### Subtask 2
首先可以貪心的發現你會想要加速的人一定是最左邊跟最右邊的，因此你枚舉最左邊的 $i$ 個人加速(同時最右邊的$K - i$個也加速)，然後發現答案就是$$\max(\frac {\lvert x - p_1 \rvert} 2, {\lvert x - p_{i + 1} \rvert}, {\lvert x - p_{N - K + i} \rvert}, \frac {\lvert x - p_N \rvert} 2)$$
但要怎麼挑這個 $x$ 呢? 有兩個方法
方法1 : 搜位置
首先我們知道
:::success
Lemma G.1
單低谷函數的 max 還是單低谷函數。
proof:
反證法，假設兩個單低谷函數$f(x), g(x)$，且$h(x) = \max(f(x), g(x))$ 不是單低谷函數，則我們取兩個低谷$p, q \ (\text{WLOG} \ p < q, h(p) = f(p), h(q) = g(q))$，則在 $p, q$ 之間必有一 $f,g$ 的交點 $r$，但$f(r) > f(p)$, $g(r) < g(p)$ (因為她在低谷前)，又$f(r) = g(r)$，所以$g(p) > f(p)$，矛盾。
:::
然後我們知道時間對位置的圖是一條直線，也是一種單低谷函數，因此他們的 max 還是單低谷函數，可以三分搜或差分二分搜。

方法2 : 搜時間
我們知道每個人經過一段時間後可以到達的區間，如果有交集那就是時間夠，所以可以對時間二分搜。
:::spoiler AC code

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int RUN_TIME = 100;

vector <int> pos;

/*
long double calc_time(long double db_L, long double nm_L, long double nm_R, long double db_R){
    long double L = db_L, R = db_R, M1, M2, T1, T2;
    int t = RUN_TIME;
    while (t--){
        M1 = L + (R - L) / 3;
        M2 = R - (R - L) / 3;
        T1 = max({abs(M1 - db_L) / 2, abs(M1 - nm_L), abs(M1 - nm_R), abs(M1 - db_R) / 2});
        T2 = max({abs(M2 - db_L) / 2, abs(M2 - nm_L), abs(M2 - nm_R), abs(M2 - db_R) / 2});
        if(T1 > T2)
            L = M1;
        else
            R = M2;
    }
    T1 = max({abs(M1 - db_L) / 2, abs(M1 - nm_L), abs(M1 - nm_R), abs(M1 - db_R) / 2});
    return T1;
}
*/

long double calc_time(long double db_L, long double nm_L, long double nm_R, long double db_R){
    long double L = 0, R = db_R - db_L, M;
    for (int t = RUN_TIME; t--;){
        M = (L + R) / 2;
        if(min(db_L + 2 * M, nm_L + M) >= max(db_R - 2 * M, nm_R - M))
            R = M;
        else
            L = M;
    }
    return L;
}

int main(){
    int N, K;
    cin >> N >> K;
    for (int i = 0, a; i < N; i++){
        cin >> a;
        pos.push_back(a);
    }
    sort(pos.begin(), pos.end());
    if(N == K){
        cout << setprecision(10) << (long double)(pos[N - 1] - pos[0]) / 4 << '\n';
        uwu
    }
    long double ans = 1e9 + 7;
    for (int i = 0; i <= K; i++){
        ans = min(ans, calc_time(pos[0], pos[i], pos[N - K + i - 1], pos[N - 1]));
    }
    cout << setprecision(10) << ans << '\n';
}

:::

$O(N \log (\varepsilon^{-1} C))$
然後我 claim 你其實只需要檢查這些線的交點，所以應該可以$O(N)$

## pH. 初華愛三角
problem setter : 楊輝 a.k.a 怪人
題解 : 餘切
first AC : 鮑 at 0:28:36

巴斯卡三角形第$N$排有$N$個數，依序為$\binom{N-1}{0}, \binom{N-1}{1}, \dots, \binom{N-1}{N-1}$，但是沒辦法用$\binom{n}{k}=\frac{n!}{k!(n-k)!}$來計算，因為$39!$很巨。
有兩種作法可以解決這題。
### 1
利用$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$打表。
要開`long long`。
預處理複雜度$O(N^2)$。
### 2
因為最後的答案不會太大，所以可以模一個夠大的質數$P$，然後用$\binom{n}{k}=\frac{n!}{k!(n-k)!}$在模$P$底下算。
預處理複雜度$O(N+\log P)$。

:::spoiler AC code

#include <bits/stdc++.h>
#define uwu return 0;

using namespace std;

const int SIZE = 50;

int n;

long long triangle[SIZE][SIZE];

int main(){
    cin >> n;
    triangle[1][1] = 1;
    for (int i = 2; i <= n; i++){
        for (int j = 1; j <= i; j++){
            triangle[i][j] = triangle[i - 1][j] + triangle[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= i; j++){
            cout << triangle[i][j] << ' ';
        }
        cout << '\n';
    }
    uwu
}

:::

# 鞭屍
weakweakweak at 1:10:51

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

int n, a[5114514];

int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    map<int,int> mp;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mp[a[i]] ^= i;
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) cout << (mp[0] ^ i) << '\n';
        else if (a[i] % 2 == 0) cout << mp[a[i] / 2] << ' ';
        else cout << 0 << ' ';
    }
    cout << '\n';
}

## 沒開 long long

pyting at 3:55:45

#pragma GCC optimize ("O3", "unroll-loops")
#pragma GCC target ("avx2", "bmi", "bmi2", "lzcnt", "popcnt")

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve ()
{
  int a, b, k;
  cin >> a >> b >> k;

  if (__builtin_popcount (a) != __builtin_popcount (b))
    return cout << "No\n", void ();

  while (a)
    {
      k -= abs (__builtin_ctz (a) - __builtin_ctz (b));
      a -= a & -a;
      b -= b & -b;
    }

  cout << (k < 0 || k & 1 ? "No" : "Yes") << '\n';
}

signed main ()
{
  ios_base::sync_with_stdio (false);
  cin.tie (nullptr);

  int t = 1;
  // cin >> t;

  while (t--) solve ();

  return 0;
}

Horse1006 at 2:02:58

#include<iostream> 
#include <bits/stdc++.h>
using namespace std;
#define ll long long;

int main()
{  
    int X;  
    cin >> X;  
    int table[X][X]={0};
    for(int i=0;i<X;i++)
        for(int j=0;j<X;j++)  
            table[i][j]++;  
    for(int i=2;i<X;i++)  
    {  
        for(int j=1;j<i;j++)  
            table[i][j] = table[i-1][j]+table[i-1][j-1];
    }  
    for(int i=0;i<X;i++)  
    {  
        for(int j=0;j<i+1;j++)  
        {  
            cout << table[i][j] << " ";  
        }  
        cout << endl;  
    }  
  
}

tim415 1:00:59

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>> vec(45);
    for(int i=0;i<45;i++){vec[i].resize(45,0);}
    vec[0][0]=1;
    cout<<1<<"\n";
    for(int i=1;i<n;i++){
        vec[i][0]=1;
        cout<<1<<' ';
        for(int j=1;j<i+1;j++){
            vec[i][j]=vec[i-1][j-1]+vec[i-1][j];
            cout<<vec[i][j]<<' ';
        }
        cout<<"\n";
    }
}

tingpeng1055 at 0:31:08

#pragma GCC optimize ("O3", "unroll-loops")
#pragma GCC target ("avx2", "bmi", "bmi2", "lzcnt", "popcnt")

#include <bits/stdc++.h>

using namespace std;

void solve ()
{
  int n;
  cin >> n;

  vector v (n + 1, vector<int> (n + 1));

  for (int i = 1; i <= n; i++)
    {
      for (int j = 1; j <= i; j++)
        {
          if (j == 1 || j == n) cout << (v[i][j] = 1) << ' ';
          else cout << (v[i][j] = v[i - 1][j - 1] + v[i - 1][j]) << ' ';
        }
      cout << '\n';
    }
}

signed main ()
{
  ios_base::sync_with_stdio (false);
  cin.tie (nullptr);

  int t = 1;
  // cin >> t;

  while (t--) solve ();

  return 0;
}

## 亂戳

tingpeng1055 at 2:30:25

#pragma GCC optimize ("O3", "unroll-loops")
#pragma GCC target ("avx2", "bmi", "bmi2", "lzcnt", "popcnt")

#include <bits/stdc++.h>

using namespace std;

const int Max = 2e9;

void solve ()
{
  int n, q;
  cin >> n >> q;

  vector<int> a (n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  a[0] = Max;

  set<int> id;
  id.emplace (0);

  multiset<int> len;
  len.emplace (0);

  int last = 0;

  for (int i = 1; i <= n + 1; i++)
    {
      if (a[i] >= a[i - 1]) continue;

      id.emplace (i);

      if (last) len.emplace (i - last);
      last = i;
    }

  auto f = [&] (int i)
  {
    auto it = id.upper_bound (i);
    if (*prev (it) == i) return;

    len.erase (len.find (*it - *prev (it)));

    len.emplace (i - *prev (it));
    len.emplace (*it - i);

    id.emplace (i);
  };

  auto g = [&] (int i, int j)
  {
    auto it_1 = id.upper_bound (i),
        it_2 = id.upper_bound (j);

    len.erase (len.find (*it_1 - *prev (it_1)));
    len.erase (len.find (*it_2 - *prev (it_2)));

    len.emplace (*it_2 - *prev (it_1));

    id.erase (prev (it_2));
  };

  while (q--)
    {
      int t;
      cin >> t;

      if (t == 1)
        {
          int p, x;
          cin >> p >> x;

          f (p);
          if (p != n) f (p + 1);

          a[p] = x;

          if (p != n && a[p] <= a[p + 1]) g (p, p + 1);
          if (a[p - 1] <= a[p]) g (*--id.lower_bound (p), p);
        }
      else
        {
          int b;
          cin >> b;

          cout << (b == 0 ? *--len.end () :
              b == 1 ? *--len.lower_bound (*--len.end ()) :
                  *-- --len.end ()) << '\n';
        }
    }
}

signed main ()
{
  ios_base::sync_with_stdio (false);
  cin.tie (nullptr);

  int t = 1;
  // cin >> t;

  while (t--) solve ();

  return 0;
}