# 2022 NCPC 校內預賽賽後題解

題目: https://drive.google.com/file/d/1UqtLTLxI16I2fuTF4bv4pdcLh0ixmlnd/view?usp=sharing

## pA
Author: LFsWang (廣告: 可以開始報名 TOPC 了)

要做一點字串處理的 Hello world, がお?
記得測第三筆範例測資。

## pB

按照題目定義，分數的算法是這樣：

對於每個$+$指令：
* 對於它之前的每次往右，加1分
* 對於它之前的每次往左，減1分

對於每個$-$指令：
* 對於它之前的每次往左，加1分
* 對於它之前的每次往右，減1分

調整計算順序，改寫一下：

對於每次往右：
* 對於它之後的每個$+$指令，加1分
* 對於它之後的每個$-$指令，減1分

對於每次往左：
* 對於它之後的每個$-$指令，加1分
* 對於它之後的每個$+$指令，減1分

因為每個$M$之後的$+$和$-$數量是已知的，所以每次往左或往右對分數的改變也是已知的。具體來說，如果一個$M$之後有$X$個$+$和$Y$個$-$，那麼往右會增加$X-Y$分，往左會減少$X-Y$分。因為需要往左往右的移動各半，所以就是$X-Y$值比較大的一半往右（用加的），比較小的一半往左（用減的）。排序一下就知道誰加誰減。

時間複雜度：$O(|S|\log|S|)$

題目來源：AtCoder Beginner Contest 027D

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

int main() {
    string s;
    cin >> s;
    int x = 0;
    long long z = 0;
    vector<int> a;
    reverse(s.begin(), s.end());
    for (char c : s) {
        if (c == '+') x++;
        if (c == '-') x--;
        if (c == 'M') a.push_back(x);
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < a.size() / 2; i++) z -= a[i];
    for (int i = (int)a.size() / 2; i < a.size(); i++) z += a[i];
    cout << z << '\n';
}

## pC

找到幾個直角，就找到幾個直角三角形；找到幾個鈍角，就找到幾個鈍角三角形。所以算直角數量和鈍角數量就好。

枚舉角的中間點$B$，將剩下的點以$B$為基準做極角排序逆時針排一圈。最好用整數做，不然應該會有誤差。極角排序可以參考[https://codeforces.com/blog/entry/72815](https://codeforces.com/blog/entry/72815)

維護兩個指針$U$和$V$：對於某個當下的點$A$，$U$是往逆時針方向看第一個使角$ABU>=90º$的點；$V$是往逆時針方向看第一個使角$ABV>=180º$的點。不存在的話定義為繞一整圈之後的$A$。需要使用內積和外積，用整數判斷，用角度表示應該不夠準。內積和外積可以參考[https://codeforces.com/blog/entry/48122](https://codeforces.com/blog/entry/48122)

可以發現$C$在$[U, V)$範圍內會使角$ABC$是直角或鈍角，且$C$在$A$的逆時針方向（如果要求$C$在$A$的逆時針方向的話，每個角就只會算到一次）。只有角$ABU$可能是直角，剩下都一定是鈍角。

時間複雜度：$O(N^2\log N)$

題目來源：AtCoder Beginner Contest 033D

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

struct point {
    ll x, y;
};

bool cmp(point p, point q) {
    bool a = p.x < 0 || (p.x == 0 && p.y < 0), b = q.x < 0 || (q.x == 0 && q.y < 0);
    if (a != b) return a < b;
    return p.x * q.y > p.y * q.x;
}

ll dot(point p, point q) {
    return p.x * q.x + p.y * q.y;
}

ll cross(point p, point q) {
    return p.x * q.y - p.y * q.x;
}

int main() {
    int n;
    ll x[2022] = {}, y[2022] = {}, z = 0, w = 0;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    for (int i = 0; i < n; i++) {
        vector<point> a;
        for (int j = 0; j < n; j++) if (i != j) a.push_back({x[j] - x[i], y[j] - y[i]});
        sort(a.begin(), a.end(), cmp);
        for (int i = 0; i < n - 1; i++) a.push_back(a[i]);
        ll u = 0, v = 0;
        for (int j = 0; j < n - 1; j++) {
            while (u < j + n - 1 && dot(a[j], a[u]) > 0 && cross(a[j], a[u]) >= 0) u++;
            while (v < j + n - 1 && cross(a[j], a[v]) >= 0) v++;
            w += v - u;
            if (dot(a[j], a[u]) == 0 && cross(a[j], a[u]) >= 0) z++, w--;
        }
    }
    cout << 1ll * n * (n - 1) * (n - 2) / 6 - z - w << ' ' << z << ' ' << w << '\n';
}

## pD
Author: LFsWang

中國剩餘定理。經典數學模板題。

對於下同於方式組

$$x\equiv r_1 \pmod {k_1}\\x\equiv r_2 \pmod {k_2}\\x\equiv r_3 \pmod {k_3}$$

可以構造出答案。設 $m=\prod {k}$。
對於第 $i$ 個方程式有：
* $m_i = m / k_i$
* 計算 $m_i$ 在模 $k_i$ 的反元素 $m_i^{-1}$
* 計算 $c_i=m_im_i^{-1}$

則構造出的解答為 $\sum r_ic_i$ 。

因為對於每一個方程式，只有自己的 $r_ic_i$ 不是 $k_i$ 的倍數，並且有
$$r_ic_i \equiv r_im_im_i^{-1}\equiv r_i \pmod {k_i}$$

注意取模逆元時，明顯的 $k_i$ 不保證是質數，因此不能用比較偷懶的 $m^{-1}\equiv m^{p-2}$ ，要使用廣義輾轉相除法解出來。

## pE

Author: Redleaf
Special thanks: meowmeowRanger and sheepRanger 幫我修了我的破爛英文

閱讀測驗題

有一個 $N \times M$ 方格，每個格子有高度。某些格子是 spawn points。
Ragoo bunnies 會在那個格子產生並且移動。
過程中，Ragoo bunnies 只會走相鄰而且高度相同或較低的格子。
一直往下走，直到停在某個低點(無法在走到更低格子的點)，或者跑到方格界外。
給定這些低點，問哪些位子可能是 spawn points。

Idea:
1. 先將相鄰而且高度相同的格子縮點成一個平台，建成 DAG (低的平台 $\rightarrow$ 高的平台)
2. 低點：DAG 上 indeg = 0 的點
3. 如果一個低點沒有 Ragoo Bunnies，則 DAG 上他所有的 ancestors 都不可能是 spawn points
4. 針對「Ragoo Bunnies 可能跑到界外」，可能需要做一些特判

Example 2 如下。方格會建立成右下角的 DAG，其中紅底表示不可能是 spawn points 的平台，綠底表示可能是 spawn points 的平台

Implementation:
1. DFS or BFS 將方格縮點，建 DAG
2. DAG 上 topological sort 判斷 spawn points

Note: DAG & topological sort 可以不用做，題目可以只靠 DFS / BFS 解出

Time complexity: $O(N \times M)$

## pF
請先閱讀：
[cp-algorithm: Maximum flow - Ford-Fulkerson and Edmonds-Karp](https://cp-algorithms.com/graph/edmonds_karp.html)
[cp-algorithm: Maximum flow - Dinic's algorithm](https://cp-algorithms.com/graph/dinic.html)

建一個二分圖，其中一邊的節點為每個可能的 laser beam 權重就是 laser beam的cost，另一邊的節點代表為每個可能的 shock wave權重就是 shock wave的cost。對於每個敵人，將能打到他的laser beam的節點和能打到他的shock wave的節點連邊。此圖的 minimum weighted vertex cover 即為答案。

vertex cover 是一個點集合且每一條邊至少有一端點在vertex cover內，因此一個vertex cover中，每個敵人(邊)至少會被一個武器(點)給擊毀。從 vertex cover上構造答案的方式就是先發射所有要發射的 laser beam，再由近到遠一一使用 shock wave。

二分圖的minimum weighted vertex cover可以透過最大流求出，建模方式如下：source 連向所有左邊的點，capacity是點權，所有右邊的點連向sink，capacity是點權，對於二分圖中原本有的邊，從左邊連向右邊，capaciry為INF。可以透過此圖的 min cut構造出 vertex cover，而min cut可以透過此圖的 max flow 求出。

補充：對於一個二分圖，若點沒有權重，根據 [Kőnig's theorem](https://en.wikipedia.org/wiki/Kőnig%27s_theorem_(graph_theory))，minimum vertex cover 等同於該圖的 maximum matching，因此求出二分圖的 maximum matching 即可，二分圖的maximum matching 可以使用flow或者是參考[演算法筆記-Matching](https://web.ntnu.edu.tw/~algo/Matching.html)。

## pG

$52$ 張牌取 $5$ 張，問和 $> 21$ 的機率，輸出最簡分數。
可以注意到 case 數非常少，完全可以暴力枚舉。

如何計算最簡分數? 你可能會用到 [std::gcd](https://en.cppreference.com/w/cpp/numeric/gcd)。

Notes: 正常電腦一秒鐘大約可以跑 $10^9$ 個指令，另外不曉得大家測機的時候有沒有注意到，其實我們的 Judge 超級快。
$52^5 \approx 3 \cdot 10^8$; ${52 \choose 5} \approx 2.6 \cdot 10^6$

Implementation hints: 標程和首殺都是寫五層迴圈。

Complexity: 看你怎麼枚舉，但是最暴力的 $O(N^5)$ 會過，$N$ 為卡片數量 (即 52)。

## pH

Idea: GYLin (已畢業選手)
Author: Redleaf

兩個人每秒走一格，過程中只會往右和往下走，問 $k$ 秒之後他們在幾個格子相遇。

觀察：畫出兩個人的路徑，可以觀察到兩路徑相交的點就是他們相遇的點。

最 naive 的作法就是直接一秒一秒模擬兩人走路的過程，但是 $k \leq 10^{18}$，這麼做會 TLE，所以我們需要一些優化。

想法一：不要每次只有一步。模擬時，一直走直到有人轉彎，此時檢查一下重疊狀況。

想法二：由於只會往右和往下移動，因此可以完全忽略自己左方和上方的路徑。因此模擬時，我們可以每次讓比較左邊的人移動。這樣一來，我們只需要紀錄每個人最後移動的橫線和直線。

Time complexity: $O(N+M)$

另外的解法：使用掃描線，配上一些資料結構，可以作到 $O((N+M) \log (N+M))$

## pI
請先閱讀：[cp-algorithm: Treap](https://cp-algorithms.com/data_structures/treap.html)

### 作法一
使用 Treap 維護每個 DVD 所在的位置，$n$ 個節點，第$i$個節點代表第$i$個學生。對於每一筆操作，將DVD插入給定的學生上，問題變成要找該位置往後第一個沒有DVD的學生是誰並將它移除。在 Treap 節點上維護一個該點為根的樹是否有人沒有$DVD$，就可以Split出插入位置右邊的Treap然後在該Treap中二分搜第一個沒有DVD的學生是誰。

### 作法二
如果同學對在 Treap 上做修改沒有信心，可以考慮使用 Treap 維護各個DVD的相對位置，然後使用其他資料結構例如set或線段樹維護哪些學生有DVD。

使用set紀錄還有哪些位置沒有DVD，每次插入就是查插入位置的lower_bound也就是第一個大於等於插入位置且沒有DVD的同學，你就可以知道我插入了這個DVD會讓誰獲得DVD。接著就erase他。

使用值是 0 或 1 的線段樹維護哪個位置有DVD。因此對於每次派發一個DVD，先查線段樹上該位置的前綴和是多少，就可以知道該DVD該在哪個位置然後插入Treap中，接著查線段樹上該位置的後綴最小值，就可以知道該位置往後第一個沒DVD的人是誰，就可以單點修改成1。

Time Complexity: $O(M\log{N})$
## pJ

https://docs.google.com/presentation/d/1jcMCRZJbWKsajkg1DxMK_Z5feL6D9Hao/edit?usp=sharing&ouid=111823925085182444561&rtpof=true&sd=true

### 括號匹配法

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

struct State {
  const static unsigned Offset = 2;
  const static unsigned Mask = (1u << Offset) - 1;
  static unsigned M;

private:
  unsigned Data;
  static unsigned bit(unsigned A, unsigned B) { return A << (B * Offset); }

public:
  State(unsigned Data) : Data(Data) {}
  unsigned raw() const { return Data; }
  void clear(unsigned Idx) { Data ^= (Data & bit(Mask, Idx)); }
  unsigned get(unsigned Idx) const { return (Data >> (Idx * Offset)) & Mask; }
  void set(unsigned Idx, unsigned Val) { // Val is {0, 1, 2}
    clear(Idx);
    Data |= bit(Val, Idx);
  }
  void shift() { Data <<= Offset; }
  void print() const { // debug
    static char ch[] = {'#', '(', ')'};
    for (unsigned i = 0; i <= M; ++i)
      cout << ch[get(i)];
    cout << endl;
  }
};

unsigned N, State::M;
unsigned LastRow, LastCol;
vector<vector<bool>> Grid;
void input() {
  cin >> N >> State::M;
  Grid.clear();
  Grid.resize(N + 2, vector<bool>(State::M + 2, false));
  string Buffer;
  LastRow = LastCol = 0;
  for (unsigned Raw = 1; Raw <= N; ++Raw) {
    cin >> Buffer;
    for (int Col = 1; Col <= State::M; ++Col) {
      if (Grid[Raw][Col] = (Buffer[Col - 1] == '.')) {
        LastRow = Raw;
        LastCol = Col;
      }
    }
  }
}

unsigned find(State S, unsigned Col, bool IsForword) {
  int Sum = 0, Ans = 0;
  auto check = [&](auto Idx) {
    int K = S.get(Idx);
    if (K == 1)
      --Sum;
    if (K == 2)
      ++Sum;
    if (!Sum) {
      Ans = Idx;
      return true;
    }
    return false;
  };
  if (IsForword) {
    for (int Idx = Col; Idx <= State::M; ++Idx)
      if (check(Idx))
        break;
  } else {
    for (int Idx = Col; Idx >= 0; --Idx)
      if (check(Idx))
        break;
  }
  return Ans;
}

long long solve() {
  if (LastRow == 0)
    return 0;
  long long Ans = 0;
  unordered_map<unsigned, long long> DP[2];
  int Cur = 0;
  DP[Cur][0] = 1;
  for (int Row = 1; Row <= N; ++Row) {
    for (int Col = 1; Col <= State::M; ++Col) {
      DP[1 - Cur].clear();
      for (auto Pair : DP[Cur]) {
        State S(Pair.first);
        unsigned Left = S.get(Col - 1), Up = S.get(Col);
        auto createState = [&](unsigned Down, unsigned Right) {
          State T(Pair.first);
          T.set(Col - 1, Down);
          T.set(Col, Right);
          return T;
        };
        auto transfer = [&](State T) {
          if (Col == State::M)
            T.shift();
          DP[1 - Cur][T.raw()] += Pair.second;
        };
        if (Grid[Row][Col] == false) { // Obstacle
          if (Left == 0 && Up == 0)
            transfer(S);
        } else if (Left == 0 && Up == 0) { // 0,0
          if (Grid[Row][Col + 1] && Grid[Row + 1][Col])
            transfer(createState(1, 2));
        } else if (Left == 0 || Up == 0) { // 0,x || x,0
          if (Grid[Row + (Left > 0)][Col + (Up > 0)])
            transfer(S);
          if (Grid[Row + (Up > 0)][Col + (Left > 0)])
            transfer(createState(Up, Left));
        } else if (Left == Up) { // 1,1 || 2,2
          unsigned Pos =
              Left == 1 ? find(S, Col, true) : find(S, Col - 1, false);
          State T = createState(0, 0);
          T.set(Pos, Left);
          transfer(T);
        } else if (Left == 2 && Up == 1) { // 2,1
          transfer(createState(0, 0));
        } else if (Left == 1 && Up == 2) { // 1,2
          if (Row == LastRow && Col == LastCol)
            Ans += Pair.second;
        }
      }
      Cur = 1 - Cur;
    }
  }
  return Ans;
}

int main() {
  input();
  cout << solve() << endl;
  return 0;
}

### 最小表示法

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

class EnDec : public vector<unsigned> {
  const static unsigned Offset = 3;
  const static unsigned Mask = (1u << Offset) - 1;

public:
  static unsigned M;
  EnDec(uint64_t Data) : vector<unsigned>(M + 1) {
    for (int Idx = M; Idx >= 0; --Idx) {
      this->at(Idx) = Data & Mask;
      Data >>= Offset;
    }
  }
  uint64_t encode() const {
    static vector<int> Table(1, 0);
    Table.resize(1);
    Table.resize(M + 2, -1);
    uint64_t Ans = 0;
    int Cnt = 1;
    for (unsigned Idx = 0; Idx <= M; ++Idx) {
      unsigned K = this->at(Idx);
      if (Table[K] == -1)
        Table[K] = Cnt++;
      Ans <<= Offset;
      Ans |= Table[K];
    }
    return Ans;
  }
  void shift() {
    for (int Idx = M; Idx > 0; --Idx)
      this->at(Idx) = this->at(Idx - 1);
    this->at(0) = 0;
  }
};

unsigned N, EnDec::M;
unsigned LastRow, LastCol;
vector<vector<bool>> Grid;
void input() {
  cin >> N >> EnDec::M;
  Grid.clear();
  Grid.resize(N + 2, vector<bool>(EnDec::M + 2, false));
  string Buffer;
  LastRow = LastCol = 0;
  for (unsigned Raw = 1; Raw <= N; ++Raw) {
    cin >> Buffer;
    for (int Col = 1; Col <= EnDec::M; ++Col) {
      if (Grid[Raw][Col] = (Buffer[Col - 1] == '.')) {
        LastRow = Raw;
        LastCol = Col;
      }
    }
  }
}

long long solve() {
  if (LastRow == 0)
    return 0;
  long long Ans = 0;
  unordered_map<uint64_t, long long> DP[2];
  int Cur = 0;
  DP[Cur][0] = 1;
  for (int Row = 1; Row <= N; ++Row) {
    for (int Col = 1; Col <= EnDec::M; ++Col) {
      DP[1 - Cur].clear();
      for (auto Pair : DP[Cur]) {
        EnDec Code(Pair.first);
        auto transfer = [&]() {
          if (Col == EnDec::M)
            Code.shift();
          DP[1 - Cur][Code.encode()] += Pair.second;
        };
        unsigned Left = Code[Col - 1], Up = Code[Col];
        if (Grid[Row][Col] == false) {
          if (Left == 0 && Up == 0) {
            Code[Col - 1] = Code[Col] = 0;
            transfer();
          }
        } else if (Left > 0 && Up > 0) {
          if (Left == Up) {
            if (Row == LastRow && Col == LastCol) {
              Code[Col - 1] = Code[Col] = 0;
              transfer();
            }
          } else {
            Code[Col - 1] = Code[Col] = 0;
            for (unsigned Idx = 0; Idx <= EnDec::M; ++Idx)
              if (Code[Idx] == Up)
                Code[Idx] = Left;
            transfer();
          }
        } else if (Left > 0 || Up > 0) {
          if (Grid[Row][Col + 1]) {
            Code[Col - 1] = 0;
            Code[Col] = Left | Up;
            transfer();
          }
          if (Grid[Row + 1][Col]) {
            Code[Col - 1] = Left | Up;
            Code[Col] = 0;
            transfer();
          }
        } else {
          if (Grid[Row][Col + 1] && Grid[Row + 1][Col]) {
            unsigned Max = 1;
            for (unsigned Idx = 0; Idx <= EnDec::M; ++Idx)
              Max = max(Max, Code[Idx]);
            Code[Col - 1] = Code[Col] = Max + 1;
            transfer();
          }
        }
      }
      Cur = 1 - Cur;
    }
  }
  for (auto Pair : DP[Cur])
    Ans += Pair.second;
  return Ans;
}

int main() {
  input();
  cout << solve() << endl;
  return 0;
}

## pK

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

// Sierpiński carpet

int pow3(int x)
{
    int ans = 1;
    while (x--)
        ans *= 3;
    return ans;
}

vector<string> out;

void dfs(int m, int x, int y)
{
    if (m == 0)
        return;
    int next = m / 3;
    for (int i = 0; i < next; ++i)
    {
        for (int j = 0; j < next; ++j)
        {
            out[x + next + i][y + next + j] = ' ';
        }
    }
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            if (i == 1 && j == 1)
                continue;
            dfs(next, x + next * i, y + next * j);
        }
    }
}

int main()
{
    int n;
    while (cin >> n)
    {
        int m = pow3(n);
        out = vector<string>(m, string(m, '#'));

        dfs(m, 0, 0);

        for (auto &s : out)
            cout << s << endl;
    }
    return 0;
}

## Final Scoreboard