__故人__

题解

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

/ 注册

全部文章 / 题解（共116篇）

Censoring

分析有一道加强版的题解这里。那道题要求有多个模板串。而这道题只有一个，那么我们可以通过来解决。考虑用栈储存路径，遇到完美匹配就返回步。时间复杂度为。代码 #include<bits/stdc++.h> using namespace std; const int N ...

2020-10-21

5 543

Book of Evil

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

2020-10-20

7 636

飞扬的小鸟

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

2020-10-19

7 759

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

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

题意从个位置中选出两两不相邻而且元素尽可能多的方案数。分析我们可以考虑递归有序列这个时候如果我们在末尾添加了新的元素，那么我们就可以在第或者第个选择一个。那么我们就有递推式。在时。特判一下就好了。最后输出因为我们对于最后一个元素可以选择也可以选择。代码 #...

2020-10-14

5 500

[ZJOI2006]物流运输

分析我们可以对于每一天考虑，如果有一天改了道，那么贪心的选择也应该是最短路，而不是其它的路径。这个还是比较显然的。那么现在考虑一个线性。令表示考虑从第天的最小代价和。那么转移为。这里引入了一个的数组。这里表示从第天到第天的合法的最短路。那么我们可以先预处理总的复...

2020-10-14

6 668

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

分析很套路的一道题，但是初始值初始时有点搞心态。主要是考虑到，很自然的想到用状压去维护。定义为当前节点在，已经过了的节点状态为。那么我们的转移也比较简单。那么我们只需要预处理即可。代码 #include<bits/stdc++.h> using namesp...

2020-10-13

6 655