- 博客(65)
- 收藏
- 关注
RSS订阅
原创 Codeforces Round #712 (Div. 2) E. Travelling Salesman Problem【思维 | DP】
题意：给定 nnn 个城市，编号从 111 到 nnn，第 i 个城市的美丽值为 aia_iai，一个销售员想从城市 111 出发，经过其他城市至少一次且仅一次，最后返回城市 111，对于两个城市 i，j(i≠j)i，j (i ≠ j)i，j(i=j)，从 iii 到 jjj 花费的费用为 max(ci,aj−ai)\max(c_i, a_j - a_i)max(ci,aj−ai)，找到完成整个过程的最小费用。1≤n≤105，0≤ai,ci≤1091 ≤ n ≤ 10^5，0 ≤ a_i
2021-04-08 16:43:32
194
1
原创 牛客IOI周赛23-普及组 D.小L的数列【DP | 质因数分解优化】
题意：给定 n 个数，定义好的序列满足如下两个条件：（1）严格递增；（2）对于相邻的两个数，它们的 gcd > 1。求最长的好的序列。2≤n≤1000002 ≤ n ≤ 1000002≤n≤100000，1≤ai≤1000001 ≤ a_i ≤ 1000001≤ai≤100000 且 aia_iai 两两不相同，1≤T≤51 ≤ T ≤ 51≤T≤5。思路：80分思路：首先排序，令 dp[i] 为以 i 结尾的最长好序列，不难得出状态转移方程为 dp[i]=max0≤j<i
2021-03-31 17:24:53
175
原创 Codeforces Round #711 (Div. 2) A. GCD Sum【数位和性质】
题意：定义 gcdSum(x) 为 x 和 x 的数位和的gcd，给定 n，求大于等于 n 的数且 gcdSum > 1 的第一个的数。1≤t≤10001 ≤ t ≤ 10001≤t≤1000, 1≤n≤10181 ≤ n ≤ 10^{18}1≤n≤1018思路：性质：数位和性质，如果一个数是 3 的倍数，那么他的数位和也是 3 的倍数，因此，n、n + 1、n + 2 其中一个数一定满足性质。AC Code:#include <bits/stdc++.h>usi
2021-03-31 09:56:33
245
原创 Educational Codeforces Round 106 D. The Number of Pairs【GCD | 质因数个数】
题意：给定 3 个正整数 c、d、x，问有多少个对数 (a, b) 满足 c∗lcm(a,b)−d∗gcd(a,b)=xc * lcm(a, b) - d * gcd(a, b) = xc∗lcm(a,b)−d∗gcd(a,b)=x，其中有 t 组测试点，t≤104,1≤c,d,x≤107t ≤ 10^4, 1 ≤ c, d, x ≤ 10^7t≤104,1≤c,d,x≤107。思路：令 a=k1∗gcd(a,b),b=k2∗gcd(a,b)a = k_1 * gcd(a, b), b = k_
2021-03-25 19:41:46
111
原创 Codeforces Round #704 (Div. 2) D. Genius‘s Gambit【构造 | 细节】
题意：给定 3 个数字 a、b、k，找到两个二进制数字 x、y (x > y)，满足如下条件：(1) x 和 y 都有 a 个 0，b 个 1；(2) x - y 二进制下有 k 个 1。x 和 y 都不能有前导零。0≤a;1≤b;0≤k≤a+b≤2⋅1050 \le a; 1 \le b; 0 \le k \le a + b \le 2 \cdot 10^50≤a;1≤b;0≤k≤a+b≤2⋅105 。思路：构造方法很巧妙对于 k≤a(a=4, b=4,k=3)k \l
2021-02-26 16:59:25
114
1
原创 Educational Codeforces Round 89 D. Two Divisors【GCD性质 | 质因数分解】
题意：给定 n 的数字 a1,a2,…,ana_1, a_2, \dots, a_na1,a2,…,an，对于每个 a，找到它的两个因子 d1 > 0，d2 > 0 满足 gcd(d1 + d2, a) = 1，如果存在就输出，否则输出 -1.1≤n≤5⋅1051 \le n \le 5 \cdot 10^51≤n≤5⋅105，2≤ai≤1072 \le a_i \le 10^72≤ai≤107思路：方法1： Codeforces 题解：上面的题解证明了构造出来的 d1
2021-02-25 23:36:25
101
原创 Codeforces Round #703 (Div. 2) D. Max Median【前缀和 | 二分答案】
题意：给定长度为 n 的数组 a，找到一个长度至少为 k 的子数组 a[l…r]，组成这个子数组的元素的中位数最大。中位数为这个子数组排序后的第 ⌊n+12⌋\lfloor \frac{n+1}{2} \rfloor⌊2n+1⌋ 个数字。1≤ai≤n，1≤k≤n≤2⋅1051 \leq a_i \leq n， 1 \leq k \leq n \leq 2 \cdot 10^51≤ai≤n，1≤k≤n≤2⋅105思路：对于本题的中位数，如果子数组长度为偶数，中位数取中间靠左那个，因此，子数
2021-02-23 22:33:35
99
原创 Codeforces Round #703 (Div. 2) C1/C2. Guessing the Greatest (easy/hard version)【二分】
题意：这是一道交互题。数组 a 有 n 个不同的数字，每一次我们可以向系统查询区间 [l,r][l, r][l,r] 中第二大的元素的位置（输出 "??? lll rrr" 即可查询），其中(1≤l<r≤n)(1 \leq l < r \leq n)(1≤l<r≤n)，我们的目标是通过这样的交互最终求得数组中最大元素的位置 p，输出 “! p”。easy 和 hard 版本的区别是允许查询的次数不同，分别允许查询 20 次和 40 次。2≤n≤1052 \leq n \leq 1
2021-02-22 22:07:50
108
原创 CH0501 货仓选址 | Codeforces Round #703 B. Eastern Exhibition【中位数】
CH0501题意：在一条数轴上有N家商店，它们的坐标分别为 A[0]~A[N- 1]。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。N<=100000, A[i]<=1000000。CH0501思路：本题我们可以利用中位数的性质来解决，将 A[0] ~ A[N - 1] 排序，设货仓建在 X 坐标处，X 的左侧商店有 P 家，右侧 Q家，若 P < Q，则把货仓向右移动移动 1 单位
2021-02-20 21:43:15
230
原创 Educational Codeforces Round 104 C. Minimum Ties【思维】
题意：n 支球队比赛，每支球队之间进行一次比赛，若平局，则双方各加一分，否则赢的球队加 3 分，输的不加分，问怎么设置输赢让各个球队的分数相同且平局的数量最少。t 组数据，每组 2≤n≤1002 \le n \le 1002≤n≤100。思路：由题意得，每支球队要与其他球队进行 n−1n - 1n−1 次比赛，若 n 为奇数，显然最优的情况应该是每支球队赢一半输一半平局次数为0，若 n 为偶数，那么每支球队输赢都是 ⌊n2⌋\lfloor \frac{n}{2} \rfloor⌊2n⌋，平局次数
2021-02-20 19:30:50
125
原创 Codeforces Round #701 (Div. 2) D. Multiples and Power Differences【LCM | 思维】
题意：给定 n 行 m 列正整数组成的矩阵 a，构造一个矩阵 b，满足如下条件：(1) 1≤bi,j≤1061 \le b_{i,j} \le 10^61≤bi,j≤106；(2) bi,jb_{i, j}bi,j 是 ai,ja_{i, j}ai,j 的倍数；(3) 相邻(共享同一条边)两个数之差的绝对值等于 k4k^4k4，其中 k≥1k ≥ 1k≥1。其中 2≤n,m≤5002 \le n,m \le 5002≤n,m≤500，1≤ai,j≤161 \le a_{i,j} \le 161≤ai
2021-02-18 22:28:13
91
原创 Codeforces Round #701 (Div. 2) C. Floor and Mod【数论 | 整除分块】
题意一对正整数 a，b 如果被称为 special ，则要满足 ⌊ab⌋=a mod b\lfloor \frac{a}{b} \rfloor = a \bmod b⌊ba⌋=amodb。给定两个数字 x，y，找到 special 的 (a, b)，其中
2021-02-17 21:51:21
123
原创 Codeforces Round #701 (Div. 2) A.Add and Divide【思维】
题意：给定数字 a、b，可以进行如下两种操作：（1）a=⌊ab⌋a = \lfloor \frac{a}{b} \rfloora=⌊ba⌋；（2）b=b+1b = b + 1b=b+1，问最少进行多少次操作才能将 a 变为 0，有 t 组数据。1≤a,b≤1091 \le a,b \le 10^91≤a,b≤109，1≤t≤1001\le t \le 1001≤t≤100。思路：假定进行 x 次 1 操作，y 次 2 操作，一定是先把 2 操作进行完了之后才进行 1 操作。考虑最差的情况，a
2021-02-14 19:59:12
1238
4
原创 Educational Codeforces Round 94 (Rated for Div. 2) D. Zigzags【枚举 | 统计技巧】
题意：给出一个数组 a1,a2…ana_1, a_2 \dots a_na1,a2…an，计算满足下列条件的元组 (i,j,k,l)(i, j, k, l)(i,j,k,l) 的个数：1≤i<j<k<l≤n;1 \le i < j < k < l \le n;1≤i<j<k<l≤n;ai=aka_i = a_kai=ak and aj=al;a_j = a_l;aj=al;其中：4≤n≤30004 \le n \le 3000
2021-02-04 23:14:02
86
原创 Codeforces Round #694 (Div. 2) D. Strange Definition【质因数分解 | 数论】
题意：定义如果两个数 x,yx, yx,y “相邻”，那么 lcm(x,y)gcd(x,y)\frac{lcm(x, y)}{gcd(x, y)}gcd(x,y)lcm(x,y) 是平方数，给定长度为 n 的数字数组 aaa，其中的每个元素 aia_iai 每一秒后都会被所有与 aia_iai 相邻(包括 aia_iai 自己)的数字的乘积替换，定义 did_idi 为与 aia_iai 相邻的数字的个数，则数组 aaa 的 beautybeautybeauty 为 max(di)max(d_
2021-01-31 00:27:12
131
原创 Codeforces Round #694 (Div. 2) C. Row GCD【GCD | 更相减损术】
题意：给出大小分别为 nnn 和 mmm 的数组 a、ba、ba、b，对于bbb中的每个元素 bjb_jbj ，问 a1+bj,a2+bj,…,an+bja_1 + b_j, a_2 + b_j, \ldots, a_n + b_ja1+bj,a2+bj,…,an+bj 的GCD是多少，其中 1≤n,m≤2⋅1051 \leq n, m \leq 2 \cdot 10^51≤n,m≤2⋅105, 1≤ai≤10181 \leq a_i \leq 10^{18}1≤ai≤1018, 1≤
2021-01-30 22:45:49
97
原创 Codeforces Round #696 (Div. 2) D.Cleaning【思维 | 枚举】
题目链接题目描述：给定一段数字序列，有一种操作是让相邻的两个数都减1，可以操作无限次，还有一种超级操作：在普通操作前让交换两个相邻的数，超级操作可以有0次或者1次，问是否可以将数字序列全都变为0。题解：遇到这种问题，可以先想想分情况考虑。考虑不使用超级操作的情况，令a为原数列，令b[0] = a[0], b[1] = a[1] - b[0], b[2] = a[2] - b[1], …, b[i] = a[i] - b[i - 1]，若最终b[n - 1] = 0且b[i]都不小于0，则“YE
2021-01-22 20:35:02
139
2
原创 Codeforces Round #693 (Div. 3) E.Correct Placement【贪心 | 两点 | iota】
题目链接题目描述：给出n个人的图像，有高和宽，图像可以横着也可以竖着，对于两张图像wi,hiw_i,h_iwi,hi 和 wj,hjw_j, h_jwj,hj，如果i能在j前面，当且仅当满足下面两个条件之一：(1)wi<wjw_i<w_jwi<wj且hi<hjh_i<h_jhi<hj；(2)hi<wjh_i<w_jhi<wj且wi<hjw_i<h_jwi<hj，对于每张图像，问是否能找到一张图像在它前面，若能
2021-01-18 16:31:00
125
原创 2020.5.31 牛客“科林明伦杯” A.点对最大值【树形dp】
题目链接题目描述：有一棵 n (1 < n < 1e6) 个结点的树，每个点和每条边都存在一个价值 (-500 ≤ w ≤ 500)。对于树上点对的价值，包括点对的起点和终点以及路径上边权值之和，不包括路径上其他点值。求这颗树上最大的点对价值为多少。点对至少需要两个点。题解：我们发现如果维护带两个端点的链比较麻烦，所以我们可以考虑维护只有一个端点的链，我们先考虑根节点，经过根节点的最长链就是从根节点的子树中选择带一个端点的最长的两条链进行相连，对于其他节点 x，如果最长链经过根节点，这
2020-10-21 18:39:58
112
原创 HDU 2050 折线分割平面【递推】
题目链接题目描述：求的是 n (0 < n ≤ 10000) 条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。关于直线分割平面：每次加一条直线分割平面，增加到第 n 条直线时，跟之前的直线最多有 n - 1 个交点，这 n - 1 交点就像把第 n 条直线分成了 (n - 1) + 1段，所以增加了 (n - 1) + 1个平面。若每次增加两条直线，假设现在是第 n 次，我们将两条直线分开加，第一条与之前的直线最多有2 *
2020-10-21 16:15:13
242
原创 关于__128的使用
关于__int128long long int 只能表示(263−12^{63}-1263−1)，而__int128可以表示(2127−12^{127}-12127−1)，但是需要自己写输入和输出，类似于快读关于快读：template<typename T> inline void re(T &x) { int f = 1; x = 0; char c = getchar(); while (!isdigit(c)) { if (c == '-')
2020-10-20 19:45:06
339
原创 HDU 2955 Robberies【0/1背包变形】
题目链接题目描述：Robber想要抢银行，每个银行的钱数为mj，抢这个银行被抓的概率为pj，在被抓概率小于 p 的情况下，求最大抢劫金额。题解：题目中给的是抢劫每个银行被抓的概率，设 p1,p2,...pnp_1, p_2, ...p_np1,p2,...pn ，由概率论知识我们可知¬p1∗¬p2∗...∗¬pn¬p_1*¬p_2*...*¬p_n¬p1∗¬p2∗...∗¬pn 为不被抓的概率，显然，如果概率不为小数，我们可以把 (1 - p) 作为容量进行 0/1 背包，但概率是小数
2020-10-20 16:12:18
110
原创 HDU 1392 Surround the Trees【凸包 | 模板】
题目链接题目描述：凸包模板题凸包：凸包 (Convex hull) 问题：给定一些点，求能把所有这些点包含在内的面积最小的多边形。可以想象有一个很大的橡皮箍，它把所有的点都箍在里面，在橡皮箍收紧之后，绕着最外围的点形成的多边形就是凸包。求凸包的算法 (Andrew算法)：算法做两次扫描，先从最左边的点沿“下凸包”扫描到最右边，再从最右边的点沿“上凸包”扫描到最左边，“上凸包”和“下凸包”合起来就是完整的凸包。步骤：把所有点按照横坐标 x 从小到大进行排序，如果 x 相同，按 y 从小到
2020-10-19 19:36:28
90
原创 EOJ Monthly 2019.11 D. 安全带【数学 | 模拟】
题目链接题目描述：初始给出一个 n 个点顺次连接而成的环，点有点权，边权是两个端点的点权乘积。现在给出一些特殊点，这些特殊点是向其他所有点都有连边，如果连边时发现两点之间已经有边，不会再次连接（即图中不会有重边）。求图中边权和。做法1（模拟）：首先我们先将这个环边的权值累加到答案中，然后求特殊点产生的权值和，我们令sum等于所有点的权值和，对于第一个特殊点 x，它的贡献为a[x] * sum - (a[x] - 相邻点的权值)，因为不会有重边，也就是说每个边只能产生一次贡献，此时 x 连的边都已经
2020-10-12 17:28:32
127
2
原创 Codeforces Round #655 C.Omkar and Baseball【思维】
题目链接题目描述：给一个1 ~ N 的排列，可以进行“特殊交换”操作，所谓特殊交换，就是选择一个子区间，然后然后对区间内的数进行重新排列，所有的数排列后不能在原来的位置，问至少要执行多少次特殊操作才能使这个排列变成 1 2 3 … n。题解：显然，若排列已经有序，那么操作次数为0若排列中所有的数都不满足a[i] = i，即所有的数都不在最终的位置(最终的位置指的是排列变为有序：a[i] = i)，这显然只需要一次特殊交换。对于其他情况，至多需要两次，下面进行证明：对于一个排列，假设它有偶数个
2020-10-12 16:38:56
89
原创 EOJ Monthly 2020.9 C. 最小表示【DP | 思维】
题目链接题目描述做法1（差分+DP）：有样例我们可知，连续的 1 可以变为一个 1 和 -1，但是也有反例，例如1110111，如果按照这样的话会变为1 0 0 -1 1 0 0 -1，共需要 4 个，但是其实正确的答案是 1 0 0 0 -1 0 0 -1，即将中间的 -1 和 1 合并成 -1，同理 1 -1 也可以合并成 -1，所以我们可以用类似于差分的方式将原数列变成差分的形式，然后进行动态规划，将能合并的进行合并，令dp[i]表示前 i 个位需要非零元素的数量，状态转移方程如下：a[
2020-10-10 21:46:31
91
原创 牛客练习赛71 A-回文数【构造 | 水题】
题目链接题目描述：分别给出 10 个数码的出现次数，你需要找到一个由这些数码组成的最小的数，满足：这个数是回文的。不能有前导 0。保证输入的所有数都不超过 10 且至少一个数大于 0。例如：0 2 4 2 0 2 0 0 0 0答案为：1223553221题解：大水题一道，为什么要记录这道题呢，是因为构造的时候傻比了，构造错了。比如 2 5 2 2 0 0 0 0 0 0，正确的结果应该是 10123132101，结果我当时构造成了：11023132011，真傻比啊。。。AC
2020-10-09 22:35:32
409
3
原创 蓝桥-算法训练 ALGO-116 最大的算式【区间DP】
题目链接题目描述：给出 N 个数字(0 ~ 9)，在不改变他们顺序的情况下，加上 K 个乘号和 N - 1 - K 个加号，问最大值，其中 2 <= N <= 15, 0 <= K <= N - 1。题解：状态设计为 dp[i][k] 表示 1 ~ i 个数中插入 k 个乘号的最大值，对于一个区间，我们向其中插入一个乘号时(我们向每个元素前面插入乘号，即下标为 2 ~ N 前面都能插入乘号)，我们要枚举乘号的位置才能知道插入在哪最优，所以对于一个区间，我们要知道插入位置前面
2020-10-07 20:31:08
126
原创 POJ 2279 Mr. Young‘s Picture Permutations【线性DP】
题目链接题目描述标号为 1 ~ N 的同学站成 k 行，每行人数为 aia_iai，规则入下图所示，同一行标号从左向右递增，同一列标号从后向前递减，前面的列数不长于后面的列数，问方案有多少种。题解：满足两个方向的递增：因为在合法的方案中，每行每列都是递增的，所以我们可以考虑从标号 1 到 N 开始放，对于同一行的递增，后放的一定大，满足了从左到右递增；对于同一列的递增，后放的也一定大(要满足这一列的行是最后一行或者要放的这一行同一列后面的行已经放了数)，这满足了从后向前递增。满足前面行数不大
2020-10-07 12:45:20
149
原创 蓝桥-算法训练 ALGO-6 安慰奶牛【最小生成树】
题目链接题目描述：原题的描述真的烂。题意是这样的：给一张图，每个点和边都有权值，经过点和边的花费为权值的大小，现在要将这个图去掉一些边使其成为一颗生成树(题目只给了图)，求从生成树的一个点 s (题目没给)出发，访问其他所有的点至少一次并返回 s 的最少花费。题解：这一看就是与最小生成树有关的题，因为题目要求从 s 出发最终还要回到 s，所以我们可以易知如果经过一条边，那么就要从这条边再回来(边要经过两次)，因为是求最小生成树，我们得想办法将结点的权值合并到边上，对于一条新的从 u ->
2020-10-01 16:35:39
89
原创 Codeforces Round #674 E. Rock, Paper, Scissors【数学 | 最大流 | 思维】
题目链接题目描述A 和 B 进行石头剪刀布游戏，共进行 n 个回合，其中 A 出 a1a_1a1 次石头，a2a_2a2 次剪刀，a3a_3a3 次布，B 出 b1b_1b1 次石头，b2b_2b2 次剪刀，b3b_3b3 次布，问 A 最多获胜的次数和最少获胜的次数。最大流做法：min：You can link the source to A’s options (2-rock, 3-scissors, 4-paper) with their respectives capacit
2020-09-30 09:35:11
153
原创 HDU 1532 Drainage Ditches【最大流 | Edmonds-Karp模板】
题目链接题目描述：最大流Edmonds-Karp算法模板题。最大流最大流问题是基于有向图的，就是求两点 (分别称为源点、汇点) 间的最大流量，图中任何点都可以作为它们的中转。在求最大流时需要满足以下 3 个性质：流量守恒。从源点 s 流出的流量和到达汇点 t 的流量相等；其他所有中转点，流入和流出相等。反对称性。设从 uuu 到 vvv 的流量是 f(u,v)f(u,v)f(u,v)，vvv 到 uuu 流量是 f(v,u)f(v,u)f(v,u)，那么 f(u,v)=−f(v,u)f(u
2020-09-29 22:46:05
143
原创 Codeforces Round #674 D.Non-zero Segments【前缀和 | set】
题目链接题目描述：题解：好题啊~不知道为啥，我感觉用英文比中文写题解更简洁。Firstly, let’s understand that the sum of the segment [l;r][l;r][l;r] is zero if pr−pl−1p_r-p_{l-1}pr−pl−1 is zero (in other words, pl−1=prp_{l-1}=p_rpl−1=pr), where pip_ipi is the sum of the first iii ele
2020-09-28 23:03:02
154
原创 Codeforces Round #674 C Increase and Copy【数学】
题目链接题目描述：题解：it is pretty intuitive that we firstly need to do all increaments and only then copy numbers. You could notice that the answer does not exceed n1/2n^{1/2}n1/2 so we can iterate from 1 to ⌊n1/2⌋\lfloor n^{1/2} \rfloor⌊n1/2⌋ and fix number w
2020-09-28 21:01:37
250
原创 EOJ Monthly 2020.9 B健康监测计划【贪心 | 思维 | 树形DP】
题目链接题目描述：华东师范大学共有 n 栋楼房，编号为 1, 2, …, n，并有 n − 1 条双向联通的道路连接这些楼房，使得任意两栋楼房之间有且仅有一条简单路径（一条简单路径是指，从一栋大楼出发，不经过重复大楼，并在另一栋大楼结束的路径）。学校为了贯彻落实常态化疫情防控政策，决定选择一些楼房，在其中各设置一个健康监测点，实时监测路过的同学的健康状况。虽然自动化检查仪器已经在全校普及，但是监测的过程依然不可避免地会影响学生的出入便捷性。所以学校需要精心安排监测点的位置，使得监测点数量尽可能多，而
2020-09-27 22:21:56
115
原创 蓝桥-算法训练 ALGO-8 操作格子【线段树 | 单点修改 | 区间求和 | 区间最值】
题目链接题目描述：有n个格子，从左到右放成一排，编号为1-n。共有m次操作，有3种操作类型：1.修改一个格子的权值，2.求连续一段格子权值和，3.求连续一段格子的最大值。对于每个2、3操作输出你所求出的结果。1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。感受：虽然线段树的题已经非常熟练了，但还是某些地方会写错，要认真写，认真检查！AC Codes：#include <iostream>#
2020-09-25 23:04:01
113
原创 蓝桥-算法训练 ALGO-5 最短路【SPFA | 模板】
题目链接题目描述：给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。1 <= n <= 20000，1 <= m <= 200000，-10000 <= len <= 10000，保证从任意顶点都能到达其他所有顶点。SPFA：边权存在负数时不能用Dijkstra。判断负圈：如果一个点进队列超过 n 次，则说明图中存在负圈 (代码中neg数组)。注意：如果是双向边的话链式前向
2020-09-25 22:58:33
105
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人