20200723比赛总结
starseven
2020-07-27 21:05:01
下面是我对20200723的题解
[T1](https://pdf.maitube.com/pdf/?e=jgGd3lmgLCNcAa)
这一道题确定了我们可以改变矩形的长宽(也就是$K*K$的矩形)
所以我们自然而然地考虑到将我们以$O(n^3)$的时间复杂度来枚举矩形+判断答案贡献转化成用二维的差分+前缀和来将**每个点作为矩形的左上角时可以对答案作出的贡献**统计下来，至此，$O(n^3)-->O(n^2)$
部分细节看代码
代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
int n, k;
char a[N][N];
int up[N], dwn[N], l[N], r[N];
int cnth[N][N], cnts[N][N], ans;
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) up[i] = l[i] = n + 1;
for(int i = 1; i <= n; i++) {
scanf("%s", a[i] + 1);
for(int j = 1; j <= n; j++) {
if(a[i][j] == 'B')
l[i] = min(l[i], j), up[j] = min(up[j], i),
r[i] = max(r[i], j), dwn[j] = max(dwn[j], i);
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cnth[i][j] = cnth[i - 1][j] + (l[i] >= (j - k + 1) && (r[i] <= j) && (l[i] != n + 1));
cnts[i][j] = cnts[i][j - 1] + (up[j] >= (i - k + 1) && (dwn[j] <= i) && (up[j] != n + 1));
}
ans += (l[i] == n + 1) + (up[i] == n + 1);
}
int maxn = 0;
for(int i = k; i <= n; i++) {
for(int j = k; j <= n; j++) {
maxn = max(maxn, cnth[i][j] - cnth[i - k][j] + cnts[i][j] - cnts[i][j - k]);
}
}
printf("%d\n", ans + maxn);
return 0;
}
```
-----------------
[T2](https://pdf.maitube.com/pdf/?e=jgnFkn3S/Xum2a)
我们分析题目可以发现，对于一个连续上升或连续下降的**连续**的子序列，你将这个子序列划分成两个对于答案并没有影响。
但是将一个曲线从最高点或者最低点划开是更优的。
所以我们可以考虑$O(n)$的dp，dp是讨论在每一个极点处是在左边划分还是右边划分。
现在代码如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int read() {
char c=getchar();while(c!='-'&&!isdigit(c)) c=getchar();
int neg=0;if (c=='-') neg=1,c=getchar();
int num=0;while(isdigit(c)) num=num*10+c-'0',c=getchar();
return neg?-num:num;
}
int a[10000001], b[10000001];
long long ans[2];
int main() {
int n = read();
int x, y, z, m;
x = read(), y = read(), z = read(), b[1] = read(), b[2] = read(), m = read();
int p = 0;
for (int i = 3; i <= n; i++) b[i] = (1ll*x*b[i-1]+1ll*y*b[i-2]+z) & ((1<<30)-1);
for (int i = 1; i <= m; i++) {
int np, l, r;
np = read(), l = read(), r = read();
while (p < np) {
++p;
a[p] = b[p] % (r - l + 1) + l;
}
}
ans[0] = -0x3f3f3f3f3f3f3f3f, ans[1] = 0;
int maxn = 0, minn = 0x3f3f3f3f;
for (int i = 1; i <= n; i++)
/*
p记录的是上一个极点位置在哪里，初始化为p=n,因为最开始时并没有极值
ans[0]记录的是上一个极值是划分在左边
ans[1]记录的是上一个极值是划分在右边
*/
if (i > 1 && i < n && ((a[i] > a[i-1] && a[i] >= a[i+1]) || (a[i] < a[i-1] && a[i] <= a[i+1]))) {
long long nxt[2] = {-0x3f3f3f3f3f3f3f3f, -0x3f3f3f3f3f3f3f3f};
nxt[0] = max(nxt[0], ans[0] + max(maxn, a[p]) - min(minn, a[p]));
if (p != i - 1) nxt[0] = max(nxt[0], ans[1] + maxn - minn);//为什么有这个限制条件
//因为如果p==i-1，说明这一个点是一个点自己构成的子序列，不对答案做贡献
else nxt[0] = max(nxt[0], ans[1]);
nxt[1] = max(nxt[1], ans[0] + max(maxn, max(a[p], a[i])) - min(minn, min(a[p], a[i])));
nxt[1] = max(nxt[1], ans[1] + max(maxn, a[i]) - min(minn, a[i]));
ans[0] = nxt[0], ans[1] = nxt[1];
maxn = 0, minn = 0x3f3f3f3f, p = i;
}
else maxn = max(maxn, a[i]), minn = min(minn, a[i]);
cout << max(ans[0] + max(maxn, a[p]) - min(minn, a[p]), ans[1] + maxn - minn) << endl;
}
```
--------------
[T3](https://pdf.maitube.com/pdf/?e=jgBt8EdHY56BIa)
臣妾做不到啊。
啊，这。