大概会记录了九月前半段模拟赛。
Table of Contents
Sept.3 开学第一考
135/300, Rank 4
T1(90/100)
Description & Solution
大膜您. 然而还是没有处理最后结果跪成了90
T2(20/100)
Description
对于一个数列, 将其划分为若干个连续子序列, 每个子序列必须严格单调增或减, 且必须交替出现. 第一个区间必须单调增.
最大化$\begin{align}\sum_{i=1}^{len}{a_i} \times \frac{1}{s}\end{align}$.
Solution
考场大力猜结论. 可以证明, 要么就是一个LIS, 对于一个LIS + LDS的情况, 无论加入一个大于平均值的单调增区间还是一个小于平均值的区间, 都一定不会使答案更优.
如果大于平均值, 直接把两个升序列拼起来就好了. 如果小于平均值, 就更会拉低整个序列的平均值.
没开long long挂成*.
T3(25/100)
Description
给你一些向量, 作为边权, 定义一个图的最大生成树, 使向量相加结果的模长最大.
Solution
考场上靠近了但还是太naïve了. 不能只枚举象限. 考虑到向量并不多, 不如直接枚举答案的方向, 每个向量在上面做投影就好了. 暑假讲过类似的题, 还是要记牢并用起来.
Sept.5 学长的题
100/300, Rank 4
T1(100/100)
Description
求包含最多好点且不包含坏点的最小面积子矩形.
Solution
$n$ 不大也不小, 上来先离散化. 发现把坏点置为$-\infty$, 就可以做最大子矩形了.
T2(0/100)
Description
给你若干个$R$进制数字的数量, 组成一个最大的$R$进制数, 使得其是$R-1$的倍数.
会查询一位的具体数字.
Solution
手玩10进制就可以发现结果一定是各位总和在10进制下仍然是$R-1$的倍数. 在更小的进制下验证一下就可以做了. 凑出一个倍数的方式就是膜一下$R-1$, 挖掉一个余数就好了. $0$不用挖.
然后在前缀和上二分. 考场不读题没看到保证能挖掉一个挂成0分
T3(0/100)
Description
有标号DAG形态数.
Solution
只有手玩分还玩错了. 二次剩余+FFT, 先留着吧.
Sept.9 Now coder Round1
65/300, Rank 11
T1(50/100)
Description
在序列$A$所有长度$\ge len$的子区间中, 最大的中位数是多少.
Solution
考场想跪了, 二分答案也没多想, 不会验证. 结果胡乱YY了一个直接按照len取结果的结论是错的, 跪成50. 其实二分答案就是验证这个数字是否至少是一个中位数. 将大于mid的数置1, 否则置-1, 取前缀和, 这样如果有大于0的区间和, 就说明能抵消掉了, 同时可以前缀最小值优化一下.
当时确实思路没有很打开, 可以说心情也十分不好, 影响发挥.
T2(15/100)
Solution
这题挂成全场倒一, 不敢写, 暴搜都不敢写. 一定要开阔胆大, 当然心细是必不可少的. 就数位DP, 注意前导0.
T3(0/100)
Description
这题太仙了, 写不了.
Sept.10 - 11 NOIP Round 1
490/700, Rank 3
D1T1(100/100)
Description
奇数长度的回文数字串, 无前导零, 方案数之和.
Solution
推式子, 等差乘等比, 逆元什么的搞一搞, 切了.
D1T2(30/100)
Description
给若干个操作区间, 每次把区间内连续没有被取得一段权值和的平方加到贡献里. 合理排序, 最大化答案. $n \le 5000,\,m \le 100000$.
Solution
一开始以为是运算要log, 结果是排序. $n$ 太小了, 看着就奇怪, 所以可以压缩区间. 把有效的留下来, 做 $n^2$ DP.
D1T3(60/100)
Description
对于一个模式串, 如果和主串某一位置起, 不匹配的位置$\le k$个, 答案就加一. 计算答案.
Solution
$k$ 不大, 但考场上也没想到怎么用. 二分LCP也没想到怎么用! 但是这两个加起来就是正解= =
D1T4(30/100)
Description
给定数列$\{a_i\},\,\{b_i\}$, 计算$\begin{align} c_i = \sum_{j = 1}^{i}{a_{\lfloor\frac{i}{j}\rfloor}b_{i\,mod\,j}} \end{align}$
Solution
猝不及防的加试, 只给了一个小时. 打表太晚了, 以后少玩式子, 上来先打表. 预计的70全写没了.
正解和70分很像了, 都要用除法分块. 但可以处理一些部分分处理不了的前缀和问题. 开一个二维数组, 分别是起点和步长. 由于取模和下取整的性质, 反正跑得过.
D2T1(100/100)
Solution
思路 + 贪心.
D2T2(100/100)
Solution
树剖啦.
D2T3(70/100)
Solution
暴搜剪枝是个绝活. 剪因子个数我是无论如何想不到.