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) 题解(2)

归档

标签

去牛客网

/ 注册

全部文章 / 贡献法（共3篇）

[Hackerrank]Summing Pieces

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

2021-08-18

0 506

Codeforces 380E - Sereja and Dividing-贡献法

改编题意：有n杯水排成一行，第i杯水中有 wi 单位体积的水. 他会选择一个区间 [l,r] ，并拿一个初始为空的杯子（杯子的容积无限大），他可以重复无限次以下操作： • 选定任意一杯水i， i∈[l,r] ． • 使i和它拿着的杯子里的水的体积变为它们的平均值．小C希望进行若干操作...

2021-08-18

0 316

Codeforces 356E Xenia and String Problem-倍增+贡献法

题意：定义一种字符串gray串满足： 1.长度为奇数 2.正中间的字母只出现一次 3.左右两端相同，左右两端也是gray串一个gray串的贡献为这个串长度的平方现给你一个长为n的字符串，你可以修改至多一个字母，使得总贡献值最大 (n<=1e5) Solution: 可以...

2021-08-18

0 388