CTime_Pup_314

不能再颓废了

0%

42609102 NOIP模拟题

发表于 更新于 分类于 阅读次数： Valine：

施工

已知 \(F(t)\ =\ \sum_{i=1}^nt_i^2+\sum_{i=2}^n|h_i+t_i-t_{i-1}-h_{i-1}|\) ，求 \(F_{min}\)

设 \(f_{i,j}\) 表示 \(t_i\ =\ j\) 时 \(F_i(t)\) 的最小值则有如下转移

\[ f_{i,j}\ = \begin{cases} f_{i-1,k}+j^2+|k+h_{i-1}-h_i-j| ,\ j>1\\\\ j^2,\ i\ =\ 1 \end{cases} \] 时间复杂度 \(O(nh_{max}^2)\)，空间复杂度 \(O(nh_{max})\)，期望得分 \(11\)

考虑优化，很明显最关键的是优化掉第二维，结合贪心我们发现最终一定有一定的区间的 \(t+h\) 相同，不依次来转移

\[ f_i\ = \begin{cases} f_j+\sum_{k=j+1}^{i-1}(h-h_k)^2+c(h_i+h_j-2h),\ j<i-1,max_{j+1\le k\le i-1}\lbrace h_k\rbrace \le \min\lbrace h_i,h_j\rbrace \\\\ f_j+|h_i-h_j|,\ j\ =\ i-1 \end{cases} \]

观察上述式子，其中 \(h\) 可由二次函数对称轴确定，具体来说

\[ \begin{aligned} g(h)\ &=\ \sum_{k=j+1}^{i-1}(h-h_i)^2+c(h_i+h_j-2h)\\\\ &=\ \sum_{k=j+1}^{i-1}(h^2+h_i^2-2hh_i)-c(h_i+h_j)-2ch\\\\ &=\ (i-j-1)h^2-2(\sum_{k=j+1}^{i-1}h_k+c)h+\sum_{k=j+1}^{i-1}h_k^2-c(h_i+h_j) \end{aligned} \]

那么当\(h\approx \frac{\sum_{k=j+1}^{i-1}h_k+c}{i-j-1}\) 时，\(g\) 值最小

现在空间复杂度 \(O(n)\) 考虑优化时间

注意到第一个转移的条件 \(j<i-1,max_{j+1\le k\le i-1}\lbrace h_k\rbrace\)

这不就是个裸的单调栈吗

用单调栈维护即可 \(O(n)\)

还有一件事

这样表示状态对于 \(i=1\) 或 \(i=n\) 比较麻烦，所以我们不妨增加两个虚拟节点，之后特判即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e6+5;
const int64 INF = 0x3f3f3f3f3f3f3f3fLL;
int n, m, c, h[N];
int64 ans = INF, f[N], s1[N], s2[N];
int s[N], top;
int64 calc(int i, int j, int hk)
{
    int64 A = i-j-1;
    int64 B = -2*(s1[i-1]-s1[j])-(i!=n+1)*c-(j!=0)*c;
    int64 C = s2[i-1]-s2[j]+1ll*(i!=n+1)*h[i]*c+1ll*(j!=0)*h[j]*c;
    int x = (int)round(-1.0*double(B)/double(A)/2.0);
    x = max(x, hk);
    if(i != n+1) x = min(x, h[i]);
    if(j != 0) x = min(x, h[j]);
    return A*x*x+B*x+C;
}
int main()
{
    freopen("construct.in", "r", stdin);
    freopen("construct.out", "w", stdout);
    n = read(), c = read();
    for(int i = 1; i <= n; ++i) 
        h[i] = read(), m = max(h[i], m),
        s1[i] = s1[i-1]+h[i],
        s2[i] = s2[i-1]+1ll*h[i]*h[i];
    s[++top] = 0; h[0] = h[n+1] = m+1;
    for(int i = 1; i <= n+1; ++i)
    {
        f[i] = f[i-1]+1ll*(i != 1&&i != n+1)*c*abs(h[i]-h[i-1]);
        while(top&&h[s[top]] <= h[i])
        {
            if(top > 1) f[i] = min(f[i], f[s[top-1]]+calc(i, s[top-1], h[s[top]]));
            --top;
        }
        s[++top] = i;
    }
    printf("%lld\n", f[n+1]);
    return 0;
}
``` 

## 蔬菜
> 求矩形区域内颜色的出现次数的平方和

玄学题目，正解是按照出现次数分组，然而莫队可以水过去，但考场上看到转移是 $O(n)$ 就果断放弃了，但确实能过 ㄟ( ▔, ▔ )ㄏ

莫队复杂度 $O(qT+\frac{n^2}{T}+\frac{n^3}{T^2}+\frac{n^4}{T^3})$ 差不多在 $T = \frac{n}{q^{\frac{1}{4}}}$ 时最优

最后，记得跳指针时先扩张再减小

```cpp
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int M = 2e2+5, N = 1e6+5;
int n, m, t;
int _[N], tot;
int c[M][M];
int bel[N], T;
struct Query
{
    int px, py, qx, qy, p;
    Query(int px = 0, int py = 0, int qx = 0, int qy = 0, int p = 0):px(px), py(py), qx(qx), qy(qy), p(p) {}
    bool operator < (const Query &_) const
    {   
        if(bel[px] != bel[_.px]) return px < _.px;
        if(py != _.py) return py < _.qy;
        if(qx != _.qx) return qx < _.qx;
        return qy < _.qy;
    }
}q[N];
int ans[N];
int px = 1, py = 1, qx = 1, qy = 1, cnt[N], ret = 1;
void cUpdate(int x, int d)
{
    for(int y = py; y <= qy; ++y)
        if(c[x][y])
            ret -= cnt[c[x][y]]*cnt[c[x][y]],
            cnt[c[x][y]] += d,
            ret += cnt[c[x][y]]*cnt[c[x][y]];
}
void rUpdate(int y, int d)
{
    for(int x = px; x <= qx; ++x)
        if(c[x][y])
            ret -= cnt[c[x][y]]*cnt[c[x][y]],
            cnt[c[x][y]] += d,
            ret += cnt[c[x][y]]*cnt[c[x][y]];
}
int main()
{
    n = read(), m = read(), t = read();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            c[i][j] = read(), _[++tot] = c[i][j];
    sort(_+1, _+tot+1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) 
            c[i][j] = lower_bound(_+1, _+tot+1, c[i][j])-_;
    T = int(1.0*n/pow(t, 0.25))+1;
    for(int i = 1; i <= n; ++i) bel[i] = i/T+1;
    for(int i = 1; i <= t; ++i)
    {
        int px = read(), py = read(), qx = read(), qy = read();
        q[i] = Query(px, py, qx, qy, i);
    }
    sort(q+1, q+1+t); ++cnt[c[1][1]];
    for(int i = 1; i <= t; ++i)
    {         
        while(px > q[i].px) --px, cUpdate(px, 1);
        while(qx < q[i].qx) ++qx, cUpdate(qx, 1);        
        while(px < q[i].px) cUpdate(px, -1), ++px;
        while(qx > q[i].qx) cUpdate(qx, -1), --qx;

        while(py > q[i].py) --py, rUpdate(py, 1);   
        while(qy < q[i].qy) ++qy, rUpdate(qy, 1);               
        while(py < q[i].py) rUpdate(py, -1), ++py;
        while(qy > q[i].qy) rUpdate(qy, -1), --qy;
        ans[q[i].p] = ret;       
    }
    for(int i = 1; i <= t; ++i) printf("%d\n", ans[i]);
    return 0;
}