A 不断减损的时间 简单题，直接贪心，对于正整数那便是能除就除。负数不操作就行。 ">using namespace std; #define pii pair<int,int> #define ll long long int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();} return f ? -x...

A Tokitsukaze and a+b=n (easy) 简单题，做法很多。 ">using namespace std; #define pii pair<int,int> #define ll long long int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();} return f ? -x...

本人能力有限，有些题做不来，也在补，求大佬指点。也欢迎大家讨论。 A World Final? World Cup! (I) 简单题，根据题意模拟，记录现有情况和还剩多少场可以踢。 ">using namespace std; #define pii pair<int,int> #define ll long long int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while(isdigit(ch)) {x =...

施工中。。 后缀自动机 (suffix automaton, SAM) SAM 的概述 可以解决很多字符串问题的强大工具。是一个可以处理字符串 SSS 的所有后缀的 最小的 确定性有限自动机。 SAM 的定义 SAM 是一张有向无环图。结点被称作 状态 ，边被称作状态间的 转移 。 图存在一个源点 t0t_0t0​ ，称作 初始状态 ，其它各结点均可从 t0t_0t0​ 出发到达。 每个 转移 都标有一些字母。从一个结点出发的所有转移均 不同 。 存在一个或多个 终止状态 。如果我们从初始状态 t0t_0t0​ 出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是字符串 SSS ...

分析 比较奥秘重重的 状态设计。定义 为覆盖以 为根的全部子树，而且向上覆盖了 层节点。 表示，覆盖了以 为根，子树节点深度 的全部节点。 初始化 对于任何情况 。选择这个节点的转移。 如果当前点是关键点，那么 。由于必须要覆盖这个节点，那么初始化为必选状态。 如果当前点不是关键点，那么 。对于非关键点可以不选。 转移 定义，不解释。 ，当儿子转移到父亲，子树深度增加一。 ，这个其实是滚动数组，只要我们正序枚举就可以了。 由于我们的转移只转移了端点，所以我们还要做一次前缀（后缀）最小值。 代码 #include<bits/stdc++.h&gt...

分析 对于两个问题，我们可以分开讨论。我们发现如果有两个相邻的红色的砖块（不包括节点 ），那么在开始之后就可以使棋子到达任意一个地方，那么我们就根据是否有两个相邻的红色砖块来讨论。 无相邻的情况，我们可以发现，直接把棋子放在偶数位置是最优的。那么第一问的答案就是偶数位置 的个数，而第二问就是偶数位置 的个数。 有相邻的情况，我们可以发现第一问的答案为 ，而第二问，我们考虑递推， 表示在这个节点放一个棋子总共需要安放的棋子数，那么转移和斐波那契数列是一样的 。当然正反都要来一次，我们从任意两个相邻的红色砖块开始都有这样的转移，那么总的复杂度就为 。 细节，开 ，而且要注意节...

吐了，比赛开始时。报名报成小号了。这次的 比较简单，没有码量题，好评。 A 分析 读懂题意，模拟即可。 代码 // sto xzc orz #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define ll long long int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();} while...

相信大家初步了解了倍增之后，想要实践一下。这里选取了牛客的例题来讲解。来个👍 呗， 。 入门知识传送门 一些简单规定 指图上的最短路，在树上为 的简单路径。 指有根树上的深度。 [AHOI2008]MEET 紧急集合 题意 给出三个点 ，找到一个节点 使 最小。 分析 我们考虑两个节点，那么比较简单，只要不走回头路就是最短的，换而言之就是 上的任意一个节点就可以。那么两个节点可以这样做，三个节点呢？我们可以类比，只要 这三条路径没有重叠，那么这样的 点就是合法的。那么现在如何找这个 点，对于 中任意两个点来说，只要 在简单路径上就可以了。那么我们可以分类讨论...

说在前面的 本人实力不高，求大佬轻喷，我尽量讲清楚一点。 例题传送门 在未作说明的情况下，有根树都以 为根。 表示，节点 的最进公共祖先。 表示，节点 的深度。 表示，节点 的树上简单路径长度。 倍增 倍增法 （英语： ），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。 引入 次询问，求一个节点的 级祖先。 分析 我们考虑最暴力的做法，每个节点保存它的父亲，那么连续跳 次父亲就可以得到 级祖先。但这样的单次复杂度为 的。 我们可以想到，由于没有修改整棵树。那么每一个节点的父亲是唯一的，那么这启发了我们使用一个算法，快速的查询祖先。...

题意 求出所以子集中最小没有出现的正整数之和。 分析 我们可以考虑一个元素的贡献，我们先考虑如果这个数 可以作为答案，那么 的每个元素至少选取了一次。那么根据乘法原理， 的总方案为 。 表示 这个数出现的次数。那么 的元素，可以选也可以不选总的方案数为 。上面的指数也可以通过前缀和维护。那么当元素的取值不连续时，我们就可以退出了，因为无论怎么选，答案都不能比这个大了。由于是考场写的，有点丑。 代码 // sto xzc orz #include<bits/stdc++.h> using namespace std; #define pii pair<int,...

分析 欢迎私聊，感觉说的不太清晰。 我们考虑如何保证每个区间的某一个种类个数达到 。这个我们可以考虑离线询问，将 的询问差分成 的答案。那么我们先把一个询问拆分成两个，再来考虑前缀的做法 。我们对于每个数，保留它的前一个和他相同相同的元素。那么枚举的右端点到了 ，那么左端点在 都是可以保证区间恰好 个的。那么这个我们可以考虑使用线段树来维护。 如何保证我们枚举的区间是保证它是最大元素。这个可以考虑动态维护两个指针 。 我们每当这两个指针中相同元素到达了 时，就移动到这个元素的 处，这样就保证了这个区间最多出现 个相同元素。 图例 代码 #include<bi...

分析 考虑求出边双连通分量，那么题目其实就是在问，有多少个桥。那么由于边双缩点之后，整个图变为树。那么树的边数就是答案。考虑新加一条边之后的贡献。那么就是树上距离，在将这个链上的权值变为 。这个考虑树链剖分或者 维护，写完才发现，好像直接并查集时间复杂度好像还要更优。这里采用了 实现，时间总复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; int read() { int x = 0,f = 0;char ch = getchar(); while(!isdigit(ch)) {if(ch == '...

题意 你有一颗 个节点的有根树 (以 号节点为根) ，求最少加入多少条边之后使得根节点（即 11 号节点）到这棵树上任意一点的距离不大于 。 分析 我们考虑覆盖一个节点有多少种方法。 在父亲节点连一条边。 在儿子节点上连一条边。 在当前节点上连一条边。 这样我们发现并不是很好做，考虑叶子节点。叶子节点只有两种可能，在自己或者在父亲上连一条边。那么我们很容易发现。在父亲处连边一定不劣于在当前节点建边。那么依次递归叶子节点就可以了，这样维护叶子节点通过 深度来维护。 代码 #include<bits/stdc++.h> using namespace std; int r...

写在前面的 本博客基本不会讲解如何运用组合数和斯特林数，应该偏向于数学证明，各类恒等式，我先咕一咕。 更新日志 11.17 基本的组合恒等式。 11.18 反演原理（很多反演放在后面讲解）。 11.18 第一类斯特林数。 11.18 第二类斯特林数。 11.18 二项式反演，斯特林反演。 定义 在未作特殊说明下。 在 时，函数值为 ，其它的所有时候函数值都为 。 表示组合数。 表示第二类斯特林数。 表示第一类斯特林数。 表示 的 阶上升幂，等价于 。 表示 的 阶下降幂，等价于 。 表示第二类斯特林数。 组合数 表示从 个有标号的元素...