CF912E Prime Gift 题解
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+...
SP1553 BACKUP - Backup Files 题解
SP1553 BACKUP - Backup Files 题解 题目链接:BACKUP - Backup Files 题意: 你在一家 IT 公司为大型写字楼或办公楼的计算机数据做备份。然而数据备份的工作是枯燥乏味的,因此你想设计一个系统让不同的办公楼彼此之间互相备份,而你则坐在家中尽享计算机游戏的乐趣。 已知办公楼都位于同一条街上。你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。 然而,网络电缆的费用很高。当地电信公司仅能为你提供 \(k\) 条网络电缆,这意味着你仅能为 \(k\) 对办公楼(或总计 \(2k\) 个办公楼)安排备份。任一个办公楼都属于唯一的配对组(换句话说,这 \(2k\) 个办公楼一定是相异的)。 此外,电信公司需按网络电缆的长度(公里数)收费。因而,你需要选择这 \(k\) 对办公楼使得电缆的总长度尽可能短。换句话说,你需要选择这 \(k\) 对办公楼,使得每一对办公楼之间的距离之和(总距离)尽可能小。 下面给出一个示例,假定你有 \(5\) 个客户,其办公楼都在一条街上,如下图所示。这 \(...
CF703D Mishka and Interesting sum 题解
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\) 的贡献,...
AT_arc172_d [ARC172D] Distance Ranking 题解
AT_arc172_d [ARC172D] Distance Ranking 题解 题目链接:AT_arc172_d [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]\) 的范围似乎有些小了,不方便我们进行修改,以满足原题的要求。...
AT_agc001_e [AGC001E] BBQ Hard 题解
AT_agc001_e [AGC001E] BBQ Hard 题解 题目链接:AT_agc001_e [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] \s...
洛谷P1817 棋盘染色 题解
洛谷P1817 棋盘染色 题解 题目链接:P1817 棋盘染色 题意: 给定一个 \(N \times M\) 的网格,每个格子可以染成黑色或者白色,要求所有黑色格子连通,所有白色格子连通,并且至少有一个黑色格子贴边,至少有一个白色格子贴边。问有多少种染色方法? 输入格式: 第一行有两个正整数 \(N, M\)。 输出格式: 只有一个正整数表示答案。 数据范围: \(1 \le N \le 7\),\(1 \le M \le 8\)。 暴力打表即可。代码如下: #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 = (a...
洛谷P1285 队员分组 题解
洛谷P1285 队员分组 题解 题目链接:P1285 队员分组 题意: 有 \(n\) 个人从 \(1\) 至 \(n\) 编号,相互之间有一些认识关系,你的任务是把这些人分成两组,使得: 每个人都被分到其中一组。 每个组都至少有一个人。 一组中的每个人都认识其他同组成员。 在满足上述条件的基础上,要求两组成员的人数之差(绝对值)尽可能小。请构造一种可行的方案。 请注意,\(x\) 认识 \(y\) 不一定说明 \(y\) 认识 \(x\);\(x\) 认识 \(y\) 且 \(y\) 认识 \(z\) 不一定说明 \(x\) 认识 \(z\)。即认识关系是单向且不可传递的。 输入格式: 输入的第一行是一个整数,代表总人数 \(n\)。 第 \(2\) 到第 \((n + 1)\) 行,每行有若干个互不相同的整数,以 \(0\) 结尾,第 \((i + 1)\) 行的第 \(j\) 个整数 \(a_{i, j}\)(\(0\) 除外)代表第 \(i\) 个人认识 \(a_{i, j}\)。 输出格式: 本题存在 Special Judge。 如果无解,请输出一行一个字符串 ...
SP19985 GCDEX2 - GCD Extreme (hard) 题解
SP19985 GCDEX2 - GCD Extreme (hard) 题解 题目链接:GCDEX2 - GCD Extreme (hard) 题意: 给定 \(n~(1\le n\le 235711131719)\) ,计算 \[ G(n)=\sum_{i=1}^n\sum_{j=i+1}^n\gcd(i,j) \] 答案对 \(2^{64}\) 取模。有多组询问 \((T\le10^4)\)。本题时限 20s 。 貌似写过这题的弱化版 UVA11424 GCD - Extreme (I) ,是一道 7 倍经验题。 不过之前的做法都不行了,现在我们来重新考察这个式子怎么做。 推式子,启动! \[ \begin{aligned} \mathrm{Ans}&= \sum_{i=1}^n \sum_{j=i+1}^n \operatorname{gcd}(i, j) \\[6pt]& =\sum_{i=1}^n \sum_{j=1}^{i-1} \operatorname{gcd}(i, j) \\[6pt]& =\sum_{d=1}^n d \sum_{...
洛谷P2714 四元组统计 题解
洛谷P2714 四元组统计 题解 题目链接:P2714 四元组统计 题意: 有 \(n\) 个正整数 \(a _ i\),你要统计有多少个四元组满足 \(\gcd(a _ i, a _ j, a _ k, a _ l) = 1\)。 输入格式: 输入包含多组数据。 对于每组数据:第一行一个正整数 \(n\),接下来一行 \(n\) 个正整数 \(a _ i\)。 输出格式: 若干行,每行对应一个输入数据,表示满足要求的四元组的个数。 数据范围: \(4 ≤ n ≤ 10000\),\(1 ≤ a _ i≤ 10000\),且数据组数不超过 \(100\)。 设 \(f(n)\) 表示 \(n\) 的倍数的出现次数。 初值 \(f(a_i)=k_i\) ,其中 \(k_i\) 表示 \(a_i\) 的出现次数(这里其实是等于 \(n\) 的情况)。 考虑转移,有 \[ f(n) \gets f(n) + \sum_{n \mid d} f(d) \] 这其实是以质因数及其幂次为坐标的 \(\pi(n)\) 维向量上的高维前缀和,参考 Dirichlet 前缀和。 考虑令 \[...
树状数组 Python实现
树状数组 Python实现 具体原理参考 浅谈树状数组 区间修改&区间查询 这里直接给出 区间修改 + 区间查询 的代码 常数超级无敌巨大。 import sys # sys.stdin = open('check.in', 'r') # sys.stdout = open('check.out', 'w') N = int(1e6 + 15) tr1 = [0] * N tr2 = [0] * N def read(): return [int(x) for x in input().split()] def lowbit(x): return x & (-x) def _add(tr, x, v): i = x while(i <= n): tr[i] += v; i += lowbit(i) def add(x, v): _add(tr1, x, v); _add(tr2, x, v * x) def _qry(tr, x): r = 0; i = x while(...
洛谷P7219 [JOISC2020] 星座 3 题解
洛谷P7219 [JOISC2020] 星座 3 题解 题目链接:P7219 [JOISC2020] 星座 3 题意: JOI 君去拍照,拍了一张大小为 \(N \times N\) 的图片,第 \(i\) 列第 \(j\) 行的格子称为格子 \((i,j)\)。 图里有白色的小白船,黄色的星星(天知道为啥星星是黄色的),黑色的空格(天知道这空格是啥),第 \(i\) 列自下往上数到第 \(A_i\) 行的格子里都是小白船,另外有 \(M\) 颗星星,第 \(i\) 颗星星在格子 \((X_i,Y_i)\),除了小白船和星星,其他格子都是空格。 现在 JOI 君定义满足下面的一个矩阵为星座: 不包含小白船 至少包含 \(2\) 颗星星 JOI 君已经看星座看了 114514 年了,他厌烦了,所以他要把图片中的一些星星涂黑变成黑色空格,涂黑第 \(i\) 颗星星会让图片增加 \(C_i\) 的不自然度。求不存在星座的最小不自然度。 输入格式 第一行一个整数 \(N\) 代表图片的大小。 第二行 \(N\) 个整数第 \(i\) 个整数 \(A_i\) 代表小白船的位置。 第三...
CF103E Buying Sets 题解
CF103E Buying Sets 题解 题目链接:Buying Sets 题意: 有一个大小为 \(n~(1 \le n \le 300)\) 的全集,每个元素是一个数 现在有 \(n\) 个子集,大小分别为 \(m_i\) ,题目保证任意 \(k\) 个子集的并的大小 \(\ge k\) 。 每个子集有一个可正可负的权值,你需要选出一些子集使得这些子集并的大小等于子集个数, 且所选子集的权值和最小。可以为空集。保证 \(\sum m_i \le 10^6\) 。 输入格式: 第一行 \(n\) ,接下来 \(n\) 行:每行第一个数是 \(m_i\) ,接下来 \(m_i\) 个数是集合中的数。 最后一行 \(n\) 个数,表示每个子集 输出格式 一行,即权值和的最小值。 考虑将权值取反,这样只需要求最大权值。 注意到,如果我们将集合看作一些点,\(n\) 个数看作 \(n\) 个点,将集合与其中的点连边 那么,不考虑「子集并的大小等于子集个数」这个限制的话,这就是一个经典的最大权闭合子图问题。 最大权闭合子图问题,就是给定一张有向图,每个点有点权(可能为负)。 现在...



![AT_arc172_d [ARC172D] Distance Ranking 题解](/qwq/img/p233.webp)
![AT_agc001_e [AGC001E] BBQ Hard 题解](/qwq/img/p198.webp)





![洛谷P7219 [JOISC2020] 星座 3 题解](/qwq/img/p65.webp)

![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)