summary-tests

Table of Contents

<mo> NOIP2016

<2016-06-06 Mon> (180 / 140+) [3/3]

DONE T1 (60 / 0)

At the beginning of the exam, I thought that the edge is undirected, then it was an easy problem. Just made a spanning tree. But the graph is directed… then I didn't know how to solve.

If we make a new graph whose edge is the difference between the same edges (no abs) the input gives you, then for any path of two nodes, their length is the same.

Just dfs the graph and check each edge.

DONE T2 (100 / 100)   fenwick

At the beginning of the exam, I thought that the position of the center of each circle wasn't limited (but in fact, it is always at (0, 0)). It took me a lot of time. In fact, this is an easy problem.

DONE T3 (20 / 40)   network_flow

The number of each kind of objects is '1000'. So I thought if some tasks might cause the number smaller than '0'. Then… a subtask can't be solved easily. But 'n' is at most '1000' and each task can only decrease by one for each kind of object… the number will never be smaller than '0'.

The gragh is DAG, so we can use 最大权闭合子图 to get the best scheme. But we have at most 5 kinds of objects… how to set the flow and cap? One way is like this: for "+-\", we set the val on 1 * (1001 ^ 2) + (-1) * (1001 ^ 1) + 0 * (1001 ^ 0), it means one second object is greater than 1000 third objects. Then we just do network-flow.

How to print the scheme? Which node 'S' can reach is a part of the best scheme. Just calculate out the 'dis' and then we can get the ans.

<2016-06-07 Tue> (92 / 182+) [3/3]

DONE T1 (10 / 100)   greedy

Junk problem… Just greedy. But I coded DP, and there are some mistakes in getting the rank of schemes. I just sorted them, but I forgot to deal the same schemes. (If a scheme 'a' is as good as 'b', the result of sorting is 'a' < 'b' or 'b' < 'a', then 'rank['a'] != rank['b']'. It's wrong.) I just get 10 point…

DONE T2 (50 / 50)   slope_optimization

I didn't have enough time to find the way optimizing the DP. I just do it in $ O(n ^ 4) $. We can find that for status (x, y), the best scheme must from status $ (x - 1, j), j < y $ or $ (j, y - 1), j < x $. Then slope optimization is available.

DONE T3 (32 / ?)   DP segment_tree heap divide_and_conquer

I didn't have enough time to solve it. Just optimize the DP \(dp_i = min\{dp_j + max\{a_{j+1...i}\}, pre_i - pre_j \leq m\}\). Just use data structure.

<2016-06-10 Fri> (180 / 250) [3/3]

DONE T1 (10 / 80)   suffix_array hash

This is a scary problem. In the begining of the exam, I thought I could use suffix array with binary search to solve it. But when I coded it, I did't have enough time, so I just write a code solving it in O(n ^ 2) (but I just get 10 points instead of 80)

for a repetition string, there is a property:

string: ----–—|----–—| new look: 1__^2_|_3__^4_| position: __i________M

For position i and M in the string ($ abs(i - M) = (L / 2) $) we find that $ (1) = (3) $ and $ (2) = (4) $. The problem is how to make sure $ (1) = (3) $ and $ (2) == (4) $. Just divide and conquer. use hash or suffix array to get LCP to solve it.

DONE T2 (70 / 70)   network_flow

I just used 状压DP in the exam, getting 70 points. The std is network flow.

We can find that if we add edge from every node to adjacent node, the graph is a bipartite graph. And the nodes we choose must be 独立集 (base on bipartite graph). Then the problem is: 带权最大独立集. Use dinic to solve it.

DONE T3 (100 / 100)   DP

I had a dream, then I AC the problem. (but I spend 2h30min…)

In the first, I thought all the odd (without $ 1 $) is the same as $ 3 $, and all the even is the same as $ 2 $. But it is a wrong conclution.

If we consider all the even (without $ 2 $) as $ 4 $, it is right. Then just DP.

<2016-06-11 Sat> (85 / 165) [3/3]

DONE T1 (15 / 100)   greedy binary_search

This problem is the same as NOIP2007 守望者的逃离 , but the data is stronger. Just binary search.

But in the exam, I thought he can fly 120m in 6s. It is wrong! He needs to spend 5s recovering and 2s flying! (That's why I only got 15 points…)

DONE T2 (50 / 50)   farthest_node_pair

My algorithm in exam is in O(n ^ 3) (due to floyd. I used this to get the length of diameters). I just found all the diameters of the tree and update the answer. But we can prove that we can get answer from any diameter.

DONE T3 (15 / 15)

A hard problem. If a number cannot be pushed into any stack, then we cannot get a solution from this status. But why it cannot be pushed? Maybe the top of both two stacks is smaller than this number. If we push it, it is impossible to pop the small number before this number (which is greater) popped.

For two number $ x, y (x < y) $, if $ x $ is in front of $ y $ and $ x $ has no chance to be popped before pushing $ y $ (only when existing a number smaller than $ x $ but smaller than $ y $), they cannot be pushed into the same stack.

Then we can make a graph: if $ x $ and $ y $ cannot be pushed into the same stack, then AddEdge(x <–> y). We have two stack, so if the graph we make is a bipartite graph, we can 二分染色. Different color means different stack.

But the size of edges is $ O(n ^ 2) $, too large for the worst status. In fact, many edges are no need. For example, if a edge is in a circle, it cannot influence 二分染色 if the graph is a bipartite graph. Then we can throw it away and the circle also disappeared, but the edges are fewer. We can prove that only $ O(n) $ edges are needed for binary graph. But if it is not binary graph, we will find this situation when we try to get a scheme.

The only problem is how to make edges fewer. there is a good way: http://debug18.com/solution-to-noip2008-twostack-enhanced/

<2016-06-12 Sun> (165 / 200) [3/3]

DONE T1 (10 / 0)

In fact, this is an easy problem, time was not enough in the exam.2 We find that, any scheme is like this:

``` There are three kinds of edges.

  1. never be visited;
  2. be visited once;
  3. be visited twice;

And the 2nd kind must make up a path. ```

For every nodes we visited:

  1. if it is visited by the 2nd kind, the cost for $ m $ is $ 1 $;
  2. if it is visited by the 3rd kind, the cost for $ m $ is $ 2 $.

So, to make more nodes visited, we should visit the node by the 1st way as much as possible. The best path must be a diameter! If diameter is $ L $, then our ans is min{n, m + 1, L + (m - L) / 2 + 1}.

DONE T2 (100 / 100)   math

This is a easy problem. Just calculate the contribution of $ 2 $ and $ 5 $. one $ 2 $ and one $ 5 $ can get one $ 10 $, a zero in the tail of the number. the number of $ 5 $ must be smaller than $ 2 $, so just calculate the contribution of $ 5 $.

For $ 5 $, these numbers have contribution: $ 5 * 1, 5 * 2, 5 * 3, 5 * 4, 5 * 5, … $ For $ 5 ^ 2 $, contribution: $ 25 * 1, 25 * 2, 25 * 3, 25 * 4, 25 * 5, … $ For $ 5 ^ 3 $, …

Calculate the sum.

DONE T3 (55 / 100)   fenwick_tree

In the exam, I thought I AC this problem… But the DP val is bigger than LONGLONGMAX in the worst situation!

First, DP. $ dpi, j $ means when $ c1 = i, p = j $, How many scheme there are. It is easy to get all the dp val with fenwick-tree.

For each query, get $ c1 $ by binary-search, and if we know $ c1 $, it is easy to get $ c2 $ by binary-search, and so on. But the memory is limited if we do it one by one. Just calculate the ans of all the query together, from $ c1 $ to $ cp $.

<2016-06-25 Sat> (250 / 250) [3/3]

I got the scores I expected!

DONE T1 (dna) (100 / 100)   DP

I spent some time (about 40 minutes) thinking a wrong algorithm. The right algorithm is consider a block of $ 1 $ as a same part. Then use DP.

DONE T2 (divpair) (100 / 100)   math

Math problem. Spending at least 1h30min. Just divide the problem into two sub-problem:

  1. a + b <= (n + 1) / m * m
  2. (n + 1) / m * m < a + b <= (n * 2) / m * m

But in exam, I just thought out the 1st situation in the beginning; I didn't pass the sample! For example, when $ n = 4 $ and $ m = 6 $, $ m < n * 2 $. But for all the pair $ (a + b = m) { (1, 5), (2, 4) } $, $ (2, 4) $ is OK but $ (1, 5) $ is not, because $ n < 5 $. For 1st situation, there won't be this problem, but in 2nd situation there will be this problem.

DONE T3 (kosare) (50 / 50)   DP 状压 容斥

This problem is a little hard… Solution: http://fuboat.leanote.com/post/problem-SPOJ-KOSARE-solution.

<2016-08-15 Mon> (130 / 140) [3/3]

DONE T1 团子大家族 (clannad)

题目大意

给你 n 种颜色的团子,以及每种颜色的团子的数量,要你构造一种排列方法,使得相邻的团子颜色不同.

分析

记团子的总数为 m. 如果存在某颜色的团子的数量为 x, 且 x > n - x + 1, 无解. 考虑贪心.首先选出数量最多的颜色,放在最前面,剩下的是一个子问题,但是下一个团子的颜色不能是之前选的.如果数量最多的仍是原来的颜色,则选数量次大的颜色. 可以证明只要初始合法,就可以得到解.

DONE T2 主线剧情 (story)

题目大意

给你有 n 个点, m 条边的无向图,要你给每一条边定向来得到一个DAG, 要你最小化所得到的 DAG 的最长路并输出. (n <= 17)

分析

对于 DAG 的最长路, 我们可以从入度为 0 的点开始,对 DAG 进行分层, 将分出的结点去掉, 重复前面的步骤, 直至图空. 可知每一层的结点两两之间无连边, 且最长路就是 层数 - 1. 至于这道题,我们也可以暴力枚举每一层是什么, 保证枚举到的结点没有连边即可.把这些点去掉, 剩下的点构成一个子问题. 记忆化,每次取所需层数最少的方案即可. 输出 层数 - 1.

DONE T3 点燃的火焰 (flame)

题目大意

这里有很多条长度不一粗细均匀的绳子,对于任一一条绳子,我们可以把它的一端或两端点燃,并且会沿着绳子每秒钟烧去一个单位长度. 现在把这些绳子拼成一棵有 n 个结点, n - 1 条边的树, 其中绳子作为树的边. 现在你可以点燃树的一些叶子结点, 使得整棵树被烧光. 问题是: 如果用这棵树计时, 可以烧出多少种不同的时间. 输出种数和前 1000 小的不同的时间. n <= 500.

分析

注意到答案只可能是某两个叶子结点的 距离 或 距离 / 2. (考虑树最后是怎么被烧完的) 所以枚举这两个叶子结点,默认点燃它们.对于其他的叶子结点,我们贪心地选: 只要不会使树提前烧完,就点燃.(这样可以尽可能使答案是 两叶子结点的距离) 然后多源最短路求出时间, 累加到答案中即可.

<2016-08-17 Wed> (260 / 260) [3/3]

DONE T1 matrix   组合数

题目大意

对于 i > 0, j > 0, 定义 F(i, j) = a * F(i - 1, j) + b * F(i, j - 1). 现在给你 F(0, 0), F(0, 1), F(0, 2), … , F(0, n) 和 F(0, 0), F(1, 0), F(2, 0), … , F(n, 0), 要你求 F(n, n). n <= 100000.

分析

将 F 写成矩阵的形式, 那么 F(n, n) 就在 第 n 行, 第 n 列. 我们考虑每一个给定的数对 F(n, n) 的贡献. 我们可以认为, F(i, j) -> F(i + 1, j) 对应在矩阵中向下走, F(i, j) -> F(i, j + 1) 对应在矩阵中向右走. 那么, 每向下走, 贡献会乘以 a; 向右走, 贡献乘以 b. 我们对于给定的数求出 每条到 (n, n) 的路径和路径的条数即可.

DONE T2 value   DP sort

题目大意

n 个物品, 每个物品有两个属性 \(v_i, w_i\), 如果拿走了一个物品, 那么我们可以得到 \(v_i\) 的价值, 但同时其他物品的价值都会减去 \(w_i\). 最大化得到的价值. n <= 5000.

分析

如果我们确定要选某一些物品, 那么拿走的顺序显然是先拿走 \(w_i\) 小的. 我们如果将物品按 \(w_i\) 排序, 那么对于任一一种选法, 排在前面的肯定先拿走. 再观察发现: 如果我们可以得到某一个物品是倒数第几个被选的, 我们就可以预先选出 \(w_i\) 对答案的影响. 设 DP(i, j), 表示一共打算选 i 个物品, 已经拿走了倒数 j 个物品时 当前最大的价值. 然后枚举每一个物品并更新即可.

DONE T3 binary   树状数组 二进制

题目大意

维护一个序列 a1..n, 支持两种操作:

  1. Modify (x y): 将 ax 改为 y
  2. Query (x y): 查询 \(\sum_{i=1}^{n} (a_i + x)~and~y\)

n <= 100000. x, y <= 2 ^ 20.

分析

对于 y, 我们考虑将 y 的二进制下每一位上为 1 时的贡献分开考虑. 假设 y 的第 j + 1 位为 1, 那么这一位对答案的贡献就是: \[2 ^ j \times \sum_{i=1}^{n} [(a_i + x)~and~2^j \neq 0]\]

我们考虑哪些数字 x 满足 \([x~and~2^j \neq 0]\). 我们发现, 当 \(x~and~(2 ^ {j + 1} - 1) \in [2 ^ j, 2 ^ {j + 1}\) 时满足. \(x~and~(2 ^ {j + 1} - 1)\) 其实就是只保留后 j + 1 位.

对于原题, 贡献就是: \[2 ^ j \times \sum_{i=1}^{n} [(a_i + x)~and~(2^{j+1} - 1) \in [2 ^ j, 2 ^ {j + 1})]\] 变化一下: \[2 ^ j \times \sum_{i=1}^{n} [a_i \in [2 ^ j - x, 2 ^ {j + 1} - x)~(mod~2 ^ {j + 1})]\] 后面的问题就是查询一段区间内有多少个数. 建值域线段树即可. 树状数组也可以. 由于 j 的取值有 20 种, 开 20 棵即可. 修改也很容易.

<2016-08-19 Fri> (220 / 200) [1/1]

DONE T3 飞扬的小鸟 (bird)

题目大意

这里有 n 种鸟和 m 个洞,每种鸟都有一定的数量, 每种鸟经过某个洞所花的时间都是特定的. 现在, 每一只鸟都要飞进任意一个洞, 每个洞每次只能有一只鸟进入, 其他要进这个洞的鸟只能等待. 最小化每一只鸟进洞所花费的时间(包括等待的时间和进洞所耗的时间)之和.

分析

多物品问题,考虑网络流. 首先,解决每一只鸟对答案的贡献: 如果这支鸟是倒数第 k 个进洞的, 进洞所耗时间为 t, 那么对答案的贡献就是 t * k. 注意到在任意方案中非, 对于同一个洞, 倒数第 k 总是唯一的. 我们把每一个洞的拆成多个洞, 分别表示 倒数第 1 个进洞, 倒数第 2 个进洞, … , 倒数第 sum 个进洞, 然后用费用流. 费用设为对答案的贡献即可.

<2016-08-21 Sun> (140 / 240) [1/1]

DONE T2 跳楼机 (srwudi)   mod 最短路

题目大意

这里有一幢 h 楼的大楼, 你现在在 1 楼的跳楼机上. 跳楼机有 4 种操作:

  1. 向上跳 x 层
  2. 向上跳 y 层
  3. 向上跳 z 层
  4. 跳回 1 楼

任何时刻不能超过 h 层; 问你能到达的楼层的数量. x, y, z <= 10 ^ 5, h <= 10 ^ 18.

分析

不妨记 \(d_i\) 为 通过操作 1, 2 到达的最小楼层, 满足该楼层 除以 z 的余数为 i. 显然, 所求的值为: \(\sum_{i=0}^{z-1}\frac{(h-(d_i+1))}{z}\) 问题是怎么求 \(d_i\). 注意到 \(d_i\) 可以转移到 \(d_{i+x}\) 和 \(d_{i+y}\), d 值分别增加 x, y. 由于是最小化 d, 跑最短路就可以了.

<2016-08-23 Tue> (100 / 280) [1/1]

DONE T3 恶魔 (qmras)

题目大意

<mo> NOIP2016-autumn

<10-25> (175 / 230) [3/3]

首先, 这三道题只有 T3 稍有难度. 其次, T1 的复杂度在考场上没有正确分析. 再次, T2 为分类讨论题, 没拍挂飞. 因此, 为求稳妥, 要么自己造数据手玩, 要么打暴力对拍.

DONE T1 circle (100 / 100)   因数分解

题目大意

给你一个长度为 n 环, 环上每个元素都有一个权值. 现在你要将它划分为 K 份, 对每份求和, 最大化它们的 gcd. 要求输出 K = 1, 2, 3, … , n-1, n 时最大化的 gcd.

分析

首先, 答案一定是元素之和的约数. 不妨枚举约数 x, 从环上任意一个位置出发, 断环, 按前缀和模 x 的结果统计最多能分多少份即可.

DONE T2 chocolate (45 / 100)   树形DP

题目大意

给你一棵树, 树上每个结点有一个权值, 请找出两条不相交的树上路径, 使得点权之和最大.

分析

直接树形DP即可.

DONE T3 city (30 / 0)   LCT 整体二分 并查集 边双

题目大意

给你一个图, 每条边有一个边权. 如果想要经过这条边, 则你的魔法值必须大于等于边权的值, 否则该边不可用. 现在给你一个询问 (u, v), 要求你输出使得 u, v 之间有至少两条不重复的路径 所需要的魔法值.

分析

可见这是边双. 最简单的思路就是将边按边权从小往大加, 如果某一时刻 (u, v) 在同一边双中, 则答案为当前的边权. 但判断是否在同一边双中要枚举所有询问. 不妨用 KRUSKAL 的思想, 构造出虚树, 倍增即可.

也可以对询问整体二分. 但为了保证每一个点联通, 以方便递归二分, 需要求出最小生成树, 然后将树边删掉. 对于每个分治结构, 将边权为 [l, mid) 的边用于合并边双. 这个可以建出树来, 打一下合并标记, 表示是否与父亲合并; 然后对于询问, 同一边双的边往左, 否则往右, 并且把结点编号改为合并后的编号. 继续递归即可.

<10-26> (130 / 130) [0/3]

T2 没想出 80 分还是太弱了. 方案算重没想到容斥还是太弱了. 原以为这种状态比较简单的 DP 题已经得心应手, 现在看来完全不是. 从一开始就想着肛 100 分, 但一步到位难度很大呀. T3 德州扑克伤不起啊…

TODO T1 (100 / 100)

TODO T2 (30 / 30)

TODO T3 (0 / 0)

<10-28> (150 / 220) [0/3]

考炸了… T1 只给 1MB 的空间, 垃圾题目… 由于 没判3个数相同的情况 + 没按大小输出, 爆 40 了… T2 原来可以用 抽屉原理 + 暴力值域线段树 来做哦… 不过主席树也算是一种可行的做法呢. (可惜耗了我 1h30min +, 哪有时间仔细想 T3) T3 利用结论做决策 + SMT 维护最优决策 ? 结论想到了, 完全没想到用 SMT 优化… 20 分的暴力还因为没判不选炸成 10 分了.

TODO T1 (40 / 100)

TODO T2 (100 / 100)

TODO T3 (10 / 20)

<10-29> (270 / 300) [0/3]

原以为 AK 了呢. 完全没有注意到附加文件 README.txt. 里面已经强调了 T3 数据范围的更改. 的确是自己的疏忽. 考试过程中试题的修正也是要引起注意的. 不过就算自己看到了也不会做…

TODO T1 (100 / 100)

TODO T2 (100 / 100)

TODO T3 (70 / 100)

<11-01> (200 / 200) [0/3]

T2 爆零被 D 了… 虽然 T1 耗了点时间, 但 T3 A 的很快, 所以 T2 还是有 1h 的时间去做的. 无奈推式子时的错误实在太多了, 改题时几乎是把所有的代码重写了一遍. 有很多错误真的是显而易见啊. 大概是因为打的时候感觉是对的, 便没有仔细想了.

TODO T1 (100 / 100)

TODO T2 (0 / 0)

TODO T3 (100 / 100)

<11-02> (160 / 160) [0/3]

今天得分很整齐呢. 180*2 + 160*12. T2 的确是想到了容斥, 但是如何容斥却毫无思绪. T3 要我求什么就算什么, 果然太听出题人的话了. 将要求的东西补集转换一下, 至少高分暴力会好打很多.

TODO T1 (100 / 100)

TODO T2 (40 / 40)

TODO T3 (20 / 20)

<11-04> (300 / 300) [0/3]

T1 是道数学题. 其实仔细推一推式子, 注意互质和整除两个条件的运用就很简单了. T3 挺有意思的. 二维 DP 的时候, 留意一下就会发现 DP 值有很多重复. 所以每次只要算不重复的部分就行了.

TODO (100 / 100) T1

TODO (100 / 100) T2

TODO (100 / 100) T3

<11-05> (250 / 250) [0/3]

T1 不会做爆 50 了… 怎么这么弱…

TODO T1 (50 / 50)

TODO T2 (100 / 100)

TODO T3 (100 / 100)

<mo> HNOI2017

<2016-08-27 Sat> (100 / 200) [3/3]

做题的速度太慢了, 主要是调试确实花了不少时间, 调暴力的时间开销不可忽略. T1 题目理解错误. 题面本身并没有什么问题, 主要是自己的主观想法导致的. T2 暴力都没有去打. T3 所想到的方法过于复杂, 严重增加代码长度和调试难度.

T1 大胖吃花生 (0 / 100)   heap

题目大意

给你一棵无根树, 每一个结点上都有一定数量的花生. 你每天必须吃掉某一个结点上的所有花生. 你可以通过树上路径到达某一结点, 但前提是这条路径上的所有结点都已经没有花生. 如果你在第 i 天吃掉了 x 个花生, 那么你将获得 i * x 的享受度. 多组询问, 每组询问告诉你你初始所在的结点, 要你输出最多能得到多少享受度. 结点数 n <= 30000, 任意结点花生个数 <= 300, 询问数 <= 10.

分析

乍一看毫无思路. 无疑, 这就是一个先选和后选的问题. 也许特殊的结点会有特殊的要求. 假设以初始点为根. 考虑整棵树中花生数最少的结点 u. 无疑, 要吃这个点, 则它的祖先要全部被吃完. 而显然, 最优解中, 当 u 的父亲被吃后, 下一个吃的一定是 u. 先吃 u 一定比后吃 u 优. 但问题是, 当 u 的父亲还没有被吃时, 我们应该吃谁. 不妨考虑合并结点: 每一个结点用二元组 (size, sum) 表示, 分别代表 合并之前有多少结点 和 被合并结点的花生数之和. 则 sum / size 可以用于表示合并后的结点的花生数. 可以用数学归纳法证明. 所以, 如果选了结点 v 后必然选 结点 u, 我们就将 u, v 合并并产生新的二元组. "花生数最少" 用堆维护即可.

T2 题目 (0 / 0)   phi

题目大意

在 n * n 的网格中画 凸多边形, 并要求将该凸多边形旋转 90 度后和原来一样. 求该凸多边形边数最大是多少. 有 T 组数据, T <= 1e5. n <= 1e18.

分析

先考虑解决 "旋转 90 度和原来一样" 的限制. 这其实就是要将凸多边形分成 4 个完全相等的部分, 每一部分都是残缺的凸多边形. 所以我们只要算出一个部分的最大边数就能得到答案.

再考虑解决凸多边形的限制: 这意味着在每一部分中斜率单调递增或递减. 容易想到, 我们只要保证边的斜率互不相等即可. 然后我们将边按斜率排序后依次拼接就能构造出凸多边形. 由于是网格图, 任何一条边都可以用 长为 x, 宽为 y 的矩形 (x, y) 的对角线表示. 只要保证不存在两条边 (x1, y1), (x2, y2) 满足 x1 / y1 = x2 / y2 即可. 如果要在这两条边中选一条, 则我们选 x 较小的更优. 这会比选另一条边构成的凸多边形更小, 且边数不变. 显然, 对于所有满足 x / y = k 的边 (x, y), 最优的 x, y 应满足 gcd(x, y) = 1.

再考虑解决 n * n 的大小限制. 对于每一部分中的所有边 (xi, yi) , 应满足 \(\sum x_i + y_i \leq n\).

不妨枚举所有满足 gcd(x, y) = 1 的 (x, y), 并按 x + y 排序, 然后从小到大选, 直到刚好满足 \(\sum x_i + y_i \leq n\). 更好的办法: 记 d = x + y, 枚举 d, 计算有多少 x 满足 gcd(x, d - x) = 1. 显然则这等价于 gcd(x, d) = 1. 显然, 满足条件的 x 有 phi(d) 个.

这就很简单了. 求一下 phi(x) * x 的前缀和然后二分, 剩下的部分直接用除法计入贡献即可. 事实上, 这个前缀和的增长速度很快, 预处理前 3e6 个即可.

T3 没给钱 (100 / 100)   HLD LCT

题目大意

给你一个无向图, 要你维护两种操作:

  1. 输入 u, v, 表示砍掉 u, v 之间的一条边. 保证此时有连边.
  2. 输入 u, v, 要你输出 从 u 到 v 有多少条边是必经的.

保证图任意时刻都是联通的. 可能出现 重边 和 自环. 可离线. 点数 <= 3e4, 边数 <= 1e5, 询问数 <= 1e5.

分析

我们考虑把删边倒序处理, 转为加边. 假如我们求了最终图的 一棵生成树, 那么 u, v 之间的必经路数就是边数. 我们每加一条边, 那么 这条边和树边构成的环 上的所有边都不是必经路. 不妨给每条边记一个标记表示 是否为必经路. 加边时把环上所有树边边的标记清为 否 即可. 用 HLD 或 LCT 维护.

<2016-09-01 Thu> (155 / 215) [3/3]

又把题目想复杂了. T1, 显然是对偶图上的最小生成树, 但是这也对应着原图的最大生成树, 不用打平面区域. 而且, 元素排序后下标的含义已改变, 错误地使用导致挂分. 暴力不好打, 自己也没有仔细造数据, 最终没能找出 BUG. T2, 原题. 考场上思路很清晰, 完成的不错. T3, 裸单纯形… 听说贪心 65 分… 应该打一个玩一玩的.

T1 捕猫计划 (40 / 100)

题目大意

这里有 n 个木桩 和 m 条藩篱, 这些藩篱构成了一些封闭的区域, 每一个区域中都有一只猫. 给你 n 个木桩的坐标 和 每条藩篱两端木桩的 编号, 要你拆除尽可能短的木桩, 使得所有的猫都能够逃出去.

分析

容易想到这是对偶图上的最小生成树. 而对偶图上的每一棵生成树 都和 原图上唯一的一棵生成树互补. 所以求出原图的最大生成树然后用总边权减去即可.

T2 学图论 (100 / 100)

题目大意

给定 N 个点, M 条无向边, Q 个询问,每个询问给定 L,R, 问连上第 L ~ R 条边后, 图中有多少联通块(询问之间互不影响).

分析

考虑离线. 我们将所有询问按 R 排序, 然后将贡献在编号上尽可能后移. 我们按编号从小到大加边. 如果两端不联通, 则直接加边; 否则, 去掉这两点路径上编号最小的边. 显然这是一个生成树的结构. 对于每个询问, 当编号为 R 的边被加后, 我们查询有多少条编号大于 L 的边在这棵生成树中. 显然是对的, 因为贡献被后移了. LCT + fenwick 即可.

T3 玩游戏 (15 / 15)

题目大意

给你一个 DAG, 你可以增加一些边的边权, 但要满足最长路不变. 求最多能增加多少. 保证入度, 出度为 0 的点各只有 1 个.

分析

我们记入度为 0 的点为 S, 出度为 0 的点为 T, 那么最长路显然是 dis(S, T). 假设加权后和S的距离为 dis', 则对于每一条边的两个端点 u->v, 要满足: dis'(v) - dis'(u) >= w(u, v) 最终还要满足 dis(T) = dis(S, T). 最大化 \(\sum dis'(v) - dis'(u) - w(u, v)\). 直接上单纯形即可.

<2016-09-04 Sun> (170 / 170) [2/2]

拿到了期望的分数. 但也仅此而已. T1 差点没有注意到细节. 这是一个环上问题, 首尾的情况要特殊考虑. T2 连暴力都没打 (但是暴力分只有 10 分, 所以弃了) T3 调了很久, 其一是写法过于复杂, 调试难度大; 其二 DP 状态用 pair 存储, 常数偏大; 其三暴力打得很复杂… 考试策略有问题. 还是应该先打暴力的. (T3 最后 5 分钟才收工, 非常虚啊…)

DONE 多边形序列 (polygon) (70 / 70)

题目大意

定义直角多边形为内角只有 90 度 或 180 度 的多边形. 对于一个点数为 n 的直角多边形, 我们可以用一个序列表示: 从某一个点出发, 如果这个点对应的内角是 90 度, 用 L 表示, 否则用 R 表示, 然后按逆时针方向到达下一个点, 重复前述操作, 直到回到初始的点. 比如, LLLL 表示一个矩形 ( 没有边长限制 ). 显然的是, 每一个序列代表的直角多边形不只一种. 现在要你求, 对于长度为 n 的序列, 有多少种序列表示出的直角多边形, 满足可以从多边形内部的某一个点看到所有的顶点

分析

因为内角和的限制, L 必定比 R 多 4 个. 由于对边长无限制, 注意到 当且仅当有连续两个 R 在序列中出现时 不合法. (可以自己画画图) 注意序列事实上是个环, 所以不能首尾同时是 R. 记 L 的数量为 x, 不妨考虑往这 (x + 1) 个空中 插 (x - 4) 个 R 进去, 但不能同时往 第 1 个 和 第 (x + 1) 个 中插入. 不妨先任意放, 然后减去最前面和最后面都插入的方案数, 即 C(x + 1, x - 4) - C(x - 1, x - 6).

DONE 石子游戏 (game) (0 / 0)

题目大意

有一类树上石子游戏的规则是这样的:在一棵有根树上,每个节点都有着一定数目的石子,两个玩家轮流进行游戏. 每次,每个玩家可以把不超过 m 个的石子移动到它的父亲上. 显然,根节点没有父亲,故每个石子一旦移动到根节点便无法再次移动. 问题是以某个节点为根的子树进行这样的游戏,是否存在先手必胜策略. 为了增加这个游戏的难度,我们对这个游戏进行一些小小的修改.现在, 我们的这棵树可能会长出新的节点.同时,每个节点上的石子数目可能会变化. 请问,以某个节点为根的子树进行这样的石子游戏,是否存在先手必胜策略.

分析

我们有一个经典的 NIM 游戏: 给你 N 堆石子, 第 i 堆石子有 Ai 个, 每次只能取走 M 个, 如果轮到某个人时无石子可取, 则此人判输. 我们定义 SG(i) = i % (M + 1), 则当 \(SG(A_1) \oplus SG(A_2) \oplus SG(A_3) \oplus ... \oplus SG(A_N)\) 不为 0 时存在必胜策略.

而这是一棵树相关的问题. 我们有一个结论: http://blog.csdn.net/kk303/article/details/6692506 这就是阶梯 NIM 游戏: N 个位置(0..N-1)上各自有一些石头, 每次可以从位置 1 至 N-1 中的一个选择 不为 0 且不超过 M 个石子移到前一位置. (从 位置 i 移至 i - 1) 如果轮到某个人无石子可移, 则此人输. 结论: 忽略偶数位置的石头后作普通 NIM 游戏, 胜负不改变. 大致证明就是如果你移偶数位置的石头, 对手一定有办法使奇数位置的石头状态不改变. 而这是树. 同样的, 忽略与根的深度差为偶数的结点, 用剩下结点作普通 NIM 游戏. 这个用 LCT 维护一下就行了.

<2016-09-08 Thu> (135 / 140) [2/3]

这场省选模拟考得不算糟, 但这很大程度上是因为 T3 是一道接触过的原题. T1 暴力打错了 (其实是因为特判打萎了) T2 老老实实地打了最暴力的暴力. 其实可以先枚举每一行 "0 变 1" 还是 "1 变 0" 来确定可以经过的点和不能经过的点, 然后再暴力. T3 以为 O(nlog2n) 的分治过不了 (毕竟 n <= 3e5), 花了很多时间想怎么优化到 O(nlogn), 但分治其实做不到那个复杂度.

TODO T1 解方程 (5 / 10)

题目大意

求出同余方程ax2+bx+c=0 (mod n)的模n不同余的解的个数. 共 t 组数据. 1<=n<=1e8, 0<=a,b,c<n, 1<=t<=1000.

DONE T2 blackflip游戏 (30 / 30)

题目大意

blackflip是一个有趣的智力游戏. 在每一个关卡里,你需要画一条不自交的路线,这条路线经过的所有格子都将会反色,游戏的目标就是要让反色后同一行的所有格子恰好都同色. 这条路线必须在棋盘内,且长度至少为1. 现在给定一个blackflip游戏的棋盘,求出有多少种不同的解.两个解不同当且仅当这两个解中的路径不同.路径相同但路径方向不同的解被认为是相同的. 棋盘大小为 n * m, 其中 n, m <= 9.

分析

显然这是一个用 插头DP 求解的问题. 但是 由于 n <= 9, 常数较大的最小表示法可能会 TLE. 可以用 广义括号表示法. 注意特判长度为 1 的. 一般的 插头DP 求的方案都是有两个独立插头的. 我的做法是: 由于在一条轮廓线上, 处于同一联通块的插头最多只有两个, 所以我们可以记 F(i) 为和 i 处于同一联通块的另一个插头. 如果 i 为 独立插头, F(i) = i. 然后用long long 压位, 用 位运算 实现所有修改, 速度会很不错.

DONE T3 graph (100 / 100)

题目大意

给定一个无向图, 每次增加一条边, 或者删除一条边. 要求判断每次操作后是不是二分图.

分析

预处理出每一条边存在的时间 [L, R), 按时间建线段树, 在区间 [L, R) 插入这条边的信息, 表示如果某结点被 [L, R) 覆盖了, 则该结点对应的时间中, 这条边始终是存在的. 每条边最多被拆成 O(logn) 条. 遍历整棵线段树, 用并查集维护这个图是不是二分图. 每遍历一个结点, 将被插入的边加入并查集, 如果插入时图不再是二分图, 则该结点所在子树的答案都为 false, 并查集撤销至访问该结点以前的状态 并 回溯. 如果该结点是叶子结点, 则该结点对应的操作为 true. 否则, 依次递归左儿子和右儿子, 递归完后 撤销, 回溯.

<2016-09-11 Sun> (100 / 60) [2/3]

T1 题目看错了 30 分暴力都没打出来… T2 树状数组 + 莫队 (复杂度 O(n*sqrt(n)*log(n))) 居然没被卡掉… 但是花了太多时间想要优化这种做法, 但是完全没想对方向啊. (直接导致T1暴力打不完) T3 没时间打暴力.

DONE T1 凸包 (random) (0 / 0)

题目大意

二维平面上有 n 个点, 第 i 个点的坐标为 (xi, yi). 对于每一个点, 我们以 1/2 的概率把它涂黑, 1/2 的概率把它涂白, 记 X 为黑点组成的凸包上点的个数, 记 X 的期望值 E[X], 输出 E[X] * 2n. 要求凸包上任意两点不重合, 任意三点不共线. 凸包可以只包含 1 个点 或 2 个点. 1 <= n <= 2000.

分析

题目实质上要我们求对于每一个点, 有多少种涂法使得该点在凸包上. 由于凸多边形点数和边数相等, 所以我们可以直接考虑统计向量的个数. (只有 1个点时是一个零向量, 2个点时是两个共线反向的向量) 对于向量 u->v, 如果要使得该向量出现在凸包中, 对于涂黑的点 A (不包括 u, v), 要满足 cross(v - u, A - u) > 0 (不能恰好为 0). 这样直接枚举点 A, 记录有多少个合法的点. 则这些点都是可选可不选. 如果这些点有 x 个, 和 点u 坐标相等的点有 y 个, 和 点v 坐标相等的点有 z 个, 则方案有 2x * (2y - 1) * (2z - 1). 但这样做是 O(n3) 的. 不妨 枚举点u, 将所有点按与点u的极角序排序, 然后 TwoPointers 点v. 这样的 TwoPointers 是在环上进行的, 会有边界问题. 不妨断环, 复制一份. 然后就 O(n2) 了.

DONE T2 子串 (substr) (100 / 60)

题目大意

这里有 n 个字符串 S1, S2, S3, … , Sn. 这里还有 q 个询问 \((l_i, r_i, P_i)\), 表示询问 \(S_{l_i}, S_{l_i+1}, S_{l_i+2}, ... S_{r_i - 1}, S_{r_i}\) 中有多少个串满足 Pi 是 Si 的子串.

分析

如果直接询问出现的次数就很水了… 不过也是可以做的. 首先对所有的 Si 建 SAM, 不同的串之间加分隔符.

建完后, 我们用 SAM 去识别 Pi, 如果识别失败, 则输出 0.

否则, 我们只需知道, 这个结点所在的子树中 (SAM 中的结点中不是都有一个 fa 指针么), 有多少个编号在 \([li, ri]\) 之间的串 Sj 的后缀对应的结点 在这个结点的子树中.

这很简单. 对每一个后缀自动机的结点p建一棵线段树, 维护有哪些串 Si 的后缀对应的结点在结点p的子树中. 这个线段树合并一下就好了.

TODO T3 乘积 (product) (0 / 0)

<2016-09-15 Thu> (10 / 30) [3/3]

发挥得不好. T1 居然打了 k(n*m) 次方的暴力, 然而在最小的测试点中, k<=10, n,m<=3, 所以是 1e9 级别的暴力 … T2 把式子推的差不多了, 但是十分不简洁, 直接导致没能发现一部分规律. T3 没打暴力. 大部分时间耗在想 T1 上了, 然而并没有想对方向.

DONE T1 鞍点 (sad) (0 / 10)

DONE T2 三角形 (new) (10 / 20)

题目大意

二维平面上有 n 个不同的点, 第 i 个点的坐标是 \((x_i, y_i)\). 定义平面 P 的炫酷度为 顶点都在P中且两直角边分别平行于两坐标轴的直角三角形的数量. 现在你可以添加一个点, 最大化这个平面的炫酷值并输出. n <= 500000.

分析

我们记 \(X(i)\) 为 n 个点中 横坐标为 i 的点的个数, \(Y(i)\) 为纵坐标. 再记 \(A(i) = \sum_{j=1}^{n}Y(y_j)[x_j = i], B(i) = \sum_{j=1}^{n}Y(x_j)[y_j = i]\), 则如果我们将点放至 (x, y) 且 不与 n 个点中的任意一个点重合, 则可以增加 X(x) * Y(y) + A(x) + B(y) 的炫酷值. 由于 \(\sum_{i=1}^{n}Y(i) = n\), 所以 Y(y) 的取值最多只有 O(sqrt(n)) 种. 这样的话我们可以枚举 x, 然后直接枚举所有 Y(y) 的取值, 对于每一种取值, 选择 B(y) 最大的 y 来更新答案. 但是不能有重点. 不妨对于当前的 x, 记录哪些 y 是不可以选的. 这个将原 n 个点按 横坐标 排个序搞搞就可以了. 重点对复杂度的贡献只会达到 O(n). 因为这个 O(sqrt(n)) 常数很小… 于是就跑过去了…

DONE T3 生成树 (count) (0 / 0)

<2016-09-22 Thu> (0 / 20) [3/3]

爆零了… 没什么好说的, T1 没往 DP 上想, T2 没发现规律, T3 没发现是傻逼费用流…

DONE T1 周末晚会 (party) (0 / 20)

DONE T2 网格棋盘 (block) (0 / 0)

题目大意

有一个n*n的网格棋盘, 每个格子都有一个标号. 不会有三个或者三个以上的格子拥有同样的标号. 现在有两种操作:

  1. 行操作. 把每一行都按任意顺序打乱重排.
  2. 列操作. 把每一列都按任意顺序打乱重排.

以上执行了两步操作. 第一步操作是行操作, 第二步操作是列操作. 现在给定初始状态和目标状态, 问: 能不能从初始状态变换到目标状态? 如果能, 最少需要几步? n <= 200. 多组数据, 不超过 200 组.

分析

仔细分析一下, 我们可以得出结论: 只要初始状态和目标状态合法, 步数不会大于等于 3. 然后我们只要判断: 答案是否为 0, 1, 2 即可. 答案为 0, 1 分别只要 memcmp 和 排序+memcmp.

至于答案为 2, 由于每一个位置只有最多两个去处, 假设先进行 行变换, 再进行 列变换, 那么如果想要到达某一位置, 其 行变换 后的位置是唯一确定的. 由于有两个位置, 这等价于两个决策. 两个决策? 2-SAT 即可! 按限制连边, 如果有解则答案为 2.

DONE T3 探险计划 (exploration) (0 / 0)

不想多说… 就是个傻逼费用流.

<2016-11-27 Sun> (270 / 270) [2/3]

不理解为什么把联赛模拟题放在现在考. 主要问题在 T1 和 T3. 都是思路十分不清晰, 调试的过程其实是尝试的过程, 因为自己根本没想清要打什么. 这样很容易把时间浪费掉.

DONE T1 (100 / 100)   单调队列

题目大意

给你一个从 1 到 n 编号的环, 位置 i 的元素为 \(a_i\), 要你求有多少对位置(u, v) (u<v) 满足环上存在一条从 u 到 v 路径使得路径上除u, v外所有元素的最大值小于 \(min\{a_u, a_v\}\). n <= 5000000

分析

首先将输入倍长, 转化为序列问题. 对于位置 i, 我们考虑计算在倍长的数组中, \((i, i+n)\) 中有多少个元素 j 满足 \(max\{a_k, k in (j, i+n)\} < min\{a_j, a_i\}\). 这个可以直接单调队列搞, 二分之类的. 但是我们要求线性. 这个仔细想一想应该也想的出来. 但是这样会算重. 我们发现, 这个算重是受最大值和次大值影响的. 特判即可.

TODO T2 (70 / 70)   概率

题目大意

分析

DONE T3 (100 / 100)   DP

题目大意

现在你是一个玩家, 你在一棵树的根结点. 每一次, 你会随机地选择一个儿子并往下走, 如果你到达了某个叶子结点, 则回到最后一次存档点, 重复上述操作, 直至到达结点 n. 其中, 从 1 到 n 的唯一路径上的结点编号依次为 1, 2, 3, … , n, 且存档点只能安放在这些位置. 结点 1, n 必须安放存档点. 现在给你树的形态以及最多可以安放多少个存档点, 请求出使得到达结点 n 期望步数最小的方案 并 输出此时的期望步数. n <= 700.

分析

如果我们可以求出 \(D(u, v) (u, v \in [1, n])\) 表示从结点 u 到结点 v 的期望步数, 剩下的就是裸的DP. 至于计算 D(u, v), 我们可以枚举从哪个叶子结点回到存档点并计算这种情况发生的概率, 同时也计算一下直接到达结点 v 的概率. 从叶子结点回到存档点后其实是子问题. 记从结点 u 出发到达结点 v 的概率为 P(u, v), 点 u, v 的距离记为 dis(u, v), 我们可以列出等式: \(D(u, v) = P(u, v) \times dis(u, v) + \sum_{w} P(u, w) \times (dis(u, w) + 1 + D(u, v))\), 解这个方程即可. 另, DP 方程 O(n3), 但把无用的状态剪掉后非常快.

<2016-12-02 Fri>

<2016-12-03 Sat>

<2016-12-04 Sun>

<2016-12-08 Thu>

<2016-12-09 Fri>

<2016-12-10 Sat>

<2016-12-11 Sun>

<2016-12-15 Thu>

<2016-12-17 Sat> [/]

T1为什么打了那么久… T3为什么打了那么久… T2神题, T1 T3 思博题…

<2016-12-18 Sun> (30 / 100) [3/3]

T1 没仔细看题: 题目明明说好了化学元素会有3个字母来着… 爆30了… T2,T3 直接弃疗…

DONE T1 化学 (chemistry) (30 / 100)   高斯消元

题目大意

给你反应物和生成物 (包括每一个化学式所带电荷数), 要你配平化学方程式, 保证有解时解唯一.

分析

首先字符串处理一波, 得出一些方程, 每一个方程都表示某一个元素的守恒或者电荷的守恒, 方程中的未知数即为题目所求的系数. 由于保证有解时结唯一, 不妨将1作为任意一个未知数的解, 然后用分数类高斯消元, 再通分即为答案. 如果该方程无解, 原问题无解. 解必须为正整数, 否则无解.

DONE T2 最小圆 (mincircle) (0 / 0)   计算几何 SET

题目大意

平面直角坐标系中有 N+1 个点, 每个点都在运动, 运动轨迹为折线. 每一个点的速度不一定相等, 但总时间相等. 现在请你确定一个半径 r, 使得存在某一时刻, 所有的点都在以点 0 为圆心, r 为半径的圆中.

分析

不妨二分答案 r, 然后对于每一个点计算出它在以点 0 为圆心, r 为半径的时间范围. 这个用 SET 维护一下即可. 但是要注意的是如何计算时间. 这需要转换参照系. 两个动点自然不好计算. 不妨假定其中之一是静止的, 将两个点的速度叠加至一个点上即可计算.

DONE T3 神奇的代码 (code) (0 / 0)   状压DP

题目大意

原题给的是代码, 大意是给你一棵树, 乱点分治(任选一个点作重心), 然后每次给重心随一个大于分治父亲的权值的权值. 初始的重心的权值可以任意. 问所有点的深度都小于给定的 K 方案数. 点数 N <= 50, K <= 15.

分析

考虑每个点的权值满足什么条件时合法. 假设我们已知所有点的权值, 然后尝试按照权值的限制来点分治. 我们发现, 只要对于任意两个权值相同的点的路径上都有比它们的权值小的节点存在. 事实上, 这就是唯一的限制了. 我们可以状压DP. 考虑在当前节点子树中的方案数. 这些方案会被其他节点的权值所影响. 考虑怎么记录这些影响. 然后按照这个状压DP. (貌似要容斥以下)

<2016-12-22 Thu> (50 / 50) [3/3]

T1 原题, 但是看错题目了, 弄错了输入格式, 外加数组没清零, 爆零了. T3 就打了一个暴力, 想到了树分块却没想到点分治, 其实这是点分治裸题…

DONE T1 方块 (cube) (0 / 0)   链表

题目大意

给你一个不完整的方块, 已知该方块原本是由 n*n*n 个 1*1*1 组成的长宽高均为 n 的方块, 且每个1*1*1的方块六个面都有着相同的颜色. 现在丢失了一部分小方块. 给你现在这个方块的六视图, 请输出当前最多还剩多少小方块.

分析

假设一个方块都不少, 那么颜色就会有矛盾. 那么我们去掉有矛盾的方块, 按照相应的方向将当前块上的颜色转移到相邻的方块上. 重复该操作, 直至没有矛盾. 剩下的方块的个数便是答案.

DONE T2 下棋 (chess) (0 / 0)   SG函数 线性基

题目大意

这是一个博弈游戏. 给你一棵n个节点, m条边的DAG,DAG上每条边都有一个颜色. 有一些硬币散落在节点上. 每轮到一个人时, 他可以选定一个硬币和一个颜色集合S, 然后删除这个硬币. 对于这个硬币所处的节点 u, 如果连出去的边的颜色在S集合中, 则这条边的终点的硬币增加一个. 不能操作者输.

分析

首先, 从SG的角度出发, 每一个硬币的对胜负的影响是独立的. 其SG值只与所在节点有关. 想办法求出每个节点对应的SG值即可.

DONE T3 树 (tree) (50 / 50)   点分治

题目大意

给你一棵边带权的树和许多询问, 每个询问形如 (l, r, u), 表示询问编号范围在 [l,r] 中的节点中与节点u 距离最小的节点, 只要求输出这个距离.

分析

做一遍点分治, 就只要考虑过根的路径了. 只要支持查询当前分治结构中编号 [l, r] 中离当前分治中心的最近的距离即可. 这个用 RMQ 预处理即可. 由于是最小值, 所以不用考虑所在子树的影响–答案不会更优. 然后就随便做了.

<2016-12-24 Sat> (30 / 30) [3/3]

滚粗. T3 一激动打了个 \(O(n\log ^ 3 n)\) (打到 12 点), 结果 TLE 了… (虽然标程也是这个复杂度) T1 没有很快地想到网络流. 明明是多物品问题. 最后没能调出来. 弃 T2.

DONE T1 OI年 (oi)   网络流

题目大意

给你一个 n*m 的网格, 有的被染成蓝色, 有的被染成白色, 还有的没有上色. 每一个蓝色格子的权值为 (4 - 除自己外与自己四联通的蓝色格子的个数). 对于一种染色方案, 定义其权值为 所有蓝色格子的权值和. 请你对没有上色的格子上色, 使得权值和最大. 输出这个权值. n,m <= 50.

分析

对于一个点, 要么蓝, 要么白, 这很容易想到二分图模型 + 最小割. 剩下的请自行思考. 不要想的太过简单.

DONE T2 双排序 (double)   DP

题目大意

给你一个 n*m 的网格, 要求你将网格用字母填满, 使得每一行的字母单调不减, 每一列的字母也单调不减. 合法形如:

abb <--合法
bbb <--合法
bbc <--合法
^^^
合法

不合法形如:

abb   <-- 合法
bcb   <-- bcb 不是单调不减的!
bbc   <-- 合法
 ^
这个 bcb 也不是!

n, m <= 10.

分析

字母放入时由于是单向限制, 所以可以从小到大枚举放入的字母. 这一点和题目 "鞍点" 的思路一样. 我们在观察每放完一个字母后棋盘的形态. 可以发现并证明, 每一行放的字母和每一列放的字母都是连续的 (不会中间空出一个), 而且会顶格. 这意味着, 每一行放的物品的个数会随行数的递增而单调不增. 我们可以考虑以棋盘的形态来 DP 了. 状态数相当于统计可重集个数, 是 \(\binom{10+9}{10} = 92378\). 每次DP时, 枚举将当前的字母放在什么位置. 对于每一个位置, 由于本次放字母不一定置放一个, 所以前继状态会很多. 如果暴力枚举前继状态, 复杂度是 \(O(\text{状态数}^2)\). 我们可以用两种思路中的其中之一来优化:

  1. 前缀和.
  2. 考虑更新出的每一个状态都是在某一状态的前提下在加上这个位置形成一个新的状态. 但是, 这个 "某一状态" 可能是已经被当前字母更新过的. 规定一下枚举顺序, 类似无限背包那样即可.

有的位置已经被钦定放什么了, 这个在枚举位置的时候判一下, 不合法不更新就是了.

DONE 最后的战役 (battle)   整体二分 点分治 线段树 BFS序 DFS序

题目大意

给你一棵树, 每一个节点都有一个权值. 每次, 你有两种操作:

  1. 给定节点u 和正整数x, 对于树中的每一个节点v, 其权值减少 \(\lfloor \frac{x}{2^d} \rfloor\), 其中 d 为 节点u 到 节点v 的距离.
  2. 给定节点v, 查询在以 1 为根的树中, 节点 v 的子树中有多少结点的权值小于等于0.

n <= 1e5, x <= 1e9. 时限 10s.

分析

首先注意到的是, d >= log x 就没有意义了. 有两种主要做法. 一种离线一种在线.

离线做法: 考虑二分答案求出每个点的权值是何时小于0的. 这个对于每个二分可以用点分治实现. 每次判断可行要 O(n log n log x) 的时间, 总复杂度 O(n log n log n log x). 然后套一个整体二分. 总复杂度仍然是 O(n log n log n log x). 然后题目就变得非常简单了~ 排个序维护子树信息即可.

在线做法: 不妨以 1 为根, 处理出 BFS 序, 然后将节点按到根的距离分层, 每层用一个线段树维护, 用以找出破产的节点. 在每一层中, 节点按 DFS 序排序. 对于每个操作1, 先考虑对子树的贡献进行处理. 首先, 有效影响的层数最多 log x 层, 其次, 对每一层的影响范围必然是一段连续的区间. 所以直接区间减啊… 那不在子树中的呢? 沿着父亲往上暴力做, 去重即可.

<2016-12-25 Sun> (100 / 200) [2/3]

误以为 T2 是思博题. 结果爆零了. T3 的确是调了太久. 大概是从 9:30 搞到 12:15 的样子, 期间调暴力调了至少 30 min. 然后就没时间做T1了…

DONE T1 积木 (jimu) (0 / 0)   记忆化搜索 剪枝

题目大意

给你一堆积木和一个色子, 每一次, 你可以掷一次色子, 色子的每一面上都有一个颜色. 每掷出一种颜色, 如果存在一块不在顶层的积木, 使得拆掉这块积木后积木堆不会倒, 那么就拆掉. 拆掉这个积木后, 便要将积木放至积木顶. 如果顶部已经放满, 则新放一层. 否则, 游戏结束. 现在已知这堆积木的状态, 求期望最少需掷几次色子使得游戏结束. 注意, 每一层都有3块积木, 分别摆在 左,中,右. 如果某一层没有积木 , 只有左边的积木仍存在 或者 只有右边的积木仍存在, 积木倒塌. n <= 6.

分析

n 这么小, 考虑爆搜. 不妨从上到下记录每一层每一块积木的颜色, 然后枚举每一种可能的后继状态. 注意到当掷出的色子一定时, 游戏者唯一能决定的就是将取出的积木放在什么位置. 选最优的位置即可. 但是, 有可能无法取出积木, 这时转移到的状态就是自己. 这种情况下, 解方程即可.

显然要记忆化. 但是直接记录状态, 状态数可能会很多. 首先, 对于某一层的积木, 我们只需要记录能够抽走的积木的颜色. 其次, 如果只有一个能抽的, 那么可以不记录其位置. 依据这些剪枝, 我们可以 HASH 出每一层积木的状态. 其次, 除了第一层积木外, 其他所有层都是相互独立的, 所以可以排序 ( 无序数列判重 ).

TODO T2 一样 (yiyang) (0 / 100)

题目大意

分析

DONE T3 神题 (godzhj) (100 / 100)   二分答案 等差数列求和

题目大意

给你一个 n*m 的棋盘, 定义一个位置被占领, 只需满足两种情况中的任意一种:

  1. 该位置被放置了棋子
  2. 该位置与棋盘边界不相通 (四联通)

要你求出当被占领的位置数 >= k 时最少需要放置多少棋子.

分析

假设棋盘无限大, 可以证明最优的放法是用棋子围出类似于菱形的形状. 举例:

   .....
  *     *
 *       *
*         *
*         *
 *       *
  *     *
   .....
   .....
  *     *
 *       *
*         *
 *       *
  *     *
   .....
   .....
  *    *
 *      *
*        *
*         *
 *       *
  *     *
   .....

然后, 棋盘不够呢? 把这个形状挤压一下就行了. 这个很好实现的. 不过如果要优化复杂度, 就要 二分+等差数列求和.

<2016-12-29 Thu> (50 / 130) [1/1]

T1 又把题意搞错了. 原来括号是可以无限嵌套的. 然而我的程序不鲁棒, 爆 20 分.
T2 打了个暴力草草收场…
T3 直接跳过.

DONE T1 ZCC Loves AVG (avg) (20 / 100)

题目大意

给你一份代码, 其中有以下语句:

game() <块>
cg(<string>);
if (<string> | !<string> | <string> == <string> | <string> != <string>)
    <语句或块>
else
    <语句或块>

其中块是指用 {} 括起来的块或代码.

假设 if 语句中用到的变量的值自始之中从没有使用过, 请求出多少 cg 语句永远不会被执行.
注意, 如果 cg(<string>)<string> 的内容相同, 我们认为它们是同一条语句.

分析

如果只对一个语句来看, 这个问题酷似一个 2-SAT 问题. 前面的 if 语句的内容就是 2-SAT 的限制.
不过我们可以发现, 按照这个思路来建边, 边都是双向的.

对, 事实上, 这是一个二分图问题. 你不过是要把点分成两个部分, 使得一部分是 TRUE, 一部分是 FALSE.
这个可以通过 建虚点+并查集 来解决, 那些限制都可以对应出连边.

由于 if 语句会结束, 这等价于撤销上一次操作, 所以需要可撤销的并查集.

<2016-02-14 Sun> (110 / 150) [/]

区间 (interval)

HOME