So… It’s been a while…

Originally, this blog was completely dedicated to my OI-related studies during my high school years, and it also hosted on a different site(cnblogs.com/Heinz). It was only migrated here as my github page because I felt like it one day. In the end, a lot of entries are now missing because they’re either lost on the original site or extremely hard to because I wrote notes on different sites as well as notebook softwares and I’m too lazy to find every single piece that’s out there on the internet. And after the migration, I mostly just left it alone collecting dust on the cyberspace. Well, I decided to change that.

So, I’m gonna be making some changes to this place. First of all, it most definitely won’t be just OI-related topics on here from now on. I’m barely an OIer nowadays anyway. I’ll be writing stuff on anything that interests me(technology, gaming, music etc), pretty much treating this like a personal diary or something. Second of all…

Well, that’s really it. Let’s see where this goes.

btw, that new Eminem single really slaps, takes me back man…

Magic Tree（CF-1193B CEOI 2019 Day 2）

题目描述：

给一个\(n\)节点的树，其中有\(m\)个点有果实，分别在编号为\(pi\)的点上，在第\(di\)天成熟，在成熟的那天收割有\(wi\)的贡献。给出\(K,di<=K\). 通过断开树上的边来收割果实，每断开一个边，取不包含根的子树，获得上面所有成熟果实的贡献值，剩下的全部丢弃。每天都可以断任意条边。 问总共能收获到的最大贡献。

俄罗斯套娃（JOISC 2016 Day 1）

题目描述

你开了一家卖俄罗斯套娃的店。因此，你向厂家订购了 \(N\)个俄罗斯套娃，这些娃娃被编号为 \(1\) 到 \(N\)，其中第 \(i\) 个套娃是一个的直径为 \(R_i\) 高度为 \(H_i\) 的直♂柱体 。每个俄罗斯套娃都只能套高和直径严格比他小的套娃。同时只要满足条件，俄罗斯套娃可以嵌套多次。

有一天，你收到了厂家的来电，告诉你你预定的 \(N\) 个娃娃不能一次性全部做完。所以第一批只会送达直径大于等于 \(A\) 并且高度小于等于 \(B\) 的所有套娃。你需要预先安排出一个方案，使送来的套娃经过若干次嵌套后，没有被套的套娃数量最小。

由于厂家经常搞大新闻，所以他会改变 \(A\) 和 \(B\) 的值，总共 \(Q\) 次，因此你需要对每对 \((A,B)\) 都作出回答，询问之间互不干扰。

若不熟悉KMP算法，强烈建议好好先去了解一下，否则这里会有很多不大理解的思想。

Trie树上的KMP?

想想原本的\(KMP\)算法，为了快速匹配，我们根据匹配串先预处理一个\(next[]\)数组，也就是最长的后缀与前缀完全匹配的位置，然后一旦遇到匹配错误的时候，就把当时的匹配指针移到他的\(next[]\)即可。

那么想想，如果有多个匹配串和一个文本串，要求你在文本串中找出能匹配到多少个串。那么想想，如果关于所有匹配串建立一颗\(Trie\)树，在这个上面进行\(KMP\)算法是否可行呢？

例题：

Keywords Search （HDU-2222）

题目描述

czh在成千上万次尝试后，终于被自己感动了，他决定换一种方式来理解cry的文章，他列举出自己掌握的所有单词，来统计词频，可是czh已经累了，不想动了，只能瘫在椅子上给你们加油了。

题目描述：

You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3…,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.

All the nodes are white initially.

We will ask you to perfrom some instructions of the following form:

• C a : change the color of node a.(from black to white or from white to black)
• A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

给出一棵n个结点的树，每条边有边权。一开始，每个点都是白色的。 再给出q个询问，每次询问有两种操作：

1.C a 表示改变a结点的颜色，黑变白，白变黑。
2.A 表示询问树上某两个白点（可以是同一个点）间最远距离 注意原题卡常，可以尝试换用clang编译器提交。

题目描述：

You are given a tree (an acyclic undirected connected graph) with N nodes. The tree nodes are numbered from 1 to N. We define dist(a, b) as the number of edges on the path from node a to node b.

Each node has a color, white or black. All the nodes are black initially.

We will ask you to perfrom some instructions of the following form:

• 0 i : change the color of i-th node(from black to white, or from white to black).
• 1 v : ask for the minimum dist(u, v), node u must be white(u can be equal to v). Obviously, as long as node v is white, the result will always be 0.

给出一棵n结点的树，边权为1，一开始每个点颜色都是黑色。 现有q个询问，每次询问会有两种操作： 1.0 i 改变i的颜色，黑变白，白变黑。 2.1 v 询问与v距离最近的白点，显然，当v颜色为白色时，答案是0。

题目描述：

给出一个长度为n的01串S，有Q个操作：
1. 翻转区间\([l,r]\)（0变1,1变0）
2. 求区间\([l,r]\)有多少不同的子串

题目描述：

Now we are planning to construct a big chimney. The chimney’s section is a 3×3 square and the center of it will have nothing like the picture below. Now we only have a lot of bricks whose size if 1×1×2, and we want to build a chimney whose height is N, so can help us to calculate how many ways we can build the chimney? The answer may be very large, so you can just tell the answer’s remainder divided by 1000000007.

用1×1×2的砖头摆出如图所示的烟囱，可以横着摆也可以竖着摆，求摆出n层高的烟囱会有多少种不同的方案。

题目描述：

On Octorber 21st, HDU 50-year-celebration, 50-color balloons floating around the campus, it’s so nice, isn’t it? To celebrate this meaningful day, the ACM team of HDU hold some fuuny games. Especially, there will be a game named “crashing color balloons”.

There will be a n^2 matrix board on the ground, and each grid will have a color balloon in it.And the color of the ballon will be in the range of [1, 50].After the referee shouts “go!”,you can begin to crash the balloons.Every time you can only choose one kind of balloon to crash, we define that the two balloons with the same color belong to the same kind.What’s more, each time you can only choose a single row or column of balloon, and crash the balloons that with the color you had chosen. Of course, a lot of students are waiting to play this game, so we just give every student k times to crash the balloons.

Here comes the problem: which kind of balloon is impossible to be all crashed by a student in k times.

撞气球游戏，一个n*n的矩阵中，有不同颜色的气球，气球的颜色最多50种（从1到50）。 游戏开始前，先选择一种颜色。游戏开始后，每次选择一行或者一列包含该种颜色的气球进行撞击。如果选择行，那么这一行的气球都会炸裂。如果选择列，这一列的气球都炸裂。 请你求出，有多少种颜色的气球，无论怎么玩，都不能在K次之内，把所有同色的气球都撞裂。

二分图

二分图又称作二部图，是图论中的一种特殊模型。

设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。