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) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章 / 脑洞（共8篇）

Codeforces875 F-神奇图论

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

2021-08-18

0 435

Codeforces626F-Group Projects-神奇状态之DP

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

2021-08-18

0 340

AtCoder Regular Contest 089 E-GraphXY-构造题

题意：给一个n,m的矩阵dx,y,构造一张小于300个点的有向图，边上的权值范围为[0,100]，也可以是未知整数x或y，要求给出固定的S，T，当x分别取[1,n]，y分别取[1,m]时，S到T的最短路为 dx,y 1≤n,m≤10 1≤dx,y≤100(1≤x≤n,1≤y≤m) ...

2021-08-18

0 308

Codeforces217E Alien DNA -线段树+逆向思考

传送门题意：给你一个字符串，n个操作 [li,ri] [ l i , r i ] ,每次操作把区间内的字符串复制一遍并打乱接在后面，打乱的规则为： s1s2s3...sn−>s2s4s6...s1s3s5... s 1 s 2 s 3 . . . s n − > s 2 ...

2021-08-18

0 354

Codeforces 932E. Team Work-数学

传送门题意：给定n,k,求 ∑nr=1Crnrk ∑ r = 1 n C n r r k n<=1e9,k<=5e3 n <= 1 e 9 , k <= 5 e 3 Solution: 冥思苦想数论方式……..最后GG 题解让人眼前一亮：定义函数...

2021-08-18

0 380

CS Academy 71E.Losing Nim-dp+容斥

传送门题意：如果一个包含i个可重复元素的数组合法，那么这个数组中每个元素的取值范围是[1,n]，这i个元素的和为n，异或和为0。给出一个数n，对于 i=[1,n] i = [ 1 , n ] ，求包含i个可重复元素的数组的方案数，对p取模 n<=500,p<=2^30 ...

2021-08-18

0 299

AGC019 E.Shuffle and Swap-DP+NTT

传送门题意：给出两个01串A,b，记 ai a i 表示A中1的出现位置， bi b i 表示B中1的出现位置，将a数组和b数组打乱后依次次交换 Aai A a i 和 Abi A b i ，求有几种方式使得A=B 字符串长度<=10000 Solution：我们可以把...

2021-08-18

0 448

BZOJ5068: 友好的生物-枚举

传送门题意： n种生物，每种生物i有k个属性 ai,j a i , j ，两种生物之间的友好程度为 Friendliness=(∑k−1i=1Ci∗di)−CK∗dK F r i e n d l i n e s s = ( ∑ i = 1 k − 1 C i ∗ d i ) − C K...

2021-08-18

0 394