Spring I

I heard something twittering on the balcony.

Walking on my tiptoe, I reached the window, through which I spotted a turtle dove standing on the stainless-steel-made railing, with a sprig in its beak. Barely had I observed it attentively when it hastily fled away, leaving behind a fuzzy silhouette.

I was leaning on the windowsill, looking down, when a ball of white captivated me, which I instantly recognized as peach blossoms. Bathed in radiant sunlight, they stretched their exquisite bodies in all directions. The balmy breeze gently swayed the flowers, carrying the scent they exuded wherever it passed. Eventually here came the spring. As I was about to return to my room, my eyes rested on a half-finished bird nest that lay on the board put on the railings.

It was unbelievable that the dove was planning to build a nest on our balcony. Yet this was the case. What’s more, I witnessed two doves erecting their lovely home together. Before long, a complete nest came out.

I could see in the mild twilight, a tiny nest lying steadily behind the huge flower pots, and an adorable dove perching on the nest. The setting sun cast its silky beams on this little cute creature through the verdant plants in the pots, resembling a warm hand patting tenderly. This tranquil scene was set off by the distant golden horizon, which formed the most enchanting landscape in the world. I could picture that under its little body, eggs were being warmed up, and new life was being brewed.

But we all know that good times do not last long, which I grasped on that drizzly evening when the dove had gone away and had not returned.

I stared at the empty nest vacantly, a sense of loss welling up in my heart. There lay the sole egg placidly, reflecting the cold light which the moon shed on the earth. Why didn’t the dove return? Maybe, I unintentionally frightened it, or, it had found a superior habitat. But, did it desert its cherished egg? On this fairly chilly rainy night, where could it go? Would it be shivering all over in the freezing wind? As the moonlight suffused the ground, I perceived that, never would I know the answer.

I leaned on the windowsill, overlooking the swaying flowers. I could hear raindrops knocking the canopy, composing a rumpled melody agitating my thoughts. I could see them trickling down the eaves, descending, sinking into puddles, feebly splattering a spray of droplets. Also I could hear the moaning wind dashing through the alley, wildly rattling loose windows and doors. I could see it wobbling the leaves furiously, severing them from branches and tugging them down. But, in the meantime, I could see the blossoms that the tree threw up in the air, being hit by the rain and being swung by the wind, while they kept emanating aroma that wafted all around. I could see the myriad scattered petals which fell on the moist tarmac, all colors draining rapidly, yet somehow, they were peculiarly appealing with the lamplight flickering in dewdrops.

It suddenly occurred to me that, unlike what I considered before, what was called spring, was not a picture in a particular style. It not only meant arrival and growth, but also meant departure and wilting to some extent.

So the spring is not all about a couple of turtle doves who are busy constructing a cozy neat twiggy nest where the new life will be brought, nor about the pale pink blossoms that bloom wherever you behold, adorning the corner of the bright blue sky. The essence of the spring lies in the persistence that the doves possess, even if they get so close to human beings and lose one of the only two eggs. It lies in the patience with which the dove squats in its nest unceasingly, awaiting the arrival of the baby, no matter the icy drizzle and the roaring gale. It lies in the optimism which encourages the blossoms to bloom vigorously in the frigid sprinkle. It lies in the devotion of the blossoms as they make the world transfigured despite the adversity they are confronted with.

I lingered on the balcony, hearkening wind and rain, dismay dissipating gradually. And here came the spring. I could sense that, distinctly.

The Beginning

The bell is about to ring. The new year is in sight.

Time flies as we grow and mature, leaving naivety behind. No sooner have we relived the past year in detail than we face the coming year hurriedly. Lay down the heavy burden, repack the travelling bag, take our initial dream, step forward readily and firmly.

It’s said those who have received compliments should be rather careful, for other’s acclaim may block the consciousness of weakness, which surely leads to failure. Yet by no means shall we belittle ourselves, since nobody will have confidence in us unless we are confident. Owning a distinct understanding of oneself, cultivating the better part, remedying what have been done that turns out a mistake, are ways to adjust our mentality.

When we gaze at the vast, dark night sky, sparsely-arranged stars hang high, whispering about what they have just witnessed on this tiny, lonely, but vigorous cerulean planet, such as a large amount of teenagers burning the midnight oil, waiting for that extraordinary moment, after which they may become an adult, or may bare his or her heart to someone else, or, may just sigh with the feeling that it seems something in life, which is hard to be aware of, has vanished silently and drastically. Whatever they see, the sparkling stars keep extending their best wishes to whom they have not known and may never know. The stars, the glinting stars, the stars that split the profound night sky, for how long will we still be able to look up at you?

When we overlook the pure white snowfield, accumulated snowflakes lie serenely, mirroring the warm, golden light that streetlamps cast, illumining the bottom of passers-by’s hearts, which originally filled with some annoying things, like working overtime without gaining anything, or getting into a conflict with someone he or she considers dearest, or, biting, frigid wind blowing right into cheek, as if thousands of sharp knives are pricking the skin. But at the time, the light disperses the dust, and pushes the haze in the heart aside, bringing peace and quiet, awakening hope for the future, for the year approaching. The snow, the crystal snow, the snow that decorates the empty city streets, will you still be here years later?

No matter how we get through the year just past, it doesn’t make any sense to immerse in the memory. We shall always look forward, but don’t forget, up in the sky, down on the ground, there must be someone else, caring you, supporting you, giving you hope whenever it seems impossible.

Anyhow, it’s a brand new beginning.

Goodbye, 2018. Hello, 2019.

Light III

He could feel drizzle patting his face.

To the best of his ability, he stood up. Anew, darkness enveloped him.

He pondered about what he had just experienced, which was patently a dreadful nightmare. Yet everything was so real, that he couldn’t persuade himself not to recall that dream.

In a moment, he caught sight of something in the distance, something that was gigantic enough to be seen. It was hard for him to put down the desire to approach it. He started padding, but he sensed something preternatural. As if he was walking through a long narrow corridor, in which there was solely enormously faint light.

When he finally reached the thing, he was astonished to find that he was facing a boundless wall which was clearly insurmountable. Scarcely had he had time to figure out what was happening when he was sucked into an exceedingly strong whirlpool, losing his consciousness.

He was astounded again when he opened his eyes.

In his sight there turned seasons. He could see fresh green seedlings protruding, carefree swallows singing and dancing freely in spring, and the brilliant sun creeping up gradually, tiny trees slowly growing to a huge proportion during summer, and with autumn coming the golden foliage fell, embellishing the azure blue sky, and before long clean white snowflakes began to appear, which indicated that winter had reigned the ground. It was quite amazed that he was able to recognize the various colors in no time, as well as the weathers he used to feel and the planets passing over head. What he once could only heard of was just in front of him, like an ancient but exquisite picture scroll opening before his face by degrees. Wherever his vision went, the superb landscapes appealed to him.

He was immersing himself in this fabulous world when in an instant, as if a heavy gate was opened, recollections flooded his brain.

He attempted to cast his mind back, and something mysterious occurred.

He could see his father holding him in his arms, while his mother cradled his brother, staring at two little lives, humming a familiar song he had heard for many times. He could see he and his brother climbing up and down at home, and his brother frequently lending him a hand without which he might have fallen off the table that was still higher than him. He could see the family outing, during which his relatives did not get weary of guiding him, telling him what was going on around, such as fragrant flowers dancing with colorful butterflies. So joyful was he at that time that as he thought, in his heart a knot was untied, and the ice melted.

Never had he realized that so many fantastic memories had been missing since his third birthday, for which he would have lived delightedly, appreciating the love and hope on earth, summoning up the courage and confidence, to strive for an entirely different life.

But it was said there was no sense crying over every mistake, for what had been done was unchangeable. He smiled, blandly, as he floated in the air, higher and higher.

Looking down, he saw himself, just lying, peacefully, on the snow-covered ground.


“There lies a wall, up to the heaven, down to the hell, left to infinity, right to where you cannot see.”

“This wall is called death.”

“Only when a person is confronted with this wall will he look back upon his entire life.”

Light II

He had no idea where he was.

And a strong feeling that he had never experienced before occupied his mind little by little.

The light was still there. So dim and nebulous was it that the dread of being encircled again by the darkness swiftly crept up from the bottom of his heart. Though he managed to shift his feet with all his strength, he could hardly budge an inch.

Brimming with confusion, he cast a glance at the ground, but only to find blur in his sight. Apparently he was trapped in a funny dream, which was made up of what he had sustained in reality.

Weak as it was, the light still produced warmth like the sun. He knew clearly the sensation of basking. The sunlight was gentle and mild. The feeling of extreme familiarity brought him back to his childhood.

He vaguely remembered that all around him were glee and thrill when he was a infant. Often his parents took him out, holding him in the arms, bathed in the sunshine. Pure and innocent, he enjoyed everything he heard, smelled, touched and tasted, not being aware of the fact that there existed something called vision, which he later thirsted for.

In his memories, his parents never loved him. Oh, maybe they were, before his third birthday. It was unbelievable that a three-year-old little boy could bear so many things in mind such as hearing a baby’s weep and his parents’ mirth, as well as realizing his disability, which had bothered him for what seemed like centuries. In fact, the voices kept reverberating in his mind, and continued pushing him to the verge of collapse. He considered that day a turning point of his life.

“My third birthday.” he smiled wryly, “My last birthday.”

He had no intention, and did not willing, to grumble at his parents. What made all the things transpire was his blindness. Even he felt guilty, and believed that himself was to blame. It was him that let his parents down, and that lost courage to live. It was his disadvantage that made him an object of ridicule, and that surrounded him with the deepest darkness. Had he not been blind, everyone would have lived a better life.

Few merry moments could be found in his recollections afterwards. Or maybe.. he pretended to have forgotten them?

He did not stop searching in his memories until the light began to peter out. His mental pain slightly alleviated as he pulled himself out of mind-wandering.

But an old saying told by his grandpa suddenly emerged in his brain, which sent shudder down his spine, “Only when a person is about to depart this world will he look back upon his entire life.”

For the first time in his life, his heart was seized by such unimaginable fear, and it nearly ceased bounding.

And there went off the light, silently, remaining darkness.

Light I

He was born blind.

He had suffered the darkness for years which he had been accustomed to, till that day, when something mysterious happened.

Abruptly he felt a soft, faint beam pierced the darkness, which seemed to be a firefly in the air, a lighthouse on the sea. Confused and attracted though, he got a sense of scare and decided not to move his feet, since he had never seen even a glimmer of light before.

In an instant the star-like light brightened, and it started twinkling. His curiosity aroused, he slowly groped his way towards the source, even if he couldn’t see it clearly. “The light is so gentle.” He thought to himself.

He recalled the period when he was surrounded by absolute darkness. It was not until his third birthday that he was told the earth was full of gorgeous scenery which he wasn’t able to witness, however he hadn’t got the point and he still lived joyfully. But gradually he had no notion of what people were talking when they chatted about weathers, landscapes, and even colors. This beset him a lot, and at last, he conceded the adversity reluctantly.

He had plodded for… how long? He couldn’t tell accurately, but he was depressed by the discovery of the fact that it was still a long distance from where the light was emitted.

Drooping his head with a sigh, he slowed his pace, disheartened. “Why should I undergo all of these?” A disgruntled thought flashed in his heart, and he couldn’t help asking.

That people queried the cause of his blindness was one of his antipathies. He had many antipathies, for instance, talking to others, but that was the very one he detested most, for always he was laughed at and was played a trick on at school, which made him consider everybody untrustworthy.

But he continued dragging himself to the light, as if he was driven by an invisible force. His mind in a turmoil, he couldn’t concentrate. He submerged himself in the past.

Was there anyone caring about him? He didn’t know, yet he would like to believe there wasn’t.

Occasionally he had a strong desire to leave this unlit world, the world with no hope, no laughter, and no happiness, to which he deemed himself useless. He was convinced of the sheer meaninglessness of life, and regarded every day as suffering. He even thought up a method. Maybe… jumping off something was a practical choice?

However, the explanation for the existence of this light remained a mystery. He didn’t care about this. He merely wished to see the source only once, which gave out light that he had yearned for for long. His ears were replete with winds, as he was rushing so fast—he found himself flying in the air.

And ultimately, he fell, asleep.

Yet light was there, still, inside his heart.

Notes on Physics

One-dimensional motion

$$
\begin{align}
v_f&=v_i+a \Delta t \\
\Delta x&=v_i \Delta t+{a \Delta t^2 \over 2} \\
\Delta x&={v_i+v_f \over 2} \Delta t \\
v_f^2&=v_i^2+2a \Delta x
\end{align}
$$

Forces and Newton’s laws of motion

$$
\begin{align}
F=ma
\end{align}
$$

Centripetal force and gravitation

$$
\begin{align}
a&={v^2 \over r}=\omega^2r \\
F&=G{m_1m_2 \over r^2}
\end{align}
$$

Work and energy

$$
\begin{align}
K&={mv^2 \over 2} \\
U_g&=F_gh=mgh \\
P&={W \over t}={Fx \over t}=Fv=mav
\end{align}
$$

Electric charge, field, and potential

$$
\begin{align}
F&=k{Q_1Q_2 \over r^2} \\
E&=k{Q \over r^2} \\
E&=2 \pi k \sigma \\
U_e&=k{Q_1Q_2 \over r} \\
V&=k{Q \over r}
\end{align}
$$

Circuits

$$
\begin{align}
R&={V \over I} \\
C&={Q \over V} \\
C&={A \over 4 \pi kd} \\
P&={U \over t}={U \over Q} \cdot {Q \over t}=VI=I^2R \\
W&=Pt=VIt=I^2Rt
\end{align}
$$

Magnetic forces, magnetic fields, and Faraday’s law

$$
\begin{align}
F&=QvB={Q \over t}(vt)B=ILB={B^2L^2v \over R} \\
B&={\mu_0I \over 2 \pi r} \\
\Phi&=BA \\
E&=N{\Delta \Phi \over \Delta t}=N{B\Delta A \over \Delta t}=NBLv \\
V_s&=V_p{N_s \over N_p}
\end{align}
$$

Momentum

$$
\begin{align}
I=mv=QLB={B^2L^2x \over R}
\end{align}
$$

Black-White Balls

题目描述

$n$ black and white balls were put into a bag. Petya doesn’t know exactly how many black balls are there among them. He knows, however, that there are $0, 1, \ldots, n$ black balls among all balls in the bag with equal probability.
Petya took $l$ balls from the bag at random, and $l_1$ of them turned out black, while $l_2$ other turned out white ($l_1+l_2=l$). Now he wants to predict how many black balls were there initially in the bag. Of course, if $l \lt n$, he can’t be sure in his prediction, but he wants to predict a segment $[a, b]$, such that the amount $k$ of black balls belongs to it with probability at least $p$.
You are given $n, l_1, l_2$ and $p$, and you must find such $a$ and $b$ that $b-a$ is minimal possible. If there are several such pairs $(a, b)$, choose the one with the smallest $a$.

题意概述

袋子里有$n$个球,每个球可能是黑色或白色。已知黑球个数在$0, 1, \ldots, n$之间等概率分布。现在从中取出$l$个球,其中有$l_1$个黑球和$l_2$个白球($l_1+l_2=l$)。要求找到一个最短的区间$[a, b]$,使得黑球个数在$[a, b]$中的概率至少为${p \over 100}$。若有多个这样的区间,输出$a$最小的。
数据范围:$1 \le n \le 50, \; 0 \le l_1 \le n, \; 0 \le l_2 \le n-l_1, \; 0 \le p \le 100$。

算法分析

令事件$A$为取出的$l$个球中有$l_1$个黑球,事件$B_i$为袋子里有$i$个黑球。根据贝叶斯定理
$$P(B_i|A)={P(B_i)P(A|B_i) \over \sum_{j=0}^n P(B_j)P(A|B_j)}$$
而我们知道
$$P(B_i)={1 \over n+1}, \; P(A|B_i)={{i \choose l_1}{n-i \choose l_2} \over {n \choose l}}$$
因此可以计算出$P(B_i|A)$,接下来只要枚举区间即可。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 55;
double a[N];

double get_c(int n, int m) {
  if (n < m)
    return 0;
  double ret = 1;
  for (int i = 0; i < m; ++i)
    ret *= 1. * (n - i) / (m - i);
  return ret;
}

int main() {
  int n, l1, l2, p;
  scanf("%d%d%d%d", &n, &l1, &l2, &p);
  double b = 0;
  for (int i = 0; i <= n; ++i)
    b += a[i] = 1. / (n + 1) * get_c(i, l1) * get_c(n - i, l2) / get_c(n, l1 + l2);
  for (int i = 1; i <= n + 1; ++i)
    for (int j = 0; j + i - 1 <= n; ++j) {
      double sum = 0;
      for (int k = j; k <= j + i - 1; ++k)
        sum += a[k];
      if (sum / b * 100 + 1e-12 >= p)
        return printf("%d %d\n", j, j + i - 1), 0;
    }
  return 0;
}

Fermat’s Last Theorem

题目描述

Given a positive integer $n$ and a positive prime number $p$, find $x, y$ and $z$ such that $x^n+y^n \equiv z^n \pmod p$ and $x, y$ and $z$ are nonzero modulo $p$ or report that there’s no such triple.

题意概述

给定一个整数$n$和一个质数$p$,判断方程$x^n+y^n \equiv z^n \pmod p \; (1 \le x, y, z \lt p)$是否存在整数解,若存在则给出一组解。有$T$组数据。
数据范围:$1 \le T \le 1000, \; 3 \le n \le 10^6, \; 2 \le p \le 10^6$。

算法分析

为了方便,以下同余方程模数均为$p$。
求出$p$的原根$g$,设$x=g^{k_1}, \; y=g^{k_2}, \; z=g^{k_3}$,方程变为
$$g^{k_1n}+g^{k_2n} \equiv g^{k_3n}$$
令$G=g^n$,则
$$G^{k_1}+G^{k_2} \equiv G^{k_3}$$
由于$g$是原根,可知$G \not \equiv 0$,因此
$$
\begin{align}
G^{k_1-k_2}+1 &\equiv G^{k_3-k_2} \\
G^{k_1-k_3}+G^{k_2-k_3} &\equiv 1
\end{align}
$$
根据费马小定理,$G^{p-1} \equiv 1$,所以只要从$1$到$p-1$枚举$i$,判断是否存在$j \le i$满足
$$G^i+1 \equiv G^j \lor G^j+1 \equiv G^i \lor G^i+G^j \equiv 1$$
若存在,则找到了一组解。若枚举到$i$时发现存在$j \lt i$满足$G^i \equiv G^j$,说明开始循环,直接输出无解。根据抽屉原理,枚举的次数不会太多。
此题时限较小,不能每组询问都清空数组,可以使用时间戳。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 1000005;
int a[N], b[N], pri[N];

int power(int a, int b, int p) {
  int ret = 1;
  for (; b; b >>= 1)
    b & 1 && (ret = 1ll * ret * a % p), a = 1ll * a * a % p;
  return ret;
}

int get_prt(int p) {
  int top = 0, k = p - 1;
  for (int i = 2; i * i <= k; ++i)
    if (!(k % i)) {
      pri[top++] = i;
      for (; !(k % i); k /= i)
        ;
    }
  if (k > 1)
    pri[top++] = k;
  for (int i = 2; i <= p - 1; ++i) {
    bool fg = 1;
    for (int j = 0; fg && j < top; ++j)
      fg &= power(i, (p - 1) / pri[j], p) > 1;
    if (fg)
      return i;
  }
  return 0;
}

int main() {
  int T;
  scanf("%d", &T);
  for (int n, p; T--;) {
    scanf("%d%d", &n, &p);
    int g = get_prt(p), gn = power(g, n, p), x = 0, y = 0, z = 0;
    for (int i = 1, G = gn; i <= p - 1; ++i, G = 1ll * G * gn % p)
      if (b[G] == T + 1)
        break;
      else {
        a[G] = i, b[G] = T + 1;
        if (b[G + 1] == T + 1) {
          x = power(g, i, p), y = 1, z = power(g, a[G + 1], p);
          break;
        }
        if (b[G - 1] == T + 1) {
          x = power(g, a[G - 1], p), y = 1, z = power(g, i, p);
          break;
        }
        if (b[1 - G + p] == T + 1) {
          x = power(g, i, p), y = power(g, a[1 - G + p], p), z = 1;
          break;
        }
      }
    x ? printf("%d %d %d\n", x, y, z) : puts("-1");
  }
  return 0;
}

Friendly Points

题目描述

Consider $n$ distinct points on a plane.
Two points from that set are said to be friends, when there exists a rectangle with sides parallel to coordinate axes that contains those two points and doesn’t contain any other point from the given set. A rectangle is said to contain a point if the point lies within the rectangle or on its border.
How many pairs of friends are there among the given points?

题意概述

给定平面上的$n$个点。定义一对点是友好点对当且仅当存在一个各边平行于坐标轴的矩形仅包含这两个点。一个点被一个矩形包含当且仅当该点在矩形内部或边界上。求有多少对友好点对。
数据范围:$1 \le n \le 10^5$。

算法分析

用CDQ分治,把平面上的问题转化为序列上的问题。将点分成上下两个部分,考虑属于不同部分的点对有多少,递归处理两个部分。
对$y$坐标分治,把两个部分中的点按$x$坐标从小到大排序,依次处理。假设处理到一个上半部分的点,当上半部分只有这个点时,下半部分可以与它构成友好点对的点的$y$坐标严格下降。因此我们可以对上半部分维护一个$y$坐标严格上升的单调栈,对下半部分维护一个$y$坐标严格下降的单调栈。在处理上半部分的某个点$p$时,用上半部分的单调栈找出$x$坐标最大的$y$坐标不大于它的点$q$,在下半部分的单调栈里二分出$x$坐标大于$q$的点有多少个,即是与$p$构成友好点对的点的个数。下半部分同理。
有一些细节:$y$坐标相同的点需放在同一部分,若某一部分中所有点的$y$坐标相同,则直接加上这一部分的答案,不递归处理;若有多个$x$坐标相同的点,上半部分只考虑$y$坐标最小的,下半部分只考虑$y$坐标最大的;两个部分中$x$坐标相同的点需同时处理。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
static int const MAX = 1000000001;
long long ans;
struct Point {
  int x, y;
  friend bool operator<(Point const &a, Point const &b) {
    return a.x < b.x;
  }
} p[N], s1[N], s2[N], tmp[N];

void calc(int l, int r) {
  if (l == r)
    return;
  int mid = (l + r) >> 1, L = mid - 1, R = mid + 1;
  for (; l <= L && p[L].y == p[mid].y; --L)
    ;
  for (; R <= r && p[R].y == p[mid].y; ++R)
    ;
  if (l > L && R > r) {
    std::sort(p + l, p + r + 1);
    return void(ans += r - l);
  }
  mid = l <= L ? L : R - 1;
  int p1 = l, p2 = mid + 1, p3 = l, t1 = 0, t2 = 0;
  calc(l, mid), calc(mid + 1, r);
  for (; p1 <= mid && p2 <= r;) {
    int x = std::min(p[p1].x, p[p2].x), mx = -MAX, mn = MAX;
    for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
      mx = std::max(mx, p[p1].y);
    for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
      mn = std::min(mn, p[p2].y);
    for (; t1 && s1[t1 - 1].y < mx; --t1)
      ;
    for (; t2 && s2[t2 - 1].y > mn; --t2)
      ;
    Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0}, r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
    for (; t1 && s1[t1 - 1].y == mx; --t1)
      ;
    for (; t2 && s2[t2 - 1].y == mn; --t2)
      ;
    if (mx > -MAX)
      ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
    if (mn < MAX)
      ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
  }
  for (; p1 <= mid;) {
    int x = p[p1].x, mx = -MAX;
    for (; p1 <= mid && p[p1].x == x; tmp[p3++] = p[p1++])
      mx = std::max(mx, p[p1].y);
    for (; t1 && s1[t1 - 1].y < mx; --t1)
      ;
    Point r1 = t1 ? s1[t1 - 1] : (Point){-MAX, 0};
    for (; t1 && s1[t1 - 1].y == mx; --t1)
      ;
    ans += s2 + t2 - std::upper_bound(s2, s2 + t2, r1), s1[t1++] = (Point){x, mx};
  }
  for (; p2 <= r;) {
    int x = p[p2].x, mn = MAX;
    for (; p2 <= r && p[p2].x == x; tmp[p3++] = p[p2++])
      mn = std::min(mn, p[p2].y);
    for (; t2 && s2[t2 - 1].y > mn; --t2)
      ;
    Point r2 = t2 ? s2[t2 - 1] : (Point){-MAX, 0};
    for (; t2 && s2[t2 - 1].y == mn; --t2)
      ;
    ans += s1 + t1 - std::upper_bound(s1, s1 + t1, r2), s2[t2++] = (Point){x, mn};
  }
  for (int i = l; i <= r; ++i)
    p[i] = tmp[i];
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i)
    scanf("%d%d", &p[i].x, &p[i].y);
  std::sort(p, p + n, [](Point const &a, Point const &b) { return a.y < b.y; });
  calc(0, n - 1), printf("%I64d\n", ans);
  return 0;
}

Recover Path

题目描述

Traveller Gregory is famous for his ability to always choose the shortest path for his journey. Ostap is a journalist who seeks for information about the recent Gregory’s trip. He managed to get the evidence that during this trip Gregory visited a number of cities. However, there is no information about the order in which they were visited, and no information about the starting city and the ending city of Gregory’s trip (the entire trip is (one of) the shortest path between these cities). Help Ostap to find any shortest path that contains all specified cities.
Country in which Gregory traveled consists of $n$ cities and $m$ undirected roads between them. For each road Ostap knows the time it takes to travel it, and the “shortest” word above is with respect to those times.
It is guaranteed that there exists some shortest path going through all specified cities.

题意概述

给定一张$n$个点$m$条边的无向图,第$i$条边的权值为$t_i$。给定其中$k$个点,要求找一对点$s, t$,使得这$k$个点都在从$s$到$t$的某条最短路径上,并输出这条路径。保证有解。
数据范围:$1 \le n, m \le 10^5, \; 1 \le t_i \le 10000$。

算法分析

显然,存在一种方案使得$s, t$在给定的$k$个点中。
从$k$个点中任选一个点,找到在$k$个点中距离它最远的点$u$,这个点一定是$s$或$t$,可以用反证法证明。接着从$u$开始跑最短路,得到一张拓扑图。令$f_i$表示从$i$到$u$的最短路径上最多包含多少个$k$个点中的点。只要按距离从小到大枚举$i$,再枚举它的连边是否可以作为最短路径中的边。同时还要记录方案。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne = 1, top, h[N], d[N], que[N], id[N], lst[N], pre[N], ans[N];
bool in[N], v[N];
struct Edge {
  int u, v, w, nxt;
} e[N << 1];

void add_edge(int u, int v, int w) {
  e[++ne] = (Edge){u, v, w, h[u]}, h[u] = ne;
  e[++ne] = (Edge){v, u, w, h[v]}, h[v] = ne;
}

void spfa(int s) {
  int qb = 0, qe = 1;
  memset(d, 0x3f, sizeof d), d[s] = 0, que[0] = s, in[s] = 1;
  for (; qb != qe;) {
    int u = que[qb++];
    in[u] = 0, qb == N && (qb = 0);
    for (int i = h[u]; i; i = e[i].nxt)
      if (d[e[i].v] > d[u] + e[i].w) {
        d[e[i].v] = d[u] + e[i].w;
        if (!in[e[i].v]) {
          if (qb == qe || d[e[i].v] > d[que[qb]])
            que[qe++] = e[i].v, in[e[i].v] = 1, qe == N && (qe = 0);
          else
            !~--qb && (qb = N - 1), que[qb] = e[i].v, in[e[i].v] = 1;
        }
      }
  }
}

int main() {
  int n, m, k, t;
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v, w; i <= m; ++i)
    scanf("%d%d%d", &u, &v, &w), add_edge(u, v, w);
  scanf("%d%d", &k, &t), v[t] = 1, spfa(t);
  int s = t;
  for (int i = 2; i <= k; ++i)
    scanf("%d", &t), v[t] = 1, d[s] < d[t] && (s = t);
  spfa(s);
  for (int i = 1; i <= n; ++i)
    id[i] = i;
  std::sort(id + 1, id + n + 1, [&](int const &i, int const &j) { return d[i] < d[j]; });
  for (int i : id) {
    lst[i] += v[i];
    for (int j = h[i]; j; j = e[j].nxt)
      if (d[e[j].v] == d[i] + e[j].w && lst[e[j].v] < lst[i])
        lst[e[j].v] = lst[i], pre[e[j].v] = j;
  }
  for (int i = 1; i <= n; ++i)
    if (lst[i] == k) {
      for (int j = pre[i]; j; j = pre[e[j].u])
        ans[top++] = j >> 1;
      break;
    }
  printf("%d\n", top);
  for (int i = 0; i < top; ++i)
    printf("%d ", ans[i]);
  puts("");
  return 0;
}