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

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

@krydom2月前

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 省选模拟赛] 旅行商

@krydom2月前

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 省选模拟赛] 隔壁老王的简单数列

@krydom2月前

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 游记

@krydom3月前

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。但他希望费用最小.

Read More →

[bzoj1010] [HNOI2008]玩具装箱toy

@krydom3月前

04/8
19:43
斜率优化

[bzoj4518] [Sdoi2016]征途

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

Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段,相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外,每一天晚上Pine都必须在休息站过夜。所以,一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v,可以证明,v×m^2是一个整数。为了避免精度误差,输出结果时输出v×m^2。

Read More →

[bzoj4518] [Sdoi2016]征途

@krydom3月前

04/8
19:40
2-SAT

[bzoj1823] [JSOI2010]满汉全席

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

满汉全席是中国最丰盛的宴客菜肴,有许多种不同的材料透过满族或是汉族的料理方式,呈现在數量繁多的菜色之中。由于菜色众多而繁杂,只有极少數博学多闻技艺高超的厨师能够做出满汉全席,而能够烹饪出经过专家认证的满汉全席,也是中国厨师最大的荣誉之一。 世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成,而他们之间还细分为许多不同等级的厨师。为了招收新进的厨师进入世界满汉全席协会,将于近日举办满汉全席大赛,协会派遣许多会员当作评审员,为的就是要在參赛的厨师之中,找到满汉料理界的明日之星。 大会的规则如下:每位參赛的选手可以得到n 种材料,选手可以自由选择用满式或是汉式料理将材料当成菜肴。大会的评审制度是:共有m 位评审员分别把关。每一位评审员对于满汉全席有各自独特的見解,但基本见解是,要有兩样菜色作为满汉全席的标志。如某评审认为,如果没有汉式东坡肉跟满式的涮羊肉锅,就不能算是满汉全席。但避免过于有主見的审核,大会规定一个评审员除非是在认为必备的两样菜色都没有做出來的狀况下,才能淘汰一位选手,否则不能淘汰一位參赛者。换句话說,只要參赛者能在这兩种材料的做法中,其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉,羊肉和牛肉时,有四位评审员的喜好如下表: 评审一 评审二 评审三 评审四 满式牛肉 满式猪肉 汉式牛肉 汉式牛肉 汉式猪肉 满式羊肉 汉式猪肉 满式羊肉 如參赛者甲做出满式猪肉,满式羊肉和满式牛肉料理,他将无法满足评审三的要求,无法通过评审。而參赛者乙做出汉式猪肉,满式羊肉和满式牛肉料理,就可以满足所有评审的要求。 但大会后來发现,在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话,所有的參赛者最多只能通过部分评审员的审查而不是全部,所以可能会发生没有人通过考核的情形。如有四个评审员喜好如下表时,则不論參赛者采取什么样的做法,都不可能通过所有评审的考核: 评审一 评审二 评审三 评审四 满式羊肉 满式猪肉 汉式羊肉 汉式羊肉 汉式猪肉 满式羊肉 汉式猪肉 满式猪肉 所以大会希望有人能写一个程序來判断,所选出的m 位评审,会不会发生 没有人能通过考核的窘境,以便协会组织合适的评审团。

Read More →

[bzoj1823] [JSOI2010]满汉全席

@krydom3月前

04/6
09:11
prufer序列 快速幂

[bzoj 4766] 文艺计算姬

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

"奋战三星期,造台计算机"。小W响应号召,花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺术细胞。普通计算机能计算一个带标号完全图的生成树个数,而文艺计算姬能计算一个带标号完全二分图的生成树个数。更具体地,给定一个一边点数为n,另一边点数为m,共有n*m条边的带标号完全二分图K_{n,m},计算姬能快速算出其生成树个数。小W不知道计算姬算的对不对,你能帮助他吗?

Read More →

[bzoj 4766] 文艺计算姬