签题补完计划-JZTXT

手贱让 cnblogs 这小崽子给我把发布时间更新了。实际上这篇文章很早就存在，只是一直没有公开而已。

从现在开始，因为现在我手上刚好有一道水题可以用来凑数！！！?

所谓补完计划是往前补的题。限定时间内（Weekly 结算计分时间）做完的题就不算了。那些我就另外开博客（你最好真的会开！）。

~~当然如果题太帅了是可以拿进来的，因为一千这个数字太恐怖了，我也比较有既鸡鸡明。~~ 我想了一下这样还是太不要脸了，所以这条规则作废吧！

签题呢，就是字面意思啦。签到题！绝对不是谐音梗！

为什么别人都是做新题而我是补旧题呢，因为我确实没补的题都有很多，以及能被我留下来的说明都是我自己做着不太爽的，值得纪念。

简单来说就是我太菜了，总之你们不准骂我，现在开始吧。

E. 玉蟾宫 // 1st

http://222.180.160.110:1024/contest/4191/problem/5

是悬线板子捏。从来没有过学单调栈的计划！

有关悬线法的具体我会在这篇博客中进行详细介绍。当然这是一篇从去年咕到现在的博客，我预计在国庆的时候赶出来吧。

注意到悬线法的一些细节，其实就是板子。

namespace XSC062 {
using namespace fastIO;
const int maxn = 1e3 + 5; 
char t;
int n, m, ans;
int s[maxn][maxn];
int l[maxn][maxn], r[maxn][maxn];
int max(int x, int y) {
	return x > y ? x : y;
}
int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%1s", &t);
			if (t == 'F')
				s[i][j] = s[i - 1][j] + 1;
			l[i][j] = j;
			while (l[i][j] > 1 && s[i][j]
						<= s[i][l[i][j] - 1])
				l[i][j] = l[i][l[i][j] - 1];
		}
	}
	for (int i = 1; i <= n; ++i) {
		r[i][m + 1] = m + 1;
		for (int j = m; j; --j) {
			r[i][j] = j;
			while (r[i][j] < m && s[i][j]
						 <= s[i][r[i][j] + 1])
				r[i][j] = r[i][r[i][j] + 1];
			ans = max(ans, s[i][j] *
						(r[i][j] - l[i][j] + 1));
		}
	}
	print(ans * 3, '\n');
	return 0;
}
} // namespace XSC062

小奇的糖果 // 2nd

https://hydro.ac/d/bzoj/p/4548

我们惊讶地发现这题被咕了一年半。

先离散化加按 y 坐标排序降一维。

我们想要最大化被选的点的数量，又不能取完所有颜色，很明显只选一种颜色不取最优（具体可能如果不取一种颜色那会有别的颜色取不到，但这只是我们的思考过程，先不去在意细节）。所以我们枚举这种不取的颜色。我们现在把这条线固定在最底下，那么所有点都能被取到。为了不取到我们现在正在枚举的颜色 \(i\)，

括号序列再战猪猪侠 // 3rd

https://hydro.ac/d/bzoj/p/4350

我们惊讶地发现这题也被咕了一年半。现在绝大部分 GM 的链接都看不到了，更别说 mjl 的了。还好当时的我聪明地留下了一个 Hydro 链接。

题面在 U 盘里的 /p/比赛/多校联赛/联合 NOIP/34th/statement.pdf。视频题解在同目录下。

是一个动态树 DP。应该先去做板子。

D. 异或区间

http://222.180.160.110:1024/contest/4424/problem/4

40pts 题解和上一题在一起的。

JZTXT

签题补完计划

E. 玉蟾宫 // 1st

小奇的糖果 // 2nd

括号序列再战猪猪侠 // 3rd

C. 踩气球 // 4th

D. 办公楼 biu // 5th

F. 生日礼物 // 6th

G. 吃 // 7th

H. 赶作业 ddl // 8th

I. Desert King // 9th

J. 最小圈 // 10th

K. Hard Life 生活的艰辛 / 最大密度子图模板 // 11th

C - V // 12th

D - Sjeckanje // 13th

E - 奇偶覆盖 // 14th

E. Segment Sum // 15th

C. 树图

D. 异或区间