塔子哥学算法

未归档

题解(1)

/ 注册

全部文章 / 未归档（共82篇）

ABC156:E-简单组合数学

传送门:https://atcoder.jp/contests/abc156/tasks/abc156_e 题目大意：给你n个房间，每个房间里一个人。一次移动可以使得一个人移动到除本身外的任意一个房间里去。问k次移动之后，房间有多少种组合状态。例如： n = 3 , k = 2. 状态有:(0,...

2020-09-17

0 714

知识点：曼哈顿距离相关

①最远曼哈顿距离 : 1.1:二维最远曼哈顿距离模板： ABC 178E 传送门:https://atcoder.jp/contests/abc178/tasks/abc178_e 两点间的曼哈顿距离为: 那它的结果可能有四种。取最大值即是它的结果: 稍微整理:将相同的点放在一个括号中得到： ...

2020-09-16

0 1010

bitset优化dp

核心:在于状态转移方程的状态只有0和1。可以将转移优化成位运算。一.NC32C简单瞎搞题传送门:https://ac.nowcoder.com/acm/contest/132/C?&headNav=www 题目思路： ,类似于:分...

2020-09-10

0 1067

根号分治，循环节，暴力-TopCoder-Flipingbits

题目大意：给你一个长度为 N (N <= 300) 的 01字符串,再给一个正整数M.每次操作可以将一个位置取反，或者将一个长度为M的倍数的前缀取反。问最少需要多少次操作，才能使字符串成为一个循环节为M的循环串. 题目思路:(未验证代码正确性) 发现制约关系: 循环节的长度与其在...

2020-09-09

0 821

图论，根号算法-三/四元环计数

算法大意：给你一张无向图，问你里面的三元环(a , b , c)的个数. 算法思路：复杂度的证明很像根号分治做法：记录度数，度数大的指向度数小的。度数相同的话编号大的指向编号小的。就原图变成一个DAG了。无环是显然的。然后对于每个点X，将出边记录下来,打标记。再对于X的出边的点，枚举出边，...

2020-09-08

0 941

好题:分层+同余最短路:HDU6071

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6071 题目大意：给你一个含四个点的带权环。问你从 2点走到 2点的权值>= k 的最短路. (边权 <= 30000 , k <= 1e18) 题目思路: 这题的思维难点在于:如...

2020-09-07

0 674

同余最短路-入门两题

P3403跳楼机传送门：https://www.luogu.com.cn/problem/P3403 题目大意：一个线段为[0,h - 1].你从0开始，每次可以朝任意方向走 x , y , z步。(前提是在线段内)。问你有多少个整数点是可以到达的。(x , y , z <= 1e5 ,...

2020-09-07

0 762

好题:KMP+动态规划:CF808G

传送门:https://vjudge.net/problem/CodeForces-808G 题目大意:给你字符串S,T。字符串S中有问号，可以随意填a ~ z 中任意一个字母。问你如何填使得T在S中出现的次数最多(可以重复匹配)。求这个次数。(S , T <= 1e5, |S| * |T| ...

2020-09-06

0 649

好题:KMP应用,数学-Om Nom and Necklace

传送门:https://vjudge.net/problem/CodeForces-526D 题目大意：对于字符串的每一个前缀，询问是否能够看成 k + 1 个 A 和 k个B交替形成的字符串。题目思路: KMP 找循环节 + 数学推导着实...

2020-09-06

0 692

Manacher+数据结构维护-2017哈尔滨A

传送门:https://vjudge.net/contest/391081#problem/A 题目大意: 给你一个字符串，让你统计其中两个等长且奇长的互相重叠组合而成的回文子串的个数. 题目思路:类似于HDU5371.都是Manacher+数据结构维护解法一：树状数组我们通过Manache...

2020-09-03

0 622