__故人__

分类

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20) 题解(117)

/ 注册

TA的专栏 52篇文章 0人订阅

30篇文章 846人学习

22篇文章 1707人学习

全部文章（共169篇）

Book of Evil

分析我们有一个性质，树的任意一个点到树另外一个点的最长距离，一定是由某一个直径的端点和该点构成的。有了这个性质。我们只需要对这几个特殊的建一个虚树。然后找到直径的端点，那么答案为这个做三次就好了。代码非常简单，因为我们不用真正的建出虚树。关于定理的证明，下文全选自网站。引理：在...

2020-10-20

7 636

飞扬的小鸟

分析我们可以先定义状态为在第列，第行所需要的最小点击次数。那么我们有如下转移这个是如果选择点击的转移。这个是不点的转移。那么我们通过滚动数组的技巧，第一种的转移优化到。然后对于的时候特判一下就好了。时间复杂度为。对于障碍物我们直接赋值。代码 #include&...

2020-10-19

7 759

关于通配符的单模式串匹配来自专栏

引入给你两个字符串。询问是否匹配。其中含有通配符。可以匹配任意一种字符。分析如果我们使用最常见的字符串匹配算法我们发现，对于的处理是非常复杂度的。这个我们引入一个函数。叫做字符串的距离函数。那么我们定义。这样如果我们把看做完全匹配的话，如果 ...

2020-10-18

2 705

多项式开根号来自专栏

引入求出多项式是满足系数对一个数取模。推导还是利用牛顿迭代。那么代入牛顿迭代的公式为然后没有学习过牛顿迭代的朋友可以看我上一篇。当然这下面这份代码不能解决的情况。那个时候应该使用二次剩余。代码 #include<bits/stdc++.h> using ...

2020-10-16

3 975

多项式快速幂来自专栏

引入求出满足的多项式。做法既然可以快速幂求，其实多项式也是可以的。那么总的复杂度为其实这个好写，常数也小，一般不会被卡。我们可以对一个多项式求和。那么求出。之后在做一次就可以了。记住，如果下面给出的代码并不能通过。代码 #include<...

2020-10-15

5 1087

多项式exp 来自专栏

引入求解系数对一个数取模。前置知识泰勒展开，这个相信学习过高数的朋友都知道。牛顿迭代，我们可以通过牛顿迭代找出一个函数的零点，当然这个是有一定限制的，这个可以百度搜一下。换句话就是已知，要求求出满足的多项式。考虑倍增，如果我们已经知道。那么根据泰勒展开因为的...

2020-10-15

4 647

Quasi Binary

分析直接贪心，没有什么思维难度。主要是考虑到贪心的选取更少的元素。那么元素个数为其中。那么考虑如果分解完后仍然这一位有，那么。代码 #include<bits/stdc++.h> using namespace std; int a[100],n,L,Ans...

2020-10-15

6 742

2020牛客国庆集训派对day2 F 来自专栏

题意分析开放式求和推导之后。因为偷懒，直接上了。代码 T=int(input()) for i in range(T): n=int(input()) b= ((n*(2*n+1)*(n+1))//6 + (n*(n+1))//2)//2 print(b*...

2020-10-14

5 484

2020牛客国庆集训派对day2 E 来自专栏

题意求两个矩阵的乘法。分析我们其实只需要知道矩阵乘法要求两个矩阵，第一个的大小为，第二个的大小为。那么才能进行乘法。而乘法的计算方式就在题面上。代码 #include<bits/stdc++.h> using namespace std; const int N = ...

2020-10-14

4 603

2020牛客国庆集训派对day2 D 来自专栏

题意求一棵最小生成树。分析就只是单纯的求一个最小生成树。代码 #include<bits/stdc++.h> using namespace std; const int N = 510*510; #define LL long long const int inf = 0x3f...

2020-10-14

5 606