Q779’s Blog

CF746G New Roads 题解 题目链接：New Roads 题意： 在Berland有 \(n\) 个城市，每一座城市都有一个单独的编号——在 \(1\) 到 \(n\) 范围内的一个整数，首都的编号是 \(1\)。现在，在Berland有一个极其严峻的问题：城市之间没有道路相连。 为了使得每个城市之间都有路相连，要在城市之间建造 \(n-1\) 条路。 在建造计划中一共有 \(t\) 个整数 \(a_1,a_2,\cdots,a_t\) ，其中 \(t\) 等于首都与离首都最远的城市之间的距离。\(a_i\) 表示一共有 \(a_i\) 座城市与首都之间的距离是 \(i\)。两个城市之间的距离等于从一座城市到另一座城市所经过的道路的数量。 而且，除了首都以外一共会有 k 座城市仅与一条道路相连。这些城市是“死胡同”，它们没有经济吸引力。首都不算在内（即，即使只有一条道路与首都相连，首都也不算在“死胡同”里）。 你的任务是做出符合所有条件的计划，或是说明符合所有条件的计划是不存在的。 输入格式： 输入数据的第一行包括三个整数 \(n,t,k~(2 \le n \le ...

洛谷P2831 [NOIP2016 提高组] 愤怒的小鸟 题解 题目链接：P2831 [NOIP2016 提高组] 愤怒的小鸟 题意： Kiana 最近沉迷于一款神奇的游戏无法自拔。 简单来说，这款游戏是在一个平面上进行的。 有一架弹弓位于 \((0,0)\) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 \(y=ax^2+bx\) 的曲线，其中 \(a,b\) 是 Kiana 指定的参数，且必须满足 \(a < 0\)，\(a,b\) 都是实数。 当小鸟落回地面（即 \(x\) 轴）时，它就会瞬间消失。 在游戏的某个关卡里，平面的第一象限中有 \(n\) 只绿色的小猪，其中第 \(i\) 只小猪所在的坐标为 \(\left(x_i,y_i \right)\)。 如果某只小鸟的飞行轨迹经过了 \(\left( x_i, y_i \right)\)，那么第 \(i\) 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行； 如果一只小鸟的飞行轨迹没有经过 \(\left( x_i, y_i \right)\)，那么这只小鸟飞行的全过...

[AGC023F] 01 on Tree 题解 题目链接：[AGC023F] 01 on Tree 题意： 给出一棵 \(n\) 个节点的树，以及一个空序列。每个节点上有一个取值在 \(\{0, 1\}\) 中的数。 每次你可以选择没有父亲节点的点删除，并且将这个节点上的数字放在当前数列末尾。 请你求出这个数列可能得到的最小逆序对数。 \(1 \le n \leq 2 \times 10^5\) 。 听说是 Exchange Argument 的经典题，之前没见过。 首先这个删父亲再倒序放实在是有些奇怪，我们可以把它看作一棵内向树的某种拓扑序。 显然，如果可选的节点中存在 \(0\) ，那么优先选这些节点一定不劣。 考虑每次选择一个节点后，将其与父亲合并。 这里考虑并查集即可，然后维护当前节点有多少个 \(0,1\) 。 对于两个节点 \(a,b\) ，记 \(a_0,a_1\) 和 \(b_0,b_1\) 是他们的 \(0,1\) 个数 由于 \(a,b\) 的子树已经按最优方案选择了，所以我们只需要考虑最小化因他们的顺序产生的逆序对即可 显然当 \(a_1 \times ...

CF1100E Andrew and Taxi 题解 题目链接：Andrew and Taxi 题意： 给定一个 \(n\) 个点 \(m\) 条边的有向图，边有权值 \(w_i\) 。 要求改变其中某些边的方向，使其成为一个有向无环图。 现在求一个改变边方向的方案，使得所选边边权的最大值最小。 数据范围： \(1 \le n,m \le 10^5,~1 \le w_i \le 10^9\) 。 考虑二分边权的最大值 \(x\) ，那么现在所有边分成了两种 边权 \(w_i\) 小于等于 \(x\) 的边 边权 \(w_i\) 大于 \(x\) 的边 显然，如果第二种边构成了环，那么这种情况是不行的。 考虑拓扑排序判环，顺便记录一下每个点的拓扑序。 那么需要翻转的第一种边 \(u_i \to v_i\) 一定有 \(T(v_i) < T(u_i)\) ，其中 \(T\) 表示节点的拓扑序。 于是这道题就做完了，还是蛮简单的。结果我连拓扑排序判环都没想到，很少用。 时间复杂度 \(\mathcal{O}(n \log m)\) 代码： #include <bit...

CF662B Graph Coloring 题解 题目链接：Graph Coloring 题意： 给出一张 \(n\) 个点，\(m\) 条边的无向图，一开始每条边可能是红色或者蓝色， 翻转一个点可以使相连的边变成相反的颜色，要求把所有边变成红色或者蓝色 问最少需要翻转的点数，并给出具体的方案 输入格式： 第一行输入 \(n,m\)，分别表示点的数量和边的数量 \((1\leq n,m\leq 100000)\) 。 第二至 \(m+1\) 行 \(u_i,v_i,c_i\)，分别表示无向边的两个点以及它的颜色，保证没有重边和自环 输出格式： 如果没有方法使其合法输出 \(-1\)， 否则第一行输出最少需要翻转的点数，第二行用空格分隔输出翻转点的编号，只需要输出一种方案 考虑对全部染成 \(\mathbf{R}\) 和全部染成 \(\mathbf{B}\) 的方案取 min。 下面以 \(\mathbf{R}\) 为例。显然每个点至多翻转 \(1\) 次，那么记 \(i\) 为点 \(i\) 不翻转，\(i + n\) 为点 \(i\) 翻转。 若 \(c_i = \mat...

2–SAT 学习笔记 现在 2–SAT 已经是蓝题了吗。 由于我的模板都不知道是多少年前写的了，所以就有了这边文章。 2–SAT 问题 模板题链接：P4782 【模板】2–SAT 题意： 有 \(n\) 个布尔变量 \(x_1,x_2,\cdots,x_n\)，另有 \(m\) 个需要满足的条件，每个条件的形式都是 「\(x_i\) 为 true / false 或 \(x_j\) 为 true / false」。比如 「\(x_1\) 为真或 \(x_3\) 为假」、「\(x_7\) 为假或 \(x_2\) 为假」。 2–SAT 问题的目标是给每个变量赋值使得所有条件得到满足。 输入格式： 第一行两个整数 \(n\) 和 \(m\)，意义如题面所述。 接下来 \(m\) 行每行 \(4\) 个整数 \(i,a,j,b\)，表示 「\(x_i\) 为 \(a\) 或 \(x_j\) 为 \(b\)」\((a, b\in \{0,1\})\) 输出格式： 如无解，输出 IMPOSSIBLE；否则输出 POSSIBLE。 下一行 \(n\) 个整数 \(x_1,x_2,\cdots...

CF912E Prime Gift 题解 题目链接：Prime Gift 题意： 给你 \(n\) 个互不相同的素数 \(p_1,p_2,\cdots,p_n\)，它们组成一个集合 \(P\)。 请你求出第 \(k\) 小的正整数，满足该数字的所有素因子 \(\in P\) \(1\le n\le 16,~2\le p_i\le 100,~\) 保证答案不超过 \(10^{18}\)。 注意到当 \(n=8\) 时，实际上符合条件数并不会很多 考虑 meet in the middle 。我们把 \(P\) 分成比较均匀的两部分 \(A,B\) ，跑 dfs 爆搜两侧的数 接着二分答案，用左侧的某个数 \(A_i\) 去匹配右侧的 \(B_j\) ，扫一遍检验排名。 时间复杂度 \(\mathcal{O}\left(\log V\left(\prod_{p_i \in A} \log_{p_i}V + \prod_{p_i \in B} \log_{p_i}V\right)\right)\) ，其中 \(V\) 是值域。 代码： #include <bits/stdc+...

nywOJ101 2^a + 2^b problem 题解 题目链接：2^a + 2^b problem 题意： 给定 \(a,b~(0 \le a,b \le 63)\) ，求 \(2^a + 2^b\) 。 输入格式： 仅一行，两个整数 \(a,b\) 。 输出格式： 仅一行，即答案。 特判 \(a=b=63\) 的情况即可。 当然如果你用 __int128 也是可以的，本题就是个弱智签到题。 时间复杂度 \(\mathcal{O}(1)\) 代码： #include <bits/stdc++.h> using namespace std; // #define int long long // #define INF 0x3f3f3f3f3f3f3f3f void up(int &x, int y) { x < y ? x = y : 0; } void down(int &x, int y) { x > y ? x = y : 0; } #define rep(i, a, b) for(int i =...

SP1553 BACKUP - Backup Files 题解 题目链接：BACKUP - Backup Files 题意： 你在一家 IT 公司为大型写字楼或办公楼的计算机数据做备份。然而数据备份的工作是枯燥乏味的，因此你想设计一个系统让不同的办公楼彼此之间互相备份，而你则坐在家中尽享计算机游戏的乐趣。 已知办公楼都位于同一条街上。你决定给这些办公楼配对（两个一组）。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。 然而，网络电缆的费用很高。当地电信公司仅能为你提供 \(k\) 条网络电缆，这意味着你仅能为 \(k\) 对办公楼（或总计 \(2k\) 个办公楼）安排备份。任一个办公楼都属于唯一的配对组（换句话说，这 \(2k\) 个办公楼一定是相异的）。 此外，电信公司需按网络电缆的长度（公里数）收费。因而，你需要选择这 \(k\) 对办公楼使得电缆的总长度尽可能短。换句话说，你需要选择这 \(k\) 对办公楼，使得每一对办公楼之间的距离之和（总距离）尽可能小。 下面给出一个示例，假定你有 \(5\) 个客户，其办公楼都在一条街上，如下图所示。这 \(...

CF703D Mishka and Interesting sum 题解 题目链接：Mishka and Interesting sum 题意： 给定 \(n\) 个数的序列 \(a\)。\(m\) 次操作。操作有一种： l r：求 \(a_l\sim a_r\) 中，出现偶数次的数的异或和（每个数只算一次）。 数据范围： \(1\le n,m\le 10^6\)，\(1\le a_i\le 10^9\)。 「出现偶数次的数的异或和」显然等于「出现的所有数的异或和」异或上「出现奇数次的数的异或和」 「出现奇数次的数的异或和」直接预处理前缀和就好了（偶数的会抵消，奇数的也只会留下一个）。 现在我们要统计「出现的所有数的异或和」，考虑用树状数组维护，做法类似于经典的 HH 的项链。 大概操作就是，先对数离散化，然后询问离线（按右端点升序排序），维护一个指针 \(r\) ，一路扫过去 扫的过程中记录每个数的出现位置 \(c_x\) ，比如现在是 \(x\) ，位置为 \(i\) ，那么将 \(c_x\) 的贡献在树状数组上去掉 再把 \(i\) 的位置加上 \(x\) 的贡献，...

[ARC172D] Distance Ranking 题解 题目链接：[ARC172D] Distance Ranking 题意： \(N\) 维空间中有 \(N\) 个点，每个点的每一维坐标都是在 \([0,10^8]\) 上的整数。 已知这些点两两连边的长度大小关系，从小到大给出，每次给出 \(a_i,b_i\) 以表示他们的连边。 求一个满足上述条件的 \(N\) 个点的构造方案。保证有解。（不能有两条边长度相等） 数据范围： \(3 \le N \le 20,~ 1 \le a_i < b_i \le N~\left(1 \le i \le \frac{N(N-1)}{2}\right)\) 。保证 \(a_i,b_i\) 互不相同。 首先考虑任意两个不同点之间的距离均相等的情况怎么做。 显然这个时候可以构造 \(p_{i,j} = [i=j]\) ，其中 \(p_{i,j}\) 表示点 \(i\) 的第 \(j\) 维坐标。 不过这个 \([0,1]\) 的范围似乎有些小了，不方便我们进行修改，以满足原题的要求。 因此我们可以将其缩放为 \(p_{i,j} =...

[AGC001E] BBQ Hard 题解 题目链接：[AGC001E] BBQ Hard 题意： 有 \(n\) 个数对 \((a_i, b_i)\)，求出 \[ \sum_{i=1}^{n}\sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j} \] 答案对 \(10 ^ 9 + 7\) 取模。 数据范围： \(1 \le n \le 2\times 10^5,~1 \le a_i,b_i \le 2000\) 。 这道题有利用组合意义的解法，这里来讲讲 OGF 的解法吧。 先考虑较为简单的 \[ \sum_{i=1}^n \sum_{j=1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j} \] 推式子，启动！ \[ \begin{aligned} & \sum_{i=1}^n \sum_{j=1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j} \\[6pt]& =\left[x^{a_i+a_j}\right] \sum_{i=1}^n \sum_{j=1}^n(...