# summary-tests

## <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-17 Wed> (260 / 260) [3/3]

#### DONE T2 value   DP sort

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

#### DONE T3 binary   树状数组 二进制

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.

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

## <mo> NOIP2016-autumn

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

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

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

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

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

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

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

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

## <mo> HNOI2017

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

#### T3 没给钱 (100 / 100)   HLD LCT

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

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

#### DONE T2 blackflip游戏 (30 / 30)

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

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

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

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

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

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

### <2016-12-17 Sat> [/]

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

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

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

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

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

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

#### DONE T2 双排序 (double)   DP

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



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



n, m <= 10.

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.

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

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

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

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

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

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

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

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


### <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
<语句或块>


HOME