第三場比賽題解

聽說吃拉麵能變強

z021：

令

x

為

m

個人過來前，長椅上目前佔最多人的人數

最大的

k

為

x + m

而對於最小的

k

：
若先去坐

x

人的那個長椅，

k

會變大，所以

m

個人應先分配到其他長椅上
於是求除了

x

人的長椅外，還剩下多少位置(rem)

for (int i = 0; i < n; i++) rem += x-a[i];

若

m \leq rem

則顯然

k = x

若

m > rem

就將部份人分配到剩下的位置中(此時長椅人數都為

x

)，
接著將剩餘的人

m - rem

平均分配到每張長椅上，

k = x + ⌈ \frac{m - rem}{n} ⌉

以下完整程式碼：

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

int const maxn = 110;

int n, m, a[maxn];

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++) scanf("%d", &a[i]);

  int x = *max_element(a, a+n), rem = 0; // remainder
  for(int i = 0; i < n; i++) rem += x-a[i];

  if(m > rem) printf("%d ", x + (m-rem)/n + !!((m-rem)%n));
  else printf("%d ", x);

  printf("%d\n", x+m);

  return 0;
}

z022：

二元二次方程式。
通常遇到方程式可以試試看「二分搜有理數」，而這題恰巧可以用上公式解。
遇到小數的時候，注意題目敘述，如果可以的話盡量多輸出幾位。

#include <bits/stdc++.h>
#define Double long double

using namespace std;

int main() {
  int T;
  cin >> T;
  while(T--) {
    Double D, a, b;
    cin >> D;
    if(D == 1 || D == 2 || D == 3) { cout << "Null" << endl; continue; }
    if(D >= 4) a = (D+sqrt(D*D-4*D)) / 2;
    else if(D == 0) a = 0;
    b = D - a;
    printf("%.9llf %.9llf\n", a, b);
  }
}

z023：

明顯的，如果採用枚舉的方式一定會吃個 TLE (寫之前最好估計一下複雜度！)
改用二分搜加速，每次抽籤就找他的 lower bound:

int* l = lower_bound(LAN, LAN+N, lot);

以下完整程式碼：

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

int const maxn = 1e6 + 10;

int N, LAN[maxn], T;

int main() {
  scanf("%d", &N);
  for(int i = 0; i < N; i++) scanf("%d", &LAN[i]);
  sort(LAN, LAN+N);

  scanf("%d", &T);
  while(T--) {
    int lot;
    scanf("%d", &lot);

    int* l = lower_bound(LAN, LAN+N, lot);

    if(*l == lot) printf("%d\n", lot);
    else if(l == LAN+N) printf("%d no\n", *(l-1));
    else if(l == LAN) printf("no %d\n", *l);
    else printf("%d %d\n", *(l-1), *l);
  }

  return 0;
}

z024：

其實就是要找

x

滿足

f (x) = \frac{\sin (e^{- x}) \cdot \sinh (x)}{k} = 0.499

的地方
在題目中有提示

k

越大，可以載重就越大，換句話說，

f

肯定是個遞增函數
因此用二分搜，low = 0, up = 50，開始搜，精度的問題請看 Code

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, i;
  int t;
  double low, up, mid, k;
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> k;
    low = 0, up = 50;
    while (up - low > 1e-12) {
      mid = (up + low) / 2;
      if (sin(exp(-mid)) * sinh(mid) / k > 0.499)
        up = mid;
      else
        low = mid;
    }
    cout << fixed << setprecision(9) << mid - 0.00000000049999999 << endl;
  }

  return 0;
}

z025：

由於詢問的次數很高，所以期待每次的詢問複雜度不能太高，需要設計方便處理詢問的流程。
名詞說明：

group: 每一個點所屬的組別編號，並且最終在當編號等於自身號碼時代表找到根。
Find: group，並且做扁平加速。

可以參照第四週教材 Union-Find Forest

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

const int maxn = 1e5+5;

int n, m, q;
int group[maxn];

int Find(int x) {
  if(group[x] == x) return x;
  return group[x] = Find(group[x]);
}

int main() {
  cin >> n >> m >> q;
  for(int i = 1; i <= n; i++) group[i] = i;

  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    group[Find(a)] = Find(b);
  }
  for(int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    cout << (Find(x) == Find(y)) << endl;
  }
  return 0;
}

第三場比賽 題解