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
不太可做，原题： P5609 [Ynoi2013] 对数据结构的爱