今天是數(shù)學(xué)歸納+遞推，考的還可以, A了3道題, 最后一題樹(shù)上的點(diǎn)分治沒(méi)有學(xué)過(guò)，本來(lái)可以得至少40分的暴力分，但爆空間，0分 預(yù)計(jì)得分：340；實(shí)際得分300，rank 2 因?yàn)槌_(kāi)最后一道題，基本都是數(shù)學(xué)題，所以寫(xiě)的比較好?! 今天的題目不難，，，再加努力(特別是圖論部分)！！！
目錄古代人的難題化學(xué)反應(yīng)巧克力樹(shù)上的點(diǎn)對(duì)
考試的時(shí)候就A了，，， 做題的時(shí)候可以考慮寫(xiě)一個(gè)搜索，從k = 1,時(shí)開(kāi)始找規(guī)律，不難發(fā)現(xiàn)是斐波那契數(shù)列 具體證明如下： 
不妨設(shè)存在解集(x, y), 又推導(dǎo)可知必存在解集(x + y, x),故滿(mǎn)足斐波拉契數(shù)列，得證；
考試的時(shí)候A了…… 本來(lái)看到這道題是一臉懵逼，于是非常無(wú)辜的寫(xiě)了一個(gè)O(n^2)的搜索 考試還剩半個(gè)小時(shí)的時(shí)候，想了想又加了個(gè)剪枝，于是就A了…… 顯然對(duì)于每一個(gè)元素的b值，僅當(dāng)他相對(duì)于另一個(gè)選擇元素最大時(shí)才會(huì)對(duì)ans產(chǎn)生影響，故想到枚舉每個(gè)元素的b值為max是的情況 可是，顯然如果要找到對(duì)于當(dāng)前元素最小的a，仍然需要一個(gè)for循環(huán)，并沒(méi)有優(yōu)化，故想到以a值為基礎(chǔ)進(jìn)行排序，這樣便可以在找到與之a(chǎn)值的差最小的元素的同時(shí)，使b[i]最大 我相信你們沒(méi)有看懂，我自己也沒(méi)有太看懂我寫(xiě)的東西，直接放代碼吧……
#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;}考試的數(shù)據(jù)并沒(méi)有出來(lái)，所以在vijos上找了另一道題，不同的使vijos是多組數(shù)據(jù)，最后因?yàn)閟canf T了3個(gè)點(diǎn)，改成cin就A了??! 思路很簡(jiǎn)單，顯然豎著切一下，對(duì)以后豎著切沒(méi)有影響，反而在那之后橫著切的都要多切一刀，所以顯然會(huì)先切代價(jià)大的，同時(shí)記錄該種切法對(duì)另一種切法的影響，再將該代價(jià)變化為受影響后的代價(jià)放入ans即可
這是考試的代碼,即一組數(shù)據(jù)
#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的代碼，即多組數(shù)據(jù)
#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;}唯一一道沒(méi)有A的題，0分，大概因?yàn)樗菆D論，不是數(shù)論吧…… 參考的黃學(xué)長(zhǎng)的代碼，詳情可參考2009年漆子超的論文例一 代碼中賦有自己的理解，不知道對(duì)不對(duì)啊…………
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define inf 0x7fffffffusing namespace std;int n, k, a, b, c;int cnt,sum,ans,root;int head[10005],deep[10005],d[10005],f[10005],son[10005];bool vis[10005];struct node { int to, next, v;} e[20005];inline void add(int a, int b, int c) { e[++cnt].next = head[a]; e[cnt].to = b; e[cnt].v = c; head[a] = cnt;}inline void findfa(int x, int fa) {//尋找樹(shù)的重心 son[x] = 1, f[x] = 0; //son為兒子個(gè)數(shù),f為x的子數(shù)的大小 for (int i = head[x]; i; i = e[i].next) { if (e[i].to == fa || vis[e[i].to]) continue; findfa(e[i].to, x); son[x] += son[e[i].to]; //更新兒子個(gè)數(shù) f[x] = max(f[x], son[e[i].to]); //更新子樹(shù)大小 } f[x] = max(f[x], sum - son[x]); //使之子樹(shù)最大 if (f[x] < f[root]) root = x; //重心是子樹(shù)大小最小的點(diǎn)-->找重心 }inline void getdeep(int x, int fa) {//更新該節(jié)點(diǎn)到其爸爸的距離 deep[++deep[0]] = d[x]; //賦上已有距離 for (int i = head[x]; i; i = e[i].next) { if (e[i].to == fa || vis[e[i].to]) continue; d[e[i].to] = d[x] + e[i].v; //用已有距離更新 getdeep(e[i].to, x); //遞歸調(diào)用 }}inline int cal(int x, int now) { //以x為根節(jié)點(diǎn)，已有路徑長(zhǎng)度為now d[x] = now; deep[0] = 0; getdeep(x, 0); //更新以x為根節(jié)點(diǎn)的子樹(shù)到x節(jié)點(diǎn)的距離 sort(deep + 1, deep + deep[0] + 1); int t = 0, l, r; for (l = 1, r = deep[0]; l < r;) { if (deep[l] + deep[r] <= k) t += (r - l), l++; //在樹(shù)上跳著找合法點(diǎn)對(duì) else r--; } return t;}inline void work(int x) { //統(tǒng)計(jì)以x為根節(jié)點(diǎn)的字?jǐn)?shù)合法數(shù)對(duì)的個(gè)數(shù) ans += cal(x, 0); //以x為根節(jié)點(diǎn)，所以 d為0 vis[x] = 1; for (int i = head[x]; i; i = e[i].next) { if (vis[e[i].to]) continue; ans -= cal(e[i].to, e[i].v); //減去x的每一個(gè)子樹(shù)中合法數(shù)對(duì)的個(gè)數(shù) sum = son[e[i].to]; //更新以x的子節(jié)點(diǎn)為根節(jié)點(diǎn)的樹(shù)的節(jié)點(diǎn)個(gè)數(shù) root = 0; findfa(e[i].to, root); //找以e[i].to為根節(jié)點(diǎn)的子樹(shù)的重心 work(root); //遞歸調(diào)用 }}int main() { while(scanf("%d %d", &n, &k) && n != 0 && k != 0) { ans = root = cnt = 0; memset(vis, 0, sizeof(vis)); memset(head, 0, sizeof(head)); for (int i = 1; i < n; ++i) scanf("%d %d %d", &a, &b, &c), add(a, b, c), add(b, a, c); sum = n, f[0] = inf; findfa(1, 0); work(root); printf("%d/n", ans); } return 0;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
