题意：每次两个人坐船过河，每次过河的时间取速度较慢的那个人，问所有人过河所需最短时间。 思路：经典贪心题目，我们将时间进行从小到大排序，根据贪心思想，我们肯定需要人过了河带船回来，显然肯定要速度快的带船回来所用时间更少，所以每次我们需要运速度较慢的人过去然后他们就不用管了。接下来对特殊情况进行讨论。 当时显然 当 当时,显然船要回一次,所以肯定是速度最快的人回， 即 当时，我们可以通过每次运两个(最慢和次慢）将情况变为前面三种情况，此时要分两种情况 类比的方法， ：通过让最慢和次慢的一起过河，从而减少一次次慢的时间，但要增加一倍次快的时间，方法是先让最快和次快过河，最快回来，最慢和次慢过河，次...

古老的牛市，遗迹的天梯 (DP) 思路：,令表示到达第级阶梯的最小步数。 因为题目保证阶梯高度递增， 所以当 然后根据题目还可以由中能够跳的转移过来。 所以我们可以枚举起跳的点.然后转移，注意开始后退的点必须小于等于,因为如果开始后退的点比还大就肯定不是最优的，因为可以直接后退到点。 时间复杂度： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=210,inf=0x3f3f3f3f; #define mst(a) memset(a,0,sizeof a) #define l...

Educational Codeforces Round 89 (A-D) 比赛没打，来补题辣。 A. Shovels and Swords 思路：数学，高中线性规划搞一下，由于对称性，可以默认，然后分两种情况搞一下就行了。  #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; #define mst(a) memset(a,0,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg ...

P4933 大师（DP) 题意：给定序列求所有子序列中为等差数列的个数。(序列长度为1，2被认为是等差序列，空序列不是等差序列)。 思路：很巧妙的,因为,数字较小。所以考虑设表示以下标的数字结尾公差为的等差序列个数。因为公差可能为负，所以整体向右移动位。 状态转移方程：. 这个是当两个数组成的等差序列。因为开始一个数的等差序列我们可以预处理就是了。所以里面是不含一个数等差序列，所以递推时要加上1. 还有一个注意的问题，因为我们不知道每个等差序列的公差是多少，所以我们在递推的时候一边递推，一边要加上贡献。 时间复杂度: #include<bits/stdc++.h> using na...

Codeforces Round #648 (Div. 2)（A-F)简要题解 A. Matrix Game ==奇偶性博弈==。显然每次选一个格子，可用的行和列都会减1，所以只需看最初可用的行和列的最小值的奇偶性即可。 B. Trouble Sort ==简单思维==。观察一下可得只要一个序列有两种类型就可以得到任何排列，若只有一种类型判断一下序列是否非递减即可。 C. Rotation Matching ==暴力==。因为向左移动次等于向右移动次，且最多移动次，所以我们只需要找到移动向左(右)移动多少次时有最大答案。我们只需记录的位置，然后计算中与相同数字的位置差，它代表序列移动的次数。最...

汉诺塔 题意：三根柱子，每次移动距离无限制，一次移动一个圆盘，问将所有圆盘从按大小顺序移动到最少需要多少步。 思路：因为这里不需要小圆盘始终在大圆盘上面，所以 设移动个圆盘的方案为，显然先将个圆盘移动到上需要步。 然后最后一个圆盘移动到需要步，然后再将个圆盘移动到需要步。 所以. 汉诺塔1 题意：三根柱子，每次移动距离无限制，一次移动一个圆盘，要求小圆盘始终在大圆盘上面，问将所有圆盘从按大小顺序移动到最少需要多少步。 思路：设移动个圆盘的方案为，显然先将个圆盘移动到上需要 步，然后最后一个圆盘移动到需要步，然后再将个圆盘移动到需要步。所以 。（另外递归或者打表都可以找到规律） 递归代码： #i...

Daizhenyang's Coin(Nim&博弈论) 传送门 思路：中心思想是将该游戏转化为多个子游戏进行和。 这里的子游戏是指：当只有一个硬币朝上位于位置的 因为有重复需要先去重，然后再异或和。 令U向上，D向下。 初始化 对应情况 (D) 。无论有多少个都是属于这个情况。因为没有硬币朝上肯定是输。  (U) 的后继状态只有,所有 同理  依次类推找规律可得， .而所有的值的二进制1的个数都为奇数。所以判断一下即可。具体证明见别的大佬的博客。。还在学习中。传送门 #include<bits/stdc++.h> using namespace std; typedef l...

高精度(阶乘,加法,减法,乘法,高精乘低精,高精除低精)模板. 最近深受高精度的困扰，想用又不是很熟练，就把高精度板子都整理了一遍了，除了高精除高精没写，不想写了，太懒了。 还是香。 便于以后使用和回顾。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e6+100; #define mst(a) memset(a,0,sizeof a) char a[N],b[N]; struct num{ int len,c[N]; }A,B,ans; num fac(int n){...

B - Multiplication 2 (大数乘法） 传送门 思路：看到高精度，首先就想到用。及其舒适。然后说说的做法。可以直接用高精度模板，但是太麻烦了。。 首先需要特判一下是否有。若有直接输出.(避免之前乘积大于但后面有0) 然后因为当不满足条件。 所以只需判断。 又因为为整数，所以当时，一定  这样就巧妙地避开了乘法。 貌似还有用也能过。但是只能每次都要判断一下。不能乘完再判断。否则会爆掉。但是由于数据太弱，貌似怎么写都能过。用写地时候，注意精度会有缺失，应该用两个数都判断一下。。不提倡用 甚至都能过。。 Python代码 n = int(input()) a = list( map ...

P1410 子序列 思路：看到最大是。就应该想到用写写。根据别人大佬的思路，我再来说说。。。首先我们可以假设为前位以结尾子序列长度为是否满足。但是我们用这一个递推是不能判断另外一个子序列是否满足的，因此我们需要用来表示前位不以结尾长度为的最后一位的最小值(根据贪心越小越有利后面的数)。这样就可以同时对两个子序列进行转移。 转移方程：,显然这是对以结尾的子序列进行更新的， 所以直接取 当，这说明前位不以结尾长度为的子序列长度可以进行更新。  最后判断一下能否到达即可。 初始状态：.其他初始化为。因为前一个字符不为结尾的序列就是空序列必然存在。 #include<bits/stdc++.h&...

P1939 【模板】矩阵加速（数列） 传送门 矩阵加速的难点就在于构造转移矩阵。 根据题目的提示显然我们的初始矩阵为  假设我们当前矩阵需要求的矩阵为 根据递推公式有 观察可得即为状态转移矩阵。 所以答案为   AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) ll n,t; struct Mat{ ll a[4][4]; Mat operator * (co...

莫比乌斯反演定理的证明。 初学给自己做个笔记，怕以后忘了。 前置知识：莫比乌斯函数的两个性质：    （这里证明用不到) 定理：若有定义在上的函数满足关系： ，则有： 证明：我们只需证上述等式右边等于左边即可。 ​  = （定义) (1) = (分配律) (2) = (的地位是可交换的) (3) = (结合律) (4) = (性质1) (5) 证毕。 如果这里还是看不懂请看下面。 对于的解释： 因为 可以理解为对每个的因子求出所有满足的,即二元组的个数。 举个例子：.     因为都是的因子，所以地位等价。 即条件可以改为 每个的因子求出所有满足的,即二元组的个数。     的解释： 显然当时...

求前个数因数和的三种方法。 纯暴力，对每个数，遍历 时间复杂度: #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<string> #include<cmath> using namespace std; typedef long long ll; const int N=1e5+5; #define mst(a) memset(a,0,sizeof a) int main(){ int n,ans=0,j;...

欧拉函数(学习笔记) 欧拉函数：,为的质因数。 . 每种质因数只有一个。 性质： 1.当为质数。 证明：显然当为质数,显然与互质。 ,当互质。 [特别地：当为奇质数时，] 证明:为积性函数，具体不详细证明。 3.当为质数的次幂。 证明：显然的倍数都不与互质，这样的数个数为 所以互质的个数为 当互质，且为倍数。 证明：根据公式有：,显然都为的质因子。 所以可改写为 接下来就可以用欧拉筛实现求欧拉函数。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; #defin...