文章

//我又来水博客啦 1. 题目 传送门＝￣ω￣＝ 2. 题解 状态压缩、搜索。 具体解释见 https://www.mina.moe/?p=362 代码： #include <bits/stdc++.h> using namespace std; int n,ans,w[15],wcnt 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 枚举每个点放进的矩形。 复杂度 540，所以要剪枝。 剪枝： 1. 最优性剪枝，如果当前保存的答案比当前方案的面积小，剪枝。 2. 如果有矩形相交，剪枝（这个你不剪会 WA）至于判断两矩形是否相交。。。 两矩形相交必然得到一个新矩形，判断新矩形是否合法即可。 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 搜索。。。 对于在一个联通块里的点，它们的答案相同。 所以标记不同颜色。 选定一个点，从这个点 dfs 遍历到的点全部设为一个颜色，并且把这个点设置为该颜色的根节点，并把根节点的答案设置为刚刚 dfs 遍历到的节点数量。 对于每次查询，我们根据这个点的颜色， 阅读更多…

题意：给定一个数字 x(x<=105)，不停得把数字得最后几位放到最前面去。求最多可以产生多少中不同得数字，求出这些数字与原数字比较大于、等于、小于的个数。 思路：每一个可能得数字就是：将原字符串自身复制一遍之后在其中截取的一段，其长度等于原数字长。 我们可以借助倍增、DC_3 或者扩展 KM 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 错误题解 虽然这题我不会做，但是 AC 还是没问题的。 ——pyhao 贪心一发发现 90 分，搞个特判就 AC 了。 各大 OJ 均可 AC。 注意这是错误的题解！思路是错误的！我只是来娱乐一发的！ 代码： #include <bits/stdc++.h> 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 就是个搜索题。。。 必须加很多剪枝。。。 剪枝剪去我们的疯狂 ——膜你抄 我搞了这几个剪枝： 1. 答案必然在最短的长度到长度之和之间。见代码第 29 行。 2. 当前枚举的答案必然可以整除长度之和。见代码第 30 行。 3. 拼一根目标棍子时，枚举过小木棍 阅读更多…

题意：在一个坐标系的原点出发走 k 步回到原点，第 i 步走 i 个单位长度。有 x 个障碍，障碍不能经过或者停留。每一步结束的地方不能再作为结束的地方。求有多少中方案以及每个方案的移动序列（用 wsne 表示），按字典序输出。 分析：垃圾题面毁我青春！它竟然没有说清楚不能在停留过的点停留！ 所以我 阅读更多…

题意：给定一个 n 个节点 m 条边的图，(n,m<=2000)(这道题口是心非，就当 n,m<=104 吧)，每条边的长度∈[0,105], 求1->求1->n 的最短路共有几条。如果有无数条输出-1. 分析：要求最短路的条数，首先肯定要求最短路的长度，再思考最短路的条数能否在求长度的 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 考虑倒推。 设 $f(i)$为时刻 $i$到时刻 $n$之间的最大空暇时间。 如果时刻 $i$无任务开始，显然 $f(i)=f(i+1)+1$。 否则枚举开始于时刻 $i$的任务，设当前枚举的任务结束时间为 $j$，则 $f(i)=max(f(j+1))$。 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 设 $f(i,j)$表示在前 $i$本书中选 $j$本书，且必然选择第 $i$本书时的最小差异值。 不难得出状态转移方程：$f(i,j)=min\{f(k,j-1)+abs(w[k]-w[i]) | j-1<=k<i\}$ 因此记 阅读更多…