Fizzmy

分类

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 并查集(4) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章（共123篇）

第一篇博客

国际惯例水水水水水~~~~

2021-08-18

0 226

最短路算法

最近好虚啊，还是复习一下最经典的最短路吧 floyd太简单就不写了 qwq 写个堆优化dijkstra好了堆优化dijkstra算法 O(m + nlogn） #include<iostream> #include<cstdio> #include<algo...

2021-08-18

0 427

基础数论入门

（一）定理和性质一、裴蜀定理如果 a,b∈N a , b ∈ N , (a,b)=d ( a , b ) = d 那么一定存在 x,y x , y 使得 d|(a∗x+b∗y) d | ( a ∗ x + b ∗ y ) 证明：非常简单，鉴于可能有数论刚入门的OIe...

2021-08-18

0 571

[Hackerrank]Summing Pieces

Hackerrank World CodeSprint 7 Summing Pieces 传送门题目大意：给你一个数列把这个数列分成若干个子串求出所有分法的权值和（权值和的计算方式为：Σ每个子串的长度*每个子串的权值和）（n<=10^6）首先想到了一个n^2的dp 但是后来不...

2021-08-18

0 506

AtCoder Grand Contest 010D

vjudge传送门题目大意：给一个GCD为1的数列，有两个人每次选出一个数把这个数-1，然后把整个数列除以新数列的GCD，询问先手和后手哪个必胜。 Solution：不难看出这是一道博弈论，我们可以假设没有GCD的限制，那么我们怎么做呢？求数列的sum然后判断sum-n的奇偶性就可以了...

2021-08-18

0 554

[Hackerrank]hourrank 19-What Are the Odds?

Hackerrank hourrank 19 What Are the Odds? 传送门题目大意：两个人在玩一个叫做Nim game（n堆石头，每个人每次从一堆中选择一个或多个石头移走，最后不能移动的人输）的游戏，他们把这个游戏更改了一下，每次在游戏前先移除[L,R]区间内的石子(L&...

2021-08-18

0 303

Codeforces 875E-Delivery Club

传送门题意：有两个人，初始在不同的位置，他们需要按照顺序到一些点，求最短的最大相隔距离 n ≤ 1 0 5 n\leq 10^5 n≤105 Solution：看到“最短的最大”，首先考虑二分，深思熟虑之后发现可以二分+dp+数据结构优化，但是这个方法太难写了，通过观察cf上其他人的做法以...

2021-08-18

0 343

Codeforces875 F-神奇图论

Codeforces875 F-Royal Questions 传送门题意： n个王子，m个公主，给出第i个公主可以嫁给的两个王子ai,bi以及嫁妆，每个王子只能娶一个公主，公主只能在两个中选一个，求最大嫁妆。 Solution：这题乍一看是一个二分图匹配，但是思考良久发现不可做，于是...

2021-08-18

0 441

Lucas定理的应用

题意：有n盏灯环形排列，顺时针依次标号为1⋯n。初始时刻为0，初始时刻第i盏灯的亮灭a[i]给定，0表示灭，1表示亮。下一时刻每盏灯的亮灭取决于当前时刻这盏灯与顺时针方向下一盏灯的亮灭。若两盏灯状态相同，则下一时刻该灯灭，否则该灯亮。求时刻t第k盏灯的状态。（n，t，k≤1e7） Soluti...

2021-08-18

0 310

Codeforces626F-Group Projects-神奇状态之DP

题意：有n个商品，每件商品有一个价值，现在要把商品分组，求每组的最大价值与最小价值的价格差的和不超过m的分组种数。 Solution： DP，朴素的dp状态（f[i][j][k]表示前i件分成j组价格差为k的方案数）发现不好转移，所以说我们考虑找一个新状态：将所有数组排序，那么每一组的最大值...

2021-08-18

0 333