-
NOI2014 购票
Description: 今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发,到SZ市参加这次盛会。 全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v,我们给出了它在这棵树上的父亲城市 $f_v$ 以及到父亲城市道路的长度 $s_v$。 从城市 v 前往SZ市的方法为:选择城市 v 的一个祖先 ...…
-
NOI2016 循环之美
Description: 牛牛是一个热爱算法设计的高中生。在他设计的算法中,常常会使用带小数的数进行计算。牛牛认为,如果在 k 进制下,一个数的小数部分是纯循环的,那么它就是美的。 现在,牛牛想知道:对于已知的十进制数 n 和 m,在 k 进制下,有多少个数值上互不相等的纯循环小数,可以用分数 $\frac{x}{y}$ 表示,其中 $1≤x≤n,1≤y≤m$,且 x,y 是整数。 一个数是纯循环的,当且仅当其可以写成以下形式: $a.\do...…
-
Luogu_MayR1 B 总统选举
Description: 秋之国共有n个人,分别编号为1,2,…,n,一开始每个人都投了一票,范围1~n,表示支持对应编号的人当总统。共有m次预选,每次选取编号[$l_i$,$r_i$]内的选民展开小规模预选,在该区间内获得超过区间大小一半的票的人获胜,如果没有人获胜,则由小C钦定一位候选者获得此次预选的胜利(获胜者可以不在该区间内),每次预选的结果需要公布出来,并且每次会有$k_i$个人决定将票改投向该次预选的获胜者。全部预选结束后,公布最后成为总统的候选人。Input: 第一行两个...…
-
Luogu_MayR1 D 核心密码B
Description:令g(n)表示n能表示成几种不同的完全k次方数(k>1),求$f(n) = \sum_{i=2}^{n} \frac{g(i)}{i}$例如,$64=2^6=4^3=8^2$,所以g(64)=3。Input:多组询问,第一行一个整数T表示询问组数。接下来T行,每行一个整数n,表示询问$f(n)$。Output:T行,每行一个实数,表示f(n),保留十四位小数。由于精度误差,你的答案和标准答案差的绝对值在$2×10^{-14}$以内即可通过Hint:对于20%的...…
-
HNOI 2017 礼物
Description:我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手环,一个留给自己,一个送给她。每个手环上各有 n 个装饰物,并且每个装饰物都有一定的亮度。但是在她生日的前一天,我的室友突然发现他好像拿错了一个手环,而且已经没时间去更换它了!他只能使用一种特殊的方法,将其中一个手环中所有装饰物的亮度增加一个相同的自然数 c(即非负整数)。并且由于这个手环是一个圆,可以以任意的角度旋转它,但是由于上面装饰物的方向是固定的,所以手环不能翻转。需要在经过亮度改...…
-
HNOI 2017 单旋
Description:H国是一个热爱写代码的国家,那里的人们很小去学校学习写各种各样的数据结构。伸展树(splay)是一种数据结构,因为代码好写,功能多,效率高,掌握这种数据结构成为了H国的必修技能。有一天,邪恶的“卡”带着他的邪恶的“常数”来企图毁灭H国。“卡”给H国的人洗脑说,splay如果写成单旋的,将会更快。“卡”称“单旋splay”为“spaly”。虽说他说的很没道理,但还是有H国的人相信了,小H就是其中之一,spaly马上成为他的信仰。而H国的国王,自然不允许这样的风气蔓延,...…
-
HNOI 2017 大佬
Link:点我点我:-)Description: 人们总是难免会碰到大佬。他们趾高气昂地谈论凡人不能理解的算法和数据结构,走到任何一个地方,大佬的气场就能让周围的人吓得瑟瑟发抖,不敢言语。 你作为一个 OIER,面对这样的事情非常不开心,于是发表了对大佬不敬的言论。 大佬便对你开始了报复,你也不示弱,扬言要打倒大佬。 现在给你讲解一下什么是大佬,大佬除了是神犇以外,还有着强大的自信心,自信程度可以被量化为一个正整数 C( 1<=C<=10^8), 想要打倒一个大佬的唯一方法...…
-
ZJOI 2011 最小割 分治
Link:bzoj点我:-) 洛谷点我:-)Description:小白在图论课上学到了一个新的概念——最小割,下课后小白在笔记本上写下了如下这段话: ”对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果结点s,t不在同一个部分中,则称这个划分是关于s,t的割。 对于带权图来说,将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量,而s,t的最小割指的是在关于s,t的割中容量最小的割“ 现给定一张无向图,小白有若干个形如”图中有多少对点它们的最小割的容量不超过x呢...…