【11.5校内测试】【倒计时5天】【DP】【二分+贪心check】【推式子化简+线段树】...
Solution
非常巧妙的建立DP方程。
據(jù)dalao們說(shuō)題目明顯暗示根號(hào)復(fù)雜度？？（反正我是沒(méi)看出來(lái)
因?yàn)槊看畏值膲K大小一定不超過(guò)$\sqrt n$，要不然直接每個(gè)位置開(kāi)一個(gè)塊答案都才為$n$。
于是大佬們想到用一個(gè)非常巧妙的數(shù)組$pos[j]$，表示順推到當(dāng)前位置$i$時(shí)，以$i$作為右端點(diǎn)，區(qū)間出現(xiàn)了$j$個(gè)顏色的左端點(diǎn)的位置。
于是每次轉(zhuǎn)移就變成了$dp[i]=min(dp[pos[j]-1]+j*j)$，而不需要把之前全部枚舉。$j$的范圍就是$<=\sqrt n$的。
所以每次新到一個(gè)位置，就對(duì)于每個(gè)$j$看是否有新的貢獻(xiàn)，記錄$cnt[j]$表示$pos[j]$到$i$當(dāng)前實(shí)際有多少個(gè)顏色。
如果$cnt[j]>j$表示當(dāng)前$pos[j]$需要往后移動(dòng)更新，那么每次往后一位一位暴力移動(dòng)查詢當(dāng)前位置是否可以作為$pos[j]$，就是判斷這個(gè)位置之后，$i$之前是否還出現(xiàn)了這個(gè)位置的顏色，如果出現(xiàn)了那么這個(gè)位置就不能作為$pos[j]$，因?yàn)樗竺孢€有貢獻(xiàn)。（據(jù)說(shuō)均攤復(fù)雜度O(n)？？）
細(xì)節(jié)通過(guò)雙向鏈表處理。
Code
#include<bits/stdc++.h> #define LL long long #define RG register using namespace std;LL dp[40005]; int nxt[40005], a[40005], pre[40005], las[40005], pos[40005], cnt[40006]; int n, m;int main() {freopen("cleanup.in", "r", stdin);freopen("cleanup.out", "w", stdout);scanf("%d%d", &n, &m);for(int i = 1; i <= n; i ++) {scanf("%d", &a[i]);pre[i] = las[a[i]];nxt[las[a[i]]] = i;las[a[i]] = i;nxt[i] = n + 1;}memset(dp, 0x3f3f3f3f, sizeof(dp)); dp[0] = 0;int siz = sqrt(n); for(int i = 1; i <= siz; i ++) pos[i] = 1;for(RG int i = 1; i <= n; i ++) {for(RG int j = 1; j <= siz; j ++) {if(pre[i] < pos[j]) cnt[j] ++;if(cnt[j] > j) {cnt[j] --;while(nxt[pos[j]] < i) pos[j] ++;pos[j] ++;}dp[i] = min(dp[pos[j] - 1] + j * j, dp[i]);}}printf("%lld", dp[n]);return 0; }Solution
二分性很明顯，但是check竟然是用搜索回溯處理？？？真實(shí)震驚
搜索大概就是每次在剩下沒(méi)有被覆蓋的點(diǎn)中找到最靠左、最靠右、最靠下、最靠上四個(gè)極點(diǎn)位置，然后每次貪心往四個(gè)角（左上、左下、右上、右下）填矩陣，更新剩下沒(méi)覆蓋的點(diǎn)，搜三層回來(lái)即可.....
真的好玄學(xué)啊QAQ但是就是過(guò)了QAQ
Code
#include<bits/stdc++.h> #define oo 0x3f3f3f3f #define LL long long using namespace std;int n, xmi, xma, ymi, yma, MA;struct Node {LL x, y; } tr[20005]; bool cmp1(Node a, Node b) { return a.x < b.x; } bool cmp2(Node a, Node b) { return a.y < b.y; }bool flag, vis[20005]; LL now;void dfs(int dep, int tot) {if(tot == n) { flag = 1; return ; }if(dep == 3) return ;bool used[20005] = {0};LL maxx = -oo, minx = oo, maxy = -oo, miny = oo;for(int i = 1; i <= n; i ++) {if(vis[i]) continue;maxx = max(maxx, tr[i].x); minx = min(minx, tr[i].x);maxy = max(maxy, tr[i].y); miny = min(miny, tr[i].y);}int cnt = 0;LL xl = minx, xr = minx + now, yl = miny, yr = miny + now; cnt = 0;for(int i = 1; i <= n; i ++) {if(vis[i]) continue;if(tr[i].x <= xr && tr[i].x >= xl && tr[i].y >= yl && tr[i].y <= yr) {vis[i] = 1; used[i] = 1; cnt ++;}}dfs(dep + 1, tot + cnt); if(flag) return ;for(int i = 1; i <= n; i ++) if(used[i]) vis[i] = used[i] = 0;xl = minx, xr = minx + now, yl = maxy - now, yr = maxy; cnt = 0;for(int i = 1; i <= n; i ++) {if(vis[i]) continue;if(tr[i].x <= xr && tr[i].x >= xl && tr[i].y >= yl && tr[i].y <= yr) {vis[i] = 1; used[i] = 1; cnt ++;}}dfs(dep + 1, tot + cnt); if(flag) return ;for(int i = 1; i <= n; i ++) if(used[i]) vis[i] = used[i] = 0;xl = maxx - now, xr = maxx, yl = maxy - now, yr = maxy; cnt = 0;for(int i = 1; i <= n; i ++) {if(vis[i]) continue;if(tr[i].x <= xr && tr[i].x >= xl && tr[i].y >= yl && tr[i].y <= yr) {vis[i] = 1; used[i] = 1; cnt ++;}}dfs(dep + 1, tot + cnt); if(flag) return ;for(int i = 1; i <= n; i ++) if(used[i]) vis[i] = used[i] = 0;xl = maxx - now, xr = maxx, yl = miny, yr = miny + now; cnt = 0;for(int i = 1; i <= n; i ++) {if(vis[i]) continue;if(tr[i].x <= xr && tr[i].x >= xl && tr[i].y >= yl && tr[i].y <= yr) {vis[i] = 1; used[i] = 1; cnt ++;}}dfs(dep + 1, tot + cnt); if(flag) return ;for(int i = 1; i <= n; i ++) if(used[i]) vis[i] = used[i] = 0; }bool check(LL mid) {now = mid; flag = 0;for(int i = 1; i <= n; i ++) vis[i] = 0;dfs(0, 0);return flag; }LL erfen() {LL l = 0, r = 100000000000, ans;while(l <= r) {LL mid = (l + r) >> 1;if(check(mid)) ans = mid, r = mid - 1;else l = mid + 1;}return ans; }int main() {freopen("cover.in", "r", stdin);freopen("cover.out", "w", stdout);scanf("%d", &n);for(int i = 1; i <= n; i ++)scanf("%lld%lld", &tr[i].x, &tr[i].y);LL ans = erfen();printf("%lld", ans);return 0; }Solution
區(qū)間修改？？發(fā)現(xiàn)沒(méi)那么簡(jiǎn)單QAQ，是求多個(gè)區(qū)間的和，沒(méi)辦法直接修改就快速求出答案。
所以推一推式子將$n^3$優(yōu)化到$n^2$，要求的區(qū)間的區(qū)間和實(shí)際上可以由每條邊的貢獻(xiàn)算出來(lái)：$\sum_{i=L}^{R}{v[i]*(i-L+1)*(R-i+1)}$，此處$R$是事先$--$了的，因?yàn)?R-R+1$的邊不能被算入貢獻(xiàn)。
化簡(jiǎn)得$\sum{iv[i] * (L + R) - i^2v[i] + v[i] * (R - L * R + 1 - L)}$所以要維護(hù)的變量實(shí)際上只有$iv[i].i^2v[i].v[i]$三個(gè)的區(qū)間和即可，用一顆線段樹(shù)結(jié)構(gòu)體就好辣。
全都要開(kāi)longlong才可以！！
Code
#include<bits/stdc++.h> #define LL long long using namespace std;LL n, m;LL gcd(LL a, LL b) {return b == 0 ? a : gcd(b, a % b); }struct Node {LL iv, v, iv2;Node operator + (const Node &a) const {Node c;c.iv = iv + a.iv; c.v = v + a.v; c.iv2 = iv2 + a.iv2;return c;} } TR[400005];LL tag[400005], iv[100005], iv2[100005];void push_down(LL nd, LL l, LL r) {if(tag[nd]) {LL d = tag[nd], mid = (l + r) >> 1;TR[nd << 1].iv += d * (iv[mid] - iv[l - 1]);TR[nd << 1].iv2 += d * (iv2[mid] - iv2[l - 1]);TR[nd << 1].v += d * (mid - l + 1);TR[nd << 1 | 1].iv += d * (iv[r] - iv[mid]);TR[nd << 1 | 1].iv2 += d * (iv2[r] - iv2[mid]);TR[nd << 1 | 1].v += d * (r - mid);tag[nd << 1] += d, tag[nd << 1 | 1] += d; tag[nd] = 0;} }void update(LL nd) {TR[nd] = TR[nd << 1] + TR[nd << 1 | 1]; }void modify(LL nd, LL l, LL r, LL L, LL R, LL d) {if(l >= L && r <= R) {TR[nd].iv += d * (iv[r] - iv[l - 1]);TR[nd].iv2 += d * (iv2[r] - iv2[l - 1]);TR[nd].v += d * (r - l + 1);tag[nd] += d;return ;}push_down(nd, l, r); LL mid = (l + r) >> 1;if(L <= mid) modify(nd << 1, l, mid, L, R, d);if(R > mid) modify(nd << 1 | 1, mid + 1, r, L, R, d);update(nd); }Node query(LL nd, LL l, LL r, LL L, LL R) {if(l >= L && r <= R) return TR[nd];push_down(nd, l, r);LL mid = (l + r) >> 1; Node ans; ans.iv = ans.iv2 = ans.v = 0;if(L <= mid) ans = ans + query(nd << 1, l, mid, L, R);if(R > mid) ans = ans + query(nd << 1 | 1, mid + 1, r, L, R);return ans; }void init() {for(LL i = 1; i <= n; i ++) {iv[i] = iv[i - 1] + i;iv2[i] = iv2[i - 1] + i * i;} }int main() {freopen("roadxw.in", "r", stdin);freopen("roadxw.out", "w", stdout);scanf("%lld%lld", &n, &m);init();for(LL t = 1; t <= m; t ++) {char s[10]; LL L, R, V;scanf("%s", s);if(s[0] == 'C') {scanf("%lld%lld%lld", &L, &R, &V);modify(1, 1, n, L, R - 1, V);} else {scanf("%lld%lld", &L, &R);R --;Node a = query(1, 1, n, L, R);LL ans = a.iv * (L + R) - a.iv2 + a.v * (R - L * R + 1 - L);LL tot = R - L + 2;LL ans2 = tot * (tot - 1) / 2;LL d = gcd(ans, ans2);ans /= d, ans2 /= d;printf("%lld/%lld\n", ans, ans2);}}return 0; }?
轉(zhuǎn)載于:https://www.cnblogs.com/wans-caesar-02111007/p/9910180.html
總結(jié)
以上是生活随笔為你收集整理的【11.5校内测试】【倒计时5天】【DP】【二分+贪心check】【推式子化简+线段树】...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
