「杂题集」- 2019年12月9日

最近都在学些科技,做些板子题。现在搜集一些个人觉得比较好的题目作为12月的第一个杂题集吧。

子集

首先,我们先考虑奇数长度段的情况(\(\{a_n\}\)已经排序):确定中位数为\(a_{mid}\),则我们发现答案为 左侧所有减去中位数的和 和 右侧所有减去中位数的和 的和,并除以元素个数。欲使价值最大,那么显然右侧需要靠近右端点进行选择, 而左侧需要靠近中位数进行选择。这个时候我们可以考虑使用二分答案来进行优化:简化对长度的枚举复杂度。

继续阅读「杂题集」- 2019年12月9日

CSP-S2 江西重赛小结

在全国复赛结束之后的两天都在疯狂地补文化课。周二的中午,回班偷看了一下手机就发现一堆未接电话。打开微信的时候就已经看到有人在抱怨江西省重新考试的事情了。

“我日。”

下午就踏上了去青山湖校区的地铁,正好赶上了竞赛课。

周六我穿好之前 ICPC 南昌赛的衣服,中午睡了个不存在的觉就踩油门去脑残大学了。这一次 CCF 为了防止江西省的悲剧再次发生,我可以感觉到 CCF 已经将脑残大学的考务整顿了一遍。

拿到题目,第一题 SB 题,特判将月份调大即可。第二题化简和式,我花了比较长的时间才彻底化简。第三题有点懵,第四题打了个暴力,第五题想了一会\(\Theta(n^2)\)就搞出来了\(\Theta(n)\)。写完这些之后我又回去改第三题,重新写了一遍代码就过了样例。可惜因为数组没有开两倍,我的这一部分努力化为了泡影。

简单总结,我并不认为这次 CSP-S2 的成绩能代表我的真实水平:首先,这套题远低于全国卷的难度;其次,数组开小这种傻逼事情有一定的偶然因素。所以,我认为全国卷的难度更能体现江西的水平。可惜,黄伟死妈了。

各位全国冬令营再见,我们到时候再来一决高下。

CSP-S2 游记 & 总结

Day 0

上午一直在看书复习,然后看教练和学弟在教室里踢瓶子(沙雕玩意)。感觉状态还可以。下午一起讲了注意事项之类的,然后就和 lcx 跑到 NCU 去了。

去的时候碰到了赣州某神仙学校,滚粗感++。又看到了神仙 zzr,滚粗感 + \(\infty\)。晚上随便打了点代码,早早就去睡了,然后梦见自己 Day 1 前两题不会写,滚粗感倍增。

Day 1

吃了早饭就跑到 NCU 去了,考前 bb 了一会就进考场了。前几天我们刚知道今年要用 NOI Linux 被打了个措手不及,NCU 的新特派员真的是傻逼至极。开考前半个小时让我们观看视频学习交题等操作,实在是觉得这个行为太不负责了。垃圾学校。

开考后 10 分钟拿到题目,看了三道题题面及数据范围,发现第一题 sb 题,就愉快的过掉了(事实上,我注意到了位运算在没有开 ull 的情况下直接移动位置的非法情况,所以我多开了一个 const 来定义了一个为 1 的 ull)。

第二题开始觉得不太好做,后面发现只需要分开考虑即可:记录以当前节点结尾的合法字串个数,再做前缀和即可。所以前一个小时把前两题都过掉了。

一开始我觉得第三题应该也是个 sb 题,后面发现巨难,然后又看错了题,导致我一直在调试第一个样例的第二组数据。所以,打了 10 分走人。当时在想如何回去给 lcx 交差,因为打得巨垃圾。最后发现大家都 210,然后就放平心态了。

Day 2

开机子之后拿到题面,第一感觉:emmm 好像都不太可做。在经过半小时的看题之后,我开始写 T3 的 75 分。一个小时后,二叉树还是没调好,所以我就直接去写 T2 的 \(\Theta(n^3)\) 的暴力,不一会就写完了。再去把 T1 的 64 分暴力拿走,设置高维的 DP 再加上简单的累计即可。

我觉得 Day 2 最可惜的是没有写出 T2 的 64 分,即使最后 5 分钟想到了:其实更换枚举顺序,发现单调性之后就有 64 分了,但是真的是菜逼,只能等待命运的降临。

总结

送掉了 T2 之后心情一直不好,然后滚回滨江上了一晚上的自闭文化课。这次比赛充满了遗憾:不仅是我,因为 NCU 的傻逼院长导致了很多选手的不必要丢分。而我,纯粹是因为菜罢了,Day 2 T2 的 64 分在未来会让我心痛很久,本来打算翻掉去年 Zepto 的分,没想到今年题目一难就直接送掉了 400 分。就等最后出结果,决定我是否能继续竞赛了。

Yali CSP-S 2019 模拟赛 – 算式树

思路

这道题思路很妙。

发现算子只有\(+, -, \times\),所以路径上的解可以表示成线性组合:\(ax + b\)。我们记录从根到下、从下到根的线性组合前缀,然后我们考虑来利用前缀进行分割:就是树上差分的那种套路。

我们先考虑父亲边为:

  • 加法/减法:从根向下直接加上即可,从下到根也直接加上就好,但是需要乘上之前的\(a\)。
  • 乘法:从根到下需要把\(a\)乘上,\(b\)加上乘积;但是如果是向上合并的话,就可以直接把\(a\)乘上就行:因为反向而言只对乘项有关。

大概这样合并:

void dfs(int u)
{
	dep[u] = dep[fa[0][u]] + 1;
	for (int i = head[u]; i != -1; i = edges[i].nxt)
		if (edges[i].to != fa[0][u])
		{
			fa[0][edges[i].to] = u, upweight[edges[i].to] = edges[i].weight;
			trs_up[edges[i].to] = trs_up[u], trs_down[edges[i].to] = trs_down[u];
			if (edges[i].weight == 1)
			{
				trs_down[edges[i].to].b = (trs_down[edges[i].to].b + vi[edges[i].to]) % mod;
				trs_up[edges[i].to].b = (1LL * trs_up[u].a * vi[u] + trs_up[u].b) % mod;
			}
			else if (edges[i].weight == 2)
			{
				trs_down[edges[i].to].b = (trs_down[edges[i].to].b - vi[edges[i].to] + mod) % mod;
				trs_up[edges[i].to].b = (1LL * trs_up[edges[i].to].b - 1LL * trs_up[u].a * vi[u] % mod + mod) % mod;
			}
			else
			{
				trs_down[edges[i].to].a = 1LL * trs_down[u].a * vi[edges[i].to] % mod;
				trs_down[edges[i].to].b = 1LL * trs_down[u].b * vi[edges[i].to] % mod;
				trs_up[edges[i].to].a = 1LL * trs_up[edges[i].to].a * vi[u] % mod;
			}
			dfs(edges[i].to);
		}
}

如何分裂边呢?我们只需要抵消掉\(a\)和\(b\)的效果即可,直接用逆元和减法就行了:考虑设置\(ax + b\)为从\(x\)到根的效果,设置\(cx + d\)为\(lca\)到根的效果,那么\(x\)到根的效果为\(ex + f\),可以列式为:

\[ e(cx + d) + f = ax + b \]

解出来就行了,然后再对\(y\)做差不多的处理就可以解决这道题了。(挺麻烦的,细节还挺多,不如打暴力

继续阅读Yali CSP-S 2019 模拟赛 – 算式树

牛客CSP-S提高组赛前集训营 2 – 解题报告

这次比赛必须要仔细反省,不能再出现暑假的精神状态。

A – 服务器需求

假设我们有很多服务器了,我们现在按天考虑,进行服务器的分配:假设有一个服务器编号集合\(\{id_i\}\),考虑一天天分配若干台,这样就可以保证每一台服务器的分配中不会出现同样的日期。

这样就可以分配完了,直接就有\(\sum a_i \leq |id_i| m\)。然后就是傻逼代码了。

继续阅读牛客CSP-S提高组赛前集训营 2 – 解题报告