2007

题目 神奇模拟题。最直接的做法就是每个石头暴力向下滚，有 \(60\) 分。但是大样例跑了 \(15s\)。稍微观察一下，会发现很多次循环都是在重复向下走到一格空位上，于是考虑优化：用 set 维护每一列的那些位置有障碍（包括石头），每次直接 lower_bound 跳到下一个位置，会快很多，大样例 ......

数位DP。 首先分析下题目，将 \(n\) 表示成一些 \(4^k\) 的数之和/差的形式 ，就可以理解为一个天平，\(n\) 放在左边，可以选一些数值为 \(4\) 的幂的砝码，放左/右都行，在让天平平衡，求方案数。 \(4^k\) 很容易联想到四进制，于是考虑把 \(n\) 转换为四进制后进行数 ......

题目链接：[Cerc2007] robotic sort 机械排序 前置知识点：文艺平衡树 具体的我们会将序号下标作为平衡树的键值，这样一来每个节点其实就是数组中的每个位置，又因为这个位置是具有有序性的，所以我要找某个位置的当前值是可以在树上二分出来的，同时考虑平衡树的一段子树打翻转标记，交换左右子 ......

目前，可供本科学生使用的生物信息学著作为数不多，本书恰恰是其中的一本。国内生物信息学，计算生物学、计算数学等领域的本科生、研究生和其他研究人员，会从书中汲取基本的算法原理、解决实际问题的方法和技巧，进而更好地从事相关研究工作。 目录 播报 编辑 1 绪论 2 算法与复杂性 2.1 算法是什么？ 2. ......

P2144 [FJOI2007] 轮状病毒 Problem 一个 \(n\) 轮状基由圆环上 \(n\) 个不同的基原子和圆心的一个核原子构成。\(2\) 个原子之间的边表示这 \(2\) 个原子之间的信息通道。 \(n\) 轮状病毒的产生规律是在 \(n\) 轮状基中删除若干边，使各原子之间有唯一 ......

题目描述 给定一棵大小为 \(n\) 的 \(1\) 为根节点的树，树用如下方式给出：输入 \(a_2,a_3,\dots,a_n\)，保证 \(1\leq a_i<i\)，将 \(a_i\) 与 \(i\) 连边形成一棵树。 接下来有 \(m\) 次操作，操作有两种： 1 l r x 令 \(a_ ......

link 题解没一个说为什么能用最小割的...（当然可能是只有我不知道） 设交换后行、列数相同的第 \(x\) 行和第 \(y\) 列（\(x,y\) 为原始位置），发现它们的交点现在位于 \((i,i)\)，原来位于 \((x,y)\)。因为无论怎么交换位置，原来的交点仍是交点。 所以可以得出一个 ......

P7446 [Ynoi2007] rfplca 可以用分块维护，记 $ b_i $ 表示这个块中第一个 \(a_i\) 不在块中的值 区间修改： 对于散块，直接暴力重构 对于整块，发现 \(b_i\) 所属点最多只会改变 \(\sqrt n\) 次，所以也暴力重构 查询： 考虑像倍增一样的过程，先把 ......

原题链接：P6370 思路 题意不多赘述。 首先这道题的 \(60\) 分暴力很好打，直接按题目中的操作做即可，时间复杂度 \(O(nr)\)。 考虑优化暴力。我们会发现很多次石头的起始点为同一列的情况，其实每一次下落的轨迹是差不多的。具体来讲应该是第一次下落的轨迹一定包含了后面每一次的轨迹。所以我 ......

题意 给定一个数 \(n\)，要求将 \(n\) 表示成一些 \(4^{k}\) 的数之和或差的形式，要求用的数最少，求方案数。 思路 首先看到这道题的数据范围 \(n\le10^{1000}\)，又是求方案数，所以想到用数位 DP。因为每一个数都是 \(4\) 的次幂，显然我们需要讲原数转化为 \ ......

题意 有 \(n\) 个工人，\(m\) 个工作。 每个人给每个工作有 \(t_{i, j}\) 的花费。 求每个工作的最小平均花费。 Sol 直接连边跑费用流不好搞。 考虑将每种工人在不同时间做的工作暴力建点。 枚举 \(k\) 表示第 \(i\) 个工人在倒数第 \(k\) 个做 \(j\) 工 ......

[SCOI2007] 修车 题目描述 同一时刻有 \(N\) 位车主带着他们的爱车来到了汽车维修中心。 维修中心共有 \(M\) 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。 现在需要安排这 \(M\) 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时 ......

前言 翻遍洛谷题解，看到大家都在套模板，却很少有人讲出为什么，使我十分崇拜天赋哥。 原题链接 关于这题的一些事实性证据 事实1.来自 事实2.来自 事实3.来自 事实4.来自 整理上述事实 1.每一次”最短“最优涂色，要么在其他颜色的基础上涂，这称之为融入一个整体；要么另辟蹊径单独找一块地涂，这称为 ......

题意 求 \(\sum_{i = 1} ^ {n} \sum_{j = 1} ^ {m} [gcd(i, j) = k]\)。 Sol \[\begin{aligned} f(k) &= \sum_{i = 1} ^ {n} \sum_{j = 1} ^ {m} [\gcd(i, j) = k] \ ......

[ZJOI2007] 仓库建设 题目描述 L 公司有 \(n\) 个工厂，由高到低分布在一座山上，工厂 \(1\) 在山顶，工厂 \(n\) 在山脚。 由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三 ......

IOI 2007 Pairs 可以考虑三个情况： 若B=1: 这其实好像没什么好说的？lower_bound就可以轻轻松松30分 code: void solve1(){ for(int i=0;i<N;i++){ std::cin>>a[i]; } sort(a,a+N); i64 ans=0; ......

P4170 [CQOI2007] 涂色 基本思路 很容易口胡一个状态。 \(F_{l,r}\) 表示 \(ch_l\) 到 \(ch_r\) 的最小操作次数。 然而转移就开始满头大汗。 状态转移 只想到 \(F_{i,i} = 1\) 以及肯定有 \(F_{l,r} = \min(F_{l,r}, ......

[SHOI2007] 园丁的烦恼 题目背景 很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。 有一天国王漫步在花园里，若有所思，他问一个园丁道： “最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……” “那么本质上 ......

P1098 [NOIP2007 提高组] 字符串的展开http://ww.luogu.com.cn/problem/P1098 注意 字符中的数字是默认小于字母的。 所以要对数字做特判。 #include <iostream> #include <string> using namespace st ......

三种食物，两个矿地。 每个矿地会记得最靠近的三种食物, 每一次给他们一个新的食物时，答案会加上有多个不同的食物。 求答案的最大值。 很简单的dp: dp[i][a1][a2][b1][b2] 表示当前已经分了i个食物, a的上两个食物为a1,a2，b的上两个食物为b1,b2。 那么转移状态为： 让s ......

挺喜欢的一题。 首先我们很容易观察到一个性质：每一行和每一列上的黑色方格的数量是不变的，只能改变它在那一行和那一列的排列顺序。由此若是有某一行或某一列上没有黑色方格，直接输出 No 即可。此时我们考虑的情况就是每一行和每一列上至少都会有一个黑色方格。 这时有一个结论：若有解我们可以仅通过交换行来达成 ......

应该都和我一样一下水了两题吧 P2491 [SDOI2011] 消防 P1099 [NOIP2007 提高组] 树网的核 题目描述 在一颗 \(n\) 个节点的无根树中，找到一条不超过 \(s\) 的路径，使得图中所有点到此路径距离的最大值最小，图中边权非负 分析 若想将此题转化到树网的核，首先要证 ......

题目描述 将一个矩形分割成 \(n\) 个小矩形，每个小矩形的总分为这个矩形内所有数的和。求各矩形总分均方差最小值。 具体思路 先来几个定义。 均方差：$$\sqrt{\frac{1}{n} \times \sum_{i=1}^n (a_i-avg)^2}$$ 方差：$$\frac{1}{n} \t ......

有一些墙壁链接(ax,ay), (bx,by) 每次若有墙壁的两边一个有水，一个为空，墙壁就破了然后水开始充了起来 找出最后还存在的墙壁 首先我们可以看出来墙壁的两边是可以用节点表示的 我们需要合并一些区间什么的, 听说这一题有些人利用对偶图来求但是我不会 可以自己想想怎么样合并/哪个区间要合并 O ......

今天开始做IOI的学习笔记, 就从我出生的年份开始吧 IOI 2007 Aliens: 给你三个整数 N, X, Y 表示网格有N * N大， 而 （X，Y）是黑色的图 那个图是这样的： #.#.# .#.#. #.#.# .#.#. #.#.# #表示黑色 .表示白色 而整个N*N的网格只有一个这 ......

P3464 显然的，先将原数变为四进制的数。 由于算的是进位/不进位的代价最小值和方案数，容易想到 dp。 这里假定该四进制数是从高位到低位的，顺序显然是由低位到高位。 令 \(f_{i,0/1}\) 表示第 \(i\) 位进 / 不进位的最小代价，\(g_{i,0/1}\) 表示的是最小代价下的方 ......

转自宋永志博客，宋永志博客 - 最纯净的系统下载站 (songyongzhi.com) Office 2007 SP3 简体中文专业增强版 2019.02(终结版) 软件介绍：1、Office 2007 SP3专业增强版，集成补丁至2019年02月，集成正版序列号，安装完后自动激活。2、Office ......

Description 给定 \(n \times m\) 的矩阵，找大小为 \(k \times k\) 的子矩阵 \(a\)，使得子矩阵 \(\max\{a\}-\min\{a\}\) 最小。 Solution Solution 1 枚举所有 \(k \times k\) 的子矩阵，然后枚举最大 ......

20230918 P3188 [HNOI2007] 梦幻岛宝珠 Statement 01背包， \(n \le 100\)，但是容量 \(m \le 2^{30}\)。 物体的体积可以写成 \(a \times 2^b(a \le 10,b \le 30)\) Solution 发现 \(W\) 太 ......

其实是我 Li-Chao-Tree 哒！！ 考虑转移 \(f_x = \min f_{anc} + (d_{x} - d_{anc})p_x + q_x\) 其中 \(anc\) 为 \(x\) 的祖先，然后满足 \(d_{anc} \geq d_{x} - li_{x})\)。 考虑如果用权值线段 ......