zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574309.html 题目链接 首先朴素dp不用讲，设 dpidp_idpi​ 表示前 iii 个数划分的总方案数，SiS_iSi​ 表示前 iii 个数的和。 dpi=∑j=0i−1dpj   (Si−Sj⩾0)dp_i=\sum_{j=0}^{i-1}dp_j\,\,\,(S_i-S_j\geqslant 0) dpi​=j=0∑i−1​dpj​(Si​−Sj​⩾0) 其中 dp0=1dp_0=1dp0​=1。 可是这样的时间复杂度为 O...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15573796.html 题目链接 一道很好的01背包变形题。 首先看一眼题很明显可以发现是背包。 此题我当时的第一反应是二维费用背包，然而会TLE+MLE，于是打开题解思考01背包做法。 设 dpidp_idpi​ 代表智商和为 iii 时情商的最大值。 dpi=max⁡j=1n(dpi−sj+fj)dp_i=\max_{j=1}^n(dp_{i-s_j}+f_j) dpi​=j=1maxn​(dpi−sj​​+fj​) 经典的01背包转移。 ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15570096.html 题目链接 先按作业的提交地点排序。 设 dp(l,r,0/1)dp(l, r, 0/1)dp(l,r,0/1) 为还剩 [l,r][l, r][l,r] 的作业没交，且下一步交 l(0),r(1)l(0), r(1)l(0),r(1) 的最小步数。 显然： dp(l,r,0)=min⁡(max⁡(dp(l−1,r,0)+∣al−1−al∣, tl), max⁡(dp(l,r+1,1)+∣ar+1−al∣, tl))dp(...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15569706.html 题目链接 纯模拟题，无任何算法或思维难度。 难度虚高了。 对于时间和空间分别排个序，然后依次进行就行了。 看一下是先遇到减速地点还是减速时间。 要注意精度问题。 时间复杂度：O(n)O(n)O(n)。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15569521.html 题外话 Trajan模板太难记了（对于我来说），然后我们教练就教了我一种dfs+并查集做法，感觉挺容易理解，反正以后我就会使用这个模板了。 前置芝士 强连通 如果有向图中的两个点能够互相到达，那么他们强连通。 强连通图 如果有向图中任意两点能够互相到达，那么这个图就是强连通图 强连通分量 有向图中的极大强连通图子图就是强连通分量。（就是没有包含这个强连通子图的更大强连通子图） 缩点 把每个强连通分量作为一个结点。 正文 ...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15569311.html 题目链接 这道题正好让我在noip前复习了一次缩点。 首先题目里有这么一句话。 另外，如果存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0。 这不就是在提示我们要用缩点吗？ 他希望知道从他的电脑（编号为1），到小X的电脑（编号为n）所需要的最短传输时间。 最短时间，就是弄个最短路就行。由于缩点后是DAG图，所以可以用dp。 我用的是dp。（其...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15568359.html 题目链接 题外话： 一道纯最小生成树的题，能出道蓝我也真服了… 本文默认使用kruskal算法，主要是因为另一种我不会 首先我们先满足 kkk 条一级道路，对所有道路按一级道路造价排序，然后用最小生成树的做法选出 kkk 条边。 对于剩下的道路按二级造价排序，然后同理继续选即可。 时间复杂度 O(nlog⁡n)O(n\log n)O(nlogn) 需要注意的是题目输出格式有误，后面是输出具体方案。第一个数代表选的边的编...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15564095.html 题目链接 题目 “余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。 他的国家有 NNN 个城市，编号为 1…N1\ldots N1…N。 一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。 为了防止管理太过分散，每个省至少要有 BBB 个城市。 为了能有效的管理，每个省最多只有 3×B3\times B3×B 个城市。 每个省必须有一个省会...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15562734.html 题目链接 一道很好的最短路+dp。 先考虑最后结果，设 dpidp_idpi​ 表示前 iii 天的最小费用。设 f(i,j)f(i, j)f(i,j) 为从第 iii 天到第 jjj 天都走同一条道路的最小费用。 f(i,j)f(i, j)f(i,j) 很好求，提前预处理这段时间内哪些点不能走然后再可以走的点内跑一遍最短路即可。 转移： dpi=min⁡j=1i(dpj+f(j+1,i)×(i−(j+1)+1)+k)d...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558545.html 题目链接 和atc之前的一道题类似，都是暴力广搜+记录状态。 从开始状态开始广搜，然后直接拿个map或者哈希记录状态即可。 时间复杂度为: O(9!)O(9!)O(9!)，因为最多也只有这么多种状态。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556// ...