这次考试我考得不好，只有 24 24 24名， 160 160 160分，主要问题就是我没有细心检查，很粗心的做完了。
这道题目我们直接用前缀和数组 ( a ) (a) (a)就行了。 直接枚举右端点，然后求出左端点。 l = r − 2 k − 1 l=r-2k-1 l=r−2k−1 我们首先把 k k k赋值为 2 k + 1 2k+1 2k+1。 然后设 q q q表示 max ( max i = 1 n x i , k ) \begin{aligned}\max(\max_{i=1}^{n}{x_i},k)\end{aligned} max(i=1maxnxi,k)。 那么答案就是用 max i = k + 1 q a i − a i − k − 1 \begin{aligned}\max_{i=k+1}^{q}{a_i-a_{i-k-1}}\end{aligned} i=k+1maxqai−ai−k−1。
比赛时 0 0 0分。 改题后满分。
最小生成树模板。 用 P r i m Prim Prim和 K r u s k a l Kruskal Kruskal都可以拿到满分。
比赛时 10 10 10分。 结果发现函数没打在 m a i n main main里。 改题后满分。
这题是菱形的前缀和数组。 可以发现将菱形倒转过来后， ( i , j ) (i,j) (i,j)应该变成 ( i + j − 1 , n − i + j ) (i+j-1,n-i+j) (i+j−1,n−i+j)。 然后就是简单的前缀和了。 直接 O ( n 2 ) O(n^2) O(n2)可以过。 类似差分。
比赛时 50 50 50分。 结果发现是数组开小了。 改题后满分。
转化此题，可以发现最难求的地方是判断这个声音由多少个奶牛组成。 其实是一个背包问题。 设 f i f_i fi表示声音 i i i由多少个奶牛组成。 则 f i = min j = 1 B f i − V j + 1 \begin{aligned}f_i=\min_{j=1}^{B}{f_{i-V_j}+1}\end{aligned} fi=j=1minBfi−Vj+1。 其实是一个完全背包。 最后只要按题意模拟即可。
比赛时满分。
