lonlyn 的小站

说明博客迁移更新中… 目前正在整理以前写的博客以及黑历史。 迁移清单博客园清单 名称 搬运 解析优化 代码优化 洛谷 P1995 程序自动分析 ok ok ok 洛谷 P5392 [Cnoi2019] 雪松树之约 洛谷 P2050 [NOI2012] 美食节 洛谷 P2053 [SCOI2007] 修车 ok Codeforces 734F Anton and School 洛谷 P3974 [TJOI2015] 组合数学 洛谷 P3567 [POI 2014] KUR-Couriers 洛谷 P1758 [NOI2009] 管道取珠 洛谷 P3195 [HNOI2008] 玩具装箱 洛谷 P2900 [USACO08MAR] Land Acquisition G 洛谷 P1261 服务器储存信息问题 洛谷 P2482 [SDOI2010] 猪国杀 洛谷 P2756 飞行员配对方案问题 洛谷 P2763 试题库问题 洛谷 P2774...

题目相关题目链接: 洛谷 P3723 [AH2017/HNOI2017] 礼物题目描述我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手环，一个留给自己，一个送给她。每个手环上各有 $n$ 个装饰物，并且每个装饰物都有一定的亮度。 但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个手环中所有装饰物的亮度增加一个相同的非负整数 $c$。并且由于这个手环是一个圆，可以以任意的角度旋转它，但是由于上面装饰物的方向是固定的，所以手环不能翻转。需要在经过亮度改造和旋转之后，使得两个手环的差异值最小。 在将两个手环旋转且装饰物对齐了之后，从对齐的某个位置开始逆时针方向对装饰物编号 $1 \sim n$，其中 $n$ 为每个手环的装饰物个数， 第 $1$ 个手环的 $i$ 号位置装饰物亮度为 $x_i$，第 $2$ 个手环的 $i$ 号位置装饰物亮度为 $y_i$，两个手环之间的差异值为（参见输入输出样例和样例解释）： $$\sum_{i=1}^{n}...

题目相关题目链接: 洛谷 P2717 寒假作业题目背景zzs 和 zzy 正在被寒假作业折磨，然而他们有答案可以抄啊。 题目描述他们共有 $n$ 项寒假作业。zzy 给每项寒假作业都定义了一个疲劳值 $a_i$，表示抄这个作业所要花的精力。 zzs 现在想要知道，有多少组连续的寒假作业的疲劳值的平均值不小于 $k$？ 简单地说，给定一个长度为 $n$ 的正整数序列 ${a_i}$，求出有多少个连续子序列的平均值不小于 $k$。 输入格式第一行是两个整数，分别表示序列长度 $n$ 和给定的参数 $k$。 第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。 输出格式输出一行一个整数表示答案。 样例 #1样例输入 #112343 2123 样例输出 #114 提示样例 1 解释共有 $6$ 个连续的子序列，分别是 $(1)$、$(2)$、$(3)$、$(1,2)$、$(2,3)$、$(1,2,3)$，平均值分别为 $1$、$2$、$3$、$1.5$、$2.5$、$2$，其中平均值不小于 $2$ 的共有 $4$ 个。 数据规模与约定 对于...

题目相关题目链接: 洛谷 P2053 [SCOI2007] 修车题目描述同一时刻有 $N$ 位车主带着他们的爱车来到了汽车维修中心。 维修中心共有 $M$ 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。 现在需要安排这 $M$ 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。 输入格式第一行有两个数 $M,N$，表示技术人员数与顾客数。 接下来 $N$ 行，每行 $M$ 个整数。第 $i+1$ 行第 $j$ 个数表示第 $j$ 位技术人员维修第 $i$ 辆车需要用的时间 $T_{i,j}$。 输出格式最小平均等待时间，答案精确到小数点后 $2$ 位。 样例 #1样例输入 #11232 23 21 4 样例输出 #111.50 提示对于 $100%$ 的数据，$2\le M\le 9$，$1\le N\le 60$，$1\le T\le...

题目相关题目链接: 洛谷 P2319 [HNOI2006] 超级英雄题目描述现在电视台有一种节目叫做超级英雄，大概的流程就是每位选手到台上回答主持人的几个问题，然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。 这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？ 输入格式输入的第一行是两个正整数 $n$ 和 $m$ ($0 < n < 1001, 0 < m <...

题目相关题目链接: 洛谷 P1066 [NOIP 2006 提高组] 2^k进制数题目描述设 $r$ 是个 $2^k$ 进制数，并满足以下条件： $r$ 至少是个 $2$ 位的 $2^k$ 进制数。 作为 $2^k$ 进制数，除最后一位外，$r$ 的每一位严格小于它右边相邻的那一位。 将 $r$ 转换为二进制数 $q$ 后，则 $q$ 的总位数不超过 $w$。 在这里，正整数 $k,w$ 是事先给定的。 问：满足上述条件的不同的 $r$ 共有多少个？ 我们再从另一角度作些解释：设 $S$ 是长度为 $w$ 的 $01$ 字符串（即字符串 $S$ 由 $w$ 个 $0$ 或 $1$ 组成），$S$ 对应于上述条件三中的 $q$。将 $S$ 从右起划分为若干个长度为 $k$ 的段，每段对应一位 $2^k$ 进制的数，如果 $S$ 至少可分成 $2$ 段，则 $S$ 所对应的二进制数又可以转换为上述的 $2^k$ 进制数 $r$。 例：设 $k=3,w=7$。则 $r$ 是个八进制数（ $2^3=8$ ）。由于 $w=7$，长度为...

题目相关题目链接: 洛谷 P2170 选学霸题目描述老师想从 $n$ 名学生中选 $m$ 人当学霸，但有 $k$ 对人实力相当，如果实力相当的人中，一部分被选上，另一部分没有，同学们就会抗议。所以老师想请你帮他求出他该选多少学霸，才能既不让同学们抗议，又与原来的 $m$ 尽可能接近。 输入格式第一行，三个正整数 $n,m,k$。 接下来 $k$ 行，每行 $2$ 个数，表示一对实力相当的人的编号（编号为 $1,2,\cdots n$）。 输出格式共一行，表示既不让同学们抗议，又与原来的 $m$ 尽可能接近的选出学霸的数目。 如果有两种方案与 $m$ 的差的绝对值相等，选较小的一种。 样例 #1样例输入 #11234 3 21 23 4 样例输出 #112 提示对于 $100%$ 的数据，满足 $1 \le n,m \le 2 \times 10^4$。 题目解析如果一组人的实力相同，那么他们所有人要么全选，要么不选，无法分割。可以用并查集来将所有人分成这样的组。 那么自然可以联想到背包 dp...

题目相关题目链接: 洛谷 P1514 引水入城题目描述在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个 $N$ 行 $M$ 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。 因此，只有与湖泊毗邻的第 $1$ 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。故一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。由于第 $N$ 行的城市靠近沙漠，是该国的干旱区，所以要求其中的每座城市都建有水利设施。那么，这个要求能否满足呢？如果能，请计算最少建造几个蓄水厂；如果不能，求干旱区中不可能建有水利设施的城市数目。 输入格式每行两个数，之间用一个空格隔开。输入的第一行是两个正整数 $N,M$，表示矩形的规模。接下来 $N$ 行，每行 $M$...

题目相关题目链接: 洛谷 P1995 程序自动分析题目描述在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。 考虑一个约束满足问题的简化版本：假设 $x_1,x_2,x_3,\cdots$ 代表程序中出现的变量，给定 $n$ 个形如 $x_i=x_j$ 或 $x_i\neq x_j$ 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：$x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1$，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。 现在给出一些约束满足问题，请分别对它们进行判定。 输入格式输入的第一行包含一个正整数 $t$，表示需要判定的问题个数。注意这些问题之间是相互独立的。 对于每个问题，包含若干行： 第一行包含一个正整数 $n$，表示该问题中需要被满足的约束条件个数。接下来 $n$ 行，每行包括三个整数...