這一次的專題是遞歸、貪心、分治之類的，題目比較簡單，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("新漢諾塔一道遞歸模擬題，考試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;}新聞熱點
疑難解答
