Noip 模擬賽。 Link

T1

考慮不進位的時候可以 \(O(n)\) 求出總和，即 \(\sum_{i=1}^{n}{f(a[i])}\)。考慮存在進位的話答案會有什麼變化，顯然每當有一次進位，總和會減少 \(9\)。

問題就轉化為了如何快速求出進位的次數，不妨枚舉那一位產生了進位。具體來説，枚舉 \(10^i\)，對於每個數，它大於 \(10^i\) 的部分對這一位的進位沒有影響。記 \(b_j=a_j \bmod 10^i\)，對於每個 \(b_j\)，與它相加會產生貢獻的數應當滿足 \(b_k + b_j \geq 10^i\)。對於這樣一個東西是顯然可以排序之後二分的。複雜度 \(O(nlogn\times 15)\)。

T2

場上隨意口胡了個貪心，甚至沒把自己 hack 掉（

一個覺得很奇妙的 trick，如何快速找到所有子區間和的最大值。遍歷一遍 \(a_i\)，將 \(1-i\) 這個區間都加上 \(a_i\)，則線段樹中維護了以 \(1-i\) 為左端點， \(i\)

回到這道題，用類似的思路可以逐步累加 \(k\) 個 \(x\)，最後取最大值即可。

T3

線段樹打掛了，只有 \(10 pts\)。

不難轉換為維護若干層，每相鄰兩層有兩條連邊，詢問兩點之間的最短路徑，帶修改，邊權均為 1。線段樹維護 \(l-r\) 層的兩個向外有連邊的位置到對方的最短路徑長度。\(push_up\) 的話跑一邊 \(Floyd\)

關於我怎麼掛的： 何意味

struct node{
	int dis[3][3];
	node(){dis[1][1]=dis[1][2]=dis[2][1]=dis[2][2]=INT_MAX;}
};
node A,B;A.dis[1][1]=-1,B.dis[1][1]=-1;
		if(ll<=mid)A=query(l,mid,ls,ll,rr);
		if(rr>mid)B=query(mid+1,r,rs,ll,rr);
		if(A.dis[1][1]==-1)return B;
		if(B.dis[1][1]==-1)return A;
		return Get_Min(query(l,mid,ls,ll,rr),query(mid+1,r,rs,ll,rr));

T4