这一次的专题是递归、贪心、分治之类的，题目比较简单，rank较之前有所进步，但是rank 11还是不够的 大概总结一下：每一道题目大概的思路都清楚，但是具体细节没有处理好，暴力分也没有得全，可能是时间比较紧的原因 放上考试的改错代码
考试目录加工生产调度新汉诺塔穿越七色虹区间
一道贪心，考试56分 按照a、b两种时间的最小值排序，从小到大枚，若min[i] == a[i]，则将第i个数从头开始放入；若min[i] == b[i]，则将第i个数从尾开始放入； 需要注意a[i]==b[i]的情况，只能放一次(WA了好久……)
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define L 1000 + 10using namespace std;struct node{ long long a, b, min;} t[L], head[L];long long n;long long ans = 0, l;inline bool comp(node x, node y) { return x.min < y.min;}int main(){ freopen("PRod.in", "r", stdin); freopen("prod.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%lld", &t[i].a); for (int i = 1; i <= n; ++i) scanf("%lld", &t[i].b), t[i].min = min(t[i].a, t[i].b); sort(t + 1, t + 1 + n, comp); int l1 = 0, l2 = n + 1; for (int i = 1; i <= n; ++i) { if (t[i].min == t[i].a) head[++l1].a = t[i].a, head[l1].b = t[i].b; else if (t[i].min == t[i].b) head[--l2].a = t[i].a, head[l2].b = t[i].b; } for (int i = 1; i <= n; ++i) { ans += head[i].a; if (l >= head[i].a) l -= head[i].a; else l = 0; l += head[i].b; } printf("%lld/n", l + ans); return 0;}一道递归模拟题，考试9分 对于n个圈子从大到小的调用函数move(a,to)，表示把第a个圈放至第to个杆子上，因为是从大到小的调用，所以每一个圈子调用后的位置就会确定，不用担心之后调用圈子会影响到它 move函数中，先将当前圈子保持不动，把除开当前圈子以外的其他所有比之小的圈子移动到aim和now之外的杆子上去，即move(1…a - 1, 6 - to - now[a])
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int n, a, x, now[100], aim[100], ans;inline void move(int a, int to) { if (now[a] == to) return ; ans++; for (int i = a - 1; i >= 1; --i) move(i, 6 - to - now[a]); printf("move %d from %c to %c/n", a, now[a] - 1 + 'A', to - 1 + 'A'); now[a] = to;}int main(){ freopen("hanoi.in", "r", stdin); freopen("hanoi.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= 3; ++i) { scanf("%d", &a); for (int j = 1; j <= a; ++j) scanf("%d", &x), now[x] = i; } for (int i = 1; i <= 3; ++i) { scanf("%d", &a); for (int j = 1; j <= a; ++j) scanf("%d", &x), aim[x] = i; } for (int i = n; i >= 1; --i) move(i, aim[i]); printf("%d/n", ans); return 0;}二分查找+勾股，考试0分 对于答案范围二分，然后check mid； 对于每一个mid，考虑加上该mid后每一个彩虹的左右两个极端范围，然后按照左端点排序(注意应该在此排序)，最后考虑是否[0,x0]均在彩虹的范围内 其中对于高度h彩虹的范围用勾股求值
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;struct node1{ double o, R;} t[10];struct node2{ double l, r;} x[10];double x0, h;double ans = 0;inline bool com(node2 a, node2 b) { return a.l < b.l;}inline bool check(double mid) { for (int i = 1; i <= 7; ++i) { if (t[i].R + mid >= h) { double h0 = sqrt((t[i].R + mid) * (t[i].R + mid) - h * h); x[i].l = t[i].o - h0, x[i].r = t[i].o + h0; } } sort(x + 1, x + 8, com); double ll = x[1].l, rr = x[1].r; for (int i = 2; i <= 7; ++i) { if (x[i].l <= rr) { if (x[i].l < ll) ll = x[i].l; if (x[i].r > rr) rr = x[i].r; } } if (ll <= 0 && rr >= x0) return 1; else return 0;}int main(){ freopen("rainbow.in", "r", stdin); freopen("rainbow.out", "w", stdout); scanf("%lf %lf", &h, &x0); for (int i = 1; i <= 7; ++i) scanf("%lf %lf", &t[i].o, &t[i].R); double l = 0.0, r = x0; while (r - l >= 0.001) { ans = (l + r)/2.0; if (check(ans)) r = ans; else l = ans; } printf("%.2lf/n", ans); return 0;}线段树+决策性优化，考试时打得暴力25分 按照每一各区间的长度有小到大排序，然后根据左右两端点用线段树维护
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <cstring>#define L 1000009#define MAXN 2147483647#define ls (x << 1)#define rs (x << 1 | 1)using namespace std;struct node{ int l, r, len;} a[L];int n, m, cnt, b[L << 1], sum[L << 2], j, ans = MAXN, lazy[L << 2];inline bool comp(node a, node b) { return a.len < b.len;}inline int build(int l, int r, int x) { if (l == r) return l; int mid = (l + r) >> 1; if (x <= b[mid]) build(l, mid, x); else build(mid + 1, r, x);}inline void down(int x, int v) { sum[x] += v, lazy[x] += v;}inline void change(int x, int l, int r, int a, int b, int v) { if (l == a && r == b) {down(x, v); return ;} if (lazy[x]) down(ls, lazy[x]), down(rs, lazy[x]), lazy[x] = 0; int mid = (l + r) >> 1; if (b <= mid) change(ls, l, mid, a, b, v); else if (a > mid) change(rs, mid + 1, r, a, b, v); else change(ls, l, mid, a, mid, v), change(rs, mid + 1, r, mid + 1, b, v); sum[x] = max(sum[ls], sum[rs]);}inline void solve() { for (int i = 1; i <= n; ++i) { while (sum[1] < m) { if (j == n) return ; j++; change(1, 1, cnt, a[j].l, a[j].r, 1); } ans = min(ans, a[j].len - a[i].len); change(1, 1, cnt, a[i].l, a[i].r, -1); }}int main(){ freopen("interval.in", "r", stdin); freopen("interval.out", "w", stdout); scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%d %d", &a[i].l, &a[i].r); b[++cnt] = a[i].l, b[++cnt] = a[i].r; a[i].len = a[i].r - a[i].l; } sort(a + 1, a + 1 + n, comp); sort(b + 1, b + 1 + cnt); for (int i = 1; i <= n; ++i) a[i].l = build(1, cnt, a[i].l), a[i].r = build(1, cnt, a[i].r); solve(); if (ans == MAXN) ans = -1; printf("%d/n", ans); return 0;}新闻热点
疑难解答
