DAY 5
T2挂了 \(50pts\) 炸纲了qwq
一个网上的题解
点击查看题解
T1 铺地板(board)
\(2\times2=1\times2+1\times 2\)
尽量将 \(2\times2\) 放入，再将 \(1\times2\) 放入，最后将 \(1\times 1\) 放入
所以奇偶分类
对于 \(n,m\) 都是偶数，需要 \(\frac{n}{2}\times \frac{m}{2}\) 块木板
对于 \(n,m\) 一奇一偶，假设 \(n\) 是偶数，需要 \(\frac{n}{2}\times \frac{m+1}{2}\)
对于 \(n,m\) 都是奇数，无法做到
记得开long long
T2 三相众物 (friend)
30分
暴力枚举
80分
将所有的战斗力值放在一起后排序
因此任何一种战斗力的选择可以看作是其中一段区间
所以我们可以枚举区间，然后判断区间中是否有 \(n\) 个三相众物
\(O(n^2)\) 暴力枚举
100分
容易发现：区间 \([l,r]\) ,随着 \(r\) 的右移，最大的合法 \(l\) 也只会右移
故用队列维护即可
T3 食堂选择 (dinner)
70分
对每个 \(x_i,q_i\) 做bfs
时间复杂度 \(O(nm)\)
100分
对于相同的\(q_i\)，可到达的结点相同。
所以相当于查询从这些结点出发到达\(x_i\)的最短路
将询问离散化，按照\(q_i\)从大到小排序。
\([\ge i]=[>i]+[=i]\)
将相同的\(q_i\)放在一起，在\([>q_i]\)的基础上再做一遍bfs，求出\([=q_i]\)的答案。
时间复杂度\(O(Qn)\)
T4 分解因数 (factor)
20分
暴力
60分
设\(f[i][j]\)表示对分解\(i\)，最大的约数为\(j\)的方案数
状态枚举\(O(nlgn)\)，转移\(O(n)\)
空间复杂度\(O(n^2)\)
80分
发现只有\(j|i\)的时候，\(f[i][j]!=0\)
故空间可以优化成\(O(nlg n)\)，状态枚举也是\(O(nlgn)\)
考虑转移，转移可以通过预处理加速优化
故总时间复杂度为\(O(nlgn)\)
100分
类似完全背包的优化
我们可以从小到大枚举\(j\)，去掉\(k\le j\)这个条件，故\(j\)这维没有意义。
可以将状态改成
则方程变成了