2024/09/29 模拟赛总结

标签：lfloor F2 texttt frac 09 29 rfloor 2024 aligned

\(0+0+0+0=0\)，感觉不如 #include <bits./stdc++.h>

#A. 你相信（）吗

\(70\) 分的 \(O(n^3)\) 算法很好解决，枚举出三盏灯的亮度后，剩下一个灯的亮度一定固定。对于每个格子剩余亮度需求取 max 即可。

然后我们充分发扬人类智慧，当 \(n \le 400\) 时跑暴力，否则考虑推式子，下面的 \(=\) 表示大概相等

令 \(i,j,k,e\) 分别为左上，右上，左下，右下灯的亮度

\[\left\{\begin{aligned}a & = i+\lfloor\frac{j}{2}\rfloor+\lfloor\frac{k}{2}\rfloor+\lfloor\frac{e}{4}\rfloor \\b & = j+\lfloor\frac{i}{2}\rfloor+\lfloor\frac{k}{4}\rfloor+\lfloor\frac{e}{2}\rfloor \\c & = k+\lfloor\frac{i}{2}\rfloor+\lfloor\frac{j}{4}\rfloor+\lfloor\frac{e}{2}\rfloor \\d & = e+\lfloor\frac{i}{4}\rfloor+\lfloor\frac{j}{2}\rfloor+\lfloor\frac{k}{2}\rfloor\end{aligned}\right. \]

我们枚举 \(i,j\)，令 \(k^`=\lfloor\frac{k}{2}\rfloor,e^`=\lfloor\frac{e}{2}\rfloor\)，对于后两个式子进行移项，得到：

\[\left\{\begin{aligned}c-\lfloor\frac{i}{2}\rfloor+\lfloor\frac{j}{4}\rfloor & = k+\lfloor\frac{e}{2}\rfloor = 2k^`+e^` & \texttt{F1} \\d-\lfloor\frac{i}{4}\rfloor-\lfloor\frac{j}{2}\rfloor & = e+\lfloor\frac{k}{2}\rfloor=2e^`+k^` & \texttt{F2}\end{aligned}\right. \]

将 \(e^`,k^`\) 当成未知数解方程，得到 \(k^`=\texttt{F1}-\frac{\texttt{F1}+\texttt{F2}}{3}, e^`=\texttt{F2}-\frac{\texttt{F1}+\texttt{F2}}{3}\)

然后因为这是大概范围，需要左右偏移找答案，偏移值 \(35\) 左右就可以了

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

LL a, b, c, d, e, c3, c4, ed, k, v, v_, ed_, ans = 1e18;

int main() {
  freopen("light.in", "r", stdin), freopen("light.out", "w", stdout);
  cin >> a >> b >> c >> d;
  if (a <= 400 && b <= 400 && c <= 400 && d <= 400) {
    for (int i = 0; i <= a; i++) {
      for (int j = 0; j <= b; j++) {
        for (int k = 0; k <= c; k++) {
          e = max({0ll, d - i / 4 - j / 2 - k / 2, (a - i - j / 2 - k / 2) << 2, (b - j - i / 2 - k / 4) << 1, (c - j / 4 - i / 2 - k) << 1}), ans = min(ans, i + j + k + e);
        }
      }
    }
    cout << ans << '\n';
    return 0;
  }
  for (int i = 0; i <= a; i++) {
    for (int j = 0; j <= b; j++) {
      c3 = c - i / 2 - j / 4, c4 = d - j / 2 - i / 4, v = c3 - (c3 + c4) / 3, v_ = c4 = (c3 + c4) / 3, v <<= 1, v_ << 1, ed = min(c, v + 35), ed_ = min(d, v_ + 35);
      for (int k = max(0ll, v - 35); k <= ed; k++) {
        e = max({0ll, d - i / 4 - j / 2 - k / 2, (a - i - j / 2 - k / 2) << 2, (b - j - i / 2 - k / 4) << 1, (c - j / 4 - i / 2 - k) << 1}), ans = min(ans, i + j + k + e);
      }
      for (int e = max(0ll, v_ - 35); e <= ed_; e++) {
        k = max({0ll, (d - i / 4 - j / 2 - e) << 1, (a - i - j / 2 - e / 4) << 1, (b - j - i / 2 - e / 2) << 2, c - j / 4 - i / 2 - e / 2}), ans = min(ans, i + j + k + e);
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

#B. 爪巴

\(O(2^n)\) 拿了 \(80\) 哈哈

标签：lfloor,F2,texttt,frac,09,29,rfloor,2024,aligned
From： https://www.cnblogs.com/bluemoon-blog/p/18443203