Chrety

分类

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

全部文章（共85篇）

BZOJ1832: [AHOI2008]聚会(LCA)

题目： 1832: [AHOI2008]聚会解析：偶尔做做水题挺爽的两两之间先求出LCA，发现至少有两个LCA是相同的，这个重复LCA也是深度最浅的那个，那我们就选择那个不重复的LCA，因为若选这个重复的LCA的话，这个重复的LCA到另一个LCA的路径会走两遍，反之只会走一遍三点间的距...

LCA 树链剖分

2019-08-19

0 484

BZOJ1799: [Ahoi2009]self 同类分布(数位DP)

题目： 1799: [Ahoi2009]self 同类分布解析：设\(f[pos][SumDigit][rem]\)为第\(pos\)位，各位数和为\(SumDigit\)，当前余数为\(rem\)的数的个数要求\(n\)可以被各位数整除，也就是\(n\%SumDigit==0\) 这个...

数位DP

2019-08-16

0 482

BZOJ3209: 花神的数论题(数位DP)

题目： 3209: 花神的数论题解析：二进制的数位DP 因为\([1,n]\)中每一个数对应的二进制数是唯一的，我们枚举\(1\)的个数\(k\)，计算有多少个数的二进制中有\(k\)个\(1\) 设\(n\)的二进制一共有\(num\)位，有\(sum[i]\)个数的二进制中有\(k\)...

数位DP

2019-08-15

0 566

BZOJ1040: [ZJOI2008]骑士(奇环树,DP)

题目： 1040: [ZJOI2008]骑士解析：假设骑士\(u\)讨厌骑士\(v\)，我们在\(u\)，\(v\)之间连一条边，这样我们就得到了一个奇环树（奇环森林），既然是一颗奇环树，我们就先考虑把环断开，设断开边边连接的两点是\(rt1\)，\(rt2\)，断环的话直接标记这条边不能...

DP 图论奇环树

2019-08-15

0 494

BZOJ1864: [ZJOI2006]三色二叉树(树形DP)

题目： 1864: [Zjoi2006]三色二叉树解析：用\(f[u][0/1/2]\)表示以\(u\)为根，颜色为绿/红/蓝时最多的数量转移没啥好说的 \(f[u][0] = max(f[l][1] + f[r][2], f[l][2] + f[r][1]) + 1\) \(f[u][...

DP 树形DP

2019-08-14

0 536

BZOJ1003: [ZJOI2006]物流运输(最短路+DP)

题目： 1003: [ZJOI2006]物流运输解析：最短路+DP 我们用\(no[i][j]\)来表示\(i\)在第\(j\)天不可以经过用\(cost[i][j]\)表示第\(i\)天到第\(j\)天的花费在最短路的时候判断一下在第\(i\)天到第\(j\)天中哪些码头不可以走，在...

图论 DP 最短路

2019-08-13

0 565

The Xor-longest Path(trie树)

题目： #10056. 「一本通 2.3 练习 5」The XOR-longest Path 解析：做完#10051后就不是很难了继续利用异或的性质有\(dis(u,v) = dis(1,u)\oplus dis(1,v)\) 把边权放到点上，然后字典树求最大异或值代码 #inclu...

trie树字符串

2019-07-29

0 654

Nikitosh 和异或(trie树)

题目： #10051. 「一本通 2.3 例 3」Nikitosh 和异或解析：首先我们知道一个性质\(x\oplus x=0\) 我们要求\[\bigoplus_{i = l}^ra_i\]的话，相当于求\[(\bigoplus_{i = 1}^la_i)\oplus (\bigoplu...

字符串 trie树

2019-07-29

0 589

P3121 [USACO15FEB]审查(AC自动机)

题目： P3121 [USACO15FEB]审查（黄金）Censoring (Gold) 解析：多字符串匹配，首先想到AC自动机建立一个AC自动机因为有删除和拼接这种操作，考虑用栈维护顺着文本串匹配的方向走，将经过的节点放入栈中，若匹配到一个模式串，就将这个模式串弹出，从栈顶开始继续走...

AC自动机字符串

2019-07-29

0 510

The XOR Largest Pair(tire树)

题目 The XOR Largest Pair 解析一年前听学长讲这道题，什么01trie，好高级啊，所以没学，现在一看。。。。看到xor就应该想到二进制，一看数据\(A_i< 2^{31}\)，考虑把所有的数都处理成长度为32的二进制数，插入字典树中，查询的时候就逐位比较，有不同的...

字符串 trie树

2019-07-27

0 596