zhangxixi的博客

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15584623.html 题目链接 首先考虑两个物品A，B。 假设先做A，则时间为：Ax+max⁡(Ay,Bx)+ByA_x+\max(A_y, B_x)+B_yAx​+max(Ay​,Bx​)+By​。 假设先做B，则时间为：Bx+max⁡(By,Ax)+AyB_x+\max(B_y, A_x)+A_yBx​+max(By​,Ax​)+Ay​。 对于A、B，我们可以在上面两种情况中取时间较少的方案。 同理，对于每一对物品，我们都可以采用以上方案...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15582269.html 早上6点摸黑起床… 坐地铁去高中部，蹭校车。 今年是我第一次参加noip，希望开门红（WA） 在地铁上在洛谷打卡，中吉，竟然没有大吉！？ 打卡QQ，在每个群里发一遍rp++ 上车了，找cmb要了2块巧克力。 到达gf，crx老师派巧克力，由于我的厚颜无耻绝顶聪明，骗走了3块巧克力。 在门口和同学拍了张照，然后就进去了… 到达考场，发现我和csp上下午的考场都一样。 带了报纸巾，一大堆食物，一瓶水，文件袋进去。 那个老师一...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15579094.html 题目链接 首先我们发现单词个数，也就是 mmm 很小，这启示着我们不需要用到什么神仙字符串算法，可以暴力kmp。 对于每个单词与原串做kmp匹配，用前缀和记录能匹配成功的，每次询问 O(m)O(m)O(m) 回答即可。 时间复杂度：O(m×(n+q))O(m\times(n+q))O(m×(n+q)) Code 1234567891011121314151617181920212223242526272829303132...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574898.html 题目链接 可以发现，我们并不需要对所有节点进行枚举，我们只需要对所有端点甚至只需要枚举右端点即可。 因为如果这个不是端点，那么在它右边的点和它所在的区间个数相同，同时右边的点必然大于这个点，所以不用考虑这个点。 按照线段覆盖问题求出每个点的覆盖情况即可，也可以说是一维扫描线（雾 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，主要是排序耗时间。 Code 12345678910111213141516...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15574730.html 题目链接 观察数据范围发现边权都小于255，所以我们可以枚举最大边权。 对于每个最大边权，我们都在不大于这个边权的剩下的边里跑一次最短路。 最后再用最短路求出的答案+所枚举的最大边权=在这个最大边权下的答案。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：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+并查集做法，感觉挺容易理解，反正以后我就会使用这个模板了。 前置芝士 强连通 如果有向图中的两个点能够互相到达，那么他们强连通。 强连通图 如果有向图中任意两点能够互相到达，那么这个图就是强连通图 强连通分量 有向图中的极大强连通图子图就是强连通分量。（就是没有包含这个强连通子图的更大强连通子图） 缩点 把每个强连通分量作为一个结点。 正文 ...