2009

原题链接 题记 就是线段树，不过树和延迟标记有点绕 code #include<bits/stdc++.h> using namespace std; struct SegmentTree { vector<int> tree, lazy;//tree代表这个节点开着灯的数量，lazy代表这个节点是 ......

题目传送门 思路 看一眼数据，\(1\le N\)，\(M\le10^9\)，太难入手了。所以这道题肯定是从 \(\text{W}\) 和 \(\text{k}\) 入手的。 对于 \(\text{W}\)：离散化（此后最多会有 \(2\times W\) 个坐标）； 对于 \(\text{k}\) ......

本书介绍分子生物学的基本常识、限制图谱和多重图谱，研究克隆和克隆图谱，讨论DNA序列相关的话题，涉及序列中模式计数的统计问题等。 [1] 图书目录 编辑 播报 《生物数学丛书》序 前言 数学符号 第0章 引言 第1章 分子生物学一些知识 第2章 限制图谱 第3章 多重图谱 第4章 求解DDP的算法 ......

## 题目描述 世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的 $150\%$ 划定，即如果计划录取 $m$ 名志愿者，则面试分数线为排名第 $m \times 150\ ......

[IOI2009] Regions Luogu P5901 题目描述 联合国区域发展委员会（The United Nations Regional Development Agency, UNRDA）有一个良好的组织结构。它任用了 \(N\) 名委员，每名委员都属于几个地区中的一个。委员们按照其资历 ......

给 EI 题解写注 qwq。。 化简方差： \[\frac{1}{n}\sum(a_i-\overline a)^2\\ =\frac{1}{n}(\sum a_i^2-2\overline {a}\sum a_i+n\overline a^2)\\ =(\frac{1}{n}-\frac{1}{n ......

[HNOI2009] 梦幻布丁 题目描述 $n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。 例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色. 输入格式 第一行是两个整数，分别表示布丁个数 $n$ 和操作次 ......

庙会捷运Fair Shuttle 公交车一共经过 n 个站点，从站点 1 一直驶到站点 n。k群奶牛希望搭乘这辆公交车。第 ii 群牛一共有 m_i只。他们希望从 s_i到 e_i去。 公交车只能坐 c 只奶牛。而且不走重复路线，请计算这辆车最多能满足多少奶牛的要求。注意：对于每一群奶牛，可以部分满 ......

脑子没了 直接做 \(2^{28}\) 肯定是不行的，所以必定要施加容斥，先考虑对行列均进行容斥，也就是枚举哪些行间、列间没有任何骨牌跨过，可以发现，这些行列将网格划分成了若干矩形，那么只要算出这些矩形的方案乘起来就行了，矩形的方案容易直接插头 \(dp\) 算 但是并没有起到优化的效果，因此考虑只 ......

链接 这道题卡了我 $40$ 多分钟。 其实就是跑两遍广搜，第一遍算出每个点距离树的最小距离，第二遍开个优先队列，算出逃回窝的途中最大可能的离它最近的树的距离的最小值。 接下来重点讲一下第二遍广搜。 首先，我们要知道，如果我们用 queue ，那么最先到的点不一定是最优的。 所以，我们需要用 pri ......

P1972 [SDOI2009] HH的项链 我们考虑将所有询问按照右端点归类。 然后从左往右扫描每个位置，如果前面有位置和它重复，就把前面的位置删掉（这样做是对的，因为右端点只可能在之后了，那么要访问到前面的位置，就必须要到达这个位置，相当于把重复的贡献减掉）。 初始时假设所有位置都不重复，都是 ......

[NOI2009] 管道取珠 - 洛谷 题目详情 - [NOI2009] 管道取珠 - BZOJ by HydroOJ 非常神奇的一个思路。 考虑我们要计算的式子的真正意义。\(\sum a_i^2\) 不就相当于让两个管道取珠系统同时进行，最后取出方案完全相同的方案数吗？ 因此我们考虑朴素 \(d ......

/* "爆int, 爆int, 你就会爆int了是吧" 还是挺难的一道题 具体思路就是通过求出b1的所有约数, 然后看看其中有几个满足gcd(a0, x) == a1 && lcm(b0, x) == b1的数x 通过上一题其实可以求出来, 在int范围内一个数的约数数量最多只有1600个 lcm可 ......

P5901 [IOI2009] Regions 给你一棵树，每个点有颜色 \(h_i\)。 多次询问，每次询问有多少对 \((u, v)\) 满足 \(u\) 是 \(v\) 的祖先且 \(u\) 的颜色是 \(r_1\) 且 \(v\) 的颜色是 \(r_2\)。 \(n, q \le 2 \ti ......

[HNOI2009] 梦幻布丁 题目描述 \(n\) 个布丁摆成一行，进行 \(m\) 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。 例如，颜色分别为 \(1,2,2,1\) 的四个布丁一共有 \(3\) 段颜色. 数据范围 对于全部的测试点，保证 \(1 \l ......

题目描述 你需要计算一个函数 \(F(x, y)\)，其中 \(x, y\) 是两个正整数序列。 bool F(std::vector<int> x, std::vector<int> y) { if (W(x).size() != W(y).size()) return false; if (W( ......

BalticOI 2009 Day1 - 甲虫 https://www.luogu.com.cn/problem/P4870 首先看到题面就能想到排序后区间 dp。 设 \(f_{i,j,0/1}\) 表示区间 \([i,j]\)，收集完毕后在哪个端点时能收集到最多的露水，但是发现转移过程中还需要这 ......

考虑将每个支撑点都先设成其下限高度，即 \(h_i\gets h_1-(i-1)\times d\)，这样就只会提高某些支撑点的高度。 显然每次提高的是一个后缀。提高某个后缀的贡献是当前高度低于原先高度的支撑点数量减去当前高度不低于原先高度的支撑点数量。选择贡献最大的后缀直到最后一个支撑点的高度等于 ......

P5901 [IOI2009] Regions 更好的阅读体验 根号分治，过掉不难，但是想 \(\mathcal O(n\sqrt n)\) 还是有一些思维含量的。 首先考虑一种暴力：预处理两两颜色间的答案，\(\mathcal O(1)\) 查询。首先枚举颜色数，然后每种颜色 \(\mathcal ......

P3870 [TJOI2009] 开关 思路：可以用线段树来维护区间中亮灯的个数，区间修改用加上懒标记就好 #include <bits/stdc++.h> #define LL long long using namespace std; const int N = 1e5 + 10; struc ......

P5189 容易想到区间 dp，考虑设计状态。 首先如果只有 \(l,r\) 两维的话，是无法转移的。然后发现 \(m\) 是转移的一个必要的条件，可加入 \(m\) 这一维。由于是区间 dp，所以只需考虑向左或向右加珠子，不妨令 \(f_{i,j,k}\) 消除 \([i,j]\) 以及 \(i\ ......

数位dp 引入 数位 ：是指把一个数字按位数一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制，就比如 链接: [SCOI2009] windy 数的二进制同理。 常见特征 要求统计满足一定条件的数的数量（即，最终目的为计数）； 这些条件经过转 ......

轮廓线 DP + 外部容斥。似乎是 CDQ 论文题。 有一个 \(n\times m\) 的矩形表格，其中有一些位置有障碍。现在要在这个表格内放一些 \(1\times2\) 或者 \(2\times1\) 的多米诺骨牌，使得任何两个多米诺骨牌没有重叠部分，任何一个骨牌不能放到障碍上。并且满足任何相 ......

二叉查找树 首先该树的中序遍历是唯一可以确定的（直接按照数据值排序即可）。 然后，因为权值可以被修改成一切实数，故我们完全可以把权值离散化掉。 于是我们现在可以设置一个 DP 状态 \(f[l,r,lim]\) 表示： 区间 \([l,r]\) 中的所有东西构成了一棵子树，且树中最小权值不小于 \( ......

所有的 \(DP\) ，只要式子一推出来（不管复杂度），那就很简单了，因为优化是成千上万种的…… 思路1: 我们考虑设 \(f[i][j][k]\) 表示：当前 \(DP\) 到第 \(i\) 块木板的第 \(j\) 个位置，共涂了 \(k\) 次，所能获得的最大收益。因为还要枚举当前这次涂是从哪到 ......

LG 任意时刻每个点最多被一条线段覆盖 暴力删每条线段是对的 插入 \([l,r]\) 时需要删除的线段要么被 \([l,r]\) 包含，要么覆盖 \(l\) 或 \(r\) 性质非常强所以做法非常多 一种比较神奇的：对于两条线段 \([l_{1},r_{1}],[l_{2},r_{2}]\)，定义 ......

水题。 发现根据限制 \(M_{i,j}=M_{j,i}\) 可以知道除了主对角线上的点，其他的点都是成对出现的。也就是说如果有一条要求的 \(a_i\) 为奇数，那么至少有一个 \(c_i\) 在主对角线上。 记 \(S=\sum\limits_{i=1}^{k} (a_i\equiv 1\pmo ......

P8074 SVEMIR \(Solution\) ： 这道题目乍一看感觉好难... 因为有绿色的加持，再加上一进题目就看见了头疼的三维坐标，不知道的还以为需要用到什么非常高大上的知识来解决这道题，其实只需要用到最小生成树就行了。 不会最小生成树的请出门左转：P3366 【模板】最小生成树 然后来仔 ......

2023-09-23 题目 P3866 [TJOI2009] 战争游戏 难度&重要性(1~10):6 题目来源 luogu 题目算法 最小割 解题思路 这道题比较简单。 我们考虑建图，需要注意的是我们要将点权变为边权： 当 \(a_{i,j}=0\) 时，\(S\to u\) 流量为 \(inf\) ......

2023-09-22 题目 P2598 [ZJOI2009] 狼和羊的故事 难度&重要性(1~10):6 题目来源 luogu 题目算法 网络流，最小割 解题思路 一道大水题。 考虑如何建图： \(u=1\) 时，\(S\to u\) 流量为 \(inf\) \(u=2\) 时，\(u\to T\) ......