【合集】紫题 20 道

发布于

开始学文化课了,这个计划会鸽一鸽


放寒假了,这个计划会加快进度


这个计划废弃了,因为有了新计划

刷题!

1. 规划

展开

题意

给定一棵大小为 $n$ 的树。

给定两个长度为 $n$ 的数组 $a$ 与 $b$。在 $1$ 到 $n$ 中选出 $m$ 个点,使得选出的点联通,求选出的点的 $a_i$ 之和 除以 选出的点的 $b_i$ 之和 的最大值。

$1 \leq m < n < 100, 1 \leq a_i, b_i \leq 10000$

题解

01 分数规划。

我们要求出 $\dfrac{\sum a_i}{\sum b_i} = c$ 的最大值,移项后可得 $\sum a_i + c \times \sum b_i$,又得到 $\sum\left(a_i - c \times b_i\right) = 0$,显然 $c$ 有单调性,于是可以二分找 $c$。

现在我们要求出一个大小为 $n - m$ 的连通块,最大化 $a_i - c \times b_i$。树形 DP。

设 $f_{i, j}$ 表示在以 $i$ 为根的子树中,选了 $j$ 个的最大值,其中 $i$ 必选。

代码

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n, m; bin >> n >> m;
  vector<tp> a(n + 1), b(n + 1), s(n + 1, 1);
  vector<vector<tp>> e(n + 1);
  bin.rar(a.begin() + 1, a.end());
  bin.rar(b.begin() + 1, b.end());
  for (tp i = 1; i < n; ++i) {
    tp u, v; bin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  m = n - m;
  auto csize = [&](auto& $, tp x, tp f) -> void {
    for (auto& i : e[x]) {
      if (i == f) continue;
      $($, i, x);
      s[x] += s[i];
    }
  };
  auto dp = [&](auto& $, tp x, tp fa, auto& r, auto& f) -> void {
    f[x][0] = 0;
    for (auto& i : e[x]) {
      if (i == fa) continue;
      $($, i, x, r, f);
      for (tp j = min(s[x], m); j >= 0; --j) {
        for (tp k = 0; k <= min(j, s[i]); ++k)
          f[x][j] = max(f[x][j], f[i][k] + f[x][j - k]);
      }
    }
    for (tp i = min(s[x], m); i >= 1; --i) f[x][i] = f[x][i - 1] + r[x];
  };
  auto check = [&](double c) -> bool {
    vector f(n + 1, vector<double>(m + 1, -INF));
    vector<double> r(n + 1);
    for (tp i = 1; i <= n; ++i) r[i] = a[i] - c * b[i];
    dp(dp, 1, 1, r, f);
    for (tp i = 1; i <= n; ++i) {
      if (f[i][m] >= 0) return true;
    }
    return false;
  };
  auto TAR = [&]() -> double {
    double l = 0, r = 10000;
    while (r - l > 0.0001) {
      double mid = (l + r) / 2;
      if (check(mid)) l = mid;
      else r = mid;
    }
    return l;
  };
  csize(csize, 1, 1);
  bin.precision(1);
  bin << TAR() + 0.05 << '\n';
}

2. 河童重工的计算机

展开
有点无语。

题意

实现一个类汇编语言的解释器。

题解

感觉写得时候还是挺顺利的。大约 3 个小时就写完了。

代码

展开

template <typename Ty>
struct KTX_65 {
  Ty R1, R2, R3, R4;
  Ty E1, E2, E3, E4;
  Ty Flag, Val, Ret, Line;
  vector<Ty> sAddr;
  map<string, string> func_start;
  vector<string> program;

  void _TO_UPPER(string& s) {
    for (auto& i : s) {
      if (i >= 'a' && i <= 'z') i = i - 'a' + 'A';
    }
  }

  string _TEMP_TO_UPPER(string s) {
    for (auto& i : s) {
      if (i >= 'a' && i <= 'z') i = i - 'a' + 'A';
    }
    return s;
  }

  Ty& Get_Value(string name) {
    _TO_UPPER(name);
    if (name.front() == '%') {
      name = name.substr(1);
      if (name == "R1") return R1;
      if (name == "R2") return R2;
      if (name == "R3") return R3;
      if (name == "R4") return R4;
      if (name == "E1") return E1;
      if (name == "E2") return E2;
      if (name == "E3") return E3;
      if (name == "E4") return E4;
      if (name == "FLAG") return Flag;
      if (name == "VAL") return Val;
      if (name == "RET") return Ret;
      if (name == "LINE") return Line;
    } else {
      static Ty tmp;
      tmp = atoll(name.c_str());
      return tmp;
    }
    assert(0);
  }

  void FUNCTION(vector<string> c) {
    tp cnt = 1;
    for (tp x = Line; _TEMP_TO_UPPER(program[x]) != "RET"; ++x) ++cnt;
    func_start[c[0]] = to_string(Line);
    // program[Line] = "JMP " + to_string(cnt);
    program[Line] = "JMP 1";
  }

  void CALLFUNC(vector<string> c) { CALL({func_start[c[0]]}); }

  void UDEF(vector<string> c) { return; }

  void HLT(vector<string> c) { exit(0); }

  void NOP(vector<string> c) { return; }

  void SET(vector<string> c) { Get_Value(c[1]) = Get_Value(c[0].c_str()); }
  
  void JMP(vector<string> c) { Line += Get_Value(c[0]) - 1; }

  void JIT(vector<string> c) {
    if (c.size() > 1 && Get_Value(c[1])) Line += Get_Value(c[0]) - 1;
    if (c.size() == 1 && Flag) Line += Get_Value(c[0]) - 1;
  }

  void CALL(vector<string> c) {
    sAddr.push_back(Line);
    Line = Get_Value(c[0]);
  }

  void RET(vector<string> c) {
    if (c.size()) Ret = Get_Value(c[0]);
    Line = sAddr.back();
    sAddr.pop_back();
  }

  void INV(vector<string> c) {
    Ty ans = -Get_Value(c[0]);
    if (c.size() > 1) Get_Value(c[1]) = ans;
    else Val = ans;
  }

  void ADD(vector<string> c) {
    Ty ans = Get_Value(c[0]) + Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void SUB(vector<string> c) {
    Ty ans = Get_Value(c[0]) - Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void MULT(vector<string> c) {
    Ty ans = Get_Value(c[0]) * Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void IDIV(vector<string> c) {
    Ty ans = Get_Value(c[0]) / Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void MOD(vector<string> c) {
    Ty ans = Get_Value(c[0]) % Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void LSFT(vector<string> c) {
    Ty ans = Get_Value(c[0]) << Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void RSFT(vector<string> c) {
    Ty ans = Get_Value(c[0]) >> Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void BAND(vector<string> c) {
    Ty ans = Get_Value(c[0]) & Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void BOR(vector<string> c) {
    Ty ans = Get_Value(c[0]) | Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void BXOR(vector<string> c) {
    Ty ans = Get_Value(c[0]) ^ Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void LGR(vector<string> c) {
    Ty ans = Get_Value(c[0]) > Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LLS(vector<string> c) {
    Ty ans = Get_Value(c[0]) < Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LGE(vector<string> c) {
    Ty ans = Get_Value(c[0]) >= Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LLE(vector<string> c) {
    Ty ans = Get_Value(c[0]) <= Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LEQL(vector<string> c) {
    Ty ans = Get_Value(c[0]) == Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LAND(vector<string> c) {
    Ty ans = Get_Value(c[0]) && Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LOR(vector<string> c) {
    Ty ans = Get_Value(c[0]) || Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void RINT(vector<string> c) {
    if (c.empty()) bin >> Val;
    else bin >> Get_Value(c.front());
  }

  void RCH(vector<string> c) {
    char t; bin >> t;
    if (c.empty()) Val = t;
    else Get_Value(c.front()) = t;
  }

  void WINT(vector<string> c) {
    Ty t;
    if (c.empty()) t = Val;
    else t = Get_Value(c.front());
    bin << (long long)t;
    bin.flush();
  }

  void WCH(vector<string> c) {
    char t;
    if (c.empty()) t = Val;
    else t = Get_Value(c.front());
    bin << t;
    bin.flush();
  }

  void _CALL_FUNCTION(string s, vector<string> c) {
    _TO_UPPER(s);

    if (s == "CALLFUNC") return CALLFUNC(c);

    if (s == "UDEF") return UDEF(c);
    if (s == "HLT") return HLT(c);
    if (s == "NOP") return NOP(c);
    if (s == "SET") return SET(c);
    if (s == "JMP") return JMP(c);
    if (s == "JIT") return JIT(c);
    if (s == "CALL") return CALL(c);
    if (s == "RET") return RET(c);

    if (s == "INV") return INV(c);
    if (s == "ADD") return ADD(c);
    if (s == "SUB") return SUB(c);
    if (s == "MULT") return MULT(c);
    if (s == "IDIV") return IDIV(c);
    if (s == "MOD") return MOD(c);
    if (s == "LSFT") return LSFT(c);
    if (s == "RSFT") return RSFT(c);
    if (s == "BAND") return BAND(c);
    if (s == "BOR") return BOR(c);
    if (s == "BXOR") return BXOR(c);
  
    if (s == "LGR") return LGR(c);
    if (s == "LLS") return LLS(c);
    if (s == "LGE") return LGE(c);
    if (s == "LLE") return LLE(c);
    if (s == "LEQL") return LEQL(c);
    if (s == "LAND") return LAND(c);
    if (s == "LOR") return LOR(c);

    if (s == "RINT") return RINT(c);
    if (s == "RCH") return RCH(c);
    if (s == "WINT") return WINT(c);
    if (s == "WCH") return WCH(c);

    assert(0);
  }

  KTX_65(string P) {
    R1 = R2 = R3 = R4 = 0;
    E1 = E2 = E3 = E4 = 0;
    Flag = Val = Ret = Line = 0;
    program.resize(2);
    for (auto& i : P) {
      if (i == '\n') program.push_back("");
      else if (i != ';') program.back().push_back(i);
    }
    if (program.back() == "") program.pop_back();
    program.push_back("HLT");
    for (Line = 1; Line < program.size(); ++Line) {
      vector<string> section {""};
      for (auto& j : program[Line]) {
        if (j == ' ') section.push_back("");
        else section.back().push_back(j);
      }
      if (section.back() == "") section.pop_back();
      string Operation = _TEMP_TO_UPPER(section.front());
      section.erase(section.begin());
      if (Operation == "FUNCTION") FUNCTION(section);
    }
    for (Line = 1; Line < program.size(); ++Line) {
      vector<string> section {""};
      for (auto& j : program[Line]) {
        if (j == ' ') section.push_back("");
        else section.back().push_back(j);
      }
      if (section.back() == "") section.pop_back();
      string Operation = section.front();
      section.erase(section.begin());
      _CALL_FUNCTION(Operation, section);
    }
  }
};

感觉这东西挺好玩的,但是原版 KTX-65 由于寄存器数量太少,并且函数在不调用的情况下也会执行,导致使用范围极度受限。

于是我就自己加强了一下,搞了个 KTX_65_PLUS。
加强的部分:

  • 有了一个大数组。
  • 寄存器数量变成 24 个。
  • 函数调用带参数。
  • 函数只有调用后才会执行。

展开

template <typename Ty>
struct KTX_65_PLUS {
  Ty R1, R2, R3, R4, R5, R6, R7, R8;
  Ty E1, E2, E3, E4, E5, E6, E7, E8;
  Ty T1, T2, T3, T4, T5, T6, T7, T8;
  Ty P1, P2, P3, P4;
  Ty Flag, Val, Ret, Line;
  vector<Ty> mem;
  vector<Ty> sAddr;
  map<string, string> func_start;
  vector<string> program;

  void _TO_UPPER(string& s) {
    for (auto& i : s) {
      if (i >= 'a' && i <= 'z') i = i - 'a' + 'A';
    }
  }

  string _TEMP_TO_UPPER(string s) {
    for (auto& i : s) {
      if (i >= 'a' && i <= 'z') i = i - 'a' + 'A';
    }
    return s;
  }

  Ty& Get_Value(string name) {
    _TO_UPPER(name);
    if (name.front() == '%') {
      name = name.substr(1);
      if (name == "FLAG") return Flag;
      if (name == "VAL") return Val;
      if (name == "RET") return Ret;
      if (name == "LINE") return Line;
      if (name == "R1") return R1;
      if (name == "R2") return R2;
      if (name == "R3") return R3;
      if (name == "R4") return R4;
      if (name == "R5") return R5;
      if (name == "R6") return R6;
      if (name == "R7") return R7;
      if (name == "R8") return R8;
      if (name == "E1") return E1;
      if (name == "E2") return E2;
      if (name == "E3") return E3;
      if (name == "E4") return E4;
      if (name == "E5") return E5;
      if (name == "E6") return E6;
      if (name == "E7") return E7;
      if (name == "E8") return E8;
      if (name == "T1") return T1;
      if (name == "T2") return T2;
      if (name == "T3") return T3;
      if (name == "T4") return T4;
      if (name == "T5") return T5;
      if (name == "T6") return T6;
      if (name == "T7") return T7;
      if (name == "T8") return T8;
      if (name == "P1") return P1;
      if (name == "P2") return P2;
      if (name == "P3") return P3;
      if (name == "P4") return P4;
      if (name.substr(0, 3) == "MEM") return mem[Get_Value(name.substr(3))];
    } else {
      static Ty tmp;
      tmp = atoll(name.c_str());
      return tmp;
    }
    assert(0);
  }

  void FUNCTION(vector<string> c) {
    tp cnt = 1;
    for (tp x = Line; _TEMP_TO_UPPER(program[x]).substr(0, 3) != "RET"; ++x) ++cnt;
    func_start[c[0]] = to_string(Line);
    program[Line] = "JMP " + to_string(cnt);
  }

  void CALLFUNC(vector<string> c) { CALL({func_start[c[0]]}); }

  void UDEF(vector<string> c) { return; }

  void HLT(vector<string> c) { exit(0); }

  void NOP(vector<string> c) { return; }

  void SET(vector<string> c) { Get_Value(c[1]) = Get_Value(c[0].c_str()); }
  
  void JMP(vector<string> c) { Line += Get_Value(c[0]) - 1; }

  void JIT(vector<string> c) {
    if (c.size() > 1 && Get_Value(c[1])) Line += Get_Value(c[0]) - 1;
    if (c.size() == 1 && Flag) Line += Get_Value(c[0]) - 1;
  }

  void CALL(vector<string> c) {
    sAddr.push_back(Line);
    Line = Get_Value(c[0]);
  }

  void RET(vector<string> c) {
    if (c.size()) Ret = Get_Value(c[0]);
    Line = sAddr.back();
    sAddr.pop_back();
  }

  void INV(vector<string> c) {
    Ty ans = -Get_Value(c[0]);
    if (c.size() > 1) Get_Value(c[1]) = ans;
    else Val = ans;
  }

  void ADD(vector<string> c) {
    Ty ans = Get_Value(c[0]) + Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void SUB(vector<string> c) {
    Ty ans = Get_Value(c[0]) - Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void MULT(vector<string> c) {
    Ty ans = Get_Value(c[0]) * Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void IDIV(vector<string> c) {
    Ty ans = Get_Value(c[0]) / Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void MOD(vector<string> c) {
    Ty ans = Get_Value(c[0]) % Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void LSFT(vector<string> c) {
    Ty ans = Get_Value(c[0]) << Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void RSFT(vector<string> c) {
    Ty ans = Get_Value(c[0]) >> Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void BAND(vector<string> c) {
    Ty ans = Get_Value(c[0]) & Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void BOR(vector<string> c) {
    Ty ans = Get_Value(c[0]) | Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void BXOR(vector<string> c) {
    Ty ans = Get_Value(c[0]) ^ Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Val = ans;
  }

  void LGR(vector<string> c) {
    Ty ans = Get_Value(c[0]) > Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LLS(vector<string> c) {
    Ty ans = Get_Value(c[0]) < Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LGE(vector<string> c) {
    Ty ans = Get_Value(c[0]) >= Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LLE(vector<string> c) {
    Ty ans = Get_Value(c[0]) <= Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LEQL(vector<string> c) {
    Ty ans = Get_Value(c[0]) == Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LAND(vector<string> c) {
    Ty ans = Get_Value(c[0]) && Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void LOR(vector<string> c) {
    Ty ans = Get_Value(c[0]) || Get_Value(c[1]);
    if (c.size() > 2) Get_Value(c[2]) = ans;
    else Flag = ans;
  }

  void RINT(vector<string> c) {
    if (c.empty()) bin >> Val;
    else bin >> Get_Value(c.front());
  }

  void RCH(vector<string> c) {
    char t; bin >> t;
    if (c.empty()) Val = t;
    else Get_Value(c.front()) = t;
  }

  void WINT(vector<string> c) {
    Ty t;
    if (c.empty()) t = Val;
    else t = Get_Value(c.front());
    bin << (long long)t;
  }

  void WCH(vector<string> c) {
    char t;
    if (c.empty()) t = Val;
    else t = Get_Value(c.front());
    bin << t;
  }

  void _CALL_FUNCTION(string s, vector<string> c) {
    _TO_UPPER(s);

    if (s == "CALLFUNC") return CALLFUNC(c);

    if (s == "UDEF") return UDEF(c);
    if (s == "HLT") return HLT(c);
    if (s == "NOP") return NOP(c);
    if (s == "SET") return SET(c);
    if (s == "JMP") return JMP(c);
    if (s == "JIT") return JIT(c);
    if (s == "CALL") return CALL(c);
    if (s == "RET") return RET(c);

    if (s == "INV") return INV(c);
    if (s == "ADD") return ADD(c);
    if (s == "SUB") return SUB(c);
    if (s == "MULT") return MULT(c);
    if (s == "IDIV") return IDIV(c);
    if (s == "MOD") return MOD(c);
    if (s == "LSFT") return LSFT(c);
    if (s == "RSFT") return RSFT(c);
    if (s == "BAND") return BAND(c);
    if (s == "BOR") return BOR(c);
    if (s == "BXOR") return BXOR(c);
  
    if (s == "LGR") return LGR(c);
    if (s == "LLS") return LLS(c);
    if (s == "LGE") return LGE(c);
    if (s == "LLE") return LLE(c);
    if (s == "LEQL") return LEQL(c);
    if (s == "LAND") return LAND(c);
    if (s == "LOR") return LOR(c);

    if (s == "RINT") return RINT(c);
    if (s == "RCH") return RCH(c);
    if (s == "WINT") return WINT(c);
    if (s == "WCH") return WCH(c);

    assert(0);
  }

  KTX_65_PLUS(string P) {
    R1 = R2 = R3 = R4 = 0;
    E1 = E2 = E3 = E4 = 0;
    Flag = Val = Ret = Line = 0;
    mem = vector<Ty>(10000000, 0);
    program.resize(2);
    for (auto& i : P) {
      if (i == '\n') program.push_back("");
      else if (i != ';') program.back().push_back(i);
    }
    if (program.back() == "") program.pop_back();
    program.push_back("HLT");
    for (Line = 1; Line < program.size(); ++Line) {
      vector<string> section {""};
      for (auto& j : program[Line]) {
        if (j == ' ') section.push_back("");
        else section.back().push_back(j);
      }
      if (section.back() == "") section.pop_back();
      string Operation = _TEMP_TO_UPPER(section.front());
      section.erase(section.begin());
      if (Operation == "FUNCTION") FUNCTION(section);
    }
    for (Line = 1; Line < program.size(); ++Line) {
      vector<string> section {""};
      for (auto& j : program[Line]) {
        if (j == ' ') section.push_back("");
        else section.back().push_back(j);
      }
      if (section.back() == "") section.pop_back();
      string Operation = section.front();
      section.erase(section.begin());
      _CALL_FUNCTION(Operation, section);
    }
  }
};

已经用这个东西写了个过河卒

展开

KTX_65_PLUS<tp> KTX_65_PLUS(R"(NOP
FUNCTION $Modify_F;
SET %P1 %T1;
MULT %T1 40 %T1;
ADD %T1 %P2 %T1;
SET %VAL %MEM%T1;
RET;
UDEF;
FUNCTION $Modify_S;
SET %P1 %T1;
MULT %T1 40 %T1;
ADD %T1 %P2 %T1;
ADD %T1 2000 %T1;
SET %VAL %MEM%T1;
RET;
UDEF;
FUNCTION $Query_F;
SET %P1 %T1;
MULT %T1 40 %T1;
ADD %T1 %P2 %T1;
RET %MEM%T1;
UDEF;
FUNCTION $Query_S;
SET %P1 %T1;
MULT %T1 40 %T1;
ADD %T1 %P2 %T1;
ADD %T1 2000 %T1;
RET %MEM%T1;
UDEF;
RINT %R1;
RINT %R2;
RINT %R3;
RINT %R4;
ADD %R1 2 %R1;
ADD %R2 2 %R2;
ADD %R3 2 %R3;
ADD %R4 2 %R4;
SET 2 %P1;
SET 1 %P2;
SET 1 %VAL;
CALLFUNC $Modify_F;
SET %R3 %P1;
SET %R4 %P2;
CALLFUNC $Modify_S;
NOP;
SET -2 %E1;
SET -1 %E2;
SET 1 %E3;
SET 2 %E4;
SET 2 %E5;
SET 1 %E6;
SET -1 %E7;
SET -2 %E8;
NOP;
SET 1 %T1;
SET 2 %T2;
SET 2 %T3;
SET 1 %T4;
SET -1 %T5;
SET -2 %T6;
SET -2 %T7;
SET -1 %T8;
NOP;
SET %R3 %P1;
SET %R4 %P2;
ADD %P1 %E1 %P1;
ADD %P2 %T1 %P2;
CALLFUNC $Modify_S;
SET %R3 %P1;
SET %R4 %P2;
ADD %P1 %E2 %P1;
ADD %P2 %T2 %P2;
CALLFUNC $Modify_S;
SET %R3 %P1;
SET %R4 %P2;
ADD %P1 %E3 %P1;
ADD %P2 %T3 %P2;
CALLFUNC $Modify_S;
SET %R3 %P1;
SET %R4 %P2;
ADD %P1 %E4 %P1;
ADD %P2 %T4 %P2;
CALLFUNC $Modify_S;
SET %R3 %P1;
SET %R4 %P2;
ADD %P1 %E5 %P1;
ADD %P2 %T5 %P2;
CALLFUNC $Modify_S;
SET %R3 %P1;
SET %R4 %P2;
ADD %P1 %E6 %P1;
ADD %P2 %T6 %P2;
CALLFUNC $Modify_S;
SET %R3 %P1;
SET %R4 %P2;
ADD %P1 %E7 %P1;
ADD %P2 %T7 %P2;
CALLFUNC $Modify_S;
SET %R3 %P1;
SET %R4 %P2;
ADD %P1 %E8 %P1;
ADD %P2 %T8 %P2;
CALLFUNC $Modify_S;
UDEF;
FUNCTION $FOR3;
SET %R5 %P1;
SET %R6 %P2;
CALLFUNC $Query_S;
JIT 15 %RET;
SUB %R5 1 %T5;
SUB %R6 1 %T6;
SET %T5 %P1;
SET %R6 %P2;
CALLFUNC $Query_F;
SET %RET %T7;
SET %R5 %P1;
SET %T6 %P2;
CALLFUNC $Query_F;
SET %RET %T8;
ADD %T7 %T8;
SET %R5 %P1;
SET %R6 %P2;
CALLFUNC $Modify_F;
RET;
UDEF;
FUNCTION $FOR2;
SET 2 %R6;
CALLFUNC $FOR3;
ADD %R6 1 %R6;
LLE %R6 %R2;
JIT -3;
RET;
UDEF;
FUNCTION $FOR1;
SET 2 %R5;
CALLFUNC $FOR2;
ADD %R5 1 %R5;
LLE %R5 %R1;
JIT -3;
RET;
CALLFUNC $FOR1;
SET %R1 %P1;
SET %R2 %P2;
CALLFUNC $Query_F;
WINT %RET;
WCH 10;
HLT)");

以后看看能不能写个猪国杀(

3. Rmq Problem / mex

展开

题意

区间 mex。

题解

其实如果这题值域多大没影响,如果有大于 $n$ 的数就当成 $n + 1$ 看即可。

分块做法

首先对所有询问做一个莫队。
然后搞一个值域分块,对于每个块维护此块是否是满的(所有值都出现过)即可。
在添加某个点的时候,只需要看当前这个值域块里有没有相同值,如果没有就计数加一。显然操作时可逆的。
对于查询,只需要依次遍历每个块,找到第一个不满的块,然后在这个块内找到没有出现过的数即可。
时间复杂度:$\mathcal O\left(n \sqrt n\right)$

4. CEOI2017 Building Bridges

展开

题意

有 $n$ 个桥墩。连接 $i$ 和 $j$ 消耗代价 $\left(h_i - h_j\right)^2$,用不到的桥墩会被拆除,代价为 $w_i$。求使 $1$ 与 $n$ 联通的最小代价。

题解

设 $f_i$ 表示链接 $1$ 到 $i$ 的最小代价,$s_i$ 表示 $\sum\limits_{j = 1}^iw_i$。

$$ \begin{aligned} f_i &= \min\limits_{j = 1}^i\left\{f_j + \left(h_i - h_j\right)^2 + s_{i - 1} - s_j\right\}\\ f_i &= \min\limits_{j = 1}^i\left\{f_j + {h_i}^2 - 2h_ih_j + {h_j}^2 + s_{i - 1} - s_j\right\}\\ f_i &= {h_i}^2 + s_{i - 1} + \min\limits_{j = 1}^i\left\{f_j - 2h_ih_j + {h_j}^2 - s_j\right\} \end{aligned} $$

到此已经可以接着用各种重量级方法维护凸包开始斜率优化了,但是其实可以用李超线段树来优化。

直线的式子很显然就是 $g\left(x\right) = -2h_jx + f_j + {h_j}^2 - s_j$,在 $x = h_i$ 时找最小值即可。

代码

constexpr tp VRange = 1e6 + 3;

struct Line {
  tp k, b;
  
  Line() : k(0), b(INF) {};
  Line(tp _k, tp _b) : k(_k), b(_b) {}
  tp operator()(tp x) { return k * x + b; }
};

tp intersection(Line a, Line b) { return (b.b - a.b) / (a.k - b.k); }

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n = bin, f = 0;
  vector<tp> h(n), w(n), s(n, 0);
  vector<Line> t(VRange * 4, Line(0, INF));
  for (tp i = 0; i < n; ++i) bin >> h[i];
  for (tp i = 0; i < n; ++i) bin >> w[i];
  for (tp i = 0; i < n; ++i) s[i] = (i ? s[i - 1] : ZERO) + w[i];
  auto modify = [&](auto $, tp x, tp l, tp r, Line e) -> void {
    if (e(l) >= t[x](l) && e(r) >= t[x](r)) return;
    if (e(l) <= t[x](l) && e(r) <= t[x](r)) { t[x] = e; return; }
    tp p = intersection(e, t[x]), mid = (l + r) / 2;
    if (e(l) <= t[x](l)) {
      if (p <= mid) CALL($, x * 2, l, mid, e);
      else CALL($, x * 2 + 1, mid + 1, r, exchange(t[x], e));
    } else {
      if (p > mid) CALL($, x * 2 + 1, mid + 1, r, e);
      else CALL($, x * 2, l, mid, exchange(t[x], e));
    }
  };
  auto query = [&](auto $, tp x, tp l, tp r, tp k) -> tp {
    dbg(t[x](k));
    if (l == r) return t[x](k);
    tp mid = (l + r) / 2;
    if (mid >= k) return min(t[x](k), CALL($, x * 2, l, mid, k));
    else return min(t[x](k), CALL($, x * 2 + 1, mid + 1, r, k));
  };
  CALL(modify, 1, 0, VRange, Line(-2 * h[0], h[0] * h[0] - s[0]));
  for (tp i = 1; i < n; ++i) {
    f = h[i] * h[i] + s[i - 1] + CALL(query, 1, 0, VRange, h[i]);
    CALL(modify, 1, 0, VRange, Line(-2 * h[i], f + h[i] * h[i] - s[i]));
  }
  bin << f << '\n';
}

void MIST() {
}

5. POI2011 Lightning Conductor

展开

题意

给定整数 $n$,和一个长度为 $n$ 的数组 $a$,求 $p_i = \left\lceil\max\left\{a_j - a_i + \sqrt{\left\lvert i - j\right\rvert}\right\}\right\rceil$

$n = 5 \times 10^5, 0 \leq a_i \leq 10^9$

题解

首先可以发现决策点单调递增,于是可以分治减少一部分无用计算。但是注意这个分治是可以被卡的,但是好写好想。

代码

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n = bin;
  vector<tp> a(n);
  vector<double> p(n, 0);
  bin.rar(FULL(a));
  auto dvd = [&](auto& $, tp l, tp r, tp L, tp R) -> void {
    if (l > r) return;
    tp mid = (l + r) / 2, c;
    double tar = 0;
    for (tp i = L; i <= min(mid, R); ++i) {
      if (a[i] + sqrt(mid - i) > tar) { c = i; tar = a[i] + sqrt(mid - i); }
    }
    p[mid] = max(p[mid], tar);
    $($, l, mid - 1, L, c);
    $($, mid + 1, r, c, R);
  };
  CALL(dvd, 0, n - 1, 0, n - 1);
  reverse(FULL(a)); reverse(FULL(p));
  CALL(dvd, 0, n - 1, 0, n - 1);
  reverse(FULL(a)); reverse(FULL(p));
  for (tp i = 0; i < n; ++i) bin << tp(ceil(p[i] - a[i])) << '\n';
}

void MIST() {
}

6. CF739E Gosha is hunting

展开

题意

你要抓神奇宝贝! 现在一共有 $n$ 只神奇宝贝。 你有 $a$ 个『宝贝球』和 $b$ 个『超级球』。『宝贝球』抓到第 $i$ 只神奇宝贝的概率是 $p_i$,『超级球』抓到的概率则是​ $u_i$。不能往同一只神奇宝贝上使用超过一个同种的『球』,但是可以往同一只上既使用『宝贝球』又使用『超级球』(都抓到算一个)。 请合理分配每个球抓谁,使得你抓到神奇宝贝的总个数期望最大,并输出这个值。

题解

直接跑费用流,虽然是 $\mathcal O\left(n^3\right)$,但是卡不满。

源点向 $A, B$ 两点分别连流量为 $a, b$,费用为 $0$ 的边。
$A, B$ 分别向每个神奇宝贝连流量为 $1$,费用为 $p_i, u_i$ 的边。
每个神奇宝贝向汇点连流量为 $1$,费用为 $0$ 的边和流量为 $1$,费用为 $-p_iu_i$ 的边(如果两个球都用,抓到的概率为 $p_i + u_i - p_iu_i$)。

代码

void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
  tp n, a, b; bin >> n >> a >> b;
  vector<vector<tuple<tp, tp, tp>>> e(n + 4);
  vector<tp> p(n), q(n);
  e[n].emplace_back(n + 1, a, 0);
  e[n].emplace_back(n + 2, b, 0);
  for (tp i = 0; i < n; ++i) {
    double x; bin >> x;
    e[n + 1].emplace_back(i, 1, p[i] = round(-x * 1e9));
  }
  for (tp i = 0; i < n; ++i) {
    double x; bin >> x;
    e[n + 2].emplace_back(i, 1, q[i] = round(-x * 1e9));
  }
  for (tp i = 0; i < n; ++i) e[i].emplace_back(n + 3, 1, 0);
  for (tp i = 0; i < n; ++i) e[i].emplace_back(n + 3, 1, round(p[i] * q[i] / 1e9));
  bin.precision(12);
  bin << -lib::MCMF(e, n, n + 3).second / 1e9 << '\n';
}

void MIST() {
}

持续更新中。。。


  • 分类: 刷题
  • 最后更新于:2024-04-20 20:13:51UTC+8
  • 标签: 无标签

暂无评论

发表评论