塔子哥学算法

分类

未归档(82) 题解(1)

/ 注册

全部文章（共83篇）

ABC156:E-简单组合数学

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

2020-09-17

0 515

知识点：曼哈顿距离相关

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

2020-09-16

0 784

E-字串-树状数组+差分做法

传送门：https://ac.nowcoder.com/acm/contest/7329/E 题目大意:给你一个长度为1e6的排列,让你统计区间[L,R]是一个值域为[L,R]的排列的区间个数. 昨天比赛的时候看了一下题目以为是析合树，就没写了emm，其实正解思路很简单。。题目思路: ...

树状数组二分扫描线思维

2020-09-12

6 661

bitset优化dp

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

2020-09-10

0 767

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

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

2020-09-09

0 637

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

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

2020-09-08

0 641

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

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

2020-09-07

0 509

同余最短路-入门两题

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

2020-09-07

0 570

好题:KMP+动态规划:CF808G

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

2020-09-06

0 460

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

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

2020-09-06

0 504