MX Round 11 解题报告
T1
水题,直接枚举计算即可。
T2
场切了,很爽!!!
因为操作是可以被覆盖的,所以考虑倒序考虑操作:一个位置一旦有了数,就再也不会变了。
然后我们考虑:有数的位置一定是一段连续的区间。这是显然的,因为每一次操作的位置于上一次相邻。
因为只有扩展了区间的操作才会形成新的不同序列,所有我们只考虑扩展了区间的操作。
但是扩展区间的操作放的是哪一个数这需要枚举,这很低效。但其实我们并不关心这个数是什么,我们枚举它只是因为需要判断能否进行下一次扩展。
明确了需求,我们就可以简化操作,只记录扩展到当前区间时必须使用的数字个数:其他非必须的操作可以通过组合数学处理。
但是还是要枚举区间,这很低效。但其实我们不关心这是区间到底在那里,只关心它的长度用于处理从一端到另一端的转移,于是我们只记录区间长度即可。位置可以通过乘上常数处理。
Take away:计数题先打暴力,再对时间开销大的部分进行优化:明确我们的需求,再简化信息。