Skip to content

Latest commit

 

History

History
192 lines (144 loc) · 5.38 KB

Tg2ed_201807.md

File metadata and controls

192 lines (144 loc) · 5.38 KB
Raw

训练指南(蓝书or大白)完善计划

训练指南第2版再版计划(内容可能变更)

[TOC]

紫书部分代码仍然欢迎贡献，参考以下链接中的TODO List

贡献与要求

  1. 有兴趣的朋友可以进行贡献，出版之后前言内会提到你的名字，但是不承诺任何物质回报。 . 贡献较大的同学有机会参与后续其它书籍的编写，参与就有可能有少许物质回报。 . 所有的贡献请发送到 [email protected]以及[email protected]。注明标题，并且给出真实姓名。 . 贡献的类型包含：
    • 题目提供代码(尽量有详尽的注释以及良好的风格)
    • 题解，要求逻辑清晰
    • 试读，成文后召集
    • 优秀代码风格样例：
void splay(Node* &o, int k) { // 找到序列的左数第k个元素并伸展到根结点
 int d = o->cmp(k); // 看看第k个元素在整个树中的位置
 if(d == 1) k -= o->ch[0]->s + 1; // 第k个元素在o的右子树中
 if(d == -1) return; // 已经在根上了
 Node* p = o->ch[d]; // 第k个元素所在的子树
 // 第k个元素是在p的左or右子树→d2, 在这颗子树中的位置→k2
 int d2 = p->cmp(k), k2 = (d2 == 0 ? k : k - p->ch[0]->s - 1);
 if(d2 != -1) { // 不是子树的根，伸展到子树根
   splay(p->ch[d2], k2); // 伸展到子树的子树的根
   if(d == d2) rotate(o, d^1); // 一条直线，先把p转上去
   else rotate(o->ch[d], d); // 不是一条直线
 } 
 rotate(o, d^1); // 从子树根旋转到o
}

新增内容：

DP

数位DP

  • 例题:

  • 习题:

斜率优化DP

  • 例题:

  • 习题:

补充习题

  • 必做1: WF 2018 Problem J: Uncrossed Knight’s Tour

数学

积性函数和莫比乌斯反演

  • Count a*b, ACM/ICPC Changchun 2015, LA7184✔
  • Visible Lattice Points(Indian ICPC training camp)✔
  • Mophues(Asia Regional Hangzhou Online 2013)✔

习题:

  • NOI2016 循环之美 BZOJ 4652
  • SPOJ GCDEX2 - GCD Extreme (hard)
  • CodeChef COPRIME3: Coprime Triples

FFT(NNT)

  • LA6886 Golf Bot(SWERC 2014)
  • WF2015 LA7159 J Tile Cutting
  • 称糖果问题(Unequalled Consumption, NWERC 2005, LA3408)
  • LA8389 Asia 2017 Nakhon Pathom B-Festival in City (FFT&XOR)

习题?:

  • CodeChef POLYEVAL
  • CodeChef COUNTARI(BZOJ-3509)
  • BZOJ1919/CTSC 2010 - Optimize(d-分治&NTT)

数据结构

线段树

例题

  • 必做1: UVa Heap Manager （线段树+模拟)

  • 例题: 线段树合并

  • 习题:

可持久化数据结构

例题:

  • SPOJ MKTHNUM NEERC2004 Northern Subregion (主席树)
  • Version Controlled IDE, ACM/ICPC Hatyai 2012,UVa12538 (可持久化Treap)

习题:

  • 必做1: WC 2016. 鏖战表达式(交互题目, 可持久化Treap)
  • 必做1: UVa12827 - Just another pachinko-like machine
  • SPOJ – COT Count on a tree
  • BZOJ2653 middle
  • 可持久化链表 Persistent Linked List Ural 1992 CVS

倍增LCA

  • HDU2586 LCA模板

树分块

例题:

  • SCOI2005-王室联邦，树分块模板

习题:

树分治

  • 路径统计(点分治, POJ1741)
  • Ironman Race in Treeland, Kuala Lumpur 2008, UVa12161 点分治
  • 必做1: UOJ Round 2. 树上GCD

莫队

例题:

  • SPOJ DQUERY，基础莫队
  • 2120: 数颜色，莫队带修改
  • [SPOJ COT2 - Count on a tree II] 树上莫队

习题:

  • 必做1: WC2013 糖果公园 带修改树上莫队

树链剖分

  • Lightning Energy Report, ACM/ICPC Jakarta 2010, UVa1674
  • 题解编写

习题:

  • 必做1: Sunlight on a Tree LA7309(树链剖分+凸包合并)

虚树

例题

  • SDOI2011 消耗战 BZOJ2286
  • 题解编写

习题:

  • 必做 CodeChef BTREE. 经典的虚树题目

KDTree

例题:

  • 必做1: UVa12939 Keep Fit. 带修改莫队+KDTree 习题:

字符串

正文变更

  • 后缀数组-补充RadixSort内容介绍

后缀树&后缀自动机

例题

  • 必做1: CTSC 2010. 珠宝商(字符串相关，后缀树，后缀自动机) 习题
  • EC Final 2015(Suffixes and Palindromes) 差分约束，回文，后缀自动机

Manacher

  • HDU4513 吉哥系列故事——完美队形II √
  • 题解

Other??

  • 必做1: Asia - Yangon2016 LA7807 Tree Pendant.
  • 必做1: ACM-ICPC Asia 2017 Nakhon Pathom泰国赛区-Problem K Optimal Binary Subtree

几何

  • The 2017 ACM-ICPC Asia Tsukuba Regional Contest D题几何
  • 必做1: WF 2018 Problem G: Panda Preserve

图论

网络流

例题:

  • [CTSC2008]祭祀river 求最长反链：网络流例题❓
  • 必做1: WF 2018 Problem E: Getting a Jump on Crime

字符串

替罪羊树??

  • WC 2014. 紫荆花之恋 替罪羊树?

动态树??

离线算法??

例题：

  • BOI2007 摩基亚Mokia CDQW分治
  • ZJOI2013 K大数查询 BZOJ3110 整体二分