牛客多校2020第二场补题

F Fake Maxpooling

题意

规定矩阵对应的值为其下标的 $lcm$ ，求所有 $k * k$ 子矩阵最大值之和。 $( n,m,k = 5000 )$

Solution

线性求 $lcm$ + 二维单调队列

线性求 $lcm$ ：

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      if (!g[i][j]) {
        for (int h = 1; h * i <= n && h * j <= m; h++) {
          g[h * i][h * j] = h;
          a[h * i][h * j] = i * j * h;
        }
      }
    }

先对每一行进行单调队列（滑动窗口）维护出最大值矩阵 $g$ ，再对列进行单调队列维护矩阵 $g$ 的最大值即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, m, k, a[N][N], g[N][N];
long long res;
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
      if (!g[i][j]) {
        for (int h = 1; h * i <= n && h * j <= m; h++) {
          g[h * i][h * j] = h;
          a[h * i][h * j] = i * j * h;
        }
      }
    }
  for (int i = 1; i <= n; i++) {
    deque<int> q;
    for (int j = 1; j <= m; j++) {
      while (!q.empty() && a[i][q.back()] < a[i][j]) q.pop_back();
      while (!q.empty() && j - q.front() >= k) q.pop_front();
      q.push_back(j);
      if (j >= k) g[i][j] = a[i][q.front()];
    }
  }
  for (int i = k; i <= m; i++) {
    deque<int> q;
    for (int j = 1; j <= n; j++) {
      while (!q.empty() && g[q.back()][i] < g[j][i]) q.pop_back();
      while (!q.empty() && j - q.front() >= k) q.pop_front();
      q.push_back(j);
      if (j >= k) {
        a[j][i] = g[q.front()][i];
        res += a[j][i];
      }
    }
  }
  printf("%lld\n", res);
  return 0;
}

C Cover the Tree

题意

给定无根树，用最少的链覆盖树的所有点。 $( n = 2e5 )$

Solution

思维 + dfs序

首先不难想到所取的链两个端点都在叶子上才会是最优的，因此答案应为 $(叶子结点数 + 1)/2$ 。

经过一番玄学证明，得到结论为按 dfs序 构造链会是最优的，任取非叶子结点为根，由 dfs序 得到叶子结点 $l1, l_2 ….l_x$ ，然后将 $l_1$ 与 $l{x/2+1}$ 构成链以此类推，若多出一个点，则与根结点连起来即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int n, u, v, root, de[N];
vector<int> g[N], res;

void dfs(int u, int fa) {
  if (de[u] == 1) res.push_back(u);
  for (auto v : g[u]) {
    if (v == fa) continue;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
    de[u]++;
    de[v]++;
  }
  for (int i = 1; i <= n; i++) {
    if (de[i] > 1) root = i;
  }
  dfs(root, -1);
  n = res.size();
  if (n & 1) res.push_back(root), n++;
  n >>= 1;
  printf("%d\n", n);
  for (int i = 0; i < n; i++) printf("%d %d\n", res[i], res[i + n]);
  return 0;
}

B Boundary

题意

已知一个圆必过点 $(0,0)$ ，需要构造该圆使得尽可能多的给定点在该圆的边界上，问最多能有几个点。 $( n = 2000, |x,y| = 100000 )$

Solution

三个点可以确定一个圆，因此不妨枚举两个点，求出圆心，圆心重合次数最多的即为答案。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;

int n, res;
double X, Y, R;

struct Point {
  double x, y;
} p[N];

map<pair<double, double>, int> mp;

bool solve(Point a, Point b, Point c)  //三点共圆圆心公式
{
  if (2 * (a.y - c.y) * (a.x - b.x) - 2 * (a.y - b.y) * (a.x - c.x) == 0 &&
      2 * (a.y - b.y) * (a.x - c.x) - 2 * (a.y - c.y) * (a.x - b.x) == 0)
    return false;

  X = ((a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y) * (a.y - c.y) -
       (a.x * a.x - c.x * c.x + a.y * a.y - c.y * c.y) * (a.y - b.y)) /
      (2 * (a.y - c.y) * (a.x - b.x) - 2 * (a.y - b.y) * (a.x - c.x));
  Y = ((a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y) * (a.x - c.x) -
       (a.x * a.x - c.x * c.x + a.y * a.y - c.y * c.y) * (a.x - b.x)) /
      (2 * (a.y - b.y) * (a.x - c.x) - 2 * (a.y - c.y) * (a.x - b.x));
  R = sqrt((X - a.x) * (X - a.x) + (Y - a.y) * (Y - a.y));

  return true;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
  Point o = {0, 0};
  for (int i = 1; i < n; i++) {
    mp.clear();
    for (int j = i + 1; j <= n; j++) {
      if (solve(o, p[i], p[j])) {
        auto now = make_pair(X, Y);
        res = max(res, ++mp[now]);
      }
    }
  }
  printf("%d\n", ++res);
  return 0;
}

J Just Shuffle

题意

一个排列经过质数次置换后得到排列 A ，求原排列。 ( n = 1e5 )

Solution

直接拍个置换开根板子就过了。。。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, m, i, j, k, o, x, l, d, a[N], g[N], nxt[N], t, q[N], b[N], ans[N];
bool v[N];
int cal(int x) {
  int i, k = m, t = 1;
  for (i = 2; i * i <= x; i++)
    if (x % i == 0) {
      while (x % i == 0) x /= i, t *= i;
      while (k % i == 0) k /= i, t *= i;
    }
  if (x > 1)
    for (t *= x; k % x == 0; k /= x, t *= x)
      ;
  return t;
}
int main() {
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (i = 1; i <= n; i++)
    if (!v[i]) {
      t = v[i] = 1;
      for (j = a[i]; j != i; j = a[j]) v[j] = 1, t++;
      nxt[i] = g[t], g[t] = i;
    }
  for (i = 1; i <= n; i++)
    if (g[i]) {
      for (t = 0, j = g[i]; j; j = nxt[j]) q[++t] = j;
      d = __gcd(l = cal(i), m);
      if (t % d) return puts("1"), 0;
      for (x = 1; x <= t; x += d) {
        for (j = 0; j < d; j++)
          for (k = 0, o = q[x + j]; k < i; k++, o = a[o])
            b[(j + 1LL * k * m) % l] = o;
        for (j = 0; j < l; j++) ans[b[j]] = b[(j + 1) % l];
      }
    }
  for (i = 1; i <= n; i++) printf("%d ", ans[i]);
}