在CSP结束近一年后，终于听人讲了这道题
惭愧啊 惭愧
36pts
一个考场都没想出来的$n^3$暴力DP
设$f_{i,j}$为考虑到$i$这个点，$i$所在块的起点为$j$，最小的时间代价
更新方法就是把$k$从$1$到$j-1$枚举，当满足题目条件($\sum\limits_{l=k}^{j-1}{a_l}\leq\sum\limits_{l=j}^{i}{a_l}$)时，$f_{i,j}=\min\{ {f_{j-1,k}+(\sum\limits_{l=j}^{i}{a_l})^2}\}$
统计答案时，$ans=\min_{i=1}^{n}{ \{f_{n,i}\} }$
记得开long long
Code
1
2
3
4
5
6
7
8
9
10
11
12
| memset(f, 0x3f, sizeof f),
f[0][0] = 0;
for (register int i = 1; i <= n; ++i)
for (register int j = 0; j <= i; ++j) {
if (!j || j == 1)
f[i][j] = sum[i] * sum[i];
for (register int k = 1; k <= j - 1; ++k)
if (sum[j - 1] - sum[k - 1] <= sum[i] - sum[j - 1])
f[i][j] = min(f[i][j], f[j - 1][k] + (sum[i] - sum[j - 1]) * (sum[i] - sum[j - 1]));
}
for (register int i = 1; i <= n; ++i)
ans = min(ans, f[n][i]);
|
64pts
首先由完全平方公式可以推出，$(\sum\limits_{i=1}^{n}a_i)^2\geq\sum\limits_{i=1}^{n}a_i^2$，当且仅当$a_i=0$时等号成立
所以如果想让总代价更小，要尽量多分块
用$f_i$表示将$1$到$i$按最优方案划分后的时间代价，$g_i$表示将$1$到$i$按最优方案划分后，最后一段的的开头为$k$，有式子
同时，显然已经划分过的段不会再参与到之后的划分中，所以令$top$表示上一次划分到的块的终点，下次划分时从$top$开始枚举即可
每次$j$从$top + 1$枚举到$i-1$，判断满足$\sum\limits_{j=top+1}^{i-1}{a_j}\geq g_j$，更新$f_i$，$g_i$和$top$即可
答案$ans=f_n$
Code
1
2
3
4
5
6
7
8
9
| for (register int i = 1; i <= n; ++i) {
f[i] = 99999999999999999;
for (register int j = top; j < i; ++j) {
if (sum[i] - sum[j] >= g[j])
f[i] = min(f[i], f[j] + (sum[i] - sum[j]) * (sum[i] - sum[j])),
g[i] = sum[i] - sum[j],
top = j;
}
}
|
有的题解是用$g_i$表示满足条件的最大的$j$，即$g_i=\max\limits_{\sum\limits_{l=g_j}^{j}{a_l}\leq\sum\limits_{l=j+1}^{i}{a_l} }{ \{j\} }$
88pts
对于判断合法的式子$\sum\limits_{l=g_j+1}^{j}{a_l}\leq\sum\limits_{l=j+1}^{i}{a_l}$，将其用前缀和表示出来，即为$sum_{j}-sum_{g_j}\leq sum_i-sum_j$
合并同类项，可得$2\cdot sum_j-sum_{g_j}\leq s_i$
令$d(j)=2sum_j-sum_{g_j}$，$g_i$表示满足条件的最大的$j$，即$g_i=\max\limits_{\sum\limits_{l=g_j}^{j}{a_l}\leq\sum\limits_{l=j+1}^{i}{a_l} }{ \{j\} }$
可以设想一下，如果$\exists x<y,\ d(x)\leq s_i,\ d(y)\leq s_i$，按照分块尽量少的原则，肯定优先选择$y$
所以$g_i$具有单调性
因此我们可以维护一个单调队列，储存有用的决策点，其中$g_i$单调递增
当队首满足条件$d(q_{head})\leq sum_i$时，根据分块尽量少的原则，选择最后的满足条件的$q_{head}$更新$g_i$
当队尾不满足$d(q_{tail})< d(i)$时，删除队尾
最后把当前点加入队列中
统计答案时，根据$g_i$往前跳即可
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
| for (register int i = 1; i <= n; ++i) {
while (l < r && sum[queue[l + 1]] - sum[pre[queue[l + 1]]] + sum[queue[l + 1]] <= sum[i])
++l;
pre[i] = queue[l];
while (l < r && sum[queue[r]] - sum[pre[queue[r]]] + sum[queue[r]] >= sum[i] - sum[pre[i]] + sum[i])
--r;
queue[++r] = i;
}
int now = n;
__int128 ans = 0;
while (now)
ans += (sum[now] - sum[pre[now]]) * (sum[now] - sum[pre[now]]),
now = pre[now];
|
100pts
把$type=1$的点写上即可
记得写高精或者__int128
省空间大法：$sum$前缀和数组重复使用
以及需要$O2$优化
Code
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
146
147
| #pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma G++ optimize(2)
#pragma G++ optimize(3)
#pragma G++ optimize("Ofast")
#pragma G++ optimize("inline")
#pragma G++ optimize("-fgcse")
#pragma G++ optimize("-fgcse-lm")
#pragma G++ optimize("-fipa-sra")
#pragma G++ optimize("-ftree-pre")
#pragma G++ optimize("-ftree-vrp")
#pragma G++ optimize("-fpeephole2")
#pragma G++ optimize("-ffast-math")
#pragma G++ optimize("-fsched-spec")
#pragma G++ optimize("unroll-loops")
#pragma G++ optimize("-falign-jumps")
#pragma G++ optimize("-falign-loops")
#pragma G++ optimize("-falign-labels")
#pragma G++ optimize("-fdevirtualize")
#pragma G++ optimize("-fcaller-saves")
#pragma G++ optimize("-fcrossjumping")
#pragma G++ optimize("-fthread-jumps")
#pragma G++ optimize("-funroll-loops")
#pragma G++ optimize("-fwhole-program")
#pragma G++ optimize("-freorder-blocks")
#pragma G++ optimize("-fschedule-insns")
#pragma G++ optimize("inline-functions")
#pragma G++ optimize("-ftree-tail-merge")
#pragma G++ optimize("-fschedule-insns2")
#pragma G++ optimize("-fstrict-aliasing")
#pragma G++ optimize("-fstrict-overflow")
#pragma G++ optimize("-falign-functions")
#pragma G++ optimize("-fcse-skip-blocks")
#pragma G++ optimize("-fcse-follow-jumps")
#pragma G++ optimize("-fsched-interblock")
#pragma G++ optimize("-fpartial-inlining")
#pragma G++ optimize("no-stack-protector")
#pragma G++ optimize("-freorder-functions")
#pragma G++ optimize("-findirect-inlining")
#pragma G++ optimize("-fhoist-adjacent-loads")
#pragma G++ optimize("-frerun-cse-after-loop")
#pragma G++ optimize("inline-small-functions")
#pragma G++ optimize("-finline-small-functions")
#pragma G++ optimize("-ftree-switch-conversion")
#pragma G++ optimize("-foptimize-sibling-calls")
#pragma G++ optimize("-fexpensive-optimizations")
#pragma G++ optimize("-funsafe-loop-optimizations")
#pragma G++ optimize("inline-functions-called-once")
#pragma G++ optimize("-fdelete-null-pointer-checks")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#ifdef DEBUG
#define __int128 long long
#endif
using std::min;
int n, type, l, r, m, p, queue[40000001], pre[40000001], x, y, z;
__int128 sum[40000001];
template<class I>
inline void write(I a) {
if (a > 9)
write(a / 10);
putchar(a % 10 + '0');
}
int main(void) {
scanf("%d%d", & n, & type);
if (!type)
for (register int i = 1; i <= n; ++i)
scanf("%lld", & sum[i]),
sum[i] += sum[i - 1];
else {
scanf("%d%d%d%lld%lld%d", & x, & y, & z, & sum[1], & sum[2], & m);
for (register int i = 3; i <= n; ++i)
sum[i] = (1LL * x * sum[i - 1] + 1LL * y * sum[i - 2] + z) & ((1 << 30) - 1);
int j = 1;
for (register int i = 1; i <= m; ++i) {
scanf("%d%d%d", & p, & l, & r);
for (; j <= p; ++j)
sum[j] = sum[j] % (r - l + 1ll) + l,
sum[j] += sum[j - 1];
}
}
l = r = 0;
for (register int i = 1; i <= n; ++i) {
while (l < r && sum[queue[l + 1]] - sum[pre[queue[l + 1]]] + sum[queue[l + 1]] <= sum[i])
++l;
pre[i] = queue[l];
while (l < r && sum[queue[r]] - sum[pre[queue[r]]] + sum[queue[r]] >= sum[i] - sum[pre[i]] + sum[i])
--r;
queue[++r] = i;
}
int now = n;
__int128 ans = 0;
while (now)
ans += (sum[now] - sum[pre[now]]) * (sum[now] - sum[pre[now]]),
now = pre[now];
write(ans);
return 0;
}
|
完结！
全体起立！
