题目链接：P3379 【模板】最近公共祖先（LCA） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) LCA是什么？ LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 求解LCA的方法 朴素法，复杂度O(N)：先把两个点x和y跳到同一深度，然后同时往上跑，当x == y时返回x或y。当整棵树接近一条链状 […]

题目链接：https://codeforces.com/gym/103729/problem/J 赛场上没做出这题，可惜了。其实一开始就想到了字符串hash，甚至思路都和题解一样，但是由于忘记了字符串hash的板子，然后一时着急就没做出来。其实不难。 题意 给定一个字符串S，问能否通过将一个连续区间[l ,r](l <= r)翻转一次使得字符串S变为一个回文串。 输出任意一种可行方案即可。 […]

1.准备资源 1.Ubuntu系统的服务器（或者用自己电脑搞虚拟机也行），我用的版本是20.04 2.联网（可能需要科学，如果不行的话，可以找镜像） 2.安装GCC编译环境 网上的教程天花乱坠，其实用apt可以快速安装，两行代码，逐行执行即可。 （需要等待一段时间...） 执行完成之后，用这行代码查询gcc版本，如果查到了，就说明装好了。 3.写一个C文件并编译运行吧！ 先创建一个C文件 用nan […]

传送门：B - At Most 3 (Judge ver.) (atcoder.jp) 题目大意 给定一个长度为N的数组（N <= 300），每次从中取出至多3个数字，问所有可能的且小于等于W的和(sum)有多少种。 思路 dfs，一共3层，每层可能的结果为a[1 ~ N]或0（不选）。 为了防止重复选择，用vis数组防止重复，还可以用k（循环开始位置）来剪枝。 第二个剪枝就是当sum &g […]

题目传送门：Problem - C - Codeforces 题目大意 有多组测试用例。 给定一个01字符串S，从前往后删除若干字符，从后往前删除若干字符，留下中间连续的一串字符，不同的方案的代价为max（删除的1的个数，留下的0的个数），问最小的代价是多少？ 思路（双指针 + 贪心） 会留下中间一段，所以可以用双指针来表示中间这一段，枚举左端点，然后贪心，复杂度为O(N)。 贪心的原理为：当留下 […]

题目传送门：Problem - 3555 (hdu.edu.cn) 题目大意 给定一个N，求[1, N]范围内的数字转换形成的字符串中包含"49"的数字。 (1 <= N <= 2^63-1) 思路 因为数据太大了，所以直接前缀和肯定行不通，所以需要数位dp。 典型的数位dp模板题。 代码

传送门：P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 顾名思义啊，一个模板题，用tarjan算法缩点之后topo + DAGdp就可以了，写一个模板，防止自己忘记。 代码

题目传送门：Beating the Dataset | LightOJ 题目大意 / Problem 有一个ACM选手在刷题，这题答案多组"YES" or "NO"，给定了数据组数和答案字节数（可以算出ye和no各有多少个），每一个数据提交后会返回正确答案并作为下一次的提交，问错误数据个数的期望。 思路 / Thought 别想复杂了。其实很简单。 首先算出X和Y，分别表示YES和NO的数目。 一 […]

传送门：http://www.lightoj.com/volume_showproblem.php?problem=1038 题目 / Problem 有T组用例。给定一个正整数N(1 <= N <= 1e5)，每次N可以等概率得除以一个因子，从而变成一个新的N，问从N变到1的次数期望。 次数期望是说，假如现在是第 i 轮变换，那么这一次(x - > y)对于结果的贡献是i * […]

传送门：Discovering Gold | LightOJ 题目描述 / Problem 在一个一维数轴上，起始点为1，终点为N。 从起始点开始，每次可以掷骰子，等概率地往后走[1, 6]中的任意距离，如果下一个点超过了N，重新掷骰子，每个点有一个金币数a[i]。求到达终点的金币期望。 思路 / Thought 期望DP。 第一种思路，是对从起始点到达该点的概率进行dp，然后乘以各点的金币数就是 […]