Day 4 上機題解
===

###### tags: `IONCAMP2019`

[Johnny Johnny](https://pc2.tfcis.org/dev/index.php/problem/view/60/)
---
first blood: **ToMmyDong**

題意為抓2個以上的數字，然後取gcd，在所有組合中取最大，
但是gcd一定是抓越多數字越小，
所以我們就窮舉所有兩兩的組合，然後取最大的gcd，
所有兩兩組合的最大值即為所求。

[老闆的時間](https://pc2.tfcis.org/dev/index.php/problem/view/78/)
---
first blood: **Elliot**

stringstream or 手動

while (getline(cin, buf)) {
  regex r("(\\d+)\\s+(\\d+)\\s+UTC(\\S+)"); // \\d 代表 0-9 的一個數字
  vector<pair<int, int>> res;
  for (auto it = sregex_iterator(buf.begin(), buf.end(), r);
        it != sregex_iterator(); ++it) {
    int h = stoi(it->str(1));
    int m = stoi(it->str(2));
    int x = round((8 - stof(it->str(3))) * 60);
    int t = (h * 60 + m + x + 1440) % 1440;
    res.emplace_back(t / 60, t % 60);
  }
  for (int i = 0; i < res.size(); ++i) {
    printf(
      "%02d:%02d%c",
      res[i].first, 
      res[i].second,
      " \n"[i + 1 == res.size()]
    );
  }
  if (res.empty()) puts("");
}

[我想要下班](https://pc2.tfcis.org/dev/index.php/problem/view/85/)
---
first blood: **wanling1212**

KMP/Z/Hashing

[惠惠的おっぱい魔法](https://pc2.tfcis.org/dev/index.php/problem/view/63/)
---
first blood: **emanlaicepsa**

(出題者說他明天再講)

[省油錢](https://pc2.tfcis.org/dev/index.php/problem/view/94/)
---
first blood: **Elliot**

KMP 最小循環節

len = |S| - |S 的最長共同前後綴|

檢查是否 len 整除 |S|

[EXPLOSION](https://pc2.tfcis.org/dev/index.php/problem/view/52/)
---
first blood: X

可以很輕易地確認，從$(x_1,y_1)$到$(x_2,y_2)$的整數點會有$\gcd(x_2-x_1,y_2-y_1)+1$。

先把所有的點(包含相交的部份)算進來，再枚舉兩線段相交，相交則須扣除重複的點，可以在對點$i$枚舉時把相交的點丟進`set`裡，最後枚舉完點$i$時扣除`set`的`size`。

時間：$O(n^2\log n)$

[Simple DP Problem](https://pc2.tfcis.org/dev/index.php/problem/view/79/)
---
First blood: **zaneyu**

使用講義程式碼的作法

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n; cin >> n;
  ExpandableHull<long long> H;
  long long dp = 0;
  for (int i = 0; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    H.addLine(Linear<long long>(b, dp));
    dp = H(a);
  }
  cout << dp << '\n';
}

[Weight on Suffix](https://pc2.tfcis.org/dev/index.php/problem/view/77/)
---
first blood: X

用 SA 找出相對應的後綴們，會得到在 SA 上的一個區間，對該區間做 RMQ

[Intersection of Lines on Integer Points](https://pc2.tfcis.org/dev/index.php/problem/view/92/)
---
first blood: **ToMmyDong**

把提供的 Line 模板找尋相交改為測試 (x, y) 座標的整數是否除盡即可

[十字騎士與危險的陷阱](https://pc2.tfcis.org/dev/index.php/problem/view/54/)
---
first blood: **wanling1212**

對字串$S$做KMP failure(next數組) build，然後定義DP:
$$
DP[i] = S[0\dots i]\text{出現在}S\text{自身的次數}
$$
已知所有$DP[i]$至少出現一次($S[0\dots i]$自身)，預先設$DP[i]=1$。
當$next[i]\neq-1$時，$DP[next[i]]+=DP[i]$。因為所有出現在$S$中的$S[0\dots i]$字串一共有$DP[i]$個，其中這$DP[i]$個字串的後綴皆包含$S[0\dots next[i]]$。
在此DP轉移的基礎下，由$i=\text{strlen}(S)-1$開始處理至0後，把DP加總即可。

時間：$O(n)$

[靜態凸包搜尋](https://pc2.tfcis.org/dev/index.php/problem/view/80/)
---
First blood: **ToMmyDong**

使用講義程式碼的作法

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  int n, m; cin >> n >> m;
  vector<Linear<long long>> UL, LL;
  for (int i = 0; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    UL.push_back(Linear<long long>(a, b));
    LL.push_back(Linear<long long>(-a, -b));
  }
  ConvexHull<long long> U(UL), L(LL);
  while (m--) {
    int x; cin >> x;
    cout << U(x) + L(x) << '\n';
  }
}