2.4

2019-11-14 10:39:19

字體：大中小

供稿：網(wǎng)友

這一次的專題是遞歸、貪心、分治之類的，題目比較簡(jiǎn)單，rank較之前有所進(jìn)步，但是rank 11還是不夠的大概總結(jié)一下：每一道題目大概的思路都清楚，但是具體細(xì)節(jié)沒有處理好，暴力分也沒有得全，可能是時(shí)間比較緊的原因放上考試的改錯(cuò)代碼

考試目錄

考試目錄加工生產(chǎn)調(diào)度新漢諾塔穿越七色虹區(qū)間

加工生產(chǎn)調(diào)度

一道貪心，考試56分按照a、b兩種時(shí)間的最小值排序，從小到大枚，若min[i] == a[i]，則將第i個(gè)數(shù)從頭開始放入；若min[i] == b[i]，則將第i個(gè)數(shù)從尾開始放入；需要注意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分對(duì)于n個(gè)圈子從大到小的調(diào)用函數(shù)move(a,to)，表示把第a個(gè)圈放至第to個(gè)桿子上，因?yàn)槭菑拇蟮叫〉恼{(diào)用，所以每一個(gè)圈子調(diào)用后的位置就會(huì)確定，不用擔(dān)心之后調(diào)用圈子會(huì)影響到它 move函數(shù)中，先將當(dāng)前圈子保持不動(dòng)，把除開當(dāng)前圈子以外的其他所有比之小的圈子移動(dòng)到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分對(duì)于答案范圍二分，然后check mid；對(duì)于每一個(gè)mid，考慮加上該mid后每一個(gè)彩虹的左右兩個(gè)極端范圍，然后按照左端點(diǎn)排序(注意應(yīng)該在此排序)，最后考慮是否[0,x0]均在彩虹的范圍內(nèi) 其中對(duì)于高度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;}