Q779’s Blog

杂题选做[1] 第一次发这种类型文章 好吧，其实是我刷题太少了，所以开始补了 \(😅\) 一些收获：（q779脑回路清奇，所以会想出很多乱七八糟的） DP有个无后效性：某阶段的状态一旦确定，则此后过程的决策不再受此前各种状态及决策的影响 暴力也是可以剪枝的 \(a_n=a_1+(n-1)d\) P1209 [USACO1.3]修理牛棚 Barn Repair 贪心。木板可以随便切，所以每次切间隔最大的。 #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1005) int n,m,a[N],b[N],res; signed main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("check.in","r",stdin); // freopen("check.out...

[计算几何] 使用叉积计算直线交点 upd.本文写于远古时期，有空再来修改。 已知直线 \(AB\) 和 \(CD\) ，其交点为 \(P\) ， 求 \(P\) 的坐标。 计算几何中一般存储向量 \(\mathbf{p},\mathbf{v}\) 表示起点的向量和方向向量 例如直线 \(AB\) 一般存储为 \(\overset{\longrightarrow}{OA},\overset{\longrightarrow}{AB}\) const double eps=1e-10; struct vct{double x,y;}p[N]; #define pf(x) ((x)*(x)) vct operator+(vct a,vct b){return {a.x+b.x,a.y+b.y};} vct operator-(vct a,vct b){return {a.x-b.x,a.y-b.y};} vct operator*(vct a,double b){retur...

半平面交的交集问题&POJ2451 Uyuw’s Concert 题解 前言 初学半平面交，就遇到了这样巨大的坑，也是挺无语… 判断交集为空的情况 poj2451 Uyuw’s Concert Description Prince Remmarguts solved the CHESS puzzle successfully. As an award, Uyuw planned to hold a concert in a huge piazza named after its great designer Ihsnayish. The piazza in UDF - United Delta of Freedom’s downtown was a square of [0, 10000] * [0, 10000]. Some basket chairs had been standing there for years, but in a terrible mess. Look at the following graph. In this case we hav...

UVA12307 Smallest Enclosing Rectangle 题解 upd.20220429 由于q779太菜，导致代码出了点锅，已经重新修改 题目链接：UVA12307 Smallest Enclosing Rectangle 题意：多组数据，给定平面上的 \(n\) 个点，分别求出周长最小、面积最小的矩形，使得所有的点均被矩形覆盖 数据范围： \(3\le n \le 10^5\) ，\(-10^5 \le x,y \le 10^5\) 看到本题，容易想到 P3187 解法是旋转卡壳 要求的是矩形，因此考虑维护三个点： \(a\) 代表当前枚举直线对面的边 \(b\) 代表当前枚举直线右侧最远的点 \(c\) 代表当前枚举直线左侧最远的点 如下图所示 其中，\(a\) 使用叉积比较，\(b,c\) 则使用点积比较 方便起见，我们称当前的底边长为 \(\text{T}\) （即图中的q[1]到q[2]） 可以发现 \(\text{T = L}+\text{R}-\text{d}\) \(\text{L}\) 表示向量 \(s_i\to c\) 在 \(\te...

洛谷P4159 [SCOI2009] 迷路 题解 题目链接：P4159 [SCOI2009] 迷路 题意：该有向图有 \(n\) 个节点，节点从 \(1\) 至 \(n\) 编号，windy 从节点 \(1\) 出发，他必须恰好在 \(t\) 时刻到达节点 \(n\)。 现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？ 答案对 \(2009\) 取模。 注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。 题目给出了邻接矩阵 首先，根据矩阵乘法的性质，我们可以发现 不考虑题目的限制，当矩阵仅由01构成时 \(M^2\) 的意义就是只通过两条边（此时边权均为 \(1\) ）能到达每个结点的方案数 则此时答案就是 \(M^t\) 可是题目给出的矩阵，至多有 \(10\) 怎么办呢？考虑把它转化新的矩阵（仅有01构成的） 对于初始矩阵的每个节点，把它化为 \(x_i\) 个结点 其中 \(x_i\) 表示出边边权的最大值 如下图 “拆点”操作 可以发现这样的话仍然是满足题意的 为什么呢？因为可以更新答案的那条路径 一定走到了 \(x_i...

洛谷P3829 [SHOI2012]信用卡凸包 题解 题目链接：P3829 [SHOI2012]信用卡凸包 题意： 给定若干个“信用卡”，求其“凸包”周长 这个题其实看上去很不可做，其实很简单 注意到（搬了一张图，来自link，不过这篇题解的代码好像挂了） 显然，由图可知，我们求的所谓凸包 就是信用卡上面那四个点组成的点集的凸包加上一个圆的面积 关于如何理解这个图形的周长恰好包括一个圆 大家就想象一只小乌龟从一点开始走，走了一大圈又回到了起点 它旋转的角度正好为 \(2\pi\) 那么这道题就变成数学题了，如何处理这4个点？ 再看图，可以发现这个圆对求凸包真的一点用都没有 直接把那四个点组成的新矩形当作处理对象 然后运用一点初中知识就可以求出来了 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define INF ((int)0x3f3f3f3f3f3f3f3f) #define inf ((int)0xc0c0c0c0c0c0c0c0) #define N (...

洛谷P3194 [HNOI2008]水平可见直线 题解 题目链接：P3194 [HNOI2008]水平可见直线 题意：在$ x-y$ 直角坐标平面上有 \(n\) 条直线 \(L_1,L_2,…L_n\)，若在 \(y\) 值为正无穷大处往下看，能见到 \(L_i\) 的某个子线段，则称 \(L_i\) 为可见的，否则 \(L_i\) 为被覆盖的。 例如，对于直线: \(L_1:y=x\); \(L_2:y=-x\); \(L_3:y=0\); 则 \(L_1\) 和 \(L_2\) 是可见的，\(L_3\) 是被覆盖的。给出 \(n\) 条直线，表示成 \(y=Ax+B\) 的形式(\(|A|,|B| \le 500000\))，且 \(n\) 条直线两两不重合，求出所有可见的直线。 一条直线C被另外两条直线A和B所覆盖 它的充分必要条件为直线C在A,B交点处的值更小一些 反之，直线C也可能对答案有贡献 那么交点的坐标是什么呢？ \[ A_1x+B_1=A_2x+B_2\\ x=\dfrac{B_2-B_1}{A_1-A_2} \] 则 \[ A_1\dfrac{B_2-B...

洛谷P3236 [HNOI2014]画框 题解 题目链接：P3236 [HNOI2014]画框 题意：小 T 准备在家里摆放几幅画，为此他买来了 \(N\) 幅画和 \(N\) 个画框。为了体现他的品味，小 T 希望能合理地搭配画与画框，使得其显得既不过于平庸也不太违和。 对于第 \(i\) 幅画与第 \(j\) 个画框的配对，小 T 都给出了这个配对的平凡度 \(A_{i, j}\) 与违和度 \(B_{i, j}\) 。整个搭配方案的总体不和谐度为每对画与画框平凡度之和与每对画与画框违和度的乘积。具体来说，设搭配方案中第 \(i\) 幅画与第 \(P_i\) 个画框配对，则总体不和谐度为 \[ \mathrm{disharmony}=\sum_{i=1}^{N}A_{i,p_i}\times \sum_{i=1}^{N}B_{i,p_i} \] 小 T 希望知道通过搭配能得到的最小的总体不和谐度是多少。 q779在水文章\(🐒\) 这道题和P5540 [BalkanOI2011] timeismoney | 最小乘积生成树 几乎就是一道题 可以先看下这篇题解（ 变化不是...

洛谷P5540 [BalkanOI2011] timeismoney | 最小乘积生成树 题解 题目链接：P5540 [BalkanOI2011] timeismoney | 最小乘积生成树 题意：给出一个 \(n\) 个点 \(m\) 条边的无向图，第 \(i\) 条边有两个权值 \(a_i\) 和 \(b_i\) 。 求该图的一棵生成树 \(T\) ，使得 \[ \left(\sum_{e\in T}a_e\right)\times\left(\sum_{e\in T}b_e\right) \] 最小 注意到对于一棵生成树，式子中的左右两边均为常数 考虑将生成树映射到平面上的点 \((x,y)\) 其中 \(x=\sum\limits_{e\in T}a_e,y=\sum\limits_{e\in T}b_e\) 那么问题就转化为了求一个点 \((x,y)\) 使得 \(x\times y\) 最小 可以发现这些点的分布存在边界 即 \(x\) 特别大 \(y\) 特别小的时候以及 \(y\) 特别大 \(x\) 特别小的时候 这两种情况分别对应点 \(A\) 和 \(B...

洛谷P2491 [SDOI2011] 消防 题解 题目链接：P2491 [SDOI2011] 消防 题意：某个国家有 \(n\) 个城市，这 \(n\) 个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为 \(z_i\) 。 这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。 现在这个国家的经费足以在一条边长度和不超过 \(s\) 的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。 你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。 看到这是一棵树，而且还要求路径的最大值 很容易想到这个枢纽要建在直径上 当 \(s\) 大于等于直径时显然成立 考虑 \(s\) 小于直径的情况，枢纽全部建在直径上仍是最优解 以下为证明： 假设只有一个枢纽结点（在直径上），我们以它为中心扩展出一条路径 离这个点最远的结点一定在直径上，而且是直径的端点 此时的最大值就...

洛谷P3299 [SDOI2013]保护出题人 题解 题目链接：P3299 [SDOI2013]保护出题人 题意：出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。 参加SDOI2012的小朋友们释放出大量的僵尸，企图攻击铭铭的家。而你作为SDOI2013的参赛者，你需要保护出题人铭铭。 僵尸从唯一一条笔直道路接近，你们需要在铭铭的房门前放置植物攻击僵尸，避免僵尸碰到房子。 第一关，一只血量为 \(a_1\) 点的墦尸从距离房子 \(x_1\) 米处速接近，你们放置了攻击力为 \(y_1\) 点/秒的植物进行防御；第二关，在上一关基础上，僵尸队列排头增加一只血量为 \(a_2\) 点的僵尸，与后一只僵尸距离 \(d\) 米，从距离房 \(x_2\) 米处匀速接近，你们重新放置攻击力为 \(y_2\) 点/秒的植物；……；第 \(n\) 关，僵尸队列共有 \(n\) 只僵尸，相邻两只僵尸距离 \(d\) 米，排头僵尸血量 \(a_n\) 点，排第二的 僵尸血量 \(a_{n-1}\) ，以此类推，排头僵尸从距离房子 \(x_n\) 米处...

Dijkstra及其复杂度证明 本文主要围绕易混淆的复杂度分析进行讨论 另外其实这个不叫迪杰斯特拉，这个叫/ˈdɛɪkstra/ qwq 一、前置知识 先放几个简单概念 无向图：图中所有的边都是两端可达的，也就是可以从任意一端通过这条边 有向图：图中所有的边都是单向的，有一个起点和一个终点，方向为起点指向终点 重边：两个结点间多条存在完全一样的边，通常它们可能拥有不同的权重或属性 自环：起点和终点相同的边 简单图：图中不存在自环和重边，显然一定存在两个结点的度数相同 多重图：存在自环或重边 更多内容可以参考这里 ，这里只介绍了一些对本文有用的概念 二、时间复杂度分析 给定一张具有非负权重的图和一个源点 \(s\) （起点），问结点 \(t\) 与 \(s\) 的最短距离是多少 设图中的结点数为 \(n\) ，边数为 \(m\) ，\(n\le m\) 算法流程： \(\text{dis[s]=0} \land \forall u \in V\backslash S , \text{dis[}u\text{]}=+\infty\) 从未确定最短路的点集 \(T\) 中找到...