2.6

2019-11-11 06:50:42

字體：大中小

來源：轉載

供稿：網友

今天是數學歸納+遞推，考的還可以, A了3道題, 最后一題樹上的點分治沒有學過，本來可以得至少40分的暴力分，但爆空間，0分預計得分：340；實際得分300，rank 2 因為除開最后一道題，基本都是數學題，所以寫的比較好?! 今天的題目不難，，，再加努力(特別是圖論部分)?。?！

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define LL long longusing namespace std;LL k, f[100];int main() {// freopen("puz.in", "r", stdin);// freopen("puz.out", "w", stdout); scanf("%lld", &k); f[1] = 1, f[2] = 1; for (int i = 3; i <= 100; ++i) { f[i] = f[i - 1] + f[i - 2]; if (f[i] > k) { 化學反應

考試的時候A了…… 本來看到這道題是一臉懵逼，于是非常無辜的寫了一個O(n^2)的搜索考試還剩半個小時的時候，想了想又加了個剪枝，于是就A了…… 顯然對于每一個元素的b值，僅當他相對于另一個選擇元素最大時才會對ans產生影響，故想到枚舉每個元素的b值為max是的情況可是，顯然如果要找到對于當前元素最小的a，仍然需要一個for循環，并沒有優化，故想到以a值為基礎進行排序，這樣便可以在找到與之a值的差最小的元素的同時，使b[i]最大我相信你們沒有看懂，我自己也沒有太看懂我寫的東西，直接放代碼吧……

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;struct node{ long long a, b;} ele[100000 + 10];long long n, ans, T;bool flag = 0;inline bool comp (node x, node y) { return x.a > y.a;}int main() {// freopen("reaction.in", "r", stdin);// freopen("reaction.out", "w", stdout); scanf("%d", &T); while(T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%lld %lld", &ele[i].a, &ele[i].b); sort(ele + 1, ele + 1 + n, comp); for (int i = 1; i <= n; ++i) { int la = i - 1, lb = i + 1; long long dis; while (la >= 1 && ele[la].b > ele[i].b) la--; while (lb <= n && ele[lb].b > ele[i].b) lb++; if (la < 1 && lb > n) continue; else if (la < 1) dis = abs(ele[lb].a - ele[i].a); else if (lb > n) dis = abs(ele[i].a - ele[la].a); dis = min(abs(ele[lb].a - ele[i].a), abs(ele[i].a - ele[la].a)); dis++; if (!flag) ans = dis * ele[i].b, flag = 1; else ans = min(ans, dis * ele[i].b); } printf("%lld/n", ans); flag = 0, ans = 0; memset(ele, 0, sizeof(ele)); } return 0;}

巧克力

考試的數據并沒有出來，所以在vijos上找了另一道題，不同的使vijos是多組數據，最后因為scanf T了3個點，改成cin就A了??! 思路很簡單，顯然豎著切一下，對以后豎著切沒有影響，反而在那之后橫著切的都要多切一刀，所以顯然會先切代價大的，同時記錄該種切法對另一種切法的影響，再將該代價變化為受影響后的代價放入ans即可

這是考試的代碼,即一組數據

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;long long ans = 0;int n, m, cnta = 1, cntb = 1;long long a[100000 + 10], b[100000 + 10];inline bool comp(long long x, long long y) { return x > y;}int main() { freopen("chocolate.in", "r", stdin); freopen("chocolate.out", "w", stdout); scanf("%d %d", &n, &m); for (int i = 1; i < n; ++i) cin >> a[i]; for (int i = 1; i < m; ++i) cin >> b[i]; sort(a + 1, a + n, comp); sort(b + 1, b + m, comp); int la = 1, lb = 1; while(la < n || lb < m) { if (a[la] < b[lb]) ans += b[lb] * cntb, cnta++, lb++; else ans += a[la] * cnta, cntb++, la++; } printf("%lld/n", ans); return 0;}

vijos的代碼，即多組數據

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;long long ans = 0;int n, m, cnta = 1, cntb = 1, T;long long a[100000 + 10], b[100000 + 10];inline bool comp(long long x, long long y) { return x > y;}int main() { freopen("chocolate.in", "r", stdin); freopen("chocolate.out", "w", stdout); scanf("%d", &T); while(T--) { ans = 0; memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); scanf("%d %d", &n, &m); for (int i = 1; i < n; ++i) cin >> a[i]; for (int i = 1; i < m; ++i) cin >> b[i]; sort(a + 1, a + n, comp); sort(b + 1, b + m, comp); int la = 1, lb = 1; while(la < n || lb < m) { if (a[la] < b[lb]) ans += b[lb] * cntb, cnta++, lb++; else ans += a[la] * cnta, cntb++, la++; } printf("%lld/n", ans); cnta = 1, cntb = 1; } return 0;}