【拾题杂谈】LuoguP2015 二叉苹果树
题面大秦为你打开题目传送门
题目描述有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树：
123452 5 \ / 3 4 \ / 1
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入格式第一行 $2$ 个整数 $N$ 和 $Q$，分别表示表示树的结点数，和要保留的树枝数量。
接下来 $N-1$ 行，每行 $3$ 个整数，描述一根树枝的信息：前 $2$ 个数是它连接的结点的编号，第 $3$ 个数是这根树枝上苹果的数量。
输出格式一个数，最多能留住的苹果的数量。
样例 #1样例输入 #1123455 21 3 11 4 102 3 203 5 20
样例输出 #1121
提示$1 \leqslant Q < N \leqslant 100$，每根树枝上的苹果 $\leqs ...
【算法介绍】树形动态规划
算法简介：旋风女仆树形 DP 是一种再树形结构上面跑的 DP ，我们经过有限次的递归统计，记录 DP 值再合并，从而解决问题。
介于树的天生递归结构，我们的树形 DP 也就有这个从父到子从子到父的递推方式。
复杂度一般就是遍历树的复杂度，如果多了维度，那就会乘上那么多。
算法演示：干净利落例题选讲：骑士团扫除专家大秦为你打开题目传送门
五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。
已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在不同的通道端点安排保安所需的费用不同。
一个保安一旦站在某个通道的其中一个端点，那么他除了能看守住他所站的那个端点，也能看到这个通道的另一个端点，所以一个保安可能同时能看守住多个端点（树的结点），因此没有必要在每个通道的端点都安排保安。
编程任务：
请你帮助超市经理策划安排，在能看守全部通道端点的前提下，使得花费的经费最少。
例题思路：支援就交给我吧题目就是一棵树，我们就考虑如何去设计状态。这个不 ...
【拾题杂谈】LuoguP1005 矩阵取数游戏
题面大秦为你打开题目传送门
题目描述帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 $n \times m$ 的矩阵，矩阵中的每个元素 $a_{i,j}$ 均为非负整数。游戏规则如下：
每次取数时须从每行各取走一个元素，共 $n$ 个。经过 $m$ 次后取完矩阵内所有元素；
每次取走的各个元素只能是该元素所在行的行首或行尾；
每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 $\times 2^i$，其中 $i$ 表示第 $i$ 次取数（从 $1$ 开始编号）；
游戏结束总得分为 $m$ 次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入格式输入文件包括 $n+1$ 行：
第一行为两个用空格隔开的整数 $n$ 和 $m$。
第 $2\sim n+1$ 行为 $n \times m$ 矩阵，其中每行有 $m$ 个用单个空格隔开的非负整数。
输出格式输出文件仅包含 $1$ 行，为一个整数，即输入矩阵取数后的最大得分。
样例 #1样例输入 #11232 31 2 33 4 2
样例输出 #1182
...
【拾题杂谈】LuoguP1063 能量项链
题面大秦为你打开题目传送门
题目描述在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 $N$ 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $n$，则聚合后释放的能量为 $m \times r \times n$（Mars 单位），新产生的珠子的头标记为 $m$，尾标记为 $n$。
需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。
例如：设 $N=4$，$4$ 颗珠子的头标记与尾标记依次为 $(2,3)(3,5)(5,10)(10,2)$。我们用记号 $\oplus$ 表示两颗珠子的聚 ...
【算法介绍】区间类动态规划
算法简介：开拓的心魂区间类动态规划，是作为线性动态规划的拓展。与线性不同的是，区间类动态规划的递推操作，可以是任意的。当我们发现这样的一道例题出现了有可以分为两个子区间合并的这样的性质，且满足最优子结构和无后效性，就是区间类动态规划的题目了。
算法演示：烈火与勇气例题选讲：冒险憧憬那么首先的，作为动态规划的题目，最好的方式还是通过例题去理解这样一个算法的大致特点。
将 $n(1≤n≤200)$ 堆石子绕圆形操场摆放，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
选择一种合并石子的方案，使得做 $n-1$ 次合并，得分的总和最小。
选择一种合并石子的方案，使得做 $n-1$ 次合并，得分的总和最大。
例题思路：踏破绝境那么首先拿到一道 DP 题，一般都会给人一种贪心的假象，这题也不例外。尤其是收到合并果子那道题的影响，有些人可能根本不会想到 DP 去，贪心的做法确实很难找到一种可以推翻掉他的数据。
那么这里先给出一个感性的证明，就是给出这个贪心错误的数据。首先明确一点：贪心策略是每次合并相邻的较小的两堆（如果 ...
【拾题杂谈】LuoguP4503 企鹅QQ
题面大秦为你打开题目传送门
题目描述两个字符串相似的定义：当且仅当这两个字符串等长且恰好只有一位不同。
例如“Penguin1”和“Penguin2”是相似的，但“Penguin1”和“2Penguin”不是相似的。
给定N个字符串，判断它们有多少对是相似的。
给定的字符串长度均等于L，且只包含大小写字母、数字、下划线以及 ‘@’ 共64种字符，而且不存在两个相同的字符串。
思路由于每个字符串的长度相当的小，也就说，我们完全可以枚举那个不一样的位，哈希求最长连号时顺便统计即可。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include<bits/stdc++.h>using namespace std;typedef unsigned long long ull;const ull P = 131;int n, L;char s[30010][210];ull hsh[30010][210];ull power[210];u ...
【拾题杂谈】LuoguP6739 Three Friends
题面大秦为你打开题目传送门
题目描述有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.
思路我们直接，大力枚举这个插入的字符，然后大力哈希判断即可。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include<bits/stdc++.h>using namespace std;typedef unsigned long long ull;const int N = 2e6 + 10;const int B = 31;ull Power[N];int n;string s;ull hsh[N];inline ull Hash(int l, int r) { return l <= r ? hsh[r] - ...
【拾题杂谈】HDU1083 Longest Common String
题面大秦为你打开题目传送门
题目描述给定两个字符串，请找出它们的最长公共子串。
思路由于本人不会后缀数组，所以我们就哈希淼过罢。
直接大力二分哈希找长度，搞定。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102#pragma GCC optimize(2)#pragma GCC optimize(3, "Ofast", "inline")#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef __int128 int128;typedef unsigned long long ull;namespac ...
【拾题杂谈】UVA10298 Power String
题面大秦为你打开题目传送门
题目描述求出一个字符串最短的循环节个数。
思路不难想到 KMP，KMP 的 next 数组的定义就是长度最长且相等的真前后缀，直接去找 $n-next[n]$ 这个长度就是我们要找的最短循环节长度，用总长除以他即可（别忘了前提是得整除）
代码1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;const int N = 1e6 + 10;char s[N];int n;int nxt[N];inline void Input() { scanf("%s", s + 1); if(s[1] == '.') return exit(0);}inline void InitNxt() { for(int i = 2, j = 0; i <= n; i++) { while (j & ...
【算法介绍】字符串算法
算法简介：玉颗珊珊月中落这篇文章是字符串算法的大集合，会提到字符串哈希，字典树，KMP以及AC自动机等常用算法。字符串哈希作为非常常用的基本手段，是读者不得不会的一种算法。KMP 算法可以快速地经行字符串的匹配、比对，以及他和字典树的结合体，AC自动机，都是非常重要的知识点。
算法演示：云台团团降芦菔字符串哈希：妙受琼阁那么作为最最基础的，这个字符串哈希应该最先讲。字符串哈希的主要思路，就是把这个字符串看成一个高进制数，从而进行比对的一种哈希算法。
那么说到把字符串转化为高进制数，不难想到位值原理，就是说每一位的值都是不一样的，对于 $B$ 进制数的第 $i$ 位（个位算作第 $0$ 位，十位是第 $1$ 位，以此类推）这一位上的 “ $1$ ” 表示的是 $B^i$ 。
那么常规的，我们考虑到数字上的一些习惯，我们不妨也设这个字符串数字的左边是高位，右边是地位，那么如何去哈希呢？不难想到了其实：$$hash_i = hash_{i - 1}\times Base + Hash(s_i)$$这一个式子中，$hash_i$ 表示前 $i$ 位的哈希结果，$Base$ 表示这个字 ...
