不会做的简单题
贪心的『策略』是一种很模糊的东西
- 如果能找到一种清晰的操作流程，自然是很好的，但如果要从数学角度进行推导，可能有些困难
- 否则，如果没办法找到一种确定的操作方式，需要确定答案的上 / 下界是可以取到的
饥饿的狐狸
https://www.luogu.com.cn/problem/P4801
第一问，发现不喝水一定不劣，故大小顺序吃饼干即可。
具体地，若 \(W<a_1\)，把 \(W\) 视作 \(a_0\) 即可；若 \(W>a_n\)，把 \(W\) 视作 \(a_{n+1}\) 即可；
若 \(a_1<W<a_n\)，那么由于喝水是没有代价的，可以从 \(W\) 一直吃到 \(a_1\)，再喝水，再从 \(W\) 一直吃到 \(a_n\)。
第二问，我们希望 \(a_i-a_j\) 这个代价中的 \(a_i\) 尽可能大，\(a_j\) 尽可能小。故尝试让前一半当 \(a_j\)，后一半当 \(a_i\) 即可，那么顺序其实无所谓，只是需要讨论一下和第一次 \(W\) 接壤的是 \(a_1\) 还是 \(a_n\)。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n;
long long w;
std::cin >> n >> w;
std::vector<long long> a(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> a[i];
std::sort(a.begin() + 1, a.end());
std::cout << std::max(w - a[1], 0ll) + std::max(a[n] - w, 0ll) << ' ';
auto calc = [&](int op) {
long long res = 0ll, now = w;
for (int i = 1, l = 1, r = n; i <= n; ++i)
if (i % 2 == op)
res += std::max(std::abs(a[l] - now), std::abs(a[l] - w)), now = a[l++];
else
res += std::max(std::abs(a[r] - now), std::abs(a[r] - w)), now = a[r--];
return res;
};
std::cout << std::max(calc(0), calc(1)) << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}SAM-Toy Cars
https://www.luogu.com.cn/problem/P3419
- 有一个大概的感受是每次丢弃『下次出现时间』最晚的一个。
- tip：玩具在地上的时候不会更新队列中的 nex。需要特别处理。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, k, p;
std::cin >> n >> k >> p;
std::vector<int> a(p + 1);
for (int i = 1; i <= p; ++i)
std::cin >> a[i];
std::vector<int> nex(p + 1), la(n + 1, p + 1);
for (int i = p; i; --i)
nex[i] = la[a[i]], la[a[i]] = i;
std::priority_queue<std::pair<int, int> > q;
std::vector<int> inq(n + 1);
int cnt = 0;
for (int i = 1; i <= p; ++i)
if (!inq[a[i]]) {
if ((int)q.size() == k) {
auto [nex, v] = q.top();
q.pop();
inq[v] = 0;
}
++cnt, q.emplace(nex[i], a[i]);
inq[a[i]] = 1;
}
else
q.emplace(nex[i], a[i]), ++k;
std::cout << cnt << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}Sports Festival
https://www.luogu.com.cn/problem/AT_agc018_b
- 会有一个显然的二分做法
- 其实可以不用二分，每次删最大的，每次更新答案
- 用带一点反证的思路是好证的
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, m;
std::cin >> n >> m;
std::vector<std::queue<int> > a(n + 1);
std::vector<int> del(m + 1), cnt(m + 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1, x; j <= m; ++j)
std::cin >> x, a[i].push(x);
++cnt[a[i].front()];
}
int res = n + 1;
for (int i = 1; i <= m; ++i) {
int mx = 0, id = 0;
for (int i = 1; i <= m; ++i)
if (cnt[i] > mx)
mx = cnt[i], id = i;
res = std::min(res, mx);
if (i == m)
break;
del[id] = 1;
for (int j = 1; j <= n; ++j) {
--cnt[a[j].front()];
for (; del[a[j].front()]; a[j].pop());
++cnt[a[j].front()];
}
}
std::cout << res << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}Linguistics
https://www.luogu.com.cn/problem/CF1685B
- 找到每一段极长交错段，把
AB和BA；处理掉 - 发现 ABABA 和 BABAB 对于
AB和BA是等价的，考虑 ABABAB 和 BABABA。发现后二者要么匹配 AB / BA，要么删去首尾后转化为另一者。但这样就会浪费掉一个消去AB或BA的机会。 - 故优先对后二者匹配 AB / BA，实在有多余再删头尾。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
int A, B, AB, BA;
std::string a;
std::cin >> A >> B >> AB >> BA >> a;
int n = (int)a.length();
a = "#" + a;
char l = a[1];
int len = 0;
std::vector<int> ab, ba, c;
for (int i = 1; i <= n; ++i) {
if (i == 1 || a[i] != a[i - 1])
++len;
if (i == n || a[i] == a[i - 1]) {
if (len != 1) {
// fprintf(stderr, "#1 len = %d, l = %c \n", len, l);
if (l == 'A' && a[i] == 'B')
ab.push_back(len);
else if (l == 'A') {
if (!A)
goto nosol;
else
--A, c.push_back(len - 1);
}
else if (a[i] == 'A')
ba.push_back(len);
else if (!B)
goto nosol;
else
--B, c.push_back(len - 1);
}
else {
// fprintf(stderr, "#2 len = %d, l = %c \n", 1, l);
if (l == 'A') {
if (!A)
goto nosol;
--A;
}
else {
if (!B)
goto nosol;
--B;
}
}
if (i == n && a[i] == a[i - 1]) {
// fprintf(stderr, "#3 len = %d, l = %c \n", 1, a[i]);
if (a[i] == 'A') {
if (!A)
goto nosol;
--A;
}
else {
if (!B)
goto nosol;
--B;
}
}
len = 1, l = a[i];
}
}
std::sort(ab.begin(), ab.end(), std::greater<int> ());
std::sort(ba.begin(), ba.end(), std::greater<int> ());
for (; !ab.empty() && AB; ) {
int x = std::min(AB, ab.back() / 2);
AB -= x, ab.back() -= x * 2;
if (!ab.back())
ab.pop_back();
}
for (; !ba.empty() && BA; ) {
int x = std::min(BA, ba.back() / 2);
BA -= x, ba.back() -= x * 2;
if (!ba.back())
ba.pop_back();
}
// fprintf(stderr, "AB = %d, BA = %d, A = %d, B = %d \n", AB, BA, A, B);
for (; !ab.empty() && BA; ) {
if (!A || !B)
goto nosol;
ab.back() -= 2, --A, --B;
int x = std::min(BA, ab.back() / 2);
BA -= x, ab.back() -= x * 2;
if (!ab.back())
ab.pop_back();
}
for (; !ab.empty(); ) {
A -= ab.back() / 2, B -= ab.back() / 2;
ab.pop_back();
}
if (A < 0 || B < 0)
goto nosol;
for (; !ba.empty() && AB; ) {
if (!A || !B)
goto nosol;
ba.back() -= 2, --A, --B;
int x = std::min(AB, ba.back() / 2);
AB -= x, ba.back() -= x * 2;
if (!ba.back())
ba.pop_back();
}
for (; !ba.empty(); ) {
A -= ba.back() / 2, B -= ba.back() / 2;
ba.pop_back();
}
if (A < 0 || B < 0)
goto nosol;
for (; !c.empty() && AB; ) {
int x = std::min(AB, c.back() / 2);
AB -= x, c.back() -= x * 2;
if (!c.back())
c.pop_back();
}
for (; !c.empty() && BA; ) {
int x = std::min(BA, c.back() / 2);
BA -= x, c.back() -= x * 2;
if (!c.back())
c.pop_back();
}
if (AB || BA)
goto nosol;
for (; !c.empty(); ) {
A -= c.back() / 2, B -= c.back() / 2;
c.pop_back();
}
if (A || B)
goto nosol;
std::cout << "YES\n";
continue;
nosol: ;
std::cout << "NO\n";
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}Sunny’s Crystals
https://www.luogu.com.cn/problem/P5584
- 如果某一时刻同时存在多个可以被删除的数，显然应该删最后一个
- 否则，发现删每一个位置对于后方关键点的贡献完全相同，故删第一个即可。
- 发现线段树没办法很好地维护『有哪些点是二的次方』，但是我们知道一个很相似的结构『有哪些点是 \(0\)』，结合起来可以马上反映出来实时维护每个点到最近一个二的此方位置的距离。
- 把非关键点 / 被删去的点赋为 inf 即可方便维护。
#include <bits/stdc++.h>
const int maxn = 3e6 + 5;
const int inf = 0x3f3f3f3f;
struct {
int l, r, u, x, d;
} t[maxn << 2];
int tot = 0;
#define lt t[p].l
#define rt t[p].r
void pushval(int p, int v) {
if (p)
t[p].d += v, t[p].u += v;
return;
}
void pushdown(int p) {
pushval(lt, t[p].d), pushval(rt, t[p].d);
t[p].d = 0;
return;
}
void pushup(int p) {
t[p].u = std::min(t[lt].u, t[rt].u);
if (t[rt].u == t[p].u)
t[p].x = t[rt].x;
else
t[p].x = t[lt].x;
return;
}
void upd(int &p, int l, int r, int x, int v) {
if (!p)
p = ++tot;
if (l == r) {
t[p].u = v, t[p].x = l;
return;
}
pushdown(p);
int mid = (l + r) >> 1;
if (x <= mid)
upd(lt, l, mid, x, v);
else
upd(rt, mid + 1, r, x, v);
pushup(p);
return;
}
void add(int p, int l, int r, int ql, int qr, int v) {
if (!p)
return;
if (ql <= l && r <= qr) {
pushval(p, v);
return;
}
pushdown(p);
int mid = (l + r) >> 1;
if (ql <= mid)
add(lt, l, mid, ql, qr, v);
if (qr > mid)
add(rt, mid + 1, r, ql, qr, v);
pushup(p);
return;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, w, m = 0, rt = 0;
std::cin >> n >> w, t[0].u = inf;
auto to = [&](int x) {
return 1 << std::__lg(x);
};
for (int i = 1, x; i <= n; ++i) {
std::cin >> x;
if (x == w)
++m, upd(rt, 1, n, i, i - to(i));
}
std::vector<int> res, del(n + 1);
for (int i = 1, now = 1; i <= m; ++i) {
for (int j = 1; j <= t[1].u; ++j) {
for (; del[now]; ++now);
del[now] = 1, res.push_back(now++);
}
pushval(rt, -t[1].u);
int pos = t[1].x;
del[pos] = 1, res.push_back(pos);
upd(rt, 1, n, pos, inf);
if (pos + 1 <= n)
add(rt, 1, n, pos + 1, n, -1);
}
std::cout << (int)res.size() << '\n';
for (auto i : res)
std::cout << i << ' ';
std::cout << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}