# Krydom: 暁の水平线に胜利を刻むのです

04/20
07:53
kruskal

## [CF 472D] Design Tutorial: Inverse the Problem

### ♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

There is an easy way to obtain a new task from an old one called "Inverse the problem": we give an output of the original task, and ask to generate an input, such that solution to the original problem will produce the output we provided. The hard task of Topcoder Open 2014 Round 2C, InverseRMQ, is a good example.

Now let's create a task this way. We will use the task: you are given a tree, please calculate the distance between any pair of its nodes. Yes, it is very easy, but the inverse version is a bit harder: you are given an n × n distance matrix. Determine if it is the distance matrix of a weighted tree (all weights must be positive integers).

04/19
21:47

## [2017.04.18 省选模拟赛] 旅行商

### ♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

moreD共在 $N$ 个城市间倒卖物品。他从 $1$ 号城市出发，自然，这 $N$ 个城市都是要访问到的。

moreD明白这应该需要写算法解决，但是由于3D眩晕症，他现在已经脸如死灰地躺在床上了(◎﹏◎)，显然不能胜任这个任务。于是他希望你能帮他解决这个问题。

04/19
21:39

## [2017.04.18 省选模拟赛] 隔壁老王的简单数列

### ♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

moreD的隔壁室友（人称隔壁老王的）liouzhou_101最近选了数论课，经过一段时间的卓有成效的学习，他非常自信，认为自己的数论水平已经可以吊打全国 $99.99\%$的学生了。O(*￣▽￣*)ブ

04/19
21:26

A：

【防AK好题（？？？）（雾）】

04/19
21:16

## [bzoj 4822] [Cqoi2017]老C的任务

### ♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

大意：给一些点和权值，询问一个矩形内的权值总和，离线
$n, m \le 10 ^ 5$

04/11
13:11

## [bzoj 4756] [Usaco2017 Jan]Promotion Counting

### ♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

The cows have once again tried to form a startup company, failing to remember from past experience that cows make terrible managers!The cows, conveniently numbered 1…N1…N (1≤N≤100,000), organize the company as a tree, with cow 1 as the president (the root of the tree). Each cow except the president has a single manager (its "parent" in the tree). Each cow ii has a distinct proficiency rating, p(i),which describes how good she is at her job. If cow ii is an ancestor (e.g., a manager of a manager of a manager) of cow jj, then we say jj is a subordinate of ii.
Unfortunately, the cows find that it is often the case that a manager has less proficiency than several of her subordinates, in which case the manager should consider promoting some of her subordinates. Your task is to help the cows figure out when this is happening. For each cow ii in the company, please count the number of subordinates jj where p(j)>p(i).
n只奶牛构成了一个树形的公司，每个奶牛有一个能力值pi，1号奶牛为树根。

04/9
16:59

04/8
19:45

## [bzoj1010] [HNOI2008]玩具装箱toy

### ♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小.

04/8
19:43

## [bzoj4518] [Sdoi2016]征途

### ♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

Pine开始了从S地到T地的征途。

Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。

04/8
19:40
2-SAT