CSP S 2019 洛谷P5665 劃分

2022-09-23 07:56:57 字數 3765 閱讀 8053

\(csp\)時發現自己做過類似這道題的題目 : p4954 [usaco09open] tower of hay 乾草塔

然後回憶了差不多\(15min\)才想出來。。。

然後就敲了\(88pts\)的部分分。當時的記憶體是\(950mb\)左右,寫一個高精就炸記憶體了。

2048 年,第三十屆 csp 認證的考場上,作為選手的小明開啟了第一題。這個題的樣例有 \(n\) 組資料,資料從 \(1 \sim n\) 編號,\(i\) 號資料的規模為 \(a_i\)。

小明對該題設計出了一個暴力程式,對於一組規模為 \(u\) 的資料,該程式的執行時間為 \(u^2\)。然而這個程式執行完一組規模為 \(u\) 的資料之後,它將在任何一組規模小於\(u\) 的資料上執行錯誤。樣例中的 \(a_i\) 不一定遞增,但小明又想在不修改程式的情況下正確執行樣例,於是小明決定使用一種非常原始的解決方案:將所有資料劃分成若干個資料段,段內資料編號連續,接著將同一段內的資料合併成新資料,其規模等於段內原資料的規模之和,小明將讓新資料的規模能夠遞增。

也就是說,小明需要找到一些分界點 \(1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n\),使得

\[\sum_^ a_i \leq \sum_^ a_i \leq \cdots \leq \sum_^ a_i

\]注意 \(p\) 可以為 \(0\) 且此時 \(k_0 = 0\),也就是小明可以將所有資料合併在一起執行。

小明希望他的程式在正確執行樣例情況下,執行時間也能儘量小,也就是最小化

\[(\sum_^ a_i)^2 + (\sum_^ a_i)^2 + \cdots + (\sum_^ a_i)^2

\]小明覺得這個問題非常有趣,並向你請教:給定 \(n\) 和 \(a_i\),請你求出最優劃分方案下,小明的程式的最小執行時間。

假設我們現在已經劃分為三個部分\(x,y,z\)滿足\(x\leq y\leq z\),那麼顯然是有

\[x^2+y^2+z^2

所以我們肯定要做到能分就分

但是貪心選取肯定是錯誤的。樣例一明顯就指出了錯誤。

考慮\(dp\)。設\(f[i]\)表示我們劃分\(1\sim i\)的所有數,以\(i\)為最後一個區塊的情況下,最後一個區塊的最小長度。

那麼列舉一個\(j\),明顯有

\[f[i]=min(\sum^_a_k)\ \ \ (\sum^_a_k\geq f[j])

\]由於\(\sum^_a_k\)滿足單調性,所以肯定選擇儘量大的\(j\)來轉移。

如果\(j\)可以轉移到\(i\),那麼轉移的同時可以求出劃分的費用

\[ans[i]=ans[j-1]+(\sum^_a_k)^2

\]這樣我們就得到了一個\(o(n^2)\)的演算法,可以得到\(64pts\)的高分。

我們發現,轉移的條件\(\sum^_a_k\geq f[j]\)其實就是\(\sum^i_a_k-\sum^i_a_k\geq f[j]\),移項就得到了\(\sum^i_a_k\geq f[j]+\sum^i_a_k\)

我們發現,在做了字首和之後,上式等號左邊只與\(i\)有關,等號右邊只與\(j\)有關。同時我們又要滿足選擇儘量大的\(j\)來轉移,所以就可以維護一個單調佇列裝\(f[j]+\sum^i_a_k\)進行轉移。

但是我們每次要選擇的是滿足\(\sum^i_a_k\geq f[j]+\sum^i_a_k\)的儘量大\(j\)進行轉移,而不是單純的最小的\(\sum^i_a_k\geq f[j]+\sum^i_a_k\)轉移。所以我們每次要不斷彈出隊頭,知道隊頭不再滿足\(\sum^i_a_k\geq f[j]+\sum^i_a_k\)。此時將最後一次彈出的元素再從頭部插入進行轉移。這樣就保證了每次選擇\(j\)最大的滿足條件的元素進行轉移。容易證明,彈出的元素不會對後面的轉移產生影響。

這樣每個元素最多進入佇列1次,時間複雜度\(o(n)\)。

這樣我們就得到了\(88pts\)的高分。

對於\(type=1\)的資料點需要使用高精,但是由於\(o(n)\)的演算法我們的記憶體已經使用了\(950mb\),所以幾乎沒有空間來敲高精。

所以此時就只能用csp不允許使用的__int128了

我們將\(ans\)改為\(\_\_int128\)型別,是可以存下最終答案的。

然後我就愉快的t了。

在嘗試過所有我知道的化學性卡常後,樣例三依然需要\(2.4s+\)才可以跑過。

所以此時就只能用csp不允許使用的ofast了

物理性卡常\(nb\)!樣例最終可以在\(0.85s\)左右跑過。

然後我就愉快的mle了。

經過輸出後,\(ans,f,sum\)三個陣列加起來是\(1200+mb\)。將近\(200mb\)的差距,只能考慮刪除一個陣列了。

\(ans\)和\(sum\)是肯定無法刪除的,而\(f\)我們發現,在轉移時是等於\(sum[i]-sum[last]\)的,其中\(last\)直可以轉移的最大的\(j\)。

所以我們考慮直接用\(sum\)陣列來表示出\(f\)陣列。這樣我們往單調佇列插入時就要插入\(i,f_i+sum_i\)兩維,因為後者在去掉\(f\)陣列後是沒辦法算出來的。

最終還是以\(1.38s,804.98mb\)過了這道題。但是在\(csp\)時是不允許用\(\_\_int128\)和\(ofast\)的,所以其實這份**無論是時間還是空間都是過不去的

#pragma gcc optimize("ofast")

#pragma gcc optimize("inline")

#include #include #include #include #include #define mp make_pair

using namespace std;

typedef long long ll;

const int n=40000010,mod=(1<<30),m=100010;

int n,x,type,cnt,id;

ll d,xx,yy,zz,m,sum[n],b[4],p[m],l[m],r[m];

__int128 ans[n];

pairlast;

char ch;

deque> q;

inline ll read()

inline void write(__int128 x)

inline ll get(int i)

int main()

q.push_back(mp(0,0));

for (register int i=1;i<=n;i++)

q.push_front(last);

int pos=last.first;

ans[i]=ans[pos]+(__int128)(sum[i]-sum[pos])*(sum[i]-sum[pos]);

while (q.size() && q.back().second>=sum[i]-sum[pos]+sum[i]) q.pop_back();

q.push_back(mp(i,sum[i]-sum[pos]+sum[i]));

} write(ans[n]);

return 0;

}