一只橘橘猫

杭电多校

coderforces(20) dp动态规划(3) icpc(8) KMP算法(3) leetcode(1) STL(1) 人工智能(2) 优先队列(1) 图论(3) 字符串(5) 搜索(2) 数学(4) 日记(1) 最短路(3) 未归档(29) 牛客多校(11) 牛客寒假训练营2020(6) 牛客练习赛(8) 线段树树状数组(2) 贪心(4) 题解(25)

/ 注册

全部文章 / 杭电多校（共7篇）

杭电多校第五场 HDU - 6629

题意：扩展kmp的匹配次数。题解：扩展kmp就是：定义母串S和子串T，S的长度为n，T的长度为m；求字符串T 与字符串S的每一个后缀的最长公共前缀；直接用模板写就行了代码：#include <iostream> #include <cstdio> #i...

扩展kmp

2019-08-23

1 700

杭电多校第四场 HDU - 6623

题意：给出一个数n<=1e18,问你将其分解成整数的唯一分解定理后对应的质数次幂的最大值。题解：这题数据真的非常狗血。先用正常的中国剩余定理求出来前10001项的次幂，然后分类讨论，如果n的四分之一次方是整数，更新最大值4 如果n的三分之一次方是整数，更新最大值3，这里不能直接用po...

整数的唯一分解定理素数

2019-08-22

0 532

杭电多校第四场 HDU - 6620

题意：给出4*4的矩阵，问你数字拼图能否能复原成原来的样子。题解：当逆序对个数的奇偶性和完成时空格所在行和初始时空格所在行的的差奇偶性相同时才有解。代码： #include <bits/stdc++.h> using namespace std; int a[20]...

逆序对思维

2019-08-22

0 813

杭电多校第三场 HDU - 6608

题意：题目给出一个数字P，让你找到一个小于P的数字Q，然后输出Q!%P即可。题解：威尔逊定理：那么式子就成了那么问题就成了求Q喽，注意求阶乘的时候用快速乘，否则会超时。代码：#include <bits/stdc++.h> using namespace std; #d...

威尔逊定理快速幂

2019-08-22

0 574

杭电多校第二场 HDU - 6601

题意：给出n个木棒，每次询问区间[l,r],问你选择任意三根木棒能够构成的最大的三角形，如果不存在三角形，输出-1 题解：肯定都知道三角形的三边的定理，任意俩边之和大于第三边，假设从最小的三角形都不匹配， 1，2，3，5，8，13，，，，形成了斐波那契数列，第44项超过1e9，那么只需枚举前...

斐波那契数列主席树

2019-08-22

0 605

杭电多校第一场 E - Path

题意：给出一个无向连通图，每条边的权值都是1，可存在重边，a在1节点，b在n节点。问你最少花费多少代价能将1到n的路径最远，如果不存在路径，输出0就行题解：先求出最短路，然后保留所有满足 dey dex = ew 的边，对于新的图求 1 到 n 的最小割即为答案，最小割模板第一次用。代...

dfs 网络流最小割

2019-08-22

0 749

杭电多校第一场 D - Vacation

题意：给出n+1辆车，给出每辆车距离动物园的距离，速度，车长度，距离动物园最远的是你所在的车，当前后俩车相遇的时候，会合并，并以速度较小的车的移速接着行驶，问你自己的车车头到达动物园需要多少时间。题解：这题一开始想着模拟，但确实有些麻烦。简单做法，也是最神奇的做法：最终通过停止线的时...

思维

2019-08-22

0 541