2024 年 5月 10 日随笔档案 - yhddd - 博客园

2024年5月10日

摘要： [JOISC2022] 监狱思路因为是一棵树，最短路径唯一，a56爆大奖在线娱乐每次都让一个人走到底。当走 \(s->t\)，\(s->t\) 中此时没有点，意味着起点这条路径上的人一定先于这个人走，终点在这条路径导航的人一定后于这个人走。对于他们的相对顺序的限制，先走向后走连边，连边跑拓扑排序看有没有环。复杂阅读全文

posted @ 2024-05-10 20:13 yhddd 阅读(2) 评论(0) 推荐(0) 编辑

P10180 题解

摘要： P10180 思路首先答案是所有连通块大小的平方和。先用并查集将相同颜色合起来，记录 \(sum_i\) a56爆大奖在线娱乐只看颜色 \(i\) 的答案。如果对于询问 \(u,v\) 不存在 \(e(i,j)\) 满足 \(a_i=u,a_j=v\)，答案为两个颜色单独的答案之和。否则只有至多 \(n-1 阅读全文

posted @ 2024-05-10 20:12 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

P10272 题解

摘要： P10272 P7525 加强版。思路分类讨论。如果 \(S\) 存在一个周期，设最小周期长为 \(len\)。那么第 \(i\) 次操作是在 \(i-1\)长度上加 \((n-len)\times 2^i\)。用字符串哈希判断是否存在长为 \(i\) 的周期，只需要判断 \(s[1,n-i]= 阅读全文

posted @ 2024-05-10 20:09 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

useful things

摘要： https://www.zhihu.com/tardis/bd/art/460373184 https://mem.ac/oi/algorithm/dynamic-linear-basis/ https://www.luogu.com/article/v7vgqau1 https://www.cnb 阅读全文

posted @ 2024-05-10 20:09 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

WC2024 游记

摘要： PKUWC2024，NOIWC2024 240125-240204 0125 晚上到酒店，太豪华了，感觉分到普通双床的好亏。 0126 PKUWC-Day1 早上发生了什么好像都忘了。居然是 linux，弄半天不会一点。试机那道题之前做过，但搞了半天。最后只会用 codeblock 写，还好 cza 阅读全文

posted @ 2024-05-10 20:07 yhddd 阅读(3) 评论(0) 推荐(0) 编辑

SAM 做题记录

摘要： 1.基本 SAM 能a56爆大奖在线娱乐某个字符串的所有子串，且正好是所有子串。 struct sam{ int p=1,cur=1; struct nd{ int len,lnk; map<int,int> ch; nd(int u=0,int v=0){ len=u,lnk=v; ch.clear(); } } 阅读全文

posted @ 2024-05-10 20:07 yhddd 阅读(2) 评论(0) 推荐(0) 编辑

P10144 题解

摘要： P10144 考场上瞪了两个小时什么没想到，最后半小时想到一个不太一样的做法，写出来了但挂了。寄。思路记 \(l=2\times L\)。令 \(i\) 取 \(a_i\) 记为 \(0\)，取 \(l-a_i\) 记为 \(1\)，写为 01 序列。考虑取 \(0/1\) 对 \(l\) 的阅读全文

posted @ 2024-05-10 20:06 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

P7482 题解

摘要： P7482 思路 cdq 分治拆成 \([l,mid]\) 到 \((mid,r]\) 的贡献。对于一个区间计算答案可以用 dp 完成。以 \(mid\) 为交界合并左右的 dp 值。设 \(f_{i,0/1}\) a56爆大奖在线娱乐区间 \([i,mid]\) 或区间 \((mid,i]\)，是否选 \(mi 阅读全文

posted @ 2024-05-10 20:05 yhddd 阅读(3) 评论(0) 推荐(0) 编辑

P8792 题解

摘要： P8792 CF891A 思路为了使数组只剩 \(1\)，需要从一个 \(1\) 开始不断与傍边的数做 gcd 操作，需要 \(n-cnt_1\) 次。如果数组中没有 \(1\)，那t_么需要连续对一段数 \([l,r]\) 做 gcd 操作得出一个 \(1\)，再用一个 \(1\) 做 \(n 阅读全文

posted @ 2024-05-10 20:05 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

P7247 题解

摘要： P7247 参考 EI 题解。思路因为随机移动，a56爆大奖在线娱乐可以不管当前在具体哪个点，发现本质不同的只有根节点和非根节点。设 \(dp_{i,0/1}\) a56爆大奖在线娱乐还剩 \(i\) 个未标记点，当前在或不在根节点。可以通过根到随机非根节点的期望 \(x\)，随机非根节点到根的期望 \(y\)，随机非根节点到阅读全文

posted @ 2024-05-10 20:05 yhddd 阅读(3) 评论(0) 推荐(0) 编辑

P6681 题解

摘要： P6681 加强版 qoj1193，\(n\leq 1000,m=16\)。思路考虑选串的过程，是给短的后面加串直到长短互换。设状态 \(id_{i,j}\) a56爆大奖在线娱乐当前长的一串末尾是 \(s_i\)，比短串长 \(j\)。枚举加入的串，状态的转移分两种：加入后短串还是比长串短。\(id_{i, 阅读全文

posted @ 2024-05-10 20:04 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

P5996 题解

摘要： P5996 网络流。同 P2762 太空飞行计划问题建图方式，将物品与 \(s\) 连 \((s,i,v_i)\)，警察与 \(t\) 连 \((j+n,t,v_j)\)，警察与对应的物品连 \((i,j+n,inf)\)，答案为所有物品的收益和减最小割。割 \(s,i,v_i\) a56爆大奖在线娱乐不选物品，阅读全文

posted @ 2024-05-10 20:04 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

P5344 题解

摘要： P5344 思路把图建出来跑 dij 即可。对于建图，可以想到对a56爆大奖在线娱乐操作 \(1\) 建一个虚点，从 \(u1\) 到 \(v1\) 向虚点连代价为 \(w\) 的边，从虚点向 \(u2\) 到 \(v2\) 连代价为 \(0\) 的边。此时图中有 \(n\times m\) 条边，无法接受，考阅读全文

posted @ 2024-05-10 20:04 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

P3697 题解

摘要： P3697 思路贪心。首先，不加快车时，能到达的车站应跟在特急车停的站之后。即对于 \(s_i\) 和 \(s_{i+1}\) 之间的 \(j\)，如果 \(j\) 可以到达，从 \(s_i\) 到 \(j\) 的站都符合条件。再考虑快车。对于一个站，最快的到达方式是：先坐特急车到最近的站点阅读全文

posted @ 2024-05-10 20:03 yhddd 阅读(2) 评论(0) 推荐(0) 编辑

P3538 题解

摘要： P3538 [POI2012]OKR-A Horrible Poem 思路先暴力。对于a56爆大奖在线娱乐询问，用 \(O(\sqrt{len})\) 枚举区间长度 \(len\) 的因数 \(i\)，再一个一个位置比较两个字符串 \(\frac{len}{i}\) 次判断。复杂度 \(O(qn\sqrt n)\ 阅读全文

posted @ 2024-05-10 20:03 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

P3280 题解

摘要： P3280 思路没有求买入了多少，a56爆大奖在线娱乐可以当作每次把能买的全都买了，走在路上不行再扔。卖出时由题意能卖多少卖多少。主要的问题是求从城到城最多能带多少东西。计算两点间路径的权值最小值而不在意距离，建最大生成树，把图改作树。通过倍增的方式，求 lca 时算路径权值的最小值。对于火车，可以理解为一条权阅读全文

posted @ 2024-05-10 20:03 yhddd 阅读(2) 评论(0) 推荐(0) 编辑

P2685 题解

摘要： title: '' date: 2024-02-28 18:45:38 tags: [题解,图论,数据结构] published: true hideInList: false feature: isTop: false P2685 简化版：P1186 思路题意即：对于一个图�a56爆大奖在线娱乐舛弦惶醣吆笮纬傻淖� 阅读全文

posted @ 2024-05-10 20:02 yhddd 阅读(2) 评论(0) 推荐(0) 编辑

lca 科技

摘要：完全二叉树求 lca https://blog.csdn.net/kksleric/article/details/7836649 先考虑完全二叉树的 lca 求法。中序遍历分配编号。设第 \(k\) 位是 \(u\oplus v\) 最左边的 \(1\)，则 \(lca(u,v)\) 是 \(u 阅读全文

posted @ 2024-05-10 20:02 yhddd 阅读(1) 评论(0) 推荐(0) 编辑

joisc2018_l 题解

摘要： joisc2018_l 思路 \(a_i\) 和 \(a_{i+1}\) 之间取最短路最优。但因为有不能折返的限制，a56爆大奖在线娱乐希望对每对 \(u,v\) 找到 \(k\) 条最短路使得�a56爆大奖在线娱乐舛系� \(u\) 的一条出边和 \(v\) 的一条入边，\(u\) 到 \(v\) 的最短路还在 \(k\) 条中。阅读全文

posted @ 2024-05-10 20:02 yhddd 阅读(4) 评论(0) 推荐(0) 编辑

GDKOI2024 游记

摘要： GDKOI2024 240105-240107 签到暴力挂分稳重向好，抽象骗分高质量发展。 Day0 考试。寄。社会主义的曲折发展；绿水青山就是金山银山。 2h 大巴，2h 酒店看电视，猫和老鼠。 Day1 开题，好，只有 T1 有一个"大"样例。 T1 图论，二分图相关，先写 \(40\) 状压阅读全文

posted @ 2024-05-10 20:01 yhddd 阅读(1) 评论(0) 推荐(0) 编辑