problem 疑似神题 首先发现一个事情：相同颜色的书一定是一起动或者一起不动，即行为平行。 发现了这件事就可以简单 \texttt{dp} 了。 #include<bits/stdc++.h> using namespace std; #define fio(x) freopen(x".in",
发布于 2025-10-18
![[THUPC 2021 初赛] 合法序列](/upload/138508263p0.png)
传送门 k 太小了，结合题目易于想到枚举前 2^k 位的状态，然后限制不是一般算法能做的，考虑 \texttt{dp} ，每加一位贡献只跟前 k-1 位有关，设进状态转移，设 f_{i,j} 表示考虑到第 i 位，后 k-1 位状态为 j 的方案数，每次转移分别考
发布于 2025-10-14
![[COI 2019] TENIS](/upload/138479350p0.jpg)
你谷传送门 非常 OI 的一道题 看到这题就往图论的方向去想了，但其实能看出本质与竞赛图有关的话甚至能更快，只可惜事先没有接触过，敏感度不够。 往正常方向推也挺好推的，但其实我在第一步就炸了，我考虑的是怎么利用整个排名表的信息维护一位选手的答案 傻逼吗我是 ，这里两者信息完全不对等，大量信息被浪费。
发布于 2025-10-11
![[CSP-S2019] 树的重心](/upload/82910218p0.png)
挺好一题，能学到许多东西。 首先看到题面所求是由对每一条边考虑产生的点的信息和，如果顺着题目的思路思考那肯定是枚举边，用边的限制考虑边的贡献，在仔细考虑一下重心相关的限制，基本就能想到倍增，预处理等方法去动态地对每条边去计算对应的重心，可喜可贺，可喜可贺。 虽然这样很好想，可具体实现似乎有点麻烦，遂
发布于 2025-09-13
题目传送门 代码实现和一些思路参考了一些题解。 遇到这种序列上研究大小的序列问题，应该主动考虑笛卡尔树。 对原序列建出一棵大根笛卡尔树。稍微转化一下问题的连边条件，首先每个节点必定和它的左子树同在所有点在同一个连通块，这样初步连边后可以看出连通块与连通块之间通过树上右链（从根一直向右走的链）的边进行
发布于 2025-09-10
![[SCOI2016] 幸运数字](/upload/138492935p0.png)
题目传送门 这题十分的顺，应该属于能一眼瞪出来的题。 首先不定数个整数异或和最大最好办法 (也有可能是唯一办法？) 就是线性基了。然后是树上路径查询问题，基本方法有两种：1. 处理每个点到根，从问题或点的性质入手，需要挖掘性质。 2.树剖，预处理加上暴力查询，相对无脑。 可以先看看简单的树剖，其做法
发布于 2025-09-06
![[JOISC 2020] 治療計画](/upload/74746113_p0.png)
题目传送门 卧槽这题有点牛逼。 像我这种蒟蒻只看题面肯定没有什么头绪，所以只好看一眼数据范围，似乎只能依赖方案在 O(m\log) 内解决。 至于为什么会想到 dp ，应该只能靠感觉吧，这题一看就很有线性dp的味道。 所以由前面的想法可以大概先设个 f_i ，至于 i 的含义只能结合方案的性质和所求
发布于 2025-09-06
题 Sol 应该存在一种经典技巧吧，就是那种可行性DP通过某种手段（感觉最常见的是贪心）压缩一个状态维度。 看到这个题首先应该有个 \texttt{native} 的想法（基于经验？）：考虑设 f_{i,j} 为考虑前 i 个灯笼，能覆盖前缀 [1,j] 的可行性。 然后这里估计能列个方程吧，又或者
发布于 2025-08-27
![[ZJOI2019] 语言](/upload/70937229p0.png)