前言
已经高三了，但是还是想玩一下，抽空写点题目，顺便记录一下。
【前情提要：本文的撰写具有滞后性，因此流失了大量细节。】
$2023.9.16$
初赛，完善程序做得稀烂，好在 $60+$ 还是过线了。真不敢相信今年浙江线会这么低，只有 $50.5 \rm{pts}$。
$2023.9.29$
呃，高三牲的国庆只有 $3$ 天。问老师要了题目，打长乐的模拟赛。
$\texttt{T1}$ 一看 $10^9$ 的数据范围加 $10^6$ 的询问就猜测是推出式子加上矩阵快速幂优化。手玩小数据推了半天，还很不要脸的用了一下 $\texttt{OEIS}$，发现 $f_n = f_{n - 1} + f_{n - 3} + 1$，所以就有了一个 $4 \times 4$ 的矩阵：
算了一下时间复杂度是 $O(T \times 4^3 \times \log n)$，好像数据有点大，可能会被卡常，但是没管了先做后面的。
$\texttt{T2}$ 似乎是个简单题，就是求 $A$ 中有多少段和 $B$ 的长度相同且含 $1$ 的个数相同。由于题目限制了询问串的总长，所以充分利用好根号这一分界线，小于的用记忆化的方式去算，大的直接暴力，时间复杂度 $O(n \sqrt{L})$。
$\texttt{T3}$ 染色，大概是要 $\texttt{dp}$，但是似乎不会。写了一个暴力外加颜色均相同的这一档的递推。
$\texttt{T4}$ 将 $n$ 个数均分到 $k$ 个集合中，保证每个集合中元素互异。设第 $i$ 个集合中的极差为 $s_i$，求 $\min (\sum_{i = 1}^{k} s_i)$。这个暴力看上去也很难打，所以陷入沉思。就在我一直盯着 $n \le 70$ 的数据范围上时，突然想到了一种乱搞做法：就是每次打乱这 $n$ 个数，然后按顺序塞入 $k$ 个集合中，若所有集合合法，那么更新答案。不断循环最后加上一个卡时就行。试了一下能过样例，真棒！
预计得分：$80 + 100 + 30 + ???$；
实际得分：$60 + 100 + 20 + 60 = 240 \texttt{pts}$。
震惊，乱搞做法竟然获得了 $60$ 的高分，这是好的。但是，$\texttt{T1}$ 被多卡了 $20$，以及 $\texttt{T3}$ 写了好长的递推的 $10 \texttt{pts}$ 好像错了没拿到分数。看了一下排名 $\texttt{rk 4}$ 还不错。
看了题解，第一题是对 $4^3$ 的矩阵转移的优化，倍增预处理然后在询问里用 $1 \times 4$ 和 $4 \times 4$ 的矩阵更新。后面两题嘛，看了题解还是实现不出来 qwq。
$2023.9.30$
$\texttt{T1}$ 简单的模拟，本来想着线段树优化求和，但马上发现差分就行了，半小时内就码完了这题。好像还抢到了一血来着。
$\texttt{T2}$ 竟然做过，是 The Shortest Statement，最短路加最小生成树的好题！但是数据范围有些差异，赛时过于高兴的复制了当时的代码，没仔细看，所以最后因为数组越界 $100 \to 40$。
$\texttt{T3}$ 又是一道考察冒泡排序的深度理解的题目，很容易想到按照奇偶位处理，但是发现复杂度怎么搞都是 $O(nm \log n)$，最后交了暴力上去。赛后订正发现题解的方法很妙，用桶记录数字，然后奇数 $+1$，偶数 $-1$，这样就可转换为数据结构维护极值。
$\texttt{T4}$ 动归，转移方程很好列：
$dp_i = \max \{dp_{j|a_i \ge a_j,0 \le j \le i - 1} - \dfrac{(i - j)(i - j - 1)}{2}\} + a_i$，答案的更新是 $ans = \max \left (ans,dp_i - \dfrac{(n - i + 1)(n - i)}{2}\right)$。然后不太会斜率优化以及不太会 $a_i \ge a_j$ 的处理，所以就实现了一个 $O(n^2)$ 的朴素 $\texttt{dp}$。由于我并没有处理负数的情况，但是好像部分分的数据有误，所以我爆灵了。
最后得分：$100 + 40 + 30 + 0 = 170$，排名 $\texttt{rk 15}$。本来应该是：$100 + 100 + 30 + 20 = 250$ 的呜呜呜……
$2023.10.01$
$\texttt{T1}$ 稍作分析就发现这个概率并没什么实际的用处，能到达与根距离为 $k$ 的结点的期望为 $2^{-k}$。直接遍历所有的根求解为 $O(n^2)$，容易想到换根 $\texttt{dp}$，$f_u = 2^{sz_u - 1} + \sum_{v \mid son_u} 2^{sz_u - sz_v - 1} f_v$，时间复杂度就变为 $O(n)$。自己实现的时候直接处理了 $2^{-k}$ 算期望，和标程的转移方程略有不同。
$\texttt{T2}$ 直接构造若干个完全图，一个完全图的三元环数为 $C_k^3 = \dfrac {k(k - 1)(k - 2)}{6}$。因此从 $500$ 开始向 $1$ 开始遍历即可。简单题，并拿到了一血。
$\texttt{T3}$ 赛时在贪心还是动规之间徘徊。还是分析不到位，最后打了个暴力交上去，但是 $\texttt{WA}$ 了。
$\texttt{T4}$ 不知怎的，写了一个模拟，也 $\texttt{WA}$ 了。
最后得分：$100 + 100 + 0 + 0 = 200$，排名 $\texttt{rk 10}$。
$2023.10.15$
打洛谷上的模拟赛，打得有点废，$100 + 8 + 25 + 0 = 133$。
$\texttt{T1}$ 想的 $\texttt{dp}$ 一直假，直到机房大佬的点拨以后才勉强写出来。反正花费了很多很多时间。赛后看题解，发现 $\texttt{ST}$ 表页行，反正赛时啥也不行。
$\texttt{T2}$ 暴力，然后润。赛后补题，其实也蛮好想的，就是基于二进制位的树上 $\texttt{dp}$，设 $g[u][i][0/1]$ 表示以 $u $为根的子树内，所有断边方案中价值在二进制下第 $i$ 位为 $0/1$ 的不与 $u$ 相连的联通块的价值乘积的和.
$\texttt{T3}$ 暴力大分讨，然后润。正解是区间 $\texttt{dp}$，时间复杂度 $O(Tn^3)$，看题解吧，思路就不写了。
$\texttt{T4}$ 没看，直接润。
$2023.10.21$
比赛日！$\texttt{rp++}$！
$\texttt{T1}$ 水题，直接暴力搜索，然后过大样例。
$\texttt{T2}$ 字符串消消乐，想了半天只会 $O(n^3)$ 的区间 $\texttt{dp}$，之后一直没有进展。害，其实出考场才发现 $O(n^2)$ 的做法也蛮好想的。当然，正解是线性做法，发现从 $1$ 到 $n$ 维护栈序列时，若对于某个时刻 $l$ 和某个时刻 $r$，两种时刻的栈序列完全相同，那么说明子串 $(l+1,r)$ 一定是可消除。
$\texttt{T3}$ 大模拟，写了半天放弃了最后一题，最后因为看错一丢丢题干，喜提 $0 \texttt{ pts}$。不说了，赛后写了 $3.02 \texttt{KB}$ 苟过了。放个代码纪念一下：
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
| #include <bits/stdc++.h>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
int n;ll p;
struct ele
{
ll len,ali_len;
string ty,name;
} ;
struct stct
{
ll len,ali_len;
string name;
vector <ele> v;
stct () {len = ali_len = 0;name = "";v.clear ();}
} tot;
map <string,int> bs;
map <string,stct> ext;
void init_basic ();
void calc (ll &p,ll x);
void op_one ();
void op_two ();
void op_three ();
void op_four ();
int main ()
{
cin>>n;init_basic ();
for (int i = 1;i <= n;++i)
{
int ty;cin>>ty;
if (ty == 1) op_one ();
if (ty == 2) op_two ();
if (ty == 3) op_three ();
if (ty == 4) op_four ();
}
return 0;
}
void init_basic () {bs["byte"] = 1;bs["short"] = 2;bs["int"] = 4;bs["long"] = 8;}
void calc (ll &poi,ll ali) {poi = ceil ((long double) poi / ali) * ali;}
void op_one ()
{
int k;stct tmp;cin>>tmp.name>>k;
for (int i = 1;i <= k;++i)
{
ele nw;cin>>nw.ty>>nw.name;
if (bs[nw.ty]) nw.len = nw.ali_len = bs[nw.ty];
else nw.len = ext[nw.ty].len,nw.ali_len = ext[nw.ty].ali_len;
tmp.ali_len = max (tmp.ali_len,nw.ali_len);tmp.v.push_back (nw);
calc (tmp.len,nw.ali_len);tmp.len += nw.len;
}
calc (tmp.len,tmp.ali_len);
ext[tmp.name] = tmp;
printf ("%lld %lld\n",tmp.len,tmp.ali_len);
}
void op_two ()
{
ele nw;ll ans = 0;cin>>nw.ty>>nw.name;
for (ele x : tot.v) calc (ans,x.ali_len),ans += x.len;
calc (ans,bs[nw.ty] ? bs[nw.ty] : ext[nw.ty].ali_len);
tot.v.push_back ({bs[nw.ty] ? bs[nw.ty] : ext[nw.ty].len,bs[nw.ty] ? bs[nw.ty] : ext[nw.ty].ali_len,nw.ty,nw.name});
printf ("%lld\n",ans);
}
void op_three ()
{
string s;stct tmp = tot;ll ans = 0;cin>>s;
for (int i = 0,j;i < s.size ();i = j + 1)
{
j = i;
while (j < s.size () && s[j] != '.') ++j;
string nw = s.substr (i,j - i);
for (ele x : tmp.v)
{
calc (ans,x.ali_len);
if (x.name == nw) {tmp = ext[x.ty];break;}
ans += x.len;
}
}
printf ("%lld\n",ans);
}
void op_four ()
{
stct tmp = tot;ll sum = 0,k,ok;cin>>k;
while (1)
{
ok = 0;
for (ele x : tmp.v)
{
calc (sum,x.ali_len);
if (sum <= k && k < sum + x.len)
{
if (bs[x.ty]) {ok = 1;break;}
tmp = ext[x.ty];
ok = 2;break;
}
sum += x.len;
if (sum > k) {ok = 0;break;}
}
if (!ok || ok == 1) break;
}
if (!ok) {puts ("ERR");return ;}
sum = 0;tmp = tot;
while (1)
{
for (ele x : tmp.v)
{
calc (sum,x.ali_len);
if (sum <= k && k < sum + x.len)
{
cout<<x.name;
if (bs[x.ty]) {puts ("");return ;}
tmp = ext[x.ty];cout<<".";
break;
}
sum += x.len;
}
}
}
|
$\texttt{T4}$ 其实但凡做了这题目多少也可得点分。（后悔.jpg)。树上的二分套二分，显然二分天数以及至少要中的时间，唯一的坑点就是可能爆 $\texttt{long long}$。
得分：$100 + 35 + 0 + 0 = 135$。为什么要写大模拟！！！为什么不做 $\texttt{T4}$！！！【所以依旧获得 $2=$】
$2023.11.8$
市一模考完，润到机房！（奈斯的安排，第三天上午就考完！【笑死我，有的人，在别人全考完的时候还没开始考……】）
【$\texttt{PS}$:喜提年排 $28$，$\texttt{OI}$ 助我一臂之力。】
下午做洛谷模拟赛。
$\texttt{T1}$ 数论题，翻译一下就是给长度为 $n$ 的序列 $a$ 和一个数 $w$，每次操作你可以选择一个 $a_i$ 使得 $a_i = a_i + 1$，至多操作 $w$ 次，最大化 $\Pi_{i = 1}^{w} a_i$。做法就是贪心选择最小值，$O(n^2)$ 即可。
$\texttt{T2}$ 找规律（赛时没找到，寄），在直到规律后，代码短的离谱。
$\texttt{T3，T4}$ 好像没做。
$2023.11.12-14$
翘了运动会，打三套模拟赛，做 $\texttt{NOIP}$ 最后的冲刺。反正打得不错，具体就不写了。
$2023.11.18$
比赛日。
$\texttt{8:30}$ 开始比赛，用福昕阅读器解码 $\texttt{pdf}$ 多次失败，后来说要从浏览器这里打开才行……
$\texttt{8:35}$ 写完缺省，开始读题。似乎是模拟 $+$ 图论 $+$ 盲猜数据结构 $+$ 盲猜数据结构/动态规划，猜的还挺准的。
$\texttt{8:45}$ 开始写 $\texttt{T1}$，真的是三年来最简单的签到题，记录一下最大最小值，然后直接 $O(n^2)$ 判断即可。
$\texttt{9:00}$ 写完，开始看 $\texttt{T2}$，发现有 $\texttt{40 pts}$ 是送的，直接敲。然后开始想正解，其间一直没用想通一个能成环的样例，所以一直手模构造，好像花了很久，然后尝试写了代码，但是一直出不来。代码越改越乱，大样例全过不了，稍微有点慌。这时候大概已经 $\texttt{10:20}$ 的样子了，吸取了之前的教训，出去上了个厕所，直接开写 $\texttt{T3}$。
想到一个 $\texttt{35 pts}$ 的朴素 $\texttt{dp}$，设 $dp_{i,j}$ 表示 $X$ 匹配到第 $i$ 位，$Y$ 匹配到第 $j$ 位是否可行，所以就有转移 $dp_{i,j} = dp_{i - 1,j} | dp_{i,j - 1} | dp_{i - 1,j - 1}$。整一个想完写完大概 $\texttt{11:40}$，拍了大样例，能过，一阵狂喜，然后开最后一题。
按照赛前“没思路就写 $\texttt{dp}$”的策略，很快想出一个 $\texttt{36 pts}$ 的 $\texttt{dp}$，$dp_{i,j}$ 表示到第 $i$ 天时，$(j,i)$ 区间均打卡而第 $j - 1$ 天不打卡的最大能量。差不多 $\texttt{12:30}$，测大样例，突然发现有问题。一顿检查后发现是初始化的锅，修了以后所以大样例都能过。写完以后怕被卡常，在判断 $(j,i)$ 区间的代码中利用 vector 加了一个二分，改完以后继续按原程序对拍，还真个我拍出错来了，发现还是初始化的问题，赶紧改！
$\texttt{12:45}$，不写了，开始检查文件名，路径，freopen 等等。
$\texttt{13:00}$，比赛结束，感觉还行，估分 $100 + 40 + 25 + 36 = 211$。
后记
这场比赛还是有一点点不满意。$\texttt{T2}$ 应该是要写出来的，考场上想得太乱把自己绕进去了。$\texttt{T4}$ 还有离散化的那一部分分没看见，这是可以拿到的；好像还有 $\texttt{10 pts}$ 的特殊部分也没看见……
感谢 $\texttt{CCF}$ 没有卡 $\texttt{T3}$ 的大常数做法（虽然能够通过读入时的特判解决这个问题）。以及 $\texttt{T2}$ 暴力不小心把 $n$ 打成了 $m$，但由于暴力肯定是卡满的，所以出的数据全部都 $n = m$（属于是逃过一劫了）。
出分啦，和自己估的一毛一样。感觉有点悬，祈祷初中生能去除的多一点。
出分数线啦！$206$！终于终于终于一等奖嘞！！！上体育课前同学来告诉我的，让我给激动得不得了。
初高中的 $\texttt{OI}$ 总算有了闭环，或许整个过程看上去很艰难，经历了停文化课，比赛失利等困难，但是我真的乐在其中。不论是洛谷的月赛，还是 $\texttt{CF}$ 的深夜鏖战，总之努力没有白费！！！
高中的竞赛算是结束了，但是洛谷的账号我是不会废滴，希望我在大学是能参加 $\texttt{ACM}$，然后继续开始写我的题解，赚我的咕值，提升我的排名！！！
最后最后，纪念一下我比赛的四道题的赛时代码。
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
|
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 3e3 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int n,m,mx[MAX],mn[MAX];char s[MAX][MAX];
int main ()
{
n = read ();m = read ();
for (int i = 1;i <= n;++i) mn[i] = INF;
for (int i = 1;i <= n;++i) scanf ("%s",s[i] + 1);
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j)
mx[i] = max (mx[i],s[i][j] - 'a'),mn[i] = min (mn[i],s[i][j] - 'a');
for (int i = 1;i <= n;++i)
{
int ok = 1;
for (int j = 1;j <= n;++j)
{
if (i == j) continue;
if (mn[i] >= mx[j]) {ok = 0;break;}
}
if (ok) printf ("1");
else printf ("0");
}
puts ("");
return 0;
}
inline int read ()
{
int s = 0,f = 1;
char ch = getchar ();
while (('0' > ch || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while ('0' <= ch && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 1e5 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int ty,t,n,m,cnt,ans,vis[MAX],a[MAX],b[MAX],st[MAX];
char str[30][2];int x[30],y[30];
vector <pair <int,int> > ve[MAX];
void dfs (int u,int ti);
void solve (int x);
bool check ();
int main ()
{
ty = read ();t = read ();
if (ty <= 2)
{
while (t--)
{
n = read ();m = read ();ans = INF;
for (int i = 1;i <= m;++i)
{
scanf ("%s",str[i]);x[i] = read ();
if (str[i][0] == '+' || str[i][0] == '-') y[i] = read ();
}
solve (1);
printf ("%d\n",ans);
}
return 0;
}
while (t--)
{
n = read ();m = read ();cnt = 0;
for (int i = 1;i <= n;++i) a[i] = 0,st[i] = 0,ve[i].clear ();
for (int i = 1;i <= m;++i)
{
char s[2];scanf ("%s",s);
if (s[0] == '+')
{
int x = read (),y = read ();
ve[y].push_back ({x,i});
st[x] = i;
for (int j = 1;j <= n;++j) vis[j] = 0;
dfs (y,i);
}
else if (s[0] == '-')
{
int x = read (),y = read ();
}
else
{
int x = read ();
if (s[0] == 'T') a[x] = 1;
if (s[0] == 'F') a[x] = 2;
if (s[0] == 'U') a[x] = 3;
if (ty >= 5)
{
st[x] = i;
for (int j = 1;j <= n;++j) vis[j] = 0;
dfs (x,i);
}
}
}
for (int i = 1;i <= n;++i)
if (a[i] == 3) ++cnt;
printf ("%d\n",cnt);
}
return 0;
}
inline int read ()
{
int s = 0,f = 1;
char ch = getchar ();
while (('0' > ch || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while ('0' <= ch && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
void dfs (int u,int ti)
{
vis[u] = 1;
for (int i = 0;i < ve[u].size ();++i)
{
int v = ve[u][i].first;
if (vis[v] || st[v] != ve[u][i].second) continue;
a[v] = a[u];
dfs (v,ti);
}
}
void solve (int x)
{
if (x == n + 1)
{
if (check ())
{
int sum = 0;
for (int i = 1;i <= n;++i) sum += (a[i] == 3);
ans = min (ans,sum);
}
return ;
}
for (int i = 1;i <= 3;++i) a[x] = i,solve (x + 1);
}
bool check ()
{
for (int i = 1;i <= n;++i) b[i] = a[i];
for (int i = 1;i <= m;++i)
{
if (str[i][0] == '+') b[x[i]] = b[y[i]];
else if (str[i][0] == '-')
{
if (b[y[i]] == 3) b[x[i]] = b[y[i]];
else b[x[i]] = 3 - b[y[i]];
}
else
{
if (str[i][0] == 'F') b[x[i]] = 1;
if (str[i][0] == 'T') b[x[i]] = 2;
if (str[i][0] == 'U') b[x[i]] = 3;
}
}
for (int i = 1;i <= n;++i)
if (a[i] != b[i]) return 0;
return 1;
}
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 2e3 + 5;
const int MOD = 1e9 + 7;
inline int read ();
int ty,n,m,q,ans,a[MAX],b[MAX],c[MAX],d[MAX],dp[MAX][MAX];
bool check1 ();
bool check2 ();
int main ()
{
ty = read ();n = read ();m = read ();q = read ();
for (int i = 1;i <= n;++i) a[i] = read ();
for (int i = 1;i <= m;++i) b[i] = read ();
if (a[1] > b[1]) ans = check1 ();
else ans = check2 ();
printf ("%d",ans);
while (q--)
{
int dx = read (),dy = read ();
for (int i = 1;i <= n;++i) c[i] = a[i];
for (int i = 1;i <= m;++i) d[i] = b[i];
while (dx--)
{
int x = read (),y = read ();
a[x] = y;
}
while (dy--)
{
int x = read (),y = read ();
b[x] = y;
}
if (a[1] > b[1]) ans = check1 ();
else ans = check2 ();
printf ("%d",ans);
for (int i = 1;i <= n;++i) a[i] = c[i];
for (int i = 1;i <= m;++i) b[i] = d[i];
}
puts ("");
return 0;
}
inline int read ()
{
int s = 0,f = 1;
char ch = getchar ();
while (('0' > ch || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while ('0' <= ch && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
bool check1 ()
{
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j) dp[i][j] = 0;
dp[1][1] = (a[1] > b[1]);
for (int i = 1;i <= n;++i)
{
for (int j = 1;j <= m;++j)
{
if (i == 1 && j == 1) continue;
if (a[i] <= b[j]) continue;
dp[i][j] |= dp[i][j - 1];
dp[i][j] |= dp[i - 1][j - 1];
dp[i][j] |= dp[i - 1][j];
}
}
return dp[n][m];
}
bool check2 ()
{
for (int i = 1;i <= n;++i)
for (int j = 1;j <= m;++j) dp[i][j] = 0;
dp[1][1] = (a[1] < b[1]);
for (int i = 1;i <= n;++i)
{
for (int j = 1;j <= m;++j)
{
if (i == 1 && j == 1) continue;
if (a[i] >= b[j]) continue;
dp[i][j] |= dp[i][j - 1];
dp[i][j] |= dp[i - 1][j - 1];
dp[i][j] |= dp[i - 1][j];
}
}
return dp[n][m];
}
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MAX = 1e3 + 5;
const int MOD = 1e9 + 7;
inline int read ();
struct node
{
int ti;ll v;
} ;
int ty,t,n,m,k,d;
ll ans,dp[MAX][MAX];
vector <node> p[MAX];
vector <ll> sum[MAX];
bool cmp (node x,node y);
ll check (int x,int y);
int main ()
{
ty = read ();t = read ();
while (t--)
{
n = read ();m = read ();k = read ();d = read ();
for (int i = 1;i <= n;++i)
for (int j = 0;j <= min (n,k);++j) dp[i][j] = -INF;
ans = -INF;
for (int i = 1;i <= m;++i)
{
int x = read (),y = read (),v = read ();
p[x].push_back ({x - y + 1,v});
}
for (int i = 1;i <= n;++i) sort (p[i].begin (),p[i].end (),cmp);
for (int i = 1;i <= n;++i)
{
if (!p[i].size ()) continue;
sum[i].push_back (p[i][0].v);
for (int j = 1;j < p[i].size ();++j) sum[i].push_back (sum[i][j - 1] + p[i][j].v);
}
dp[0][0] = 0;
for (int i = 1;i <= n;++i)
{
for (int j = 0;j <= min (i,k);++j)
{
int l = max (i - j + 1,1),r = i;
dp[i][0] = max (dp[i][0],dp[i - 1][j]);
if (j) dp[i][j] = max (dp[i][j],dp[i - 1][j - 1] + check (l,r) - d);
}
}
for (int i = 0;i <= min (n,k);++i) ans = max (ans,dp[n][i]);
printf ("%lld\n",ans);
for (int i = 1;i <= n;++i) p[i].clear (),sum[i].clear ();
for (int i = 1;i <= n;++i)
for (int j = 0;j <= min (n,k);++j) dp[i][j] = -INF;
}
return 0;
}
inline int read ()
{
int s = 0,f = 1;
char ch = getchar ();
while (('0' > ch || ch > '9') && ch != EOF)
{
if (ch == '-') f = -1;
ch = getchar ();
}
while ('0' <= ch && ch <= '9')
{
s = s * 10 + ch - '0';
ch = getchar ();
}
return s * f;
}
bool cmp (node x,node y)
{
return x.ti < y.ti;
}
ll check (int x,int y)
{
int l = 0,r = p[y].size () - 1,ans = -1;
while (l <= r)
{
int mid = (l + r) >> 1;
if (x <= p[y][mid].ti) ans = mid,r = mid - 1;
else l = mid + 1;
}
if (ans == -1) return 0;
if (ans == 0) return sum[y][sum[y].size () - 1];
else return sum[y][sum[y].size () - 1] - sum[y][ans - 1];
}
|
