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

ソロモンの悪夢、見せてあげる!

@krydom1周前

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).

Read More →

[CF 472D] Design Tutorial: Inverse the Problem

@krydom1周前

04/19
21:47
Delaunay三角剖分 欧几里得最小距离生成树

[2017.04.18 省选模拟赛] 旅行商

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

前面说到moreD在天际里投机倒把赚钱,看着自己的金币蹭蹭往上涨当然是一件令人偷税愉悦(●’◡’●)的事情。
但是考虑到在路上跑的时间成本,整件事情就不那么让人满意了。
moreD共在 N 个城市间倒卖物品。他从 1 号城市出发,自然,这 N 个城市都是要访问到的。
好消息是,moreD装了一个奇怪的mod,可以让他使用飞行坐骑,于是两个城市间的距离就是它们之间的直线距离。
由于moreD玩游戏的时候是个没有耐心的人,他希望最小化在路上最长花费的时间,也就是说,使得在城市间飞行的距离的最大值最小。
moreD明白这应该需要写算法解决,但是由于3D眩晕症,他现在已经脸如死灰地躺在床上了(◎﹏◎),显然不能胜任这个任务。于是他希望你能帮他解决这个问题。
无畏的勇者(没有龙可以屠实在是不好意思了)啊,赶快解决这个问题,把moreD从无尽跑路的深渊中拯救出来吧!

Read More →

[2017.04.18 省选模拟赛] 旅行商

@krydom1周前

04/19
21:39
Fib循环节 快速幂 矩阵乘法

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

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

moreD的隔壁室友(人称隔壁老王的)liouzhou_101最近选了数论课,经过一段时间的卓有成效的学习,他非常自信,认为自己的数论水平已经可以吊打全国 99.99\%的学生了。O(* ̄▽ ̄*)ブ
某天 12 点他正准备起床的时候,突然想到了这么一个问题:给出一个 n ,求 Fib(2^n)
这里的 Fib 定义为 Fib(0)=0, Fib(1)=1 , 对于 n\ge2, Fib(n)=Fib(n-1)+Fib(n-2)
然而还有一周数论就要期末考了,他还要好好复习争取吊打全国 100\% 的学生,于是他决定把这个问题交给一个骨骼精奇的小朋友——也就是你——来解决。如果你能成功解决这个问题,就可以得到来自liouzhou_101的祝福哦~
无畏的勇者(吐槽这个称号你就输了)啊,赶快解决这个问题,将全国学生从liouzhou_101的手里拯救出来吧!

Read More →

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

@krydom1周前

04/19
21:26
spfa 乱搞 暴力 离线

[czyz 2017.04.16 noip- 模拟赛]

A:http://czyzuoj.com/problem/77

B:http://czyzuoj.com/problem/78

C:http://czyzuoj.com/problem/79

 

A:

【防AK好题(???)(雾)】

假·在线,从前往后做应该是不能做的....

因为最后一行解密出来是0,0,0,所以我们先可以直接知道最后一个询问的答案

然后发现如果已经知道了第i个询问的答案,求解第i-1个询问的答案只要接一个一元一次方程就可以了... Read More →

[czyz 2017.04.16 noip- 模拟赛]

@krydom3周前

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号奶牛为树根。
问对于每个奶牛来说,它的子树中有几个能力值比它大的。

Read More →

[bzoj 4756] [Usaco2017 Jan]Promotion Counting

@krydom3周前

04/9
16:59
游记

JSOI 2017 游记

DAY 0

今年和往常不一样 round 1 就在自己学校啊,往年似乎都是round 2 的样子

中午就看见有好多dalao在食堂,然而我们并没有饭票只好自己买锅吃了啊(雾

下午jyy讲课,并不是很能理解线性规划对偶这种东西

晚上听zzy说饭票可以换锅啊.... 可是由于我校良好的作息时间高一高二双休所以之后没锅了23333

然后考前越发觉得自己虚啊 以前懒都不高兴学什么东西

然后这个晚上学了一下斜率优化和2-sat 背了一下sa就去睡觉了 Read More →

JSOI 2017 游记