开始学文化课了,这个计划会鸽一鸽
放寒假了,这个计划会加快进度
这个计划废弃了,因为有了新计划
刷题!
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() {
}
持续更新中。。。