NOI 系列真题练习笔记

2024-07-10 05:24| 来源: 网络整理| 查看: 265

前言

NOIP 前开始做做真题，虽然每年都风格迥异，不过感受一下 OI 风格的题目还是有一定意义的。

P1016 旅行家的预算

贪心地考虑，在一个油站，如果加油，要么加满，要么加到足够行驶到下一个加油点的油量，在下一个更便宜的加油点再加油。

是否存在后效性呢？在下一个油站始终可以加满，所以应该没有。当然，这鬼数据范围乱搜一下就完事了。

代码语言：javascript复制#include const int maxn = 100; int n; double totaldis,C,per; double cost[maxn],dis[maxn]; double res = 1e18; void dfs(int now,double totalcost,double nowhave) { if(nowhave < 0) return; if(now == n) return (void)(res = res > totalcost ? totalcost : res); for(int i = now + 1;i= qh3 && maxx == q3[qh3]) Q[++qt] = q3[qh3++]; } for (int i = t; i val = val, this->id = id; } bool operator(const snake& b) const { return val != b.val ? val > b.val : id > b.id; } } q1[maxn], q2[maxn]; inline snake getmax() { snake res; if (qt1 >= qh1) res = std::max(res, q1[qh1]); if (qt2 >= qh2) res = std::max(res, q2[qh2]); return res; } inline snake getmin() { snake res; res.val = 1 = qh1) res = std::min(res, q1[qt1]); if (qt2 >= qh2) res = std::min(res, q2[qt2]); return res; } inline void popmax() { if(qt1 >= qh1 && qt2 >= qh2) { if (q1[qh1] > q2[qh2]) ++qh1; else ++qh2; } else if (qt1 >= qh1) ++qh1; else ++qh2; } int lastmin; inline void popmin() { if(qt1 >= qh1 && qt2 >= qh2) { if (q1[qt1] < q2[qt2]) --qt1, lastmin = 1; else --qt2, lastmin = 2; } else if (qt1 >= qh1) --qt1, lastmin = 1; else --qt2, lastmin = 2; } inline void recovermin() { if(lastmin == 1) ++qt1; else if(lastmin == 2) ++qt2; } inline snake getsecmin() { snake res; popmin(), res = getmin(), recovermin(); return res; } inline int totalcount() { return std::max(0, qt1 - qh1 + 1) + std::max(0, qt2 - qh2 + 1); } bool dfs()//搜索敢不敢吃 { if(totalcount() == 2) return 1; snake maxx = getmax(), minn = getmin(), secmin = getsecmin(); maxx.val -= minn.val; if(maxx > secmin) return 1; else { popmax(), popmin(), q2[++qt2] = maxx; return !dfs(); } } int main() { read(T); for (int t = 1; t X_b - \dfrac{(X_c - X_b)}{3}

值域比较小，感觉要从值域上做手脚了。

X_a > \dfrac{4}{3} \times X_b - X_c

首先，可以发现，X_b - X_a = 2 \times (X_d - X_c) 这个式子是有意义的，可以考虑为两个值的差两倍于令两个值。并且可以发现，X_b - X_a 是偶数时才合法。

然后其实 X_b - X_a < \dfrac{X_c - X_b}{3}c 点的范围不能太远，再结合值域，感觉就是打个暴力了。

之前的式子应该都全部白化简了。

可以考虑枚举 X_b，然后再枚举 X_a，保证 X_b - X_a 是偶数，然后 X_b - X_a = 2 \times (X_d - X_c)，因此上界是 10000，而每次跳两步，其实是 O(5000^2) 的。

此时只需要查询对于所有合法的 X_c，差分数组打个标记，然后对每个 X_c 的对应的 X_d 也标记一下，这时候发现一开始枚举差值会比较好。

乱搞一下就行了，反正是普及组的题目。

大概就是枚举差值，然后做个可行对数前缀和，然后再差分做区间修改。细节多，多调调就行了。普及组的假题。

代码语言：javascript复制#include #include #include const int bufSize = 1e6; #define DEBUG inline char nc() { #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++; } template inline T read(T &r) { static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag; } const int maxn = 2e5 + 100; int n, m, a[maxn], num[maxn]; int A[maxn], B[maxn], C[maxn], D[maxn]; int tmp[maxn]; int pairnum[maxn]; signed main() { read(n), read(m); int maxx = 0, minn = 200000; for (int i = 1; i = minb; --i) tmp[i] += tmp[i + 1]; for (int b = up; b >= minb; --b) { int a = b - 2 * dis; if(a < 1) break; if(!num[a] || !num[b]) continue; A[a] += num[b] * tmp[b], B[b] += num[a] * tmp[b]; } } for (int i = 1; i

【本文地址】

公司简介

联系我们