本人由于一些个人原因，心情不是很好。本博客因此停更一段时间，恢复时间待定。

# Kuririn MIRACLE

感谢东南大学的

CoupDeGrace同学提供本题题解。

# 描述

传送门：The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online - Problem I

As we know, DreamGrid is a master of planning algorithm. Recently, a new type of autonomous car appears in Gridland. With the shape of a circle, the car can move in any direction. Being interested in this car, DreamGrid decides to design a specific path planning algorithm for it. Here is the first case he wants to solve.

Consider two cars on the two-dimensional plane with the same radius of $r$. We now want to move the center of the first car from $(0, 0)$ to $(d, 0)$, where $d$ is positive. The second car, starting its move with its center located at $(2r, 0)$, can be considered as an obstacle moving towards the positive direction of the x-axis with a **constant** speed of $v$. Luckily, after installing a new engine, the first car can move twice as fast as the obstacle car, which means the **maximum** speed of the first car can be $2v$.

DreamGrid wants to know the shortest time needed to move the first car to the end point without colliding with the second car. That is to say, before arriving at the end point, the circle representing the first car can’t intersect with (but can be tangent to) the circle representing the second car.

As DreamGrid is too busy, you are asked to solve this simple problem for him. Of course, if you successfully solve this problem, you will get a brand-new autonomous car in the Gridland!

# Morgana Net(矩阵快速幂)

# 描述

传送门：ACM-ICPC 2018 徐州赛区网络预赛 - Problem K

Morgana is learning Convolutional Neural Network, he builds a neural network called “morgana net”.

In brief, given a $N \times N$ matrix $A$ that represents a picture. Every layer in morgana net is doing work as follow:

$$\displaystyle A_{k+1}[i][j] = f(\sum_{p = i - m}^{i + m}\sum_{q = j - m}^{j + m} A_k[p][q]\ B[p - i + m + 1][q - j + m + 1])$$

Every layer can be represented by a $N \times N$ matrix $A_k$ and $A_k$ means it is the $k$th layer. $B$ is the $(2m+1) \times (2m+1)$ matrix represents convolution kernel. And if $(p, q)$ are out of $A$, $A[p][q]$ will be $0$ (if $p \le 0$ or $q \le 0$ or $p > n$ or $q > n$). $f(x)$ is the activation function and in morgana net $f(x) = x \mod 2$.

Now morgana gives you the input $A_0$ represents a picture, he wants to know after ttt layers, how many nerve cells’ value are equal to $1$ . (that means how many elements in At are equal to $1$).

# Set(01字典树合并+延迟更新)

# 描述

传送门：ACM-ICPC 2018 南京赛区网络预赛 - Problem H

Shinku is very interested in the set. One day, she got $n$ sets, and the $i$-th number $a_i$ is in the $i$-th set. But she doesn’t think it is interesting enough, so she applies mmm magic to these sets. There are three kinds of magic:

1 $1\ u\ v$: If the uuu-th and $v$-th numbers are not in one set, then the Shinku’s magic will merge the set containing the $u$-th number and the set containing the $v$-th number.

2 $2\ u$: Shinku’s magic adds $1$ to each number in the set containing the $u$-th number.

3 $3\ u\ k\ x$: Shinku can immediately know how many numbers $t$ in the set containing the $u$-th number satisfy $t\equiv x (\bmod\ 2^k)(0 \le k\le 30,0\le x<2^k)$.

But unfortunately, for some reason the type $3$ magic fails. So Shinku wants you to tell her the answer after every type $3$ magic.

Note that there can be multiple numbers with the same value in one set, that is, numbers with the same value will not disappear when merged.

# Shell Necklace(CDQ分治+FFT)

# 描述

传送门：2016 Multi-University Training Contest 1 - Problem H

Perhaps the sea‘s definition of a shell is the pearl. However, in my view, a shell necklace with n beautiful shells contains the most sincere feeling for my best lover Arrietty, but even that is not enough.

Suppose the shell necklace is a sequence of shells (not a chain end to end). Considering i continuous shells in the shell necklace, I know that there exist different schemes to decorate the i shells together with one declaration of love.

I want to decorate all the shells with some declarations of love and decorate each shell just one time. As a problem, I want to know the total number of schemes.

# Prime Distance On Tree(树上点分治+FFT)

# 描述

You are given a tree. If we select 2 distinct nodes uniformly at random, what’s the probability that the distance between these 2 nodes is a prime number?

# A Simple Problem with Integers(均摊复杂度线段树)

# 描述

传送门：2018 ACM 国际大学生程序设计竞赛上海大都会赛 - Problem H

You have $N$ integers $A_1, A_2, … , A_N$. You are asked to write a program to receive and execute two kinds of instructions:

`C a b`

means performing $A_i = (A_i^2 \mod 2018)$ for all $A_i$ such that $a ≤ i ≤ b$.`Q a b`

means query the sum of $A_a, A_{a+1}, …, A_b$. Note that the sum is not taken modulo $2018$.

# GRE Words(AC自动机+Fail树+线段树优化DP)

# 描述

传送门：2011 Asia ChengDu Regional Contest - Problem G

Recently George is preparing for the Graduate Record Examinations (GRE for short). Obviously the most important thing is reciting the words.

Now George is working on a word list containing N words.

He has so poor a memory that it is too hard for him to remember all of the words on the list. But he does find a way to help him to remember. He finds that if a sequence of words has a property that for all pairs of neighboring words, the previous one is a substring of the next one, then the sequence of words is easy to remember.

So he decides to eliminate some words from the word list first to make the list easier for him. Meantime, he doesn’t want to miss the important words. He gives each word an importance, which is represented by an integer ranging from -1000 to 1000, then he wants to know which words to eliminate to maximize the sum of the importance of remaining words. Negative importance just means that George thought it useless and is a waste of time to recite the word.

Note that although he can eliminate any number of words from the word list, he can never change the order between words. In another word, the order of words appeared on the word list is consistent with the order in the input. In addition, a word may have different meanings, so it can appear on the list more than once, and it may have different importance in each occurrence.

# XM Reserves(FFT建模)

# 描述

传送门：2016 ACM/ICPC Asia Regional Qingdao Online- Problem H

As an eligible Ingress Resistance Agent you should know your power source, the Exotic Matter.

We call it XM, which is the driving force behind all of our actions in Ingress.

XM allows us to construct items through hacking portals, to attack enemy portals, make links and create fields.

We try to collect XM from the ground. XM concentration come from location based services, meaning that areas with a lot of foot traffic have higher amounts versus places that don’t.

You can collect XM by moving through those areas.

The XM will be automatically harvested by your Scanner when it is within your interaction circle/range.

Alice decides to select a location such that she can collect XM as much as possible.

To simplify the problem, we consider the city as a grid map with size ‘$n * m$’ numbered from $(0,0)$ to $(n-1,m-1)$.

The XM concentration inside the block $(i,j)$ is $p(i,j)$.

The radius of your interaction circle is $r$.

We can assume that XM of the block $(i,j)$ are located in the centre of this block.

The distance between two blocks is the Euclidean distance between their centres.

Alice stands in the centre of one block and collects the XM.

For each block with the distance $d$ smaller than $r$ to Alice, and whose XM concertation is $p(i,j)$, Alice’s scanner can collects $p(i,j)/(1+d)$ XM from it.

Help Alice to determine the maximum XM which she can collect once he stands in the centre of one block.

# Tachibana Kanade's Toku(AC自动机+数位DP)

# 描述

传送门：Codeforces Round #248 (Div. 1) - Problem C

Tachibana Kanade likes Mapo Tofu very much. One day, the canteen cooked all kinds of tofu to sell, but not all tofu is Mapo Tofu, only those spicy enough can be called Mapo Tofu.

Each piece of tofu in the canteen is given a m-based number, all numbers are in the range $[l, r]$ ($l$ and $r$ being m-based numbers), and for every m-based integer in the range $[l, r]$, there exists a piece of tofu with that number.

To judge what tofu is Mapo Tofu, Tachibana Kanade chose n m-based number strings, and assigned a value to each string. If a string appears in the number of a tofu, the value of the string will be added to the value of that tofu. If a string appears multiple times, then the value is also added that many times. Initially the value of each tofu is zero.

Tachibana Kanade considers tofu with values no more than k to be Mapo Tofu. So now Tachibana Kanade wants to know, how many pieces of tofu are Mapo Tofu?