抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

前言

不再颓废,再战一年

学习内容

  • 状压 dp
  • 动态 dp

做题记录

21/06/01

  • P3829 [SHOI2012]信用卡凸包

旋转函数横纵坐标写反了有 50pts。。。

21/06/02

  • P3303 [SDOI2013] 淘金

f_{i, j, 0/1} 表示从小到大第 i 位,当前乘积为 j ,有没有卡着 n 的上界,顺推跑数位 dp。之后给每个元素记录一个指针,放进优先队列里面找结果。

21/06/03

  • P3694 邦邦的大合唱站队

状压 dp,考虑 S 为乐队排好的状态(0 为没有排,1 为排了),之后从小到大枚举状态,枚举最后一个位置的乐队

  • P1441 砝码称重

枚举每个状态然后 bitset

  • P3092 [USACO13NOV]No Change G

状压, f_S 为硬币状态 S 能买到最多物品的个数

  • P3052 [USACO12MAR]Cows in a Skyscraper G

状压,设 f g 两个 dp 数组求解

21/06/04

  • P2915 [USACO08NOV]Mixed Up Cows G

状压,状态内记入最后一个摆的牛(后效性) O(2^nn^2)

  • P3959 [NOIP2017 提高组] 宝藏

思路比较清奇的状压

21/06/05

  • P4719 【模板】"动态 DP"&动态树分治

动态 dp

21/06/06

  • SP1716 GSS3 - Can you answer these queries III
  • P5024 [NOIP2018 提高组] 保卫王国

动态 dp

21/06/09

  • UVA1336 修缮长城 Fixing the Great Wall

区间 dp,注意结果是向下取整

21/06/10

  • P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

线段树合并模板,注意一定是边遍历树边合并线段树边统计答案,因为线段树在合并之后就会发生奇怪的改变。

  • P3521 [POI2011]ROT-Tree Rotations

线段树合并

  • P3919 【模板】可持久化线段树 1(可持久化数组)

主席树初探

  • P3834 【模板】可持久化线段树 2(主席树)

静态区间第 k 小。对于每个位置都建上 [1, r] 的权值线段树(使用主席树),然后用差分的思想查询即可。

21/06/11

  • BZOJ #3545. [ONTAK2010]Peaks

并查集 + 权值树上二分

  • P2824 [HEOI2016/TJOI2016]排序

二分答案经典题

  • P5494 【模板】线段树分裂

线段树分裂。注意垃圾回收不要写炸

21/06/12

  • CF558E A Simple Task

线段树分裂,注意细节。

  • P5829 【模板】失配树

fail 树上的 lca

21/06/13

  • P4516 [JSOI2018]潜入行动

重在复杂度分析的树形背包, O(nk) ,转移方程平凡。需要注意细节的处理,要先复制一份 dp 数组,且注意 long long 问题。

  • CF490F Treeland Tour

线段树合并优化 dp

21/06/14

  • P3572 [POI2014]PTA-Little Bird

单调队列优化 dp。

  • P7114 [NOIP2020] 字符串匹配

Z 算法,思维好题。

评论




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme